scala haskell functional-programming terminology

What is "value" in pure functional programming?

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.

Solution

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:

Constant literals are terms:
```
42
```
Functions applied to other terms are terms:
```
atan2(123, 456 + 789)
```
Function literals are terms
```
(x: Int) => x * x
```
Constructor invocations are terms:
```
Option(42)
```

Contrast this to:

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.
Likewise, trait and type definitions are not terms:
```
type Bar = Int
sealed trait Baz
```

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

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:

This is a term, but it's not in normal form, because it can be reduced to 42:
```
40 + 2
```
This is not in weak head normal form:
```
((x: Int) => x * 2)(3)
```
because we can further evaluate it to 6.
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
```
This is not in normal form, because it can be simplified further:
```
42 :: List(10 + 20, 20 + 30)
```
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.