97 points by tosh 5 months ago
I'm impressed that they seem to have managed to get a mark-sweep GC to work with only 2K of RAM. Or does it use a special non-GC mode with small amounts of RAM?
Lots of computers did garbage collection in the seventies and eighties.
Commodore VIC-20 with 4kB of RAM is not far off the mark, for example, but AFAIK the BASIC could handle strings and DIM declared 1D/2D arrays.
Ok, it was not mark and sweep, but the difference isn't much.
Linearly scanning heap is fast when you have just 2 kB of RAM.
When the heap is compacted, next object can be allocated after the last address. If there's not enough room after last address, just scan until a large enough deleted area is found. If even that fails just compact the heap.
To save memory, each the first byte of allocation should be sufficient metadata for most allocations.
For example, values 1-126 could be reserved for object length. The highest bit can used for MARK bit. 127 could mean object is longer than 127 bytes.
0 could mean deleted, next byte contains original length, so that it's possible to scan forward past deleted objects.
So scan through all heap objects, setting MARK to 0. Mark the reachable objects. Scan again, delete all unmarked objects.
Of course updating all the references to objects that moved due to compacting will be slow, but it's just 2 kB one needs to scan. If that is too inefficient, one can always maintain a handle mapping instead of direct references at cost of some RAM.
They've used the classic technique of the bottom bit of the car pointer. The code is easy enough to read: https://github.com/technoblogy/ulisp/blob/master/ulisp.ino
#define mark(x) (car(x) = (object *)(((uintptr_t)(car(x))) | MARKBIT))
#define unmark(x) (car(x) = (object *)(((uintptr_t)(car(x))) & ~MARKBIT))
#define marked(x) ((((uintptr_t)(car(x))) & MARKBIT) != 0)
#define MARKBIT 1
Marking isn't the problem. It's fitting a minor + major heap into 2K. In my (small, but not very optimized) ML implementation a useful minor heap is probably min 64K.
If you have some space to spare, consider femtolisp: https://github.com/JeffBezanson/femtolisp
What does femtolisp have compared to ulisp?
Also there is this board, Lisp Badge that runs ulisp and has a keyboard and screen on the pcb board!
Or, if you have an installation of Julia, just run `julia --lisp` to get the same thing ;-)
I'm curious how uLisp compares to esp-lisp (https://github.com/yesco/esp-lisp) on the esp32, which appears to be the most performant of the microcontrollers listed.
Related: A Common LISP for embedded systems. Prof. Rod Brooks (MIT)
developed for building robots using the Moto68332 with 32K of memory, but will work down to about 10K.
I have always wanted something like this. I can't really build this myself because I have no hardware skills.
If you have the desire, there has never been a better time to learn!
Enjoyed the introduction to uLisp a lot. The author is also a very good teacher and writer.
From 2016: https://news.ycombinator.com/item?id=11777662
Requires a princely 32K, or less than their logo.
Drat, and here I was hoping to get it running on an unexpanded 16K Speccy...
There's always http://blog.funcall.org/lisp/2015/10/30/zx-spectrum-lisp/