Evaluating expressions of the combinator calculus

[Output]

The Javascript program in this page evaluates expressions of the SKI combinator calculus, built of the combinators i, k, and s and the application operator ` (so that `xy is x applied to y). It lacks the lambda operator; but any function built from these combinators and lambda is either

lambda x f, where f does not depend on x, which can be rewritten `kx,
lambda x x, which can be rewritten i, or
lambda x `fg, which can be rewritten ``s lambda x f lambda x g;

so, inductively, any such function can be written without lambda. (Thus, this program implements a subset of Unlambda -- indeed, it implements the Unlambda notation of Lazy K exactly.)

The combinators are defined as follows.

`ix = x
``kxy = x
```sxyz = ``xz`yz

Again, `xy denotes the function x applied to the function y, which might more conventionally be written x(y).

This program will evaluate an expression of the combinator calculus until either there are no instances of i, k, or s with one, two, or three curried arguments, respectively, or for 728 steps, where at each step the earliest evaluatable function is selected. Before evaluation, whitespace is removed, and up to 8 replacements are made of #?# with the contents of the input area labelled #?# or of #n#, where n is a positive integer not exceeding 9, with a representation of the Church integer n. After these replacements every character other than ` is treated as a single function. The intermediate steps of the evaluation will be shown iff the box labelled 'Show Steps' is checked, otherwise only the final result will be shown. The output area will be cleared before any evaluation iff the box labelled 'Clear Output' is unchecked.

This page was last (minorly) modified 23 January 2006.
Up