I wanted to write a test case that really hammers uLisp’s tail-call elimination and closure code hard, so after scratching my head for a while I decided to write a Unlambda interpreter. It is done using currying and continuation-passing style so there are lots of anonymous lambdas (18 of them in fact).
Here it is:
(defun k (x cont1)
"Constant generator"
(cont1 (lambda (y cont2)
"Constant function"
(cont2 x))))
(defun s (x cont1)
"Substitutor"
(cont1 (lambda (y cont2)
"Substitution first application"
(cont2 (lambda (z cont3)
"Substituted aplication"
(x z (lambda (xf)
(y z (lambda (yv)
(xf yv cont3))))))))))
(defun i (x cont)
"Identity"
(cont x))
(defun v (x cont)
"Black hole"
(cont v))
(defun c (x cont1)
"Call/cc"
(x (lambda (y cont2)
"A continuation"
(cont1 y)) cont1))
(defun mkpch (ch)
(lambda (x cont)
"printer"
(princ ch)
(cont x)))
(defun r (x cont)
"carriage return"
(terpri)
(cont x))
(defun md (dg)
(let (g)
(lambda (h cont)
"promise"
(if g (h g cont) (eu dg (lambda (gg) (setf g gg) (h gg cont)))))))
(defun pu (str)
"parse unlambda program"
(let* ((index -1)
(getc (lambda ()
(incf index)
(unless (< index (length str))
(error "too many `s"))
(char str index)))
(pui (lambda ()
(case (getc)
(#\` (list (pui) (pui)))
(#\k k)
(#\s s)
(#\v v)
(#\i i)
(#\r r)
(#\c c)
(#\d 'd)
(#\. (mkpch (getc)))
(t (error "unknown character at position ~a" index)))))
(out (pui)))
(unless (= index (1- (length str)))
(error "not enough `s"))
out))
(defun eu (ast &optional (cont (lambda (x) x)))
"eval unlambda program - continuation-passing style. ast should be a lambda or a cons of ast"
(if (and (consp ast) (= (length ast) 2) (not (eq (car ast) 'lambda)))
(eu (first ast) (lambda (fe)
(if (eq fe 'd)
(md (cdr ast))
(eu (second ast) (lambda (ae)
(fe ae cont))))))
(cont ast)))
(eu (pu "`r`````````````.H.e.l.l.o.,. .w.o.r.l.d.!i"))
"```s``s``sii`ki`k.*``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk`k``s`ksk"
Invoke a program as (eu (pu <string>)). The one queued up to run if you just paste everything in is the “Hello, World!”; the last line is a string that you can paste in is David Madore’s Fibonacci asterisk program. (Because it runs infinitely, it will eventually crash; see below.) There are plenty of other Unlambda programs at http://ftp.madore.org/pub/madore/unlambda/CUAN/.
Interestingly enough, despite having tail-call elimination, the thing that prevents this implementation from being able to run Unlambda programs that never terminate is the garbage collector. Each continuation is a closure and this interpreter makes no attempt to optimize these closures (even if the continuation’s action is simply to invoke a parent continuation with the result passed). This means that every function invocation ends up using more and more and more memory until either a) uLisp runs out of memory, or b) the garbage collector tries to mark one of these ginormous objects and winds up blowing the C call stack.
Either way, I hope you like it!