Visible Lisp Computer
14th August 2019
The Visible Lisp Computer is a Lisp interpreter that displays the contents of the Lisp workspace on an OLED display, so you can see program execution and garbage collection in real time:
Visible Lisp Computer displays the contents of the Lisp workspace on an OLED display as it runs.
It's a special version of my uLisp interpreter for ARM boards [1], designed to run on an Adafruit ItsyBitsy M0, or an ATSAMD21E on a prototyping board, interfaced to an I2C OLED display.
For example, when you evaluate a recursive function, such as the Fibonacci function, you can see the memory being allocated to perform the calculation, and garbage collections clearing unused memory. Apart from being fun, it's educational, giving an insight into how a language with garbage collection works.
Introduction
The Visible Lisp Computer runs on an Adafruit ItsyBitsy M0, which is an ideal ATSAMD21 board for running uLisp. It's available from Adafruit [2], or Pimoroni in the UK [3].
The Lisp workspace is displayed on a 64x48 OLED display. This is an ideal fit, as uLisp running on an ATSAMD21 gives you a workspace of 3072 free Lisp objects (each of 8 bytes), and the 64x48 display provides 3072 pixels. I chose a low-cost monochrome I2C display, available from AliExpress [4]. The program would also work on larger SSD1306-based OLED displays, such as the widely available 128x64 ones.
Free Lisp objects are displayed in black, and when an object is in use it is displayed in white. Periodically you see the garbage collection reclaiming used objects that can no longer be accessed.
The circuit
Here's how to connect up the display to the Adafruit ItsyBitsy M0:
Circuit of the Visible Lisp Computer based on an Adafruit ItsyBitsy M0.
You need pullup resistors of about 4.7kΩ from SDA and SCL to VCC.
Instead of using an Adafruit ItsyBitsy M0 you can build an equivalent Visible Lisp Computer using an ATSAMD21E on a prototyping board by following my earlier project Minimal ATSAMD21 Computer:
Version of the Visible Lisp Computer built on a prototyping board.
The I2C OLED display connects to GND, VCC, SDA (pin 21), and SCL (pin 22). Again, you need 4.7kΩ pullup resistors from SDA and SCL to VCC.
Example
Here's an example of the Visible Lisp Computer in action.
First we enter a sample Lisp function to evaluate; I'll use the Fibonacci function, as it should be familiar to most programmers:
(defun fib (n) (if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))
Initially the display is black. After entering this in the Serial Monitor the display shows:
The function is stored in the Lisp workspace as a series of Lisp objects, indicated by the row of white pixels starting in the top left corner.
Evaluating the function by entering, for example:
(fib 10)
allocates Lisp objects as the function is executed, indicated by a white block extending down from the top of the display:
This call to the Fibonacci function executed within the workspace available, without triggering a garbage collection.
If we now evaluate:
(fib 16)
the function triggers several garbage collections as it executes to reclaim unused objects, while leaving the intermediate values, which are still in use, visible on the display:
Turning off the workspace display
The workspace display is on by default. Because updating the display causes Lisp programs to run more slowly, I've added a Lisp command to turn the display off; give the command:
(display nil)
To turn it back on again give the command:
(display t)
The standard version of uLisp does a garbage collection after you input each command at the Serial Monitor or REPL. When running the workspace display this is disabled, to avoid the lag caused by the garbage collection after every line of input. If you want to tidy up the screen display before running a program you can do a manual garbage collection by giving the command:
(gc)
The program
The workspace display interfaces with uLisp in three places. In each case a flag, DISPLAYFLAG, determines whether the workspace display is active.
Lisp objects
All objects in ARM uLisp consist of two 4-byte cells, so every object occupies 8 bytes. There are several different types of object, such as symbol, number, or cons, identified by the constant in the left-hand cell:
- A symbol contains '2' in the left cell, and the name of the symbol packed in the right cell, or a pointer to the symbol in a symbol table.
- A number contains '4' in the left cell, and the 32-bit signed integer value in the right cell.
- Finally, a cons contains an address pointer in each cell pointing to other objects.
Address pointers are always larger than the largest constant used to identify other types of object.
Initialising the workspace
When the workspace is first initialised, by calling initworkspace(), all the objects are added to a list of free objects:
The corresponding pixels on the workspace display are plotted in black with a call to PlotObject():
void initworkspace () { Freelist = NULL; for (int i=WORKSPACESIZE-1; i>=0; i--) { object *obj = &Workspace[i]; if (tstflag(DISPLAYFLAG)) PlotObject(i, 0); car(obj) = NULL; cdr(obj) = Freelist; Freelist = obj; Freespace++; } }
Allocating an object
A Lisp object in the workspace is allocated by a call to myalloc(). It's taken off the freelist and returned by the call. For example, creating the list:
(fib 6)
will take four objects from the freelist:
The corresponding pixels in the workspace display are plotted in white:
object *myalloc () { if (Freespace == 0) error2(0, PSTR("no room")); object *temp = Freelist; Freelist = cdr(Freelist); Freespace--; if (tstflag(DISPLAYFLAG)) PlotObject(((int)temp - (int)Workspace)>>3, 1); return temp; }
The address of the object is calculated by subtracting the address of the start of the workspace from the address of the new object, and dividing by eight because each Lisp object is 8 bytes.
Freeing an object
Finally, a Lisp object is freed by a call to myfree(). It is put on the front of the freelist, and the corresponding pixel in the workspace display is plotted in black:
inline void myfree (object *obj) { car(obj) = NULL; cdr(obj) = Freelist; Freelist = obj; if (tstflag(DISPLAYFLAG)) PlotObject(((int)obj - (int)Workspace)>>3, 0); Freespace++; }
Objects are freed automatically during garbage collection; the programmer doesn't have to worry about freeing objects.
Graphics display routines
This display maps each byte in the display memory to a vertical column of eight pixels. Unfortunately the SSD1306 display driver chip doesn't support reading back of the contents of the display memory, so to provide the ability to change a single pixel, without affecting the others in the same column, a copy of the display memory is maintained in RAM; fortunately it's only 384 bytes (64x48/8).
The routines used to implement the workspace display are InitDisplay(), to initialise the OLED display, ClearDisplay() to clear the display, and PlotObject(), which plots a pixel corresponding to a Lisp object in the workspace.
Uploading the program
Whether you're using an Adafruit ItsyBitsy M0, or an ATSAMD21E on a breadboard as described in my article Minimal ATSAMD21 Computer, upload the Visible Lisp Computer as follows:
- If you haven't already got it, install the Adafruit SAMD Boards in the Boards Manager.
- Select the Adafruit ItsyBitsy M0 board.
- Upload the Visible Lisp Computer file to the board.
You should then be able to run uLisp, and enter commands at the Serial Monitor as described in Using uLisp.
This is based on the current version of uLisp, Version 2.8a, but for simplicity it only supports the Adafruit ItsyBitsy M0 Boards Manager option.
Here's the whole Visible Lisp Computer program: Visible Lisp Computer program.
Or get it from GitHub here: Visible Lisp Computer.
Further suggestions
The current project simply distinguishes between an allocated Lisp object (white) and a free object (black). Using a colour display you could use different colours to identify the different types of object: nil, symbol, integer, stream, character, float, string, or cons.
- ^ Lisp for microcontrollers on uLisp.
- ^ Adafruit ItsyBitsy M0 Express on Adafruit.
- ^ Adafruit ItsyBitsy M0 Express on Pimoroni.
- ^ White 0.66 inch OLED Display Module 64x48 on AliExpress.
blog comments powered by Disqus