What is "value" in pure functional programming?

Question

What constitutes a value in pure functional programming?

I am asking myself these questions after seeing a sentence:

Task(or IO) has a constructor that captures side-effects as values.

• Is a function a value?
  • If so, what does it mean when equating two functions: assert(f == g). For two functions that are equivalent but defined separately => f != g, why don't they work as 1 == 1?
• Is an object with methods a value? (for example IO { println("") })
• Is an object with setter methods and mutable state a value?
• Is an object with mutable state which works as a state machine a value?

How do we test whether something is a value? Is immutability a sufficient condition?

UPDATE: I'm using Scala.

Answer 1

What constitutes a value in pure functional programming?

Background

In pure functional programming there is no mutation. Hence, code such as

case class C(x: Int)

val a = C(42)
val b = C(42)

would become equivalent to

case class C(x: Int)

val a = C(42)
val b = a

since, in pure functional programming, if a.x == b.x, then we would have a == b. That is, a == b would be implemented comparing the values inside.

However, Scala is not pure, since it allows mutation, like Java. In such case, we do NOT have the equivalence between the two snippets above, when we declare case class C(var x: Int). Indeed, performing a.x += 1 afterwords does not affect b.x in the first snippet, but does in the second one, where a and b point to the same object. In such case, it is useful to have a comparison a == b which compares the object references, rather than its inner integer value.

When using case class C(x: Int), Scala comparisons a == b behave closer to pure functional programming, comparing the integers values. With regular (non case) classes, Scala instead compares object references breaking the equivalence between the two snippets. But, again, Scala is not pure. By comparison, in Haskell

data C = C Int deriving (Eq)
a = C 42
b = C 42

is indeed equivalent to

data C = C Int deriving (Eq)
a = C 42
b = a

since there are no "references" or "object identities" in Haskell. Note that the Haskell implementation likely will allocate two "objects" in the first snippet, and only one object in the second one, but since there is no way to tell them apart inside Haskell, the program output will be the same.

Answer

Is a function a value ? (then what it means when equating two function: assert(f==g). For two function that is equivalent but defined separately => f!=g, why not they work like 1==1)

Yes, functions are values in pure functional programming.

Above, when you mention "function that is equivalent but defined separately", you are assuming that we can compare the "references" or "object identities" for these two functions. In pure functional programming we can not.

Pure functional programming should compare functions making f == g equivalent to f x == g x for all possible arguments x. This is feasible when there is only a few values for x, e.g. if f,g :: Bool -> Int we only need to check x=True, x=False. For functions having infinite domains, this is much harder. For instance, if f,g :: String -> Int we can not check infinitely many strings.

Theoretical computer science (computability theory) also proved that there is no algorithm to compare two functions String -> Int, not even an inefficient algorithm, not even if we have access to the source code of the two functions. For this mathematical reason, we must accept that functions are values that can not be compared. In Haskell, we express this through the Eq typeclass, stating that almost all the standard types are comparable, functions being the exception.

Is an object with methods a value ? (for example, IO{println("")})

Yes. Roughly speaking, "everything is a value", including IO actions.

Is an object with setter methods and mutable states a value ? Is an object with mutable states and works as a state machine a value ?

There is no mutable state in pure functional programming.

At best, the setters can produce a "new" object with the modified fields.

And yes, the object would be a value.

How do we test if it is a value, is that immutable can be a sufficient condition to be a value ?

In pure functional programming, we can only have immutable data.

In impure functional programming, I think we can call most immutable objects "values", when we do not compare object references. If the "immutable" object contains a reference to a mutable object, e.g.

case class D(var x: Int)
case class C(c: C)
val a = C(D(42))

then things are more tricky. I guess we could still call a "immutable", since we can not alter a.c, but we should be careful since a.c.x can be mutated. Depending on the intent, I think that some would not call a immutable. I would not consider a to be a value.

To make things more muddy, in impure programming, there are objects which use mutation to present a "pure" interface in an efficient way. For instance one can write a pure function that, before returning, stores its result in a cache. When called again on the same argument, it will return the previously computed result (this is usually called memoization). Here, mutation happens, but it is not observable from outside, where at most we can observe a faster implementation. In this case, we can simply pretend the that function is pure (even if it performs mutation) and consider it a "value".

Answer 2

I'll try to explain what a value is by contrasting it with things that are not values.

Roughly speaking, values are structures produced by the process of evaluation which correspond to terms that cannot be simplified any further.

---

Terms

First, what are terms? Terms are syntactic structures that can be evaluated. Admittedly, this is a bit circular, so let's look at a few examples:

1. Constant literals are terms:

   42
   

