[Haskell-cafe] Linguistic hair-splitting
wren ng thornton
wren at freegeek.org
Sun Feb 14 19:38:47 EST 2010
Alexander Solla wrote:
> On Jan 27, 2010, at 4:57 PM, Conor McBride wrote:
>> Yes, the separation is not clear in Haskell. (I consider this
>> unfortunate.) I was thinking of Paul Levy's call-by-push-value
>> calculus, where the distinction is clear, but perhaps not as fluid as
>> one might like.
> What, exactly, is the supposed difference between a value and a
> computation? Please remember that computations can and very often do
> "return" computations as results. Please remember that in order for a
> function to be computed for a value, binding and computation must
> occur. And that for every value computed, a computation must occur,
> even if it is "just" under identity the identity function.
The difference is ontological. To pull in some category theory ---only
because it helps make the distinction explicit--- there's a big
difference between a morphism |A->B| and an exponential object |B^A|.
What's the difference? Well, one is a morphism and the other is an
object; they're simply different sorts of things, and it's a syntactic
error to put one in the place of the other.
In Cartesian Closed Categories (and similar) it so happens that the
category "has exponentials", i.e. for every morphism |f:A->B| there
exists an exponential object |o:B^A|. Because of the has-exponentials
law, we know that in a CCC for every |f| there's an |o| and for every
(exponential) |o| there's an |f|; but that does not mean that |f| and
|o| are the *same* thing, it merely means we can conceptually convert
So what has any of this to do with Haskell? For the non category
theorists in the audience: morphisms capture the notion of functions as
procedures; that is, morphisms *do* things (or: are actions).
Exponential objects capture the notion of functions as values/arguments;
that is, objects *are* things. Down in the compiler we make the same
exact distinction when distinguishing code or code pointers (morphisms)
from closures (objects).
In functional languages there are invisible coercions between
functions-as-procedures and functions-as-values. The problem, as it
were, is that the coercion is invisible. Why is this a problem? Most of
the time it isn't; it's part of what makes functional programming so
clean and elegant. Consider the identity monad. It's a simple monad,
it's exactly the same thing as using direct values except with a newtype
wrapper. Since it's exactly the same, why not try writing a program
using |Id| everywhere instead of using the direct style. If you try this
you'll see just how much invisible coercion is going on. That's part of
the reason why it's sugared away.
But some of the times you want or need to be explicit about the
coercions (or conversely, want to change which coercions are implicit).
Consider for instance the problem of having distinct functions |map| vs
|mapM| or any other |foo| vs |fooM|. The reason for this proliferation
is that, syntactically, we must write different code depending on
whether we're using the invisible coercions of direct values, vs whether
we're making the coercions explicit by using some monad (or applicative,
Haskell and similar languages choose a particular set of coercions to
make invisible and implicit. Currying, uncurrying, application, etc. But
there's nothing sacred about choosing to make those particular coercions
invisible instead of choosing a different set of coercions to sugar away.
More information about the Haskell-Cafe