HOME

lispski

SKI combinators in Lisp

This is day 2.

Today turned out to be messy. At first I wanted to implement a Forth interpreter in Rust, but I'm not very familiar with Forth, so I spent way too much time reading up on the specs before I could actually get started. It also occured to me that it might actually be more fun to try and write an interpreter in assembler. I might try my hand at Forth in 6502 assembler, which I've been playing around with.

In the evening I decided to leave Forth for now, and instead implement something extremely simple: an SKI combinator interpreter in Common Lisp.

How did it go?

After a lot of initial mucking around, I finally decided that the basic terms, S, K, and I, should be implemented as curried functions in a function table. That way it'll be easier to extend the implementation to include user defined functions.

It took me a few tries to get the ski-step function correct, but it's actually quite simple, but only because it requires the terms to be in a SKI-tree as described in the Wikipedia article. If xs is a pair it evaluates each term and applies the first to the second one. Either the evaluated first term is a term or a closure: If it is a closure use that, otherwise look up the function in the function-table.

As soon as ski-step was finished, the only thing that posed a problem was ski-treeify, which turns a right-handed tree into a left-handed tree, such as SKI-trees must be.

The result is not too good, but I've been under some time constraints, having started in the evening. I'd like to extend the implementation to allow declarations like:

F = SK

To make big programs easier to write. I'm not sure it'd play well with my current everything-is-one-char approach, but if I wanted to play with boolean logic or arithmetic, it'd crucial.

Another fun project, and I've learned more about how SKI-combinators work. Now it's time for bed!