🚀 go-pugleaf

A few years ago I worked on such a project with Randy Sargent.  We
wrote a Logo compiler for the 6811 microprocessor.

Well, it was sort of a Logo compiler.  It supported procedure
definition, recursion, integer arithmetic, global and local variables,
and Logo control structures like IF, ELSE, REPEAT (we added FOREVER,
an infinite REPEAT).  It wasn't a full Logo, though: it didn't support
words and lists and string processing. 

It was pretty neat though.  Rather than compiling straight into 6811
native code, we used a "pseudo-code" approach:  the compiler generated
pseudo-opcodes for a stack based language.  A short (700 byte) program
running on the 6811 interpreted these pseudo-op codes to implement the
stack language.

The stack language concept is cool because a given program will be
much smaller when compiled into stack language rather than native
processor code.  Consider the following expression compiled in both
representations:

	3 + 4

The typical compiler will push those values on the stack (first
loading them into registers) and then call the routine to perform the
addition, something like this:

	6811 opcode	bytes

	LDD	#3	3
	PSHB		1
	PSHA		1
	LDD	#4	3
	PSHB		1
	PSHA		1
	JSR	add	3

	total bytes	13

In our stack compiler, things like "push a number onto the stack" and
"add the two numbers on the stack" were primitive opcodes, so the same
expression would compile into the following:

	pseudocode	bytes

	Push 3		3
	Push 4		3
	Add		1

	total bytes	7

For our application, this space savings was key: the final code would
have to run on a microcontroller system that had only 2K (that's right
2048 bytes) of program memory (the memory was internal to the CPU
chip; it was a one-chip microcontroller system).  The first 700
bytes or so were taken up by the stack code interpreter program,
leaving about 1400 bytes for the "Logo program."  That turned out to
be enough to do some basic fun stuff.

The system was a little clunky to use:  first you would create your
Logo program using a text editor; then you would run the compiler on
that file.  The compiler would produce an "object" file of sorts.
Then you would run a user interaction program and load the object
file.  This program would download your compiled code to the
controller board (over a serial line), and then allow limited
interaction with the program:  you could call a Logo function that you
had defined, passing it any arguments, and a return value would be
printed back on your terminal.

My favorite (non-robotic) demo was to compute the fibonacci of 20,
using the doubly-recursive fibonacci definition.  The little CPU would
chug for 30 seconds or so before coming up with the (correct) answer.
If you tried to get a fib any higher than that you'd overflow the
stack (there were only 256 bytes of RAM) and the thing would crash.
It was pretty amusing.

If anyone is interested in the source code I'm sure I could dig it up
and send it to you (I'd have to get Randy's permission first).  We
used the Unix tools LEX (a lexical analyzer) and YACC (Yet Another
Compiler Compiler) to build the parts of the program that tokenized
and processed the Logo input program.  The rest is written in portable
C; at various points in time, we had the system running on Unix,
MS-DOS, and Macintosh platforms.  (The code is undocumented---this
letter has more documentation than ever's been written for it.)

If anyone is interested, let me know.

	- Fred Martin