2. Functions applied to other terms are terms:

   atan2(123, 456 + 789)
   

3. Function literals are terms

   (x: Int) => x * x
   

4. Constructor invocations are terms:

   Option(42)
   

Contrast this to:

1. Class declarations / definitions are not terms:

   case class Foo(bar: Int)
   

   that is, you cannot write

   val x = (case class Foo(bar: Int))
   

   this would be illegal.

2. Likewise, trait and type definitions are not terms:

   type Bar = Int
   sealed trait Baz
   

3. Unlike function literals, method definitions are not terms:

   def foo(x: Int) = x * x
   

   for example:

   val x = (a: Int) => a * 2 // function literal, ok
   val y = (def foo(a: Int): Int = a * 2) // no, not a term
   

4. Package declarations and import statements are not terms:

   import foo.bar.baz._ // ok
   List(package foo, import bar) // no
   

---

Normal forms, values

Now, when it is hopefully somewhat clearer what a term is, what was meant by "cannot be simplified any further*? In idealized functional programming languages, you can define what a normal form, or rather weak head normal form is. Essentially, a term is in a (wh-) normal form if no reduction rules can be applied to the term to make it any simpler. Again, a few examples:

1. This is a term, but it's not in normal form, because it can be reduced to 42:

   40 + 2
   

2. This is not in weak head normal form:

   ((x: Int) => x * 2)(3)
   

   because we can further evaluate it to 6.

3. This lambda is in weak head normal form (it's stuck, because the computation cannot proceed until an x is supplied):

   (x: Int) => x * 42
   

4. This is not in normal form, because it can be simplified further:

   42 :: List(10 + 20, 20 + 30)
   

5. This is in normal form, no further simplifications possible:

   List(42, 30, 50)
   

Thus,

• 42,
• (x: Int) => x * 42,
• List(42, 30, 50)

are values, whereas

• 40 + 2,
• ((x: Int) => x * 2)(3),
• 42 :: List(10 + 20, 20 + 30)

are not values, but merely non-normalized terms that can be further simplified.

---

Examples and non-examples

I'll just go through your list of sub-questions one-by-one:

Is a function a value

Yes, things like (x: T1, ..., xn: Tn) => body are considered to be stuck terms in WHNF, in functional languages they can actually be represented, so they are values.

If so, what does it mean when equating two functions: assert(f == g) for two functions that are equivalent but defined separately => f != g, why don't they work as 1 == 1?

Function extensionality is somewhat unrelated to the question whether something is a value or not. In the above "definition by example", I talked only about the shape of the terms, not about the existence / non-existence of some computable relations defined on those terms. The sad fact is that you can't even really determine whether a lambda-expression actually represents a function (i.e. whether it terminates for all inputs), and it is also known that there cannot be an algorithm that could determine whether two functions produce the same output for all inputs (i.e. are extensionally equal).

Is an object with methods a value? (for example IO { println("") })

Not quite clear what you're asking here. Objects don't have methods. Classes have methods. If you mean method invocations, then, no, they are terms that can be further simplified (by actually running the method), so they are not values.

Is an object with setter methods and mutable state a value? Is an object with mutable state which works as a state machine a value?

There is no such thing in pure functional programming.

Answer 3

Values are

1. Immutable/Timeless
2. Anonymous
3. Semantically Transparent

What is the value of 42? 42. What is the "value" of new Date()? Date object at 0x3fa89c3. What is the identity of 42? 42. What is the identity of new Date()? As we saw in the previous example, it's the thing that lives at the place. It may have many different "values" in different contexts but it has only one identity. OTOH, 42 is sufficient unto itself. It's semantically meaningless to ask where 42 lives in the system. What is the semantic meaning of 42? Magnitude of 42. What is the semantic meaning of new Foo()? Who knows.

I would add a fourth criterion (see this in some contexts in the wild but not others) which is: values are language agnostic (I'm not certain the first 3 are sufficient to guarantee this nor that such a rule is entirely consistent with most people's intuition of what value means).

Answer 4

The contrast with imperative languages is stark. In inperitive languages, like Python, the output of a function is directed. It can be assigned to a variable, explicitly returned, printed or written to a file.

When I compose a function in Haskell, I never consider output. I never use "return" Everything has "a" value. This is called "symbolic" programming. By "everything", is meant "symbols". Like human language, the nouns and verbs represent something. That something is their value. The "value" of "Pete" is Pete. The name "Pete" is not Pete but is a representation of Pete, the person. The same is true of functional programming. The best analogy is math or logic When you do pages of calculations, do you direct the output of each function? You even "assign" variables to be replaced by their "value" in functions or expressions.