ces

From Binary Lambda Calculus to Binary/BitForth

When I first read John Tromp's paper about the Binary Lambda Calculus (BLC) (sometime in 2014, I think) my knee jerk reaction was to think about what the equivalent of it in Forth might look like since I was already familiar with the SK combinators. I had jotted down some of my notes then, with a fairly obvious Forth equivalent and kept it aside, since it seemed fairly trivial.

I'm dusting it off now and putting it online here in case it is of some theoretical interest - just in case this isn't a well trodden path already.

Before I jump into the discussion about the Forth version, let me try to summarize Tromp's BLC first.

In BLC, lambda calculus terms are denoted using the regular 0 and 1 bits which we know and love where the 00 prefix denotes abstraction, a 01 prefix denotes application and a 1 prefix denotes the de Bruijn index (+1 since the Tromp indices start at 1, not 0).

Please see Tromp's talk / paper for additional details.

A really succinct context free grammar/CFG in Yacc/Bison that can parse BLC might look like this:

%%
L : '0' '0' L | '0' '1' L L | '1' N ;
N : '0' | '1' N ;

Note that this CFG will actually accept strings that are a superset of BLC [^1], but I just want to provide a high level gist/overview of what is needed to handle BLC for those who wish to be lazy and prefer to not read Tromp's paper (very readable, trust me, so go read it first). For the exact (and more correct but also more obfuscated) implementation, see Tromp's 2012 IOCCC entry or for a really tiny implementation that fits in the 512 byte x86 boot sector, see Justine Tunney's implementation.

The obvious Forth equivalent to this is to think of the two available values 0 and 1 as denoting either "literals" or "invocations" but we need some means of denoting the length of the literals themselves so that we are not tied to the word length of a specific CPU/architecture.

So, for the Forth implementation, I'll choose to continue to use BLC's run length encoded numbers as Forth "literals", i.e numbers that get pushed on the data stack. With this choice, the Forth VM implementation is also a 2-liner expressible in lex/flex and obviously it qualifies as a much simpler codebase since it is just a finite state machine(FSM)/regexp as compared to the pushdown automaton(PDA) needed for BLC's context free grammar(CFG):

%%
0
1+0

If we assume that the run length encoded literals are pushed onto the data stack (as is usually customary in Forth) we have a choice of what to do with the standalone 0's. An easy choice is to treat it as the opcode of a "parameterless one instruction set computer"/OISC, such as Richard Howe's subleq implementation of eforth, except that the subleq parameters will now need to be pulled from the data stack.

Since an OISC is pretty inefficient (both in terms of time and space), a more pragmatic choice that matches the capabilities of CPUs that are available nowadays might be to use a "cheat version" of the OISC that exploits all of the capabilities of the underlying hardware.

If we choose to use a "subroutine threaded"/STC Forth VM where both primitives and defined words end in a "ret" instruction (which returns control via the machine stack), we could use the '0' to denote a "call" which is usually implemented at "step 23" in my implementation of romforth.

This allows the entirety of the implementation of a Forth VM, that I'll call "bitforth", to be coded in romforth itself in just 7 lines of lex/flex:

%%
0       { printf("call\n"); }
1+0     { printf("%ld\n", strlen(yytext)-2); }
.       { /* error */ exit(1); }
%%
int yywrap() {}
int main() { yylex(); }

This implementation implies that the literals which are passed to the "call" are addresses containing code which implements the primitives/defined words. Since the addresses that are needed to invoke the underlying machine code will vary across different architectures/ports, we can attempt to make this more portable by using the standard trick from computer science of applying one level of indirection such that the literals are indices into a jumptable vector, the elements of which points to the addresses of the primitives and defined words of the underlying implementation.

The portable version of "bitforth" then just needs an additional "fetch"/@ operator before the "call" (thus trading off a bit of speed, for portability) as shown below:

%%
0       { printf("@ call\n"); }
1+0     { printf("%ld\n", strlen(yytext)-2); }
.       { /* error */ exit(1); }
%%
int yywrap() {}
int main() { yylex(); }

A "lower level" implementation using binary bits rather than the ascii byte representations of 0 and 1 as shown above will obviously be more compact in terms of the binary code. Alternatives to the run length encoding of numbers might also result in space savings (one option might be to use the "Not Quite Huffman"/nqh-zig port of romforth, for this). For now, coding this up as a layer over romforth and turning it into a working implementation is left as an exercise to the reader (i.e me, since I'm probably the only reader of this blog - unless Jared Krinke also happens to drop by).

In any case, I guess I'll eventually get around to doing it in my copious free time just to see if I can fit it into the x86 boot sector and get it smaller than Cesar Blum's sectorforth and Fuzzballcat's milliforth

Footnotes:

[1]: A wee bit longer (and stricter) CFG for BLC might be:

%%
T : L | A ;
L : '0' '0' E ;
A : '0' '1' E E ;
E : T | '1' N ;
N : '0' | '1' N ;
← Previous
○ Solarpunk Webring
Next →