[Haskell-cafe] Linguistic hair-splitting

[wren ng thornton]

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 
between them.

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, 
or whatever).

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.

-- 
Live well,
~wren