Fancy Programming Papers

[jducoeur]

For my own future reference as much as anything, but other hardcore programmers might find these interesting: I've continued to do a good deal of surfing in my spare time this past week, digging deeper into new-and-cool programming concepts. A few papers that I want to read and keep track of:

Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-Transform is apparently one of the key papers underlying Scala's Continuations mechanism. Continuations are one of those moderately abstruse but increasingly important concepts, describing how you wrap up a program's state and pass it around. At the high theoretic level, a bunch of common control-flow concepts like loops are often nowadays being described in terms of continuations.

The Essence of the Iterator Pattern analyzes the way that iteration is commonly performed in various languages, decomposes it into its key concepts, and then builds up a new pattern that (theoretically -- I'm only a third of the way through the paper) captures the best of all of them.

Issue 13 of the Monad.Reader contains a key article, the Typeclassopedia -- an organized list of the crucial higher-order type classes. It builds from Functors up through Monads, Monoids, Applicative Functors, etc, etc. Still not an easy read, and focused on Haskell (I was asking on the scala-debate list this morning for somebody to please write a decent course in advanced functional-programming concepts using Scala and Scalaz -- it turns out that they are working on it), but the best-organized examination of the topic that I've found to date.

Comments

[learnedax.livejournal.com]

Interesting articles, that I should clearly read. I do twitch a bit at the thought of mapping something like a loop as a form of continuation, considering the staggering overheads involved in bundling them up. I've always liked them as a concept, but rarely run into a circumstance where I could have stomached the costs - except, I suppose, for times when threading served the same purpose, at a similar cost but with better language support.

[jducoeur]

Well, I'm not sure that anybody *actually* implements loops as continuations outside the extremely purist-functional world -- Scala is built on the JVM, so I think that its "ordinary" looking loops are constructed just like Java's. (Its extended form of for loop is a separate beast entirely, but is more a variation of map than a true loop anyway.)

My impression (I haven't really internalized the discussion) is that, from a purist's POV, the "break" statement is problematic -- that's when continuations seem to come up in theoretical discussions. In *practical* discussions, though, continuations mostly seem to get used for really novel control flows that aren't natively supported in the language. To support that, Scala provides CPS continuations at the library level; I don't yet really grok their usage, but that's on my to-learn list...

[learnedax.livejournal.com]

Yeah, something like a coroutine would be a fine place to use them. And I'm happy when languages do support CPS, even if I don't often use it.

Breaks in loops seem fine to me, because I'm comfortable with the whole thing being syntactic sugar for gotos. (Of course, parallelized foreach loops and such can reasonably have a very different basis, but there are still plenty of times a plain sequential loop is the most useful thing.) If one conceptualized all of one's looping through tail recursion, breaking would be the same problem as mid-function return, of course...