Skip to content

Beginnings

Jump to bottom
Andrew Ernest Ritz edited this page Jan 4, 2020 · 2 revisions

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 decided to start there. The result is a small implementation of lisp which has minimal 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 John McCathy’s original paper just 10:

  1. (quote expr) - expr
  2. (car l) - the head of the list - (car (quote (1 2 3))) = 1
  3. (cdr l) - the tail of the list - (cdr (quote (1 2 3))) = (2 3)
  4. (cons expr1 expr2) - cons constructs lists and is the inverse of car and cdr - (cons (quote a) (quote (b c))) = (a b c)
  5. (equal symbol1 symbol2) - T if symbol1 = symbol2 - (equal (car (quote (a b))) (quote a)) = true (t)
  6. (atom expr) - T if expr is a symbol (atom)
  7. (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.
  8. (label x 1) - 1 is assigned to x
  9. (label ff (lambda (x y) (cons (car x) y))) - defines the function ff - (ff '(a b) (cdr '(c d))) = (a d)
  10. (eval expr env) - Evaluate an expression within the current environment

The additional primitives added by me are:

  1. nilp
  2. append
  3. concat
  4. loop
  5. block
  6. progn
  7. if
  8. define
  9. ldefine
  10. print
  11. terpri
  12. <
  13. >
  14. +
  15. -
  16. /
  17. *
  18. =

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.

Because I was concentrating on writing the code I didn't really check that everything works as expected. I'll be doing this over the next few months as I add error checking. The code and examples I've released work OK so only minor changes are probably needed, which is good because I'm running out of space!

Clone this wiki locally