Author:
Source
A couple nights ago I wrote about a superfluous Scheme
implementation
and promised to move on from sheepishly justifying my egregious behavior in
my next note, and finally mention some results from this experiment.
Well, no: I am back on my bullshit. Tonight I write about a couple of
implementation details that discerning readers may find of interest:
value representation, the tail call issue, and the standard library.
what is a value?
As a Lisp, Scheme is one of the early “dynamically typed” languages.
These days when you say “type”, people immediately think propositions
as
types,
mechanized proof of program properties, and so on. But “type”
has another denotation which is all about values and almost not at all
about terms: one might say that
vector-ref has a type, but
it’s not part of a proof; it’s just that if you try to vector-ref a
pair instead of a vector, you get a run-time error. You can imagine
values as being associated with type tags: annotations that can be
inspected at run-time for, for example, the sort of error that
vector-ref will throw if you call it on a pair.
Scheme systems usually have a finite set of type tags: there are
fixnums, booleans, strings, pairs, symbols, and such, and they all have
their own tag. Even a Scheme system that provides facilities for
defining new disjoint types (define-record-type et al) will implement these via a secondary type tag layer: for example that all record
instances are have the same primary tag, and that you have to retrieve
their record type descriptor to discriminate instances of different
record types.
Anyway. In Whiffle there are immediate types and heap types. All values
have a low-bit tag which is zero for heap objects and nonzero for
immediates. For heap objects, the first word of the heap object has
tagging in the low byte as well. The 3-bit heap tag for pairs is chosen so that
pairs can just be two words, with no header
word.
There is another 3-bit heap tag for forwarded objects, which is used but the
GC when evacuating a value. Other objects put their heap tags in the low 8
bits of the first word.
Additionally there is a “busy” tag word value, used to prevent races
when evacuating from multiple threads.
Finally, for generational collection of objects that can be “large” —
the definition of large depends on the collector implementation, and is
not nicely documented, but is more than, like, 256 bytes — anyway these
objects might need to have space for a “remembered” bit in the object
themselves. This is not the case for pairs but is the case for, say,
vectors: even though they are prolly smol, they might not be, and they
need space for a remembered bit in the header.
tail calls
When I started Whiffle, I thought, let’s just compile each Scheme
function to a C function. Since all functions have the same type, clang and gcc will have
no problem turning any tail call into a proper tail call.
This intuition was right and wrong: at optimization level -O2, this
works great. We don’t even do any kind of loop recognition /
contification: loop iterations are tail calls and all is fine. (Not the
most optimal implementation technique, but the assumption is that for
our test cases, GC costs will dominate.)
However, when something goes wrong, I will need to debug the program to
see what’s up, and so you might think to compile at -O0 or -Og. In
that case, somehow gcc does not compile to tail calls. One time while
debugging a program I was flummoxed at a segfault during the call
instruction; turns out it was just stack overflow, and the call was
trying to write the return address into an unmapped page. For clang, I
could use the musttail
attribute;
perhaps I should, to allow myself to debug properly.
Not being able to debug at -O0 with gcc is annoying. I feel like if GNU were an actual thing, we would have had the equivalent of a musttail attribute 20 years ago already. But it’s not, and we still don’t.
stdlib
So Whiffle makes C, and that C uses some primitives defined as inline
functions.
Whiffle actually lexically embeds user Scheme
code
with a
prelude,
having exposed a set of
primitives
to that prelude and to user code. The assumption is that the compiler
will open-code all primitives, so that the conceit of providing a
primitive from the Guile compilation host to the Whiffle guest magically
works out, and that any reference to a free variable is an error. This
works well enough, and it’s similar to what we currently do in
Hoot
as well.
This is a quick and dirty strategy but it does let us grow the
language to something
worth using. I think I’ll come back to this local maximum later if I
manage to write about what Hoot does with modules.
coda
So, that’s Whiffle: the Guile compiler front-end for Scheme, applied to
an expression that prepends a user’s program with a prelude, in a
lexical context of a limited set of primitives, compiling to very simple
C, in which tail calls are just return f(...), relying on the C
compiler to inline and optimize and all that.
Perhaps next up: some results on using Whiffle to test Whippet. Until
then, good night!
