Technology

kragen/stoneknifeforth: a tiny self-hosted Forth implementation

This is StoneKnifeForth, a very simple language inspired by Forth. It
is not expected to be useful; instead, its purpose is to show how
simple a compiler can be. The compiler is a bit under two pages of
code when the comments are removed.

This package includes a “metacircular compiler” which is written in
StoneKnifeForth and compiles StoneKnifeForth to an x86 Linux ELF
executable.

There is also a StoneKnifeForth interpreter written in Python (tested
with Python 2.4). It seems to be about 100× slower than code emitted
by the compiler.

(All of the measurements below may be a bit out of date.)

On my 700MHz laptop, measuring wall-clock time:

  • compiling the compiler, using the compiler running in the interpreter,
    takes about 10 seconds;
  • compiling the compiler, using the compiler compiled with the compiler,
    takes about 0.1 seconds;
  • compiling a version of the compiler from which comments and extra
    whitespace have been “trimmed”, using the compiler compiled with the
    compiler, takes about 0.02 seconds.

So this is a programming language implementation that can recompile
itself from source twice per 24fps movie frame. The entire “trimmed”
source code is 1902 bytes, which is less than half the size of the
nearest comparable project that I’m aware of, otccelf, which is 4748
bytes.

As demonstrated by the interpreter written in Python, the programming
language itself is essentially machine-independent, with very few
x86 quirks:

  • items on the stack are 32 bits in size;
  • arithmetic is 32-bit;
  • stack items stored in memory not only take up 4 bytes, but they are
    little-endian.

(It would be fairly easy to make a tiny “compiler” if the source
language were, say, x86 machine code.)

The output executable is 4063 bytes, containing about 1400
instructions. valgrind reports that it takes 1,813,395 instructions
to compile itself. (So you would think that it could compile itself
in 2.6 ms. The long runtimes are a result of reading its input one
byte at at time.)

Why? To Know What I’m Doing

A year and a half ago, I wrote a metacircular Bicicleta-language
interpreter, and I said:

Alan Kay frequently expresses enthusiasm over the metacircular Lisp
interpreter in the Lisp 1.5 Programmer’s Manual. For example, in
http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=273&page=4
he writes:

Yes, that was the big revelation to me when I was in graduate
school — when I finally understood that the half page of code on
the bottom of page 13 of the Lisp 1.5 manual was Lisp in
itself. These were “Maxwell’s Equations of Software!” This is the
whole world of programming in a few lines that I can put my hand
over.

I realized that anytime I want to know what I’m doing, I can just
write down the kernel of this thing in a half page and it’s not
going to lose any power. In fact, it’s going to gain power by
being able to reenter itself much more readily than most systems
done the other way can possibly do.

But if you try to implement a Lisp interpreter in a low-level language
by translating that metacircular interpreter into it (as I did later
that year) you run into a problem. The metacircular interpreter
glosses over a large number of things that turn out to be nontrivial
to implement — indeed, about half of the code is devoted to things
outside of the scope of the metacircular interpreter. Here’s a list
of issues that the Lisp 1.5 metacircular interpreter neglects, some
semantic and some merely implementational:

  • memory management
  • argument evaluation order
  • laziness vs. strictness
  • other aspects of control flow
  • representation and comparison of atoms
  • representation of pairs
  • parsing
  • type checking and type testing (atom)
  • recursive function call and return
  • tail-calls
  • lexical vs. dynamic scoping

In John C. Reynolds’s paper, “Definitional Interpreters
Revisited”, Higher-Order and Symbolic Computation, 11, 355–361
(1998), he says:

In the fourth and third paragraphs before the end of Section 5, I
should have emphasized the fact that a metacircular interpreter is
not really a definition, since it is trivial when the defining
language is understood, and otherwise it is ambiguous. In
particular, Interpreters I and II say nothing about order of
application, while Interpreters I and III say little about
higher-order functions. Jim Morris put the matter more strongly:

The activity of defining features in terms of themselves is highly
suspect, especially when they are as subtle as functional
objects. It is a fad that should be debunked, in my opinion. A
real significance of [a self-defined] interpreter . . . is that it
displays a simple universal function for the language in
question.

On the other hand, I clearly remember that John McCarthy’s
definition of LISP [1DI], which is a definitional interpreter in the
style of II, was a great help when I first learned that language. But
it was not the sole support of my understanding.

(For what it’s worth, it may not even the case that self-defined
interpreters are necessarily Turing-complete; it might be possible to
write a non-Turing-complete metacircular interpreter for a
non-Turing-complete language, such as David Turner’s Total Functional
Programming systems.)

A metacircular compiler forces you to confront this extra complexity.
Moreover, metacircular compilers are self-sustaining in a way that
interpreters aren’t; once you have the compiler running, you are free
to add features to the language it supports, then take advantage of
those features in the compiler.

So this is a “stone knife” programming tool: bootstrapped out of
almost nothing as quickly as possible.

Why? To Develop a Compiler Incrementally

When I wrote Ur-Scheme, my thought was to see if I could figure out
how to develop a compiler incrementally, starting by building a small
working metacircular compiler in less than a day, and adding features
from there. I pretty much failed; it took me two and a half weeks to
get it to compile itself successfully.

Part of the problem is that a minimal subset of R5RS Scheme powerful
enough to write a compiler in — without making the compiler even
larger due to writing it in a low-level language — is still a
relatively large language. Ur-Scheme doesn’t have much arithmetic,
but it does have integers, dynamic typing, closures, characters,
strings, lists, recursion, booleans, variadic functions, let to
introduce local variables, character and string literals, a sort of
crude macro system, five different conditional forms (if, cond, case,
and, or), quotation, tail-call optimization, function argument count
verification, bounds checking, symbols, buffered input to keep it from
taking multiple seconds to compile itself, and a library of functions
for processing lists, strings, and characters. And each of those
things was added because it was necessary to get the compiler to be
able to compile itself. The end result was that the compiler is 90
kilobytes of source code, about 1600 lines if you leave out the
comments.

Now, maybe you can write 1600 lines of working Scheme in a day, but I
sure as hell can’t. It’s still not a very large compiler, as
compilers go, but it’s a lot bigger than otccelf. So I hypothesized
that maybe a simpler language, without a requirement for compatibility
with something else, would enable me to get a compiler bootstrapped
more easily.

So StoneKnifeForth was born. It’s inspired by Forth, so it inherits
most of Forth’s traditional simplifications:

  • no expressions;
  • no statements;
  • no types, dynamic or static;
  • no floating-point (although Ur-Scheme doesn’t have floating-point either);
  • no scoping, lexical or dynamic;
  • no dynamic memory allocation;

And it added a few of its own:

  • no names of more than one byte;
  • no user-defined IMMEDIATE words (the Forth equivalent of Lisp macros);
  • no interpretation state, so no compile-time evaluation at all;
  • no interactive REPL;
  • no do loops;
  • no else on if statements;
  • no recursion;
  • no access to the return stack;
  • no access to the filesystem, just stdin and stdout;
  • no multithreading.

Surprisingly, the language that results is still almost bearable to
write a compiler in, although it definitely has the flavor of an
assembler.

Unfortunately, I still totally failed to get it done in a day. It was
15 days from when I first started scribbling about it in my notebook
until it was able to compile itself successfully, although git only
shows active development happening on six of those days (including
some help from my friend Aristotle). So that’s an improvement, but
not as much of an improvement as I would like. At that point, it was
13k of source, 114 non-comment lines of code, which is definitely a
lot smaller than Ur-Scheme’s 90k and 1600 lines. (Although there are
another 181 lines of Python for the bootstrap interpreter.)

It’s possible to imagine writing and debugging 114 lines of code in a
day, or even 300 lines. It’s still maybe a bit optimistic to think I could
do that in a day, so maybe I need to find a way to increase
incrementality further.

My theory was that once I had a working compiler, I could add features
to the language incrementally and test them as I went. So far I
haven’t gotten to that part.

Why? Wirth envy

Michael Franz writes:

In order to find the optimal cost/benefit ratio, Wirth used a highly
intuitive metric, the origin of which is unknown to me but that may
very well be Wirth’s own invention. He used the compiler’s
self-compilation speed as a measure of the compiler’s
quality. Considering that Wirth’s compilers were written in the
languages they compiled, and that compilers are substantial and
non-trivial pieces of software in their own right, this introduced a
highly practical benchmark that directly contested a compiler’s
complexity against its performance. Under the self-compilation speed
benchmark, only those optimizations were allowed to be incorporated
into a compiler that accelerated it by so much that the intrinsic
cost of the new code addition was fully compensated.

Wirth is clearly one of the great apostles of simplicity in
programming, together with with Edsger Dijkstra and Chuck Moore. But
I doubt very much that the Oberon compiler could ever compile itself
in 2 million instructions, given the complexity of the Oberon
language.

R. Kent Dybvig used the same criterion; speaking of the 1985–1987
development of Chez Scheme, he writes:

At some point we actually instituted the following rule to keep a
lid on compilation overhead: if an optimization doesn’t make the
compiler itself enough faster to make up for the cost of doing the
optimization, the optimization is discarded. This ruled out several
optimizations we tried, including an early attempt at a source
optimizer.

Far-Fetched Ways This Code Could Actually be Useful

The obvious way that it could be useful is that you could read it and
learn things from it, then put them to use in actually useful
software. This section is about the far-fetched ways instead.

If you want to counter Ken Thompson’s “Trusting Trust” attack, you
would want to start with a minimal compiler on a minimal chip;
StoneKnifeForth might be a good approach.

Blind Alleys

Here are some things I thought about but didn’t do.

Making More Things Into Primitives

There are straightforward changes to reduce the executable size
further, but they would make the compiler more complicated, not
simpler. Some of the most-referenced routines should be open-coded,
which should also speed it up, as well as making them available to
other programs compiled with the same compiler. Here are the routines
that were called in more than 10 places some time ago:

 11 0x169  xchg
 13 0xc20  Lit
 22 0x190  -  (now replaced by +, which is only used in 25 places)
 25 0x15b  pop
 26 0x1bc  =
 35 0x13d  dup
 60 0x286  .

Of these, xchg, pop, -, =, and dup could all be open-coded
at zero or negative cost at the call sites, and then their definitions
and temporary variables could be removed.

I tried out open-coding xchg, pop, dup, and +. The executable
shrank by 346 bytes (from 4223 bytes to 3877 bytes, an 18% reduction;
it also executed 42% fewer instructions to compile itself, from
1,492,993 down to 870,863 on the “trimmed” version of itself), and the
source code stayed almost exactly the same size, at 119 non-comment
lines; the machine-code definitions were one line each. They look
like this:

dup 'd = [ pop 80 . ; ]               ( dup is `push %eax` )
dup 'p = [ pop 88 . ; ]               ( pop is `pop %eax` )
dup 'x = [ pop 135 . 4 . 36 . ; ]     ( xchg is xchg %eax, (%esp)
dup '+ = [ pop 3 . 4 . 36 . 89 . ; ]  ( `add [%esp], %eax; pop %ecx` )

However, I decided not to do this. The current compiler already
contains 58 bytes of machine code, and this would add another 9 bytes
to that. The high-level Forth definitions (: dup X ! ; and the
like) are, I think, easier to understand and verify the correctness
of; and they don’t depend on lower-level details like what
architecture we’re compiling for, or how we represent the stacks.
Additionally, it adds another step to the bootstrap process.

Putting the Operand Stack on %edi

Forth uses two stacks: one for procedure nesting (the “return stack”)
and one for parameter passing (the “data stack” or “operand stack”).
This arrangement is shared by other Forth-like languages such as
PostScript and HP calculator programs. Normally, in Forth, unlike in
these other languages, the “return stack” is directly accessible to
the user.

Right now, StoneKnifeForth stores these two stacks mostly in memory,
although it keeps the top item of the operand stack in %eax. The
registers %esp and %ebp point to the locations of the stacks in
memory; the one that’s currently being used is in %esp, and the
other one is in %ebp. So the compiler has to emit an xchg %esp, %ebp instruction whenever it switches between the two stacks. As a
result, when compiling itself, something like 30% of the instructions
it emits are xchg %esp, %ebp.

Inspired, I think, by colorForth, I considered just keeping the
operand stack pointer in %edi and using it directly from there,
rather than swapping it into %esp. The x86 has a stosd
instruction (GCC calls it stosl) which will write a 32-bit value in
%eax into memory at %edi and increment (or decrement) %edi by 4,
which is ideal for pushing values from %eax (as in Lit, to make
room for the new value). Popping values off the stack, though,
becomes somewhat hairier. The lodsd or lodsl instruction that
corresponds to stosl uses %esi instead of %edi, you have to set
“DF”, the direction flag, to get it to decrement instead of
incrementing, and like stosl, it accesses memory before updating
the index register, not after.

So, although we would eliminate a lot of redundant and ugly xchg
instructions in the output, as well as the Restack, u, U, and
%flush functions, a bunch of the relatively simple instruction
sequences currently emitted by the compiler would become hairier.
I think the changes are more or less as follows:

  • ! is currently pop (%eax); pop %eax, which is three bytes; this
    occurs 17 times in the output. The new code would be:
    sub $8, %edi
    mov 4(%edi), %ecx
    mov %ecx, (%eax)
    mov (%edi), %eax
    This is ten bytes. store, the byte version of !, is similar.
  • - is currently sub %eax, (%esp); pop %eax, which is four bytes;
    this occurs 23 times in the output. The new code would be seven
    bytes:
    sub $4, %edi
    sub %eax, (%edi)
    mov (%edi), %eax
    There’s something analogous in <, although it only occurs three
    times.
  • in JZ, jnz, and Getchar, there are occurrences of pop %eax,
    which is one byte (88). The new code would be five bytes:
    sub $4, %edi
    mov (%edi), %eax
    JZ occurs 38 times in the output, jnz occurs 5 times, and
    Getchar occurs once.
  • Msyscall would change a bit.

There are 193 occurrences of push %eax in the output code at the
moment, each of which is followed by a move-immediate into %eax.
These would just change to stosd, which is also one byte.

So this change would increase the amount of machine code in the
compiler source by 10 – 3 + 7 – 4 + 5 – 1 + 5 – 1 + 5 – 1 = 22 bytes,
which is a lot given that there’s only 58 bytes there now; I think
that would make the compiler harder to follow, although Restack does
too. It would also increase the size of the compiler output by (10 –
3) * 17 + (7 – 4) * 23 + (5 – 1) * (38 + 5 + 1) = 364 bytes, although
it would eliminate 430 xchg %esp, %ebp instructions, two bytes each,
for a total of 2 * 430 – 364 = 496 bytes less; and the resulting
program would gain (4 – 2) * 17 + (3 – 2) * 23 + (2 – 1) * (38 + 5 +

  1. = 101 instructions, then lose the 430 xchg instructions.

My initial thought was that it would be silly to space-optimize
popping at the expense of pushing; although they happen the same
number of times during the execution of the program, generally more
data is passed to callees than is returned to callers, so the number
of push sites is greater than the number of pop sites. (In this
program, it’s about a factor of 2, according to the above numbers.)
Also, consumers of values from the stack often want to do something
interesting with the top two values on the stack, not just discard the
top-of-stack: - subtracts, < compares, ! and store send it to
memory. Only JZ and jnz (and pop) just want to discard
top-of-stack — but to my surprise, they make up half of the pops.

However, I wasn’t thinking about the number of places in the compiler
where machine code would be added. What if I used %esi instead of
%edi, to get a single-byte single-instruction pop (in the form of
lodsl) instead of a single-byte push? This would make Lit (the
only thing that increases the depth of the operand stack) uglier, and
each of the 193 occurrencies of push %eax that result from the 193
calls to Lit in the compilation process would get four bytes bigger
(totaling 772 extra bytes) but the seven or so primitives that
decrease the depth of the operand stack would gain less extra
complexity. And we’d still lose the xchg %esp, %ebp crap, including
the code to avoid emitting them.

What’s Next

Maybe putting the operand stack on %esi.

Maybe factor some commonality out of the implementation of - and
<.

If we move the creation of the ELF header and Msyscall and /buf to
run-time instead of compile-time, we could eliminate the # and
byte compile-time directives, both from the compiler and the
interpreter; the output would be simpler; Msyscall and /buf
wouldn’t need two separate names and tricky code to poke them into the
output; the tricky code wouldn’t need a nine-line comment explaining
it; the characters ‘E’, ‘L’, and ‘F’ wouldn’t need to be magic
numbers.

Maybe factor out “0 1 -“!

Maybe pull the interpreter and compiler code into a literate document
that explains them.

Maybe building a compiler for a slightly bigger and better language on
top of this one. Maybe something like Lua, Scheme, or Smalltalk. A
first step toward that would be something that makes parsing a little
more convenient. Another step might be to establish some kind of
intermediate representation in the compiler, and perhaps some kind of
pattern-matching facility to make it easier to specify rewrites on the
intermediate representation (either for optimizations or for code
generation).

Certainly the system as it exists is not that convenient to program
in, the code is pretty hard to read, and when it fails, it is hard to
debug — especially in the compiler, which doesn’t have any way to emit
error messages. Garbage collection, arrays with bounds-checking,
finite maps (associative arrays), strong typing (any typing, really),
dynamic dispatch, some thing that saves you from incorrect stack
effects, metaprogramming, and so on, these would all help; an
interactive REPL would be a useful non-linguistic feature.

Copyright status

I (Kragen Javier Sitaker) wrote StoneKnifeForth in 2008 and published
it immediately in Argentina. I didn’t add an explicit copyright
license at the time, but here is one now:

To the extent possible under law, Kragen Javier Sitaker has waived
all copyright and related or neighboring rights to
StoneKnifeForth. This
work is published from: Argentina.

For more details, I’ve included the CC0 “legal code” in
LICENSE.md.

Related work

Andre Adrian’s 2008 BASICO: http://www.andreadrian.de/tbng/

  • is a small imperative programming language that is just powerful
    enough to compile itself (compiler bootstrapping).
  • has no GOTO, but has while-break-wend and multiple return
  • has C-like string handling.
  • is implemented in less then 1000 source code lines for the compiler.
  • produces real binary programs for x86 processors, not P-code or
    Byte-Code.
  • uses the C compiler toolchain (assembler, linker)
  • uses C library functions like printf(), getchar(), strcpy(),
    isdigit(), rand() for run-time support.

Actually it produces assembly, not executables.

Version 0.9 was released 15 Jul 2006. The 1000 source lines include a
recursive-descent parser and a hand-coded lexer.

Sample code:

// return 1 if ch is in s, 0 else
func in(ch: char, s: array char): int
var i: int
begin
  i = 0
  while s[i] # 0 do
    if ch = s[i] then
      return 1
    endif
    i = i + 1
  wend
  return 0
end

FIRST and THIRD, from the IOCCC entry.

Ian Piumarta’s COLA system.

Oberon.

Fabrice Bellard’s OTCC.

F-83.

eForth, especially the ITC eForth.

Jack Crenshaw’s Let’s Build a Compiler. This is a how-to book
that walks you through an incrementally-constructed compiler for a toy
language, written in Pascal, in about 340 pages of text. The text is
really easy to read, but it will still take at least three to ten
hours to read. It uses recursive-descent parsing, no intermediate
representation, and it emits 68000 assembly code.

Ikarus.

Ur-Scheme.

PyPy.

Bootstrapping a simple compiler from nothing:
Edmund GRIMLEY EVANS
2001
http://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html

Related Articles

Back to top button