Back to index
Under the hood
This chapter describes some internals of LispMe. You don't need this to
work with LispMe, but some people asked me about the implementation, so
here you are:
The latest version 3.2 of LispMe was developed with GCC 2.95.2-kgpd,
prc-tools 2.0, PilRC v2.5b3, and the PalmOS 4.0 SDK
on a PC running Windows XP and tested with Poser 3.2 and the PalmOS5
Altogether LispMe consists of about 26000 lines of highly compact C code.
All error handling is done using Pilot's ErrCatch and
ErrThrow macros/functions and not a single function from the
C library has been used.
The trick I found to create executables >32k code with GCC is fortunately
no more necessary prc-tools 2.0, since multi-segment applications are
If you're interested in these
topics, have a look here.
The implementation techniques of LispMe (V3.0) have been presented at the
Scheme workshop of the
PLI 2001 conference
in Florence in September 2001.
A detailed article is available as
DVI (80 kB) or as
compressed PostScript (99 kB).
LispMe is based on the SECD virtual machine described in
The name stems from the 4 main registers this machine operates on:
Functional Programming - Application and Implementation
Prentice Hall International
In fact, all registers hold pointers to list structures in the heap,
so for example going to the next machine instruction is accomplished
by an assignment of the form C = cdr(C);
|S||stack||used to hold intermediate values while
evaluating an expression
|E||environment||used to hold the current environment
|C||control||the machine-language program being
|D||dump||a stack the other registers are pushed on
when a new function is called
The virtual machine currently has 93 different instructions (much
less than prior versions, since many builtin procedures have been
re-implemented as native C calls).
The main extensions
to Henderson's machine are
The runtime environment is represented as a list of frames, where
each frame is a list of values. Variables are always accessed by
lexical adresses (a pair indicating the frame and the offset of the
variable). This is exactly the form you see when tapping the
names button. In fact, the first
step in each evaluation is assigning the value list to the E register.
In contrast to Henderson's approach, the compiler is not bootstrapped,
it's implemented in C like the rest of LispMe. The reasons for that are
compilation speed and saving heap memory for user programs.
- error checking
- including function arity in closures
- closures with variable number of arguments
- support for tail-recursion
- continuation support
- support for sequencing (begin)
- real, complex, char, string, vector and port support
- compile quasiquote templates to SECD code
- support for macros and eval
- call native functions
A LispMe expression is compiled by traversing its tree structure and
consing up a list of machine instructions backwards to avoid using
append. There's a simple peephole optimizer mainly used for
removing unnecessary stack operations and for propagating returns
through conditionals to provide proper tail recursion elimination.
There's also a compile time environment (represented as a list of lists,
mirroring the structure of the runtime environment) to determine lexical
adresses for all variables. You can view the SECD code of a closure
The compiler is extensible by registering keyword/C-function
Macros are expanded by calling the VM with the expansion procedure
and the original source expression as argument.
Parsing is divided into 2 steps:
Scanning and formatting floating point was particularly nasty, as the
Pilot ROM routines FlpFToA and FlpAToF are unusable
(limited precision, limited exponent range, no error support), so all
this stuff had to be written from scratch.
Each LispMe session is kept in a separate database bearing the same
name as the session. All LispMe session databases use creator ID
fbLM so that the total memory used by them is displayed correctly
in the memory application.
- The scanner groups characters into tokens by using a
finite automaton consisting of 28 states. Most of the states deal
with real and complex numbers and escape sequences in strings.
- The parser is recursive-descent
In each session database, at least 7 records are used:
Starting with version 1.7, LispMe mo more uses the dynamic heap for
its memory, instead it works directly on DB blocks, gaining
write access via MemSemaphoreReserve. This is a much discussed
technique, as accessing memory out of its bounds can overwrite other
databases and even require a hard reset. On the other hand, LispMe has
been out for some months now and several hundred people have tested it and
I never got a report of an "invalid pointer access". Furthermore, there's
no way in LispMe to create an invalid pointer by will or accident (like
in other Scheme implementations, too). All
pointers are created in the memory subsystem which almost certainly
is bugfree. So I finally decided to use this technique to make a
bigger heap available on all Pilots.
LispMe uses mark/scan garbage collector for heap cells and floating
point cells. The reasons for preferring mark/scan to copying garbage
- Record 0: Global vars, root pointers
- Record 1: The atom store; all identifier names are entered here by the
reader. The names are simply stored one after another separated by
- Record 2: The floating point store; all floating point numbers are stored
here (8 bytes each). Unused cells are linked into a free list.
- Record 3: car pointers of the heap; 32 bit each
- Record 4: cdr pointers of the heap; 32 bit each
In contrast to versions before 3.2, the heap has been split in two
blocks of the same size. The car and the cdr pointer
at the same relative address form a "virtual" heap cell.
The cells do not
carry type tags, instead the pointers do according to this table:
Primitives (symbols and the associated values) are stored
in a two-dimensional (ragged) table consisting of upto
64 frames of upto 32 entries each. Currently, 21 frames are used,
extension modules can use the rest. The very first frame
(SPECIAL_MODULE) contains special values, like
empty list, #f, #t, or
a closure tag.
|sddd dddd dddd ddd0
||16 bit signed offset from virtual heap base,
which is 32k above actual heap begin (no scale neccessary)
|sddd dddd dddd dd01
||14 bit signed integer (-8192 .. 8191)
|dddd dddd dddd 0011
||unsigned 12 bit index into atom table
(shift right 4 bits), 4kb atom space
|dddd dddd dddd 0111
||unsigned 12 bit index into double table
(shift right 1 bit and unmask 3 low bits), 4096 reals
|ffff ffss sss0 1011
||Primitive symbol, 64 frames of 32 symbols
|ffff ffss sss1 1011
||Primitive value, 64 frames of 32 values
|0000 0000 0000 1111
||vector header in heap, upper 8 bit unused, cdr field
of this cell contains 16 bit record index (untagged!)
|0000 0000 0001 1111
||string header in heap, similar to vector
|0000 0000 001s 1111
||bigint header in heap, similar to vector, s is sign
|0000 tttt 0100 1111
||Foreign data, 4 type bits, cdr field of this cell
points to 32 bit value (untagged!)
|cccc cccc 1000 1111
||8 bit ANSI character
All pointers into the heap are relative pointers (offsets) to
two virtual heap base pointers lying 32k behind the actual
beginning of the heap (one for the cars and one for the
cdrs). This allows relocation of the heap by the
operating system. Additionally,
this saves memory (16 bit relative pointers vs. 32 bit absolute
pointers) and maps nicely to the 68000 adressing mode
adress register indirect with index and offset, which
uses signed offsets .
- Record 5: The input field
- Record 6: The output field
- Each vector and string occupies a single DB record starting
with record number 6. Starting in version 3.1,
a vector or string is identified by its record index stored
(instead of the unique ID in earlier versions)
in a cons cell in the heap. Each record has a PTR back to its
header cell as its first element to allow garbage
collection care for changing record indices when deleting a record.
All in all, a typical garbage collection of 16k heap takes about
- Memory usage has top priority on the Pilot. Wasting half of the
memory with copying GC isn't affordable.
- All heap cells have the same size, so fragmentation can't happen
- Heap compaction (provided by copying GC) doesn't affect performance,
as there's no virtual memory or cache on the Pilot.
- The disadvantage that mark/scan GC has to touch every memory
cell in the heap is ignorable with heap sizes possible on the Pilot
Foreign types can register garbage collection hooks for finalization
and marking other referenced cells.
Strings, vectors, and bigints are garbage collected without having
to move their actual contents. Instead, DmAttachRecord() is
used to swap the memoryblock/record number association and unused
records are moved to the end of the workspace database where they
can be deleted without having to shift intermediate records.