Josh Stone, Blog

Josh’s projects and security nerdery

Lisp on an AVR?

I’m working on a new version of my USB HID testing rig. This one is a little more robust – i.e., not consisting of a bundle of Arduino shields and a breadboard. I’ve also started playing with more USB-related things, like using a raw HID to transfer data faster. As I’ve been experimenting, I’ve started thinking about the ultimate in usability. I really want to be able to script the behavior of the device dynamically, without having to reprogram it with new features.

So I worked a bit this evening on a very small Lisp interpreter for the AVR. So far, it’s not even running on the AVR – I’m simulating it on my Linux boxen. But the design of the interpreter is pointed at eventual implementation on AVR hardware.

There are, of course, a number of serious concessions to fit everything in a few kilobytes of RAM. There have been some other projects in this area, but even the most specifically targeted one I can find made too many concessions for my preferences. I want to be able to do things like define variables and iterate – maybe even user-definable functions, though RAM may not be sufficient for that. I envision the final product will allow me to write “builtin” functions in C for the AVR, and drive execution with interpreted kind-of-Lisp.

I will have no garbage collection – can’t afford it – but the interpreter will manage its own memory. By statically mapping a memory range for CONS cells and a symbol table, I can fix hard limits on how far a script can grow. But this will also allow me to ensure that everything fits on the AVR without having to implement malloc() and free().

A CONS cell is (currently) a triple, consisting of a type descriptor (one byte), the car (two bytes), and the cdr (one byte). No, I don’t plan on handling dotted franken-conses. All data types will map back to a cons, and I can calculate how many CONS cells take how much space, and keep it under control.

Here’s a simple “hello world” example in my current simulator. It’s a little more than hello world – it prints out a string (a sequence of chars) and the result of a little math – but still cool to experiment with how a realistic script might behave:

ULisp VM Test