A tribute to:
Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
(as found in paper/recursive.pdf)
A micro-subset of scheme / the original LISP in a single C file: komplott.c
The LISP interpreter translated to Odin in
komplodin.odin. More lines of code, but I am less familiar with the
language and am translating directly from C, so there are probably ways
to make it a cleaner solution.
When I posted this to lobste.rs, gingerBill (creator of Odin) was kind enough to make a more direct translation of the C code into Odin, which can be viewed in this gist: komplott.odin.
Since the lobste.rs posting, I have tweaked the Odin version a bit more, and so it differs from the C version quite a bit in the implementation details. I've tried to keep the output and functionality of the two programs the same though.
-
Single file implementation.
-
Less than 500 lines of code (~600 lines for the Odin version)
-
Scheme-compliant enough for the test programs to be executable by GNU Guile (not sure if this is true anymore)
-
Copying semi-space garbage collector based on Cheney's Algorithm.
For more details on how it works, Andy Wingo has a great post about this kind of garbage collector on his blog (wingolog).
-
Limited tail call optimization (not true TCO; see
tests/true-tco.scm). -
Near-zero error handling.
-
Zero thread safety or security.
Also includes:
An implementation of the core of LISP 1.5 from 1962
-
To build the
komplottexecutable, runmake komplott. The only dependency aside frommakeisgcc. -
To build the Odin version (
komplodin), runmake komplodin. This depends on the Odin compiler. -
To run the LISP 1.5 interpreter and a couple of test cases, run
make test.
The version presented in the README is slightly tweaked from the one
that can be found in tests/lisp15.scm in order to more closely
resemble early LISP rather than scheme: #t and #f are written as
t and nil.
(define pairlis (lambda (x y a)
(cond ((null? x) a)
(t (cons (cons (car x) (car y))
(pairlis (cdr x) (cdr y) a))))))
(define assoc (lambda (x a)
(cond ((equal? (caar a) x) (car a))
(t (assoc x (cdr a))))))
(define atom? (lambda (x)
(cond
((null? x) t)
((atom? x) t)
(t nil))))
(define evcon (lambda (c a)
(cond
((eval (caar c) a) (eval (cadar c) a))
(t (evcon (cdr c) a)))))
(define evlis (lambda (m a)
(cond
((null? m) nil)
(t (cons (eval (car m) a)
(evlis (cdr m) a))))))
(define apply (lambda (fun x a)
(cond
((atom? fun)
(cond
((equal? fun (quote CAR)) (caar x))
((equal? fun (quote CDR)) (cdar x))
((equal? fun (quote CONS)) (cons (car x) (cadr x)))
((equal? fun (quote ATOM)) (atom? (car x)))
((equal? fun (quote EQ)) (equal? (car x) (cadr x)))
(t (apply (eval fun a) x a))))
((equal? (car fun) (quote LAMBDA))
(eval (caddr fun) (pairlis (cadr fun) x a)))
((equal? (car fun) (quote LABEL))
(apply
(caddr fun)
x
(cons
(cons (cadr fun) (caddr fun))
a))))))
(define eval (lambda (e a)
(cond
((atom? e) (cdr (assoc e a)))
((atom? (car e))
(cond
((equal? (car e) (quote QUOTE)) (cadr e))
((equal? (car e) (quote COND)) (evcon (cdr e) a))
(t (apply (car e) (evlis (cdr e) a) a))))
(t (apply (car e) (evlis (cdr e) a) a)))))
(define evalquote (lambda (fn x) (apply fn x (quote ()))))
Here is an example of actual LISP 1.5 code:
((LABEL MAPCAR
(LAMBDA (FN SEQ)
(COND
((EQ NIL SEQ) NIL)
(T (CONS (FN (CAR SEQ))
(MAPCAR FN (CDR SEQ)))))))
DUP LST)
; where
; DUP -> (LAMBDA (X) (CONS X X))
; LST -> (A B C)To prevent reading from continuing indefinitely, each packet should end with STOP followed by a large number of right parentheses. An unpaired right parenthesis will cause a read error and terminate reading.
STOP )))))))))))))))))