rwmj 13 days 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?
vardump 12 days ago [-]
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.

pjc50 13 days ago [-]
They've used the classic technique of the bottom bit of the car pointer. The code is easy enough to read:

    #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
rwmj 12 days ago [-]
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.
Iwan-Zotow 13 days ago [-]
If you have some space to spare, consider femtolisp:
eggy 13 days ago [-]
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!

jballanc 12 days ago [-]
Or, if you have an installation of Julia, just run `julia --lisp` to get the same thing ;-)
nanomonkey 12 days ago [-]
I'm curious how uLisp compares to esp-lisp ( on the esp32, which appears to be the most performant of the microcontrollers listed.
jackhack 12 days ago [-]
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.

bibyte 12 days ago [-]
I have always wanted something like this. I can't really build this myself because I have no hardware skills.
russh 12 days ago [-]
If you have the desire, there has never been a better time to learn!
microspino 13 days ago [-]
Enjoyed the introduction to uLisp a lot. The author is also a very good teacher and writer.
dang 12 days ago [-]
tomcam 13 days ago [-]
Requires a princely 32K, or less than their logo.
bitwize 12 days ago [-]
Drat, and here I was hoping to get it running on an unexpanded 16K Speccy...