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.

I'd welcome suggestions for improving uLisp Zero, in particular: polishing the C code, making it more platform-independent, and solving the compiler warnings on the MSP430 and ARM platforms. Post comments on the uLisp Forum in the uLisp Zero category.

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.
Arduino MKRZero (ARM Cortex M0+) Arduino 3072 35 sec  

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.