The ION machine

We earlier noted that applying the S combinator causes two nodes to refer to the same subterm. This sharing saves room, but we can save more.

Suppose two nodes X and Y point to the same subterm T. On reducing X, our reduce function created a new subterm U, and changed X to point to U and left Y pointing to T (reminiscent of copy-on-write).

Instead, we should simply replace T with U so that reducing either one of X or Y causes both to point to U afterwards. This strategy is known as lazy evaluation, and our lazy function below carries it out.

Even though the result is the same, we see this order as different to normal order, because we reduce both X and Y (and possibly other nodes) even if they are not the two left-most subterms.

The tacit application of load n to load (n + 1) creates complications with lazy evaluation, which we work around with the aid of the identity combinator. For example, if an application evaluates to K, then we replace it with IK.

For primitive functions, we use a trick described in depth by Naylor and Runciman, The Reduceron reconfigured and re-evaluated: we introduce a combinator called # and reduce, say, # 42 f to f(# 42) for any f. For example, the term (I#2)(K(#3)S)(+)) reduces to (+)(#3)(#2).

In this fashion, the first two arguments of (+) are always primitive integers, so our code for reducing (+)(#m)(#n) simply pulls out the words m and n from certain locations in memory and returns #s where s == m + n modulo 2³².

This scheme resembles the approach described by Peyton Jones and Launchbury, Unboxed values as first class citizens in a non-strict function language. For example, they define integer subtraction as follows:

After Scott-encoding, we have:

In other words, using their notation, 42 f reduces to f(42#). However, our subtraction operator also boxes the result, while they have a separate boxing step, which is better for optimization. We may wish to follow suit and split off boxing, though it likely means introducing supercombinators to reap the benefits.

We support the operations + - / * % = L. The first 5 have the same meaning they do in C, while the last 2 are equivalent to C’s (==) and (<=).

We add a couple of useful macros: the R combinator (equivalent to CC) and the (:) combinator (equivalent to B(BK)(BCT)).

Below, the I combinator is not lazy: for instance, every time we encounter the subterm I(I(Ix)) we must reduce three I combinators. The competition version of this code does lazily evaluate I combinators, but consequently treads carefully near the top of the stack.

For us, a program P is a function from a string to a string, where strings are Scott-encoded lists of characters.

To run P on standard input and output, we initialize the VM with P(0?)(.)(T1) then repeatedly reduce until asked to reduce the (.) combinator.

The 0 combinator takes one argument, say x. The term 0x reduces to IK at the end of input or (:)(#c)(0?) where c is the next input character. The unused argument x is a consequence of the ION machine’s peculiar encoding of applications and the need to ensure there is at most one 0 combinator in the heap.

The 1 combinator takes two arguments, say x and y. The first argument x should be an integer constant, that is, #c for some c. Then the character with ASCII code c is printed on standard output, and the expression 1xy is reduced to y(.)(T1).

(In ION assembly, symbols, letters and digits are just names of combinators. In particular, the (.) combinator is not a binary operator representing function composition. Similarly, 0 and 1 do not represent integers; the names of these combinators were inspired by the file descriptors of standard input and output.)

Edward Kmett’s talk Combinators Revisited contains many relevant references and ideas.

Other choices for implementing lambda calculus include: