Lisp conquers the (small) world!

November 3, 2005

Why embedded?
err...usually either because you are getting paid to or because you want to program some device that won't let you develop on a real machine. Or because you are in a bizarre situation that requires extreme levels of size optimization.

Why Lisp?
If you are coding in an extremely resource-constrained environment, you have 4 main choices:

This will almost certainly work on whatever platform you are coding for, but it is very low level, without actually being capable of direct register manipulation. On the other hand, toolchain support is peerless, and the performance is excellent compared to most languages.

This is guaranteed to work anywhere, although you might need to spend some time learning the instruction set. You will be able to do everything, which is good, because you will have to.

Incredibly enough, there have evidently been forth interpreters coded to fit in ~40 bytes on disk. This boggles the mind(at least, it does for me). Forth is a pretty good language for bottom-up coding, so it is conceivable that the program resulting from writing a forth in assembler and embedding the interpreter for that in the rest of the application would be smaller than the application would be written in strait asm. This is only hearsay, as I have never seen a 40-odd byte forth, but it is a very small language, after all.

There are many, many resources on doing embedded programming in either C or asm, and some on forth. I would not presume to offer judgements on which resources are worthwhile, not having done much with any of them. However, I have done a fair bit with the last, and often best, (that is, if you are not overly attached to your memory leaks) choice.

There are a multitude of lisps, differing widely in just about every characteristic. At the low end, a few K is enough disk space. The following is my experience with a number of very small lisp/scheme implementations.

SIOD (Scheme In One (Day|Defun)):
SIOD is a very nice, largish scheme (approx R4Rs), with superb FFI and a very good code-base. SIOD for Windows is available, as is SBDSIOD, which gives SIOD databese support through sdb. SIOD FFI is worth a second mention-you can pass a lambda to windows as a callback function, and all of the argument marshalling, stack management, etc., is handled by a rather inscrutable bit of assembler code. This is pretty amazing for such a small implementation-something like 200K compiled for windows.

This is the pick of the litter, for my money. It is smallish ( I have compiled it down to 19 K on windows), has excellent performance, a superb codebase, and can readily be extented. Heow Eide-Goodman ported it to the Sharp Zaurus, and reported that the work was trivial. It is coded in pure ANSI C, so it should compile anywhere, and it embeds nicely - (it is embedded in the GIMP, last I heard).

Hedgehog is fairly large among the lisps on this page-it weighed in above 100K, and I could not find any FFI. Also, it appears to be Unix-only. It is a lisp-2, so those of you who cannot rest at night without being able to write (list list) have an option. Interestingly, almost all of the very small lisps are in a single namespace. I do not know why this is-easier to implement, perhaps?

Lisps I have not used, but marvel at in the dark of night: Lisp in....javascript?
Lisp in...10K?
Lisp in...awk?
lisp in...Lego?
dream-another small scheme
(part of)scheme in ocaml
scheme in forth
small lisp in C
another scheme in javascript
small lisp on linux.
dream, a scheme in asm for linux x86 and ppc
lisp in the IOCCC
Lisp in robots Lisp in one letter These describe L, a CL subset for robotics.
scheme on PIC microcontrollers