The Point of Laziness in Programing Languages

http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/

by gus_massa • 15 years ago

22 8 15 years ago

existentialtype.wordpress.com

ScottBurson3• 15 years ago

variables in a lazy language range over computations, including the non-terminating computation, whereas in a strict language they range only over values

This is a very interesting comment that I am not sure I believe.

Let me acknowledge up front that I am aware that the author is a Haskell expert, and I am not anything resembling one. So this comment is definitely from an interested-onlooker perspective.

Still, from what little I know, it seems to me that variables in Haskell still range over values, not over computations. For instance, the expression "x == y" is not true when x and y are the same computation; it is true when those computations yield the same value. I understand that operationally, those values may not be computed until needed for the equality test, and I understand that the computation of one of them may not terminate; but I still don't see how that means that the variables range over computations.

What am I missing?

Periodic2• 15 years ago

Let's say you have a type that's a value of a typeclass Typeable that has a function "a -> String" (the real Typeable class has the signature "a -> TypeRep) which tells you that type of the argument.

Let's now say I define some data type:

    data Foo = Foo

and make it an instance of typeable.

    instance Typeable Foo where
        typeOf _ = "Foo"

Note that the function doesn't actually care what's in it. The following is all valid:

    > typeOf (Foo)
    "Foo"
    > typeOf (undefined :: Foo) -- making an bottom value of type Foo
    "Foo"
    > typeOf (let f y = if y then Foo else f y in f False) -- not terminating computation.
    "Foo"

All three of these are valid variables. They may be stored as thunk, and only when you try to extract the value of the thunk do they cause errors. It is still perfectly valid to pass them around as values and store them.

ScottBurson3• 15 years ago

See my reply to happy4crazy. Your examples are interesting, but I still think that to say that bottom is an element of every Haskell type is to commit a level confusion. It would be more accurate to simply say that expressions and variables in Haskell don't always have values. What your examples show is simply that the language is not strict: an expression can have a value even if one of its subexpressions does not.

In mathematics, we don't have this notion of a variable with no value, so to write a formal semantics for Haskell we have to make up this "meta-value" bottom. But it should not be confused with a value in the language, as it is not one.

Again, this is all my intuition and I'm not an expert. But so far, I don't see what's wrong with this view.

happy4crazy• 15 years ago

I'm also in the interested-onlooker camp, but I think this is an example of a variable denoting a computation rather than a value. It's a Haskell version of an exercise in SICP:

> p = p

> if True then "I'm the value of this expression" else p

I would love it if someone would help me phrase this more precisely: the variable p doesn't really have a value, in the sense that evaluating it fully will never finish; it's bottom, the non-terminating computation.

ScottBurson3• 15 years ago

Right. To me, and again I'm not an expert on semantics, but to me, bottom isn't a value in the value domain of the language; it's a meta-value, if you will, a value in the semantics but not in the language. And what it represents is precisely the absence of any value in the value domain of the language.

After all, you can't in the language compare two "bottom values" to see if they're equal; there's not even a notion of equality.

So the way I would want to put it is that bottom is a notion that we use in modelling the semantics of languages (and I've used it in modelling strict languages too; the value returned by a function when it throws an exception is modelled as bottom), but it's not a value in the language. This contradicts the author's entire argument that the Haskell type system doesn't permit the definition of recursive types.

I'd have to learn a lot more to be able to make this argument with any authority. But that's my intuition.

tel• 15 years ago

Most directly: == defines equivalence classes within particular types (polymorphic over types fulfilling Eq). This means by definition it's domain is limited to processes which result in a Eq-able type at which point it defines equality as equality of that final type.

Your example only seems strange when you assume semantics of equality that are more dramatic than actually used.

ggchappell• 15 years ago

Lots of nice answers here. How about another:

You're both right. Variables x, y range over computations, and "x == y" is true when those computations yield the same value.

> What am I missing?

The fact that your statement does not contradict the one in the article.

The Point of Laziness in Programing Languages

Related Stories