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:
General
LispMe was developed with GCC 2.7.2.2, PilRC 1.7 and prc-tools-0.5.0 on
a PC running OS/2 Warp and tested with CoPilot.
All tools have been ported to OS/2 by
Thomas Johler.
Altogether LispMe consists of about 10000 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.
I finally found a way to create executables >32k code with GCC without
having to use shared libraries! This involves some tricks with
object code and runtime library order. If you're interested in these
topics, feel free to email me.
LispMe is based on the SECD virtual machine described in
Peter Henderson
Functional Programming - Application and Implementation
Prentice Hall International
ISBN 0-13-331579-7
The name stems from the 4 main registers this machine operates on:
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
executed
|
D | dump | a stack the other registers are pushed on
when a new function is called
|
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);
The virtual machine currently has 137 different instructions, most of
them dealing with LispMe's primitive procedures. The main extensions
to Henderson's machine are
- 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
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 this 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.
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
with disasm.
Macros are expanded by calling the VM with the expansion procedure
and the original source expression as argument.
Parsing is divided into 2 steps:
- The scanner groups characters into tokens by using a
finite automaton consisting of 22 states. Most of the states deal
with real and complex numbers and escape sequences in strings.
- The parser is recursive-descent
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.
LispMe uses 3 blocks of memory, where each block size is adjustable in
the Preferences dialog.
- The atom store: All identifier names are entered here by the
reader. The names are simply stored one after another separated by
'\0' bytes. In the memory dump database this block is
record 0.
- The floating point store: All floating point numbers are stored
here (8 bytes each). Unused cells are linked into a free list.
In the memory dump database this block is record 1.
- The heap store: Each heap cell is 32 bit and consists of two
pointers (car and cdr), 16 bit each. The cells do not
carry type tags, instead the pointers do according to this table:
sddd dddd dddd ddd1
| 15 bit signed integer (-16384 .. 16383)
|
0ddd dddd dddd dd00
| 15 bit signed offset into heap
(no scale neccessary, negative offsets never used)
|
0ddd dddd dddd d010
| 12 bit index into atom table (char*)
(shift right 3 bits)
|
0ddd dddd dddd d110
| 12 bit index into double table (double*)
(unmask 3 low bits, no scale necessary)
|
1000 00aa aaaa aa10
| 8 bit ASCII char
|
1111 00dd dddd dd10
| vector in heap, upper 8 bit of UID, cdr field
of this cells contains lower 16 bit (untagged!)
|
1111 10dd dddd dd10
| string in heap, upper 8 bit of UID, cdr field
of this cells contains lower 16 bit (untagged!)
|
1111 11xx xxxx xx00
| reserved for special values
|
1111 00xx xxxx xx00
| special value tags in car of list
|
Some special values are 0xfff8 for empty list,
0xfff4 for #f,
0xfff0 for #t,
0xf0fc for a closure tag or
0xf0e4 for a complex tag (There are some more).
All pointers into the heap are relative pointers (offsets) to the
beginning of the heap. 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.
In the memory dump database the heap is record 2.
- Each vector and string occupies a single DB record starting with record number
6 (5 for LispMe10). A vector or string is identified by its
unique ID in a cons cell in the heap. To distinguish vectors from
strings, a string record has always its 'secret' bit set.
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
collection are:
- 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
All in all, a typical garbage collection of 16k heap takes about
0.2 seconds.