Der Blog

Here's an interesting toy language/Turing tarpit for you: Lazy K.

You may already have seen Unlambda, which is essentially the lambda calculus in programming langauge form. (Actually, as its name suggests, it doesn't actually have any lambdas - it's really based on the equivalent SKI combinator calculus.) However, Unlambda is a horrible dirty - ahem, I mean impure functional language because 1) it isn't lazy and so programs in it can sometimes gratuitously fail to terminate, and 2) it has an exception to the evaluation rules (the d 'function') and side effects (the .x function prints the character x). Also, in Unlambda version 1 there is no way to do input.

Lazy K is no easier to write programs in than Unlambda (that's hardly the point, is it? :). But it solves all these problems: it is lazily evaluated; there are no side effects; and you can do input.

Wait a minute, I hear you cry, how can you do input with no side effects? Even Haskell, the paragon of freedom from side effects, has exceptions for I/O. Well Lazy K takes the common Haskell idiom of stream-based I/O and makes it mandatory. So a Lazy K program is just a function which operates on (infinite, lazily constructed) lists of natural numbers (i.e., Church numerals) to produce lists of natural numbers. This abstracts I/O out of the program, so rather than being side-effects, input is a front-effect and output a back-effect. And although it's in principle impossible to specify exactly when output happens, there are well documented ways of doing it in practice in the presence of lazy evaluation.

It's an interesting approach, and is exactly why Haskell programmers like the lazy stream I/O idiom so much; as the Lazy K page says:

Lazy K programs live in the same timeless Platonic realm as mathematical functions, what the Unlambda page calls "the blessed realm of the pure untyped lambda calculus." Just as garbage collection hides the process of memory management from the programmer, so referential transparency hides the process of evaluation. The fact that some calculation is necessary in order to view a picture of the Mandelbrot set, or in order to "run" a Lazy K program, is an implementation detail. That's the essence of functional programming.