4 ms·

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

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?

Periodic 15y 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.
- ScottBurson 15y 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.
  - Periodic 15y ago
    In comparison to math, I think bottom is very close to the idea of an undefined value. What is the value of 4/0? What is the derivative of a step function at 0? Mathematics often goes out of its way to make sure things aren't undefined by defining domains that exclude the undefined values. In programming we do the same thing most of the time. I think what I missed is that bottom in Haskell is really an exception. It's a value that doesn't really exist. Trying to force it gives an exception. The real results of a computation are concrete values, non-termination and exceptions.
happy4crazy 15y 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.
- ScottBurson 15y 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 15y 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 15y 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.

Periodic 15y 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.

ScottBurson 15y 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.
- Periodic 15y ago
  In comparison to math, I think bottom is very close to the idea of an undefined value. What is the value of 4/0? What is the derivative of a step function at 0? Mathematics often goes out of its way to make sure things aren't undefined by defining domains that exclude the undefined values. In programming we do the same thing most of the time. I think what I missed is that bottom in Haskell is really an exception. It's a value that doesn't really exist. Trying to force it gives an exception. The real results of a computation are concrete values, non-termination and exceptions.

happy4crazy 15y 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.

ScottBurson 15y 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 15y 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 15y 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.