Haskell – What is a Haskell Value?

haskell

What is the meaning of the term "value" in statements such as:

  1. A Haskell function is a first-class value
  2. Every value has a type

In both statements, I am left wondering what a value is and have a
nagging conceptual gap when reading Haskell programming texts.

So, bottom-line: is there a definition of a Haskell value?

Thank you.

Best Answer

All these terms - expressions, values, and "class" - are general PL concepts that have no specific ties to Haskell, and are best understood under a more general framework. To keep things brief, I will only describe these ideas informally, although it is important to realize they can all be rigorously defined within a formal logical framework.

Expressions

Expressions are the basic units of programming; in some sense, programs are expressions. Here are some examples of expressions (in a small made-up language):

  • 1 + 3 * 3
  • concat("hello", "world")
  • let x = pow(2, 2) in pow(x, x)
  • lambda x. x

Notice that lambda x. x (the identity function) is an expression in this language. It can be used interchangeably in any context in which an expression is expected; for example, instead of 1 + 1 we can write 1 + lambda x. x*. In particular, since the arguments to a function are expressions, and functions themselves are expressions, we may pass functions to functions as arguments, such as map(lambdax. x, [1, 2, 3]).

Thus, higher-order functions are but a consequence of treating functions as expressions. In contrast, in a language that does not do so, like C, such an expression is not even a program in that language.

* This is valid according to the abstract syntax of the language, but the code will not type-check. More on this later.

Dynamics and Values

Expressions are static. It is the job of the dynamics of a language to tell us how expressions are to be evaluated during run-time. The (operational) dynamics consists of a set of simple transition rules for transforming one form of expression into another. For example, our dynamics may have a rule that, informally, says "n1 + 0 transitions to n1".

The values in a language are a subset of expressions that we consider to be fully evaluated; we write programs (expressions) to compute values. The expressions given above evaluate to:

  • 7
  • "hello world"
  • 256
  • lambda x. x

Tangent: It should be the case that a value cannot transition to another expression, but the converse does not generally hold; there are some expressions (e.g. 7 + "hello world") that cannot be evaluated further, yet are not values. The purpose of a type system is to avoid such situations.

Thus, to declare that "functions are values" we must a priori insist that functions be expressions. In our language, we do consider functions to be values; thus, lambda x. x is a value, and map(lambda x. x, [1 2 3]) is a valid expression.

As far as I know, it would be useless to create a language in which functions are expressions but not values.