17 Jan 2010
(updated 17 Jan 2010 at 01:31 UTC) »
Via Wes Felter, I came
across a fun puzzle language by my old friend C Guy Yarvin. I
think of Nock
as being in a family of languages with certain things in
common: tiny number of primitives, definition can fit on a
t-shirt, not quite practical, but powerful and expressive
enough that you can imagine writing real programs in it. If
this sort of thing appeals to you, I recommend checking it
out. I took up his challenge to write an interpreter and
sample program, and the core Python interpreter is 38 lines
Other languages in this vein include SKI
combinators, pure lambda calculus, pure
LISP, universal turing machines, and Brainfuck.
No doubt my readers
can come up with several more examples.
All this reminded me of my own Io, which I designed, oh,
about 22 years ago. Io is basically a language in which the
only primitive is continuations. Because it encompasses
the power of simple lambda calculus, you can implement
arithmetic and data structures using Church numerals.
Probably the best introduction to Io is the chapter
out of Raphael Finkel's book,
and there's some more good description in notes
by Kragen Sitaker.
I only wrote up half of my ideas in the SIGPLAN Notices
(PDF). The other half was
primitives for parallelism. In addition to the pure
language, "par k1 k2" fires off continuations k1 and k2 in
parallel. Then "join k" invokes k with two new
continuations, call them "alpha" and "beta". If one thread
calls "alpha f" and another "beta x", then the two threads
join at that point and invoke "f x". With this primitive,
you can easily implement the full range of concurrency
operations, including cells with state, input and output
(hence the name of the language), etc.
I used to think it would be a good idea to build real
systems in Io, but now I guess I've grown up a little. For
one, while I think it's important for any serious student of
languages to understand CPS, I'm no longer a huge fan
of actually using it. Plus, it's much harder to implement
things like Io efficiently than I originally thought.
But these languages sure are fun to play with!