(d A (q (
(y x)
(v (c (h x)
(c
(c (q q) (c y ()))
(t x))))
)))
(d K (q (
(x)
(c (q K1) (c (c (q q) (c x ())) ()))
)))
(d K1 (q (
(y x)
x
)))
(d S (q (
(x)
(c (q S1) (c (c (q q) (c x ())) ()))
)))
(d S1 (q (
(y x)
(c (q S2) (c (c (q q) (c y ())) (c (c (q q) (c x ())) ())))
)))
(d S2 (q (
(z y x)
(A (A z y) (A z x))
)))
Try it online! (The three examples are the identity combinator (S K K), the mockingbird combinator (S (S K K) (S K K)), and an infinite loop, so you'll need to halt the program to see the output from the first two.)
This is an interpreter for SK combinator calculus (which is Turing complete), built in tinylisp-without-i.
Usage, and principles behind this
The basic idea is to do control flow via v, which lets us inspect an atom via using it as the name of a function. As is usual in implementations of combinator calculus, we make use of five families of combinators (S and K themselves, plus partially applied versions of them; K can be given one argument to produce K1, S can be given one or two arguments to produce S1 or S2).
In order to be able to use these for control flow with v, we store our combinators in a form that looks like a tinylisp function call but with one argument missing, and the arguments in reverse order:
S is stored as (S);K is stored as (K);S applied to one argument x is stored as (S1 (q x));K applied to one argument x is stored as (K1 (q x));S applied to two arguments x and y is stored as (S2 (q y) (q x)).
Our combinator application operator A works by inserting the argument it's being given as the second element of the function it's given, in the form (q arg) (thus producing a complete tinylisp function call), and then evaluating it with v. (This is the reason that the arguments have to be reversed – we can't insert a value at the end of a list of unknown length when we have no workable control flow, but we can insert an element in any specific position relative to the start via using hardcoded chains of h and t.) A can be used directly to write programs (allowing specification of arbitrarily complex input), and is used indirectly in the implementation of S2 (which is what makes loops possible).
To write a complete program, you write S as (q (S)), K as (q (K)), and application of f to x as (A x f) (I decided to consistently reverse arguments everywhere, which is probably less confusing then reversing them only in some places). For example, the implementation of the identity function, which in Lisp syntax would be (S K K), looks like this when used as input to this interpreter:
(A (q (K)) (A (q (K)) (q (S))))
Explanation
Most of this program is just list manipulation, building up lists from templates. The "inside" of most of these is the fragment (c (q q) (c x ())). (c x ()) inserts (c) x as the first element of an empty list (()), thus producing (x). The fragment as a whole inserts (c) a literal q ((q q)) as the first element of that, thus producing (q x). The same technique is then repeated to produce a list whose elements are of the form (q x) and which starts with an appropriate combinator, and this is the only thing done in the implementations of S, S1 and K.
A is very similar – the only differences are that the resulting list is evaluated as tinylisp code (v) rather than simply being returned, and that the list is constructed as the head of the function ((h x)), followed by the argument formatted as (q y), followed by any arguments that may have been curried into the combinator (this is the tail of x, (t x)).
K1 and S2 contain all the actual logic, and are implementations of the K and S combinators, as per the definition of SK combinator calculus; K returns its first argument x and ignores its second argument Y, whereas S returns (A (A z y) (A z x)) (which can simply be written directly in the function body).
