[plt-scheme] Common history among streams, continuations, and monads?

On Jul 7, 2007, at 6:18 PM, Grant Rettke wrote:

> Hi folks,
>
> Over the past week or two I've been looking at Haskell.
>
> I read this paper:
>
> http://research.microsoft.com/~simonpj/papers/history-of-haskell/ 
> index.htm
>
> It was a fun read. It is really interesting to hear about the whole
> story. It sounds like the Haskell folks wanted Scheme to be lazy, and
> were hurt that it wasn't!

Interesting perspective. I was around when it all happened and  
watched it through Indiana's lazy side of the PL group.

> The paper mentions that IO in Haskell was originally implemented using
> either streams or continuations. I'd never thought of something like
> that before.

When people use the word "continuations" they mean two distinct  
though related things:
  [1] the language construct (e.g., call/cc and the values it creates)
  [2] an organization principle for programs
One can and usually does model [1] with [2], but you don't have to  
use continuations, even if you do use denotational semantics or  
interpreters. Earliest evidence: Sitaram and Felleisen, some POPL  
some 15 years ago.

In this context, the authors are using the second one.

I do think that they should actually have used 2-dimensional laziness  
instead of falling back on quasi-imperative programming with monads.  
But that's water under the bridge.


> Are streams and continuations just part of the standard toolbox that
> all FP developers hold? Is there some greater theory to streams and
> continuations? I know of them as language features, but not more than
> that.


In a sense, monads are a generalization of continuations (sense [2]).  
Technically, monads are an "organization principle" in category  
theory with which people can "shrink" the available space of  
categories and play more. If you start with order-enriched CCCs  
(Cartesian Closed Categories), you have an algebraic model of the  
typed lambda calculus. You can model primitives and even fixed- 
points. If you step back and just use CCs with Monads, you can tease  
out more "imperativeness". For example, you recognize that Omega (the  
primitive infinite loop) is an effect. So now you can bring a "zoo-o- 
logical" order to the world of programming constructs. These are  
Eugenio's words from 1989, as he visited Rice and we inspected Monads  
vs A Normal Form (and its transformation).

[Warning: Monads do not do all imperative programming. Example:  
functional continuations (as captured by F NOT shift). You can't even  
model them with cps (i.e., sense [2] -- in my opinion, though one can  
liberally view other things as cps) so monads don't do it either. One  
day I need to check out arrows but I don't think they do it either.]

Now, once you see all this and you know that Denotational semantics  
is "programming with the semantics on the sleeves" it's not a far  
step to incorporate monads into a functional language a la Haskell.  
That's what these people do. As an organization principle, they are  
as much as programming tool as they are a tool for reasoning  
(especially constraining reasoning) about programs. As such they are  
as much related to types as to linguistic construct design. Reading  
about monads just via Scheme macros won't do them justice.

> In Haskell, those were replaced with doing IO via monads. Have they
> all got something in common? Some shared thread?

Nah.

> I'm still reading up on what is so great about monads. It concerns me
> when loads of folks say that "It is too complicated, don't worry about
> it, just know that it is pure and that they work." I know someone
> understands, I just haven't found that someone writing up a concise
> explanation yet. There is the awkward squad paper on my list, of
> course.

Life is about investing. As you endeavor to read these papers, you  
may wish to ponder where else you can invest your time or whether  
you're ready to invest your time in that thread.

-- Matthias