Mini-SK Combinator Reduction on a ZX Spectrum (Next)

VIDEO DESCRIPTION:

Play, download and edit the free video Mini-SK Combinator Reduction on a ZX Spectrum (Next).

The 48k Spectrum had about 40.5 KB of usable memory (the rest being used for screen memory and housekeeping for BASIC).

Today, 40.5 KB may seem like nothing, but in fact it is enough to run meaningful programs and even new programming environments. Despite the limited memory, the Spectrum had native compilers for C, Pascal, and even a Prolog interpreter.

Here, I show that a combinator reduction machine. It implements combinatory logic with the well-known combinators S/K/I and the slightly less often mentioned B and C combinators.

The system provides an interactive top-level loop, with some built in support for generating church numerals, as well as macros (holding some predefined combinator expressions) for convenience (including factorial, fibonacci and Collatz sequence length (a.k.a. the 3n+1 or tnpo problem).

Note that exlist1 is the list [0,1,2] and exlist2 is the list [2,0,7,5,1,3,6], with numbers encoded as Church numerals and lists encoded using the usual pair-encoding representation.

The implementation supports laziness, both avoiding evaluation that is not necessary to produce the result, and avoiding repeated recomputation of the same term (as happen with call-by-name).

The code is written in C (and C library with printf, etc.). The core is simple enough that it can run on a 16K spectrum, as shown in an earlier video (vimeo.com/431042094).

Although the combinator-reduction shown here looks primitive (e.g., there are no numbers, booleans, pairs or lists per se, they must be created from functions), these features are easily added. This core would allow a functional programming similar to Haskell.

The code was written in C, and runs on a ZX Spectrum, ZX Spectrum Next, on CP/M, and on modern machines, too. Here it's shown running on a ZX Spectrum Next, which runs 8x faster than the original Spectrum; the exact same code would run on an ordinary Spectrum, just a little slower.

(Some typing has been sped up, and a couple moments where a typo was entered and corrected deleted, but otherwise computation times represent actual time.)

Download, play and edit free videos and free audios from Mini-SK Combinator Reduction on a ZX Spectrum (Next) using RedcoolMedia.net web apps