Home
LISP has a long distinguished history and is the second oldest high level programming language in use today. My interest in this language led me to create a version for the Parellella board. The starting point was a blog post on the parallella forum discussing how much LISP could fit on the board. In trying to answer this question for myself, I came across numerous references to John McCarthy’s paper, "A Micro-Manual for Lisp - not the whole Truth" and therefore stsrted there. The result is a small implementation of lisp which is void of any garbage collection but does run on the Parallella 16 board.
So how many primitives does one need to implement a turing complete version of LISP. Well, according to Johm McCathy’s original paper just 10:
-
(quote expr) - expr
-
(car l) - the head of the list - (car (quote (1 2 3))) = 1
-
(cdr l) - the tail of the list - (cdr (quote (1 2 3))) = (2 3)
-
(cons expr1 expr2) - cons constructs lists and is the inverse of car and cdr - (cons (quote a) (quote (b c))) = (a b c)
-
(equal symbol1 symbol2) - T if symbol1 = symbol2 - (equal (car (quote (a b))) (quote a)) = true (t)
-
(atom expr) - T if expr is a symbol (atom)
-
(cond (predicate_1 expr_1) ... (predicate_n expr_n)) - the value of expr_i when predicate_i is true - (cond ((atom (quote a)) (quote b)) ((quote t) (quote c))) = b.
-
(label x 1) - 1 is assigned to x
-
(label ff (lambda (x y) (cons (car x) y))) - defines the function ff - (ff '(a b) (cdr '(c d))) = (a d)
-
(eval expr env) - Evaluate an expression within the current environment
The aditoinal primitives added by me are:
-
nilp
-
append
-
concat
-
loop
-
block
-
progn
-
if
-
define
-
ldefine
-
print
-
terpri
-
<
-
>
-
+
-
-
-
/
-
*
-
=
The extra functions are for printing, looping, block processing, list processing and integer arithmetic.
The code isn’t documented because I intend to do that with a series of blog posts over the next few months or so. This being the first.