Alan Kay on type systems

I'm not against types, but I don't know of any type systems that aren't a complete pain, so I still like dynamic typing.

(HT Paul Snively)

Delimited continuations papers 2

Had a conversation with a friend about delimited, composable continuations again. Previously, I've linked to some papers about delimited continuations. Here are two important ones:

Representing Monads: We show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with "composable continuations". As part of the development, we extend Meyer and Wand's characterization of the relationship between continuation-passing and direct style to one for continuation-passing vs. general "monadic" style. We further show that the composable continuations construct can itself be represented using ordinary, non-composable first-class continuations and a single piece of state. Thus, in the presence of two specific computational effects -- storage and escapes -- any expressible monadic structure (e.g., nondeterminism as represented by the list monad) can be added as a purely definitional extension, without requiring a reinterpretation of the whole language. The paper includes an implementation of the construction (in Standard ML with some New Jersey extensions) and several examples.

A monadic framework for delimited continuations: Delimited continuations are more expressive than traditional abortive continuations and they apparently seem to require a framework beyond traditional continuation-passing style (CPS). We show that this is not the case: standard CPS is sufficient to explain the common control operators for delimited continuations. We demonstrate this fact and present an implementation as a Scheme library. We then investigate a typed account of delimited continuations that makes explicit where control effects can occur. This results in a monadic framework for typed and encapsulated delimited continuations which we design and implement as a Haskell library.

I've blogged about the API and hair-raising example offered in this paper before.

The Kernel Underground

A quick update on Kernel buzz:

There are now fourfivesixseven19 (I stopped counting) implementations of Kernel and Kernel-like languages:

• SINK, by John Shutt. Scheme.
• klisp, by Andres Navarro. C.
• js-vau and vau.rkt by Tony Garnock-Jones. JavaScript and Racket.
• Hummus, Cletus, and Pumice, by Alex Suraci. Haskell, Atomy, and RPython.
• Schampignon, Virtua, and Wat by me. JavaScript.
• Klink, by Tom Breton. C.
• Karyon, by Jordan Danford. Python.
• εlispon, by Pablo Rauzy. C.
• fexpress, by Ross Angle. JavaScript.
• Qoppa, by Keegan McAllister. Scheme.
• Schrodinger Lisp, by Logan Kearsley. Python.
• squim, by Mariano Guerra. JavaScript.
• Nulan, by Pauan. Python.
• IronKernel, by Ademar Gonzalez. F#.
• Bronze Age Lisp, by Oto Havle. Assembly.
• Pywat, by Piotr Kuchta. Python.
• Wat.pm, by unknown. Perl.
• Extensible Clojure

Check them out for inspiration, and write your own. It's fun. Fexprs are fun exprs!

There are some interesting Kernel discussions going on in the Guile thread (and here) on LtU. David Barbour provides welcome criticism. (The truth can only be found in conflict. - Tarkovksy)

Oh, and I created this:

Syntax is a monad

I'm becoming aware of a whole Lambda-Meme-Universe! This one via Dorophone:

Oleg cat

(via Paul)

Mortal combat

A slightly confused anonymous commenter (I get to say such things about anonymous commenters, right?) reminded me of this quote by Ray Dillinger:

The scheme community is now very invested in its macrology; they got there by long hard work and emotional processing and yelling and screaming and weeping and gnashing of teeth, and they still remember the pain of not having a standard macrology. You will not pry it away except from their cold dead fingers, and you will not redefine it without defeating them in mortal combat.

I think the commenter misunderstood my earlier post. Syntactic extension is absolutely necessary, and modern Scheme macro systems are a fine way to do it.

On macros

This post by David Barbour is one of the most insightful statements on macros I have read (along with Vladimir Sedach's analysis):

It has been my impression that, no matter what specific thing you use macros to do, you can later invent a neat language feature that handles the problem in a clean and nice manner. The problem is the "later". Macros can do it "now"... in an ugly, brutish manner, true, but the job gets done. ...

Even among people who find macros smelly, you'll find many who think macros the least distasteful of these choices.

John Shutt's response ties this in with fexprs - instead of delegating the job to a separate preprocessing step, let the language itself have the power of self-extension:

Macros are an unpleasant feature to compensate, somewhat, for limitations of a language. It's better to compensate for the limitations than to leave the limitations in place without compensating at all. Better still, though, would be to eliminate the offending limitations. (Remove the weaknesses and restrictions that make additional features appear necessary.) Make no mistake, fexprs don't necessarily increase the uniform flexibility of the language; but with care in the design they can do so, and thereby, the jobs otherwise done by macros are brought within the purview of the elegant language core. So instead of an ugly brutish fix with macros now and hope for a more elegant replacement later, one can produce a clean solution now with fexprs.

PS: This point is subtle. After all Scheme is already self-extensible. But Scheme macros still are an additional "layer" on top of, and separate from, the core language. Kernel's fexprs are not - they are the core language, thus bringing self-extension within the purview of the elegant language core.