Lambda the Ultimate

"it's a bit like choosing to judge "compiled OCaml" by ocamlc instead of ocamlopt." Except that ocamlc is only about four times slower than ocamlopt on my machine, while CLisp is something like ten times slower than SBCL. Roughly, of course.

http://esoteric.voxelperfect.net/wiki/HQ9_Plus

Many people seem to believe that 'succinct' is a synonym for 'compressed', regardless of the comprehensibility of the result, but that's not the case. The American Heritage Dictionary defines 'succinct' as "Characterized by clear, precise expression in few words". That's the sense in which the word is being used in this context.

Take LISP, replace lists with tuples, add names to members of tuples and you have Piccola forms. Am I missing something?

Lists and tuples are equal anyway, aren't they? they only have a small implementation difference: the function used to navigate from one member to the other is different.

I agree that it's still large in comparison to Forth (of which I am very fond), but I haven't seen much in the way of tiny implementations of languages that aren't either low-level (like Forth) or teaching toys (like implementations of Scheme in one page of code).

I'd love to see some examples of ultra-tiny Lisp interpreters. With Forth, I've gotten to the point where I could write the core in a few hundred bytes (not an exaggeration), but in the process I move a lot of concerns from the language implementer to the user. A tiny Lisp might be a better route to take.

Old thread, but I just took a look at the language spec and was also quite alarmed at the size of this "little" Lisp dialect. Good take away for me - a limited set of data types does not by itself a small language make.

Now, getting something like Lisp to live in 128K code space and 4K of RAM (AVR ATMega128) would be a truly minimalistic feat!

That's pretty doable. See e.g.:

1. BIT: A Very Compact Scheme System for Embedded Applications: "With this system, we demonstrate that it's clearly possible to run Scheme programs on a microcontroller with 64 KB of memory such as the Motorola 68HC11. Executables that include the whole library can be as little as 22 KB."

2. XS: Lisp on Lego MindStorms

3. LEGOScheme (project may be moribund)

4. Not Lisp, but the Transterpreter implements the occam-pi language, which is modeled on the CSP calculus.

The big problem with porting these tiny languages is that the AVR uses Harvard architecture (for the most part, the ones you mention seem to expect a von Neumann architecture). So, only 4K (in the case of the ATMega128) is available for the heap (minus call stacks, etc).

As bad as this sounds, the AVR stuff is pretty cheap and fast (and is fairly popular in embedded and gaining popularity in hobby robotics). The program space flash (128K on the ATMega128) is writable, so I've seen one implementation of forth "compile" words into the flash. Still, for languages requiring GC, 4K isn't a lot to work with. (Ironically, the processor runs up to 16 MIPS -- so doing GC time-wise probably wouldn't be too painful).

When I posted that comment, I was actually thinking about PICBIT: A Scheme System for the PIC Microcontroller, but I forgot that there were two papers and didn't realize that the latter one was more appropriate (I've worked with PIC and Ubicom/Scenix chips, but not the Motorola ones). The PICBIT paper talks about running with 2K of RAM.

I just scanned the paper, it looks very interesting. But, it seems to be describing running a byte code interpreter (VM) on the PIC. I am more interested in interactivity. What would you have to strip from a Lisp in order to have a very simple (but extensible) "interpreter" running in ROM (plus just 2-4K of RAM). *Potential Answer: Just about everything that makes Lisp interesting and useful ;-)

Sure, parsing and lexing would be expensive (but speed is not needed -- the language would be a "control" or "shell" language for the micro controller). What I want is a way to "script" a micro controller.

Why would you want an ordinary interpreter on a system that size? Would being able to take in new parsed sexps be sufficient?

Not to hijack this thread, but I stumbled here while looking around for interpreter ideas for a small project: I've got an AVR micro controller board controlling an iRobot Create. While tethered to a PC, I want a "casual" programmer to be able to try out a few things interactively (rather than install a full C toolchain).

For the actual autonomous action, scripts would be loaded onto an SD card connected to the AVR. Aside from the debugging capabilities I would have by putting the intepreter on the AVR, I like the idea of *not* relying on a PC environment.

However, you are right, I wouldn't want an "ordinary interpreter". I want an interpreter engine upon which to build a DSL specifically geared toward driving and reacting to the Create.

My first thought was to go with a very minimalistic Tcl like interpreter (but Tcl is geared toward strings, I have no use for strings).

Try building yourself a tiny cons+atoms lisp with a binary rep to get started with? If you don't mind keeping the initial prototypes PC-bound you should be able to do that in a day or so in an FPL without having planned it out beforehand, though it won't be the most efficient interpreter/VM ever.

We have a Scheme implementation for AVR-based Mica-series wireless sensor nodes. It's entirely interpreted, with primitives written in C, and pages to serial flash for virtual memory. Programs are stored as lists, and can in fact transmit themselves over the wireless network; if you don't need this feature, it should be possible to change the program representation to something more compact. The interpreter can run on a PC or a sensor node.
[actornet paper] [actornet software]

I dabbled in robots about five years ago and again last year, and I might do it again.

Five years ago, I had thoughts like yours, although AVR in-system-programming makes downloading so convenient that I was never seriously tempted to bring my 1980s-era Forth skillz up to date.

These days, though, you can get something like Gumstix, which (for $109 at the price I just surfed to, or $154 if you choose to hang your Bluetooth adapter there) gets you Linux and 64M RAM. There is a reasonably-complicated robot problem, popular here in Dallas, that is my mental benchmark for entry-level robot design (gathering up cans). I think today the natural place for AVRs in a flexible robot in that class would be to hang the AVRs from some sort of bus (TWI, e.g.) running to a Gumstix-class Linux+wireless board. Then unless you just enjoy the achievement of building your control hardware from $18 of parts (which I grant is pretty neat), running more than device-driver-level software on an AVR seems unnecessary. And I like working in Lisp, but I don't mind writing C or assembly for the kinds of 1-page-of-code device drivers that I envision on the AVRs. ("Device drivers" for midrange embedded microcontrollers, the kinds of devices that include big chunks of network stacks or polygon-shading libraries or filesystems or whatever, might be a different matter.)

When it comes to low power consumption, nothing beats a simple 8-bit without an OS. GC can be a power hog too (as well as just managing a malloc/free managed heap), so maybe that is why Forth always seems to find a home on the smallest processors.

The question I am really pondering is how small can a high level language get before it loses all its "character" and usefulness. Specifically, I am talking about target hosted interpreters (not PC hosted compilers).

This is not directly relevant to your post, but is interesting nevertheless and is in this vein. I've run across Adam Dunkels before (probably due to Protothreads which I'm fairly certain have been discussed on LtU before). His work is pretty cool.

'should be entertaining, especially to those of us who like to do things like implementing raytracers in 256 bytes of object code. Oh, and useful to; yes, it should be useful as well.

You may want to check out joy (a cousin of forth) with implementation in ANSI C.

|du -ksh joy
96K joy