Alternate compact implementation of Objects


hi David,

It was amazing to run such high-level language such as lisp in atmega328.
But sad to see only 320 objects in ram at a time.

I wonder if a variable width scheme for object representation could save some bytes.

Lets assume Symbol and Number objects will only appear inside a List object. Global variables can be put inside a list to achieve this. This assumption essentially reduces size of Symbol and Number objects to 2 bytes + some bits. I am not sure if a single variable could be part of multiple lists and invalidate this assumption.

The list object will still be 4 bytes. But car will represent the object directly if its a Symbol or Number, and a pointer if its another List. Some additional bit needs to be used to represent the type of object(Symbol, Number, List) car points to.

Does it make sense.
I do not know of the detailed implementation. So I may be missing some important details.

There are other alternate techniques that could save further. For example,

  1. Number object can be split into 2 type based on their size (one byte or two byte). Since one byte numbers are quite common in arduino, this could save a lot.
  2. Symbol object could represent the index into the symbol table and be one byte, instead of the radix40 function name it contains.
  3. List object can be better represented instead of car, cdr. For each additional entry in the list, it wastes/uses one cdr pointer. If one list item could contain multiple car pointers, it could be better.

Let me know. Thanks


Thanks for your suggestions.

Yes, memory is very limited on the ATmega328, but there are other platforms such as the ATmega2560 that give enough cells for some substantial applications.

My concern is that having different object sizes would make memory management much more complicated - especially garbage collection. However, I encourage you to try your ideas on a fork of uLisp.


I see. Thanks. Let me try this.
Yes. gc and mem management are tricky.

ATmega328 is the most common one used in arduino uno, nano, micro, etc.
Would be great if substantial apps are able to run in it.

Can a single variable be part of multiple lists at the same time, in your ulisp implementation.