Skip to content

Home

Jump to bottom
drewvid edited this page Dec 30, 2015 · 14 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 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:

  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)) = value 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 expression withing the current env

The aditoinal 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 difference is accounted for by the extra functions 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.

The code is hosted on github. There you can find two versions of LISP - a version for the Parallella board with no garbage collection and one with rudimentary garbage collection which compiles and runs on a standard computer.

The implementation

The most important part of a LISP implementation is the function EVAL. While this is the case Idid in fact start by implementing the READ and PRINT functions first after deciding on am appropriate data structure for linked lists.

Clone this wiki locally