2

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.

  • 3
    What other programming languages are you familiar with? I'll write up an answer comparing Haskell with respect to the concept of "values" and "types". – ErikR Aug 6 '16 at 4:28
5

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.

  • Agreed with value being a general PL concept. But in FP, it seems that valoe is overloaded and vaguely defined or described. – S Thong Aug 7 '16 at 14:25
  • 3
    That's not Haskell's stance; I don't know where you got that from, it's plain wrong like I said. Please don't go spreading that incorrect knowledge around just FYI. – gardenhead Aug 8 '16 at 16:50
  • 3
    No, what you said continues to be wrong. Expressions are not values. Functions are a form of expression. A function abstraction is an expression that is also a values. Variables are not values either. – gardenhead Aug 8 '16 at 17:28
  • 3
    Still wrong... I'm not sure if I'm being unclear, but you seem to be making up definitions and assumptions out of thin air. I think you should read a book on programming languages to understand these concepts better - I don't think there's enough room in an answer for me to do these concepts justice. Try either Pierce's Type Systems for Programming Languages or Harper's Practical Foundations for Programming Languages. – gardenhead Aug 8 '16 at 18:11
  • 3
    I never said only functions can be first-class values (btw, there are no first- or second-class values, just values). Other forms of expressions and types can be values as well e.g. 5, "hello world" are also values. 5 + 5 is not a value because it hasn't yet been evaluated (it can be reduced to 10). You also said that "expressions" are not values - I guess I'm not sure what you meant by that, but the distinction is that some expression are values, but not all expressions - the two terms are related but not synonyms. – gardenhead Aug 8 '16 at 19:08
2

A value in Haskell is pretty much the same as a value in any other language.

Exampels of values:

numbers     - e.g. 1, 2, 3, etc.
characters  - e.g. 'a', 'Z', '$', ...
strings     - e.g. "Hello", "foobar", ...
tuples      - e.g. (14, 'S') - a tuple of a number and the letter 'S'
functions   - e.g. \x -> x + 1
lists       - e.g. [6,5,4]
booleans    - e.g. True, False

And it also includes user defined records and anything else you would consider as being "data".

Also, just like in Java, C#, C++ and other typed languages, every value has a type. Some examples:

value        type
1            Integer
"Hello"      String
'X'          Char
(3,'z')      (Int, Char)

To be a "first-class value" means that you can assign the value to a variable, pass it as parameter to a function - basically there are no restrictions on how you can create or use it. Most values in modern languages are "first-class" these days, but that wasn't always the case. In early versions of the C language the only functions that could exist in your program had to be declared at in the global scope. There was no way to create a function with local scope.

For instance, in this Python fragment I've created a new function add1 which only exists in the scope of the subroutine main:

def main():
  def add1(x):
    return x+1
  print add1(5)

That's not possible in K&R C. In early versions of Java it was not possible to create a function that was not a method call. But times have changed, and most programming languages don't have these kinds of restrictions on functions anymore.

  • 2
    "But times have changed, and most programming languages don't have these kinds of restrictions on functions anymore.": If I am not mistaken, nested functions and procedure have been in Pascal since the '70. Standard C does not have them even today. – Giorgio Aug 6 '16 at 6:19
2

A value is the result of evaluating an expression.

In Haskell there is no distinction between expressions whose result is a function and the ones that return some data values. A function name is already a valid expression, it's easy to construct anonymous functions etc. That's what's meant by saying that functions are first-class values - you can have expressions that evaluate to functions. But in some (most?) languages working with functions is much harder.

I wouldn't say that ever value has a type, rather that every expression has a type. The important property is that when an expression is evaluated, the value has the same type as the original expression. For example, if your function has the return type int, you expect that indeed when it's evaluated, the result will be an intvalue.

  • Close - "value is a result of an evaluation" . Result would be a piece of information, either irreducible ( number, word,...) or a piece of code (data structure, function,...). What I was looking for is an intuitive term for an entity that can be a concrete value or code. – S Thong Aug 7 '16 at 14:18
  • 1
    @SThong I understand what you're looking for, but I'm not aware of any better term. For a given language you can have different semantics, which define what is "evaluation" or "values". It seems that neither Haskell Report defines a particular evaluation. For example for the lambda calculus one way is to define evaluation as computation of β-normal form. But when running a language like Haskell on a computer, values will be some data structures. – Petr Pudlák Aug 7 '16 at 17:59
  • 1
    @SThong I'd say that identifying values with normal forms would be a good approximation of what you're looking for. An expression evaluates (via beta reductions) to a normal form, and for primitive values and data types the normal form is very intuitive. – Petr Pudlák Aug 7 '16 at 18:05
  • AJT Davie in "Intro to FP systems using Haskell" liken value to an abstract entity. P Hudak in "A Gentle Into to Haskell 98" qualify values as abstract entities that we regard as answers. But if I phrase the "the first-class" verbiage in terms of abstract entity, I'll get an unsatisfactory "functions are first-class abstract entity" and wonders what else isn't an abstract entity. I like the term "form" - much used in the LISP literature. Thx. – S Thong Aug 8 '16 at 16:35
  • Here's another thought. In Math, f(1) has a concrete value, but f(x) is a form or expression of x that has an unknown value since x is unknown. I think when the Math guys say "the value of f(x) is bounded", they are saying the range of f(x) is bounded. Seems the closest to the value of a function is an abstraction of it's range. – S Thong Aug 8 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.