Lambda the Ultimate

With the silly season in full swing, I thought it would be nice to throw the forums open for members to indulge a bit of light whimsy. For a long time, my favourite programming conceits have been embedded language interpreters. These tools evoke in me the mystery and wonder of bootstrapping, and the seemingly magical ability to overcome the limitations of a computer's hardware instruction set with new facilities implemented in software. And from these devices rise many wonderful things: domain specific languages, the often elegant implementation of these tools on severly constrained platforms, and the pragmatic efficiency tradeoffs required to do so.

Let's hear of your favourites. To kick things off, here are two of mine.

1. The Apollo Guidance Computer

This extract is from 'E-2502 AGC4 Basic Training Manual' (http://www.ibiblio.org/apollo/NARA-SW/E-2052.pdf)

The Apollo Guidance Computer was designed with the idea that its weight, size and power supply were costly items. Mission requirements warrant a hardware compromise of a word length with a minimum of 15 bits and an instruction repertoire of 33 instructions with which to work. The result, therefore, is a small, fairly simple machine with limited abilities. While the AGC hardware provided for manipulation of single- and double-precision quantities, frequent need arose to handle multi-precision quantities, triginomic operations, vector and matrix operations, and extensive scalar operations. Thus, to fulfill the system requirements planned for the lunar missions within the constraints of hardware limitations, it is necessary to employ software to expand the capabilities of the AGC.

[Some discussion on subroutine calling overhead elided.]

Thus to solve the memory wastage problem caused by frequent use of the calling sequences, it is expedient to create an entirely special mnemonic language in which each mnemonic corresponds to a subroutine. Since, in many cases, the new mnemonic instructions require no addresses, we design a packed instruction format which stores two seven-bit operation codes in one word of memory and any required address constants in the two following words.

2. The Apple II SWEET16

Steve Wozniak writes about the development of the Apple II in BYTE magazine, May 1977 (http://oldcomputers.net/byteappleII.html)

The Story of Sweet Sixteen

While writing Apple BASIC, I ran into the problem of manipulating the 16 bit pointer data and its arithmetic in an 8 bit machine.

My solution to this problem of handling 16 bit data, notably pointers, with an 8 bit microprocessor was to implement a non-existent 16 bit processor in software, interpreter fashion, which I refer to as SWEET16.

SWEET16 contains sixteen internal 16 bit registers, actually the first 32 bytes in main memory, labelled RO through R15. RO is defined as the accumulator, Rl5 as the program counter, and R14 as a status register. R13 stores the result of all COMPARE operations for branch testing. The user accesses SWEETl6 with a subroutine call to hexadecimal address F689. Bytes stored after the subroutine call are thereafter interpreted and executed by SWEET16. One of SWEET16's commands returns the user back to 6502 mode, even restoring the original register contents.

Implemented in only 300 bytes of code, SWEET16 has a very simple instruction set tailored to operations such as memory moves and stack manipulation. Most op codes are only one byte long, but since she runs approximately ten times slower than equivalent 6502 code, SWEET16 should be employed only when code is at a premium or execution speed is not. As an example of her usefulness, I have estimated that about l K bytes could be weeded out of my 5 K byte Apple-II BASIC interpreter with no observable performance degradation by selectively applying SWEET16.

I'd love to hear of other gems, particularly those that are embedded to expand platform capabilities, and not so much standalone virtual machines or interpreters.