komplott
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
Features
- Single file implementation.
- Scheme-compliant enough for the test programs to be executable by GNU Guile.
- Copying garbage collector based on Cheney's Algorithm.
- Limited tail call optimization (not true TCO; see
tests/true-tco.scm). - Near-zero error handling.
- Zero thread safety or security.
Also includes:
lisp15.scm
An implementation of the core of LISP 1.5 from 1962
Instructions
-
To build the
komplottexecutable, runmake. The only dependency aside frommakeisgcc. -
To run the LISP 1.5 interpreter and a couple of test cases, run
make lisp15.
LISP 1.5
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 )))))))))))))))))