## uLisp Zero

uLisp Zero is a pared-down version of uLisp, capable of running in 8 Kbytes of program memory with 1 Kbyte of RAM. It is intended as a starting point for anyone wanting to develop their own dialect of Lisp, design another Lisp-like language, or just understand how a Lisp interpreter works.

It's similar to the first version of uLisp I got working, but takes advantage of the bug fixes and improvements from the latest version of uLisp.

Because it doesn't contain any platform-specific features the same code will run on either Arduino ATmega platforms or Energia MSP430 platforms.

You program uLisp Zero in the same way as uLisp, just by typing commands in the Arduino/Energia Serial Monitor; see Using uLisp.

#### Download

Download the latest version of uLisp Zero here:

uLisp Zero Version 1.1 - 18th May 2017

or get it from GitHub at https://github.com/technoblogy/ulisp-zero.

### Requirements

Program memory: At least 8 Kbytes.

RAM: At least 1 Kbytes.

Adjust the value of WORKSPACESIZE to suit the amount of RAM you have available; the default setting is suitable for 2 Kbytes.

### Specification

- Types: symbols and lists.
- Symbols: Up to three characters, a-z and 0-9.
- Functions and symbols: nil, t, lambda, quote, defun, defvar, setq, if, not, null, cons, atom, listp, consp, symbolp, eq car, cdr, eval, globals, locals
- Garbage collection.

### Platforms

I've tested uLisp Zero 1.1 on the following platforms:

Platform |
IDE |
Cells |
Benchmark |
Notes |

Arduino Uno (ATmega328) | Arduino | 320 | N/A | Not enough memory to run the benchmark. |

Arduino Mega 2560 (ATmega2560) | Arduino | 1280 | 162 sec | |

ATmega1284 | Arduino | 2880 | 162 sec | |

MSP430F5529 LaunchPad | Energia | 1280 | 100 sec | |

MSP430FR5969 LaunchPad | Energia | 3072 | 188 sec | Using FRAM for the workspace; see below. |

Arduino Zero (ARM Cortex M0+) | Arduino | 2048 | 35 sec | |

Adafruit Feather M0 (ARM Cortex M0) | Arduino | 2048 | 35 sec | Problem with serial port; see below. |

Arduino Due (ARM Cortex M3) | Arduino | 8000 | 25 sec | Requires Arduino IDE 1.8.1 or later. |

**Cells** gives the recommended value for the WORKSPACESIZE constant, giving the number of Lisp cells of storage available.

**Benchmark** gives the time taken to run the Hofstadter Q sequence benchmark.

#### Notes

On the MSP430FR5969 you can use the FRAM for the workspace by defining:

object Workspace[WORKSPACESIZE] __attribute__((section(".text"))) WORDALIGNED;

On the Adafruit Feather M0 there an unresolved problem that the serial port hangs if you attempt to paste a long listing into the serial monitor; this doesn't happen with any of the other platforms.

### Examples

Here are some example programs that uLisp Zero can evaluate:

#### Interleave two lists

Interleaves two lists of the same length.

(defun int (one two) (if (null one) nil (cons (car one) (cons (car two) (int (cdr one) (cdr two))))))

For example:

> (int '(a b c) '(d e f)) (a d b e c f)

#### Last item of a list

Returns the last item of a list.

(defun end (lst) (if (null (cdr lst)) (car lst) (end (cdr lst))))

For example:

> (end '(a b c d)) d

#### Append two lists

Joins two lists into a single list:

(defun app (one two) (if (null (cdr one)) (cons (car one) two) (cons (car one) (app (cdr one) two))))

For example:

> (app '(a b c) '(d e f g)) (a b c d e f g)

#### Reverse a list

Reverses a list. Uses **app** from the previous example:

(defun rev (lst) (if (null (cdr lst)) lst (app (rev (cdr lst)) (cons (car lst) nil))))

For example:

> (rev '(a b c d e f)) (f e d c b a)

#### Longest Common Subsequence

To prove that uLisp Zero can calculate something non-trivial, here is a routine to find the Longest Common Subsequence (LCS) of two lists; in other words, the longest sequence of elements that occur in the same order in both lists.

For example, the LCS of (1 2 3 5 6 8 9) and (2 3 4 6 7 8) is (2 3 6 8).

First we define a routine **lgr** that returns **nil** if the first list is not longer than the second list:

(defun lgr (a b) (if (null b) a (lgr (cdr a) (cdr b))))

For example:

> (lgr '(a b c) '(a b c)) nil > (lgr '(a b c d) '(a b c)) (d)

Then we define **lon** that uses this to return the longer of two lists:

(defun lon (a b) (if (lgr a b) a b))

For example:

> (lon '(a b c d) '(a b c)) (a b c d)

Finally, here's the definition of **lcs**:

(defun lcs (a b) (if (null a) nil (if (null b) nil (if (eq (car a) (car b)) (cons (car a) (lcs (cdr a) (cdr b))) (lon (lcs a (cdr b)) (lcs (cdr a) b))))))

For example:

> (lcs '(1 2 3 5 6 8 9) '(2 3 4 6 7 8)) (2 3 6 8)

The algorithm works as follows:

- If the two lists have the same first element, the LCS is this followed by the LCS of the lists with the first element removed.
- Otherwise try ignoring the first element of each list in turn. The LCS is the one that gives the longest result.

#### Hofstadter Q sequence

This is one of several recursive sequences described in Douglas Hofstadter's book "Gödel, Escher, Bach: an Eternal Golden Braid", and was included in the uLisp Benchmarks.

Since uLisp Zero doesn't have numbers, this version of the benchmark uses the length of the lists to denote the numbers. I use "x"s, but you could use any list of symbols.

First we define an **add** function; this is the same as the append function, **app**, defined above:

(defun add (one two) (if (null (cdr one)) (cons (car one) two) (cons (car one) (add (cdr one) two))))

For example, to add 2 and 3:

> (add '(x x) '(x x x)) (x x x x x)

Next we need an equivalent subtract function, **sub**. This is the same as the **lgr** function defined above (negative numbers aren't supported!):

(defun sub (a b) (if (null b) a (sub (cdr a) (cdr b))))

For example:

> (sub '(x x x x) '(x x)) (x x)

The following function returns **t** if its argument is less than or equal to 2, and **nil** otherwise:

(defun le2 (n) (null (cdr (cdr n)))

For example:

> (le2 '(x x)) t

Finally, here's the definition of **q**:

(defun q (n) (if (le2 n) '(x) (add (q (sub n (q (cdr n)))) (q (sub n (q (cdr (cdr n))))))))

On an Arduino Mega 2560 (q 21) takes 162 secs to return the answer 12:

> (q '(x x x x x x x x x x x x x x x x x x x x x)) (x x x x x x x x x x x x)

Here are all the examples in a single file: uLisp Zero examples.