uLisp: Lisp for microcontrollers

    #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

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.

Also there is this board, Lisp Badge that runs ulisp and has a keyboard and screen on the pcb board!

http://www.technoblogy.com/show?2AEE