• rwmj 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?

  • vardump 5 months 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 5 months ago

    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
  • rwmj 5 months 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 5 months ago

    If you have some space to spare, consider femtolisp: https://github.com/JeffBezanson/femtolisp

  • eggy 5 months 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 5 months ago

    Or, if you have an installation of Julia, just run `julia --lisp` to get the same thing ;-)

  • nanomonkey 5 months ago

    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.

  • jackhack 5 months ago

    Related: A Common LISP for embedded systems. Prof. Rod Brooks (MIT) https://www.researchgate.net/publication/2949173_L_--_A_Comm...

    developed for building robots using the Moto68332 with 32K of memory, but will work down to about 10K.

  • bibyte 5 months ago

    I have always wanted something like this. I can't really build this myself because I have no hardware skills.

  • russh 5 months ago

    If you have the desire, there has never been a better time to learn!

  • microspino 5 months ago

    Enjoyed the introduction to uLisp a lot. The author is also a very good teacher and writer.

  • tomcam 5 months ago

    Requires a princely 32K, or less than their logo.

  • bitwize 5 months ago

    Drat, and here I was hoping to get it running on an unexpanded 16K Speccy...