Wednesday, April 4, 2012

Continuations and self-reference

Recently, I've been on a kick looking up info on continuations, delimited and undelimited. Last year, I had gotten into a curious programming "notation" (not so much a language, as the high-brow conception of one), with a bare-bones interpreter written in OCaML. I decided to first, translate the interpreter into Haskell (ironically, the author had originally tried writing it in Haskell, but "got stuck"), then study how it worked, and eventually re-write it "the right way." Since the "notation" uses continuations expressly in its control flow, I thought I should make sure my mental grasp on them was as firm and steady as I could make it, so off to thesis-ville I went.

Once there, I found out, as mentioned, that "continuations" aren't the whole story; there are both delimited and undelimited continuations, and they are different. So I read as much as I could stand on what the difference was, and how said difference made a difference. One of the most surprising places I found information on it was Oleg Kiselyov's site - not surprised that it had info, only that I understood it. What surprised me even more, was that (undelimited) continuations, especially Scheme's call/cc (call-with-current-continuation, in Lisp-speak), were so tied in with self-referentiality.

Looking further on the okmij site, I noticed an article on "polyvariadic Y," that is, a fully polymorphic fix-point operator. This is useful, in that it lets you describe the mutual fixed point of a group of expressions. What was a little sad for me, coming to the party so late (the original article was from a mailing list discussion in Oct. 2003), was that I immediately recognized the type used for the poly-Y operator: it was ([[a -> b] -> a -> b] -> [a -> b]) just a less general form of what "we" in the Haskell world (especially those who hang out in #haskell on freenode) call the loeb function: (Functor f) => f (f c -> c) -> f c, in Haskell-speak.

Not terribly mind-blowing, but it just seems that that (loeb) function isn't just entertaining, but is downright useful, as are types themselves. For more information on the loeb function, please check out Academy Award-winning (heh-heh) Dan "sigfpe" Piponi's blog; he does a much better job of setting it up, and showing how it's useful.

On a side note, I think that this usefulness in helping to spot abstract idea tie-ins, is the greatest benefit of using types, although having them define and catch constraints on one's code is also a big plus.