Diatom: Baby Steps

Virtual Machine

The Diatom virtual machine (VM) is a very simple stack VM consisting of two stacks (return & data stack) and a flat memory space. Each element on the stack is a word wide (4 bytes) and can only be accessed by the provided stack-manipulating instructions (pop, dup, etc. - consult the /Instruction Set/ section for a comprehensive list). Memory can either be accessed byte- or word-wise.

Everything else mostly behaves as one would expect with the exception that arithmetic operations don't overflow but instead saturate, meaning that the value won't get past the maximum/minimum representable value. This definitely has some negative performance implications as it doesn't match the behaviour of most CPUs but it makes overflows easier to detect as one only needs to compare against the max/min values.

I also believe it makes way more sense for embedded applications that for example controll a plane's flight path to be stuck at not quite the right elevator deflection than overflowing and moving the elevator into the entirely wrong direction.

The stack depth and memory size is configurable in the current Go implementation.

Most Forths are implemented directly in assembly of the target CPU but implementing it against a VM makes porting to new environments pretty easy - e.g. getting it to run in the browser has been pretty straight forward.

Assembler

One downside of having a home-brew virtual machine is that we somehow have to generate the machine code for it as well. For this I have implemented a simple assembler that takes the VM assembly as input and emits the corresponding byte-code.

Apart from this basic translation task, the assembler also supports forward-referencing labels, some built-in macros tailored to implementing Forths and, of course, comments:

           ( Jump to the address of ":main". )
           const -1 cjmp @main

           ( Declare a variable "x" that is 4 bytes wide. )
           .var x 4 .end

           ( Define a new word "double" that executes "dup" and "+". )
           .codeword double dup + .end

           ( Define a new word "quadruple" that calls the word "double" twice. )
           ( "!<word>" is a macro that expands to "call _dict<word>". )
           .codeword quadruple !double !double .end

           ( Directly call the word "quadruple". )
           :main
           const 4 call _dictquadruple
           ( "_dict<word>" is a generated label that points to the
                 code section of "quadruple". )

Preamble

With the VM and the assembler in place, we already have everything to run a bare-bones Forth interpreter - except the actual code to bootstrap it...

The preamble.dasm file is exactly that. Clocking in at ~ 600 lines of assembly (including comments), it sets everything up to get the first Forth read-eval-print-loop (REPL) started.

It is based on the amazing jonesforth implementation and mainly takes care of setting up the Forth dictionary, implementing word lookups and compilation.

It is definitely larger in size than it needs to be but for now it gets the job done and I'll revisit it once the higher-level constructs are more established.

Standard Library

This is the first actual Diatom code and it's where stuff gets interesting. Right now it is pretty barren but this is the place where the basic language primitives are defined and where it will diverge from most Forth implementations quite a bit.

I'm still figuring this part out as I try to use Diatom in some everyday scripts and add what I deem necessary to complete the task.

Still, I think it is showing off one of Forths greatest advantages pretty well - it doesn't require much code to bootstrap itself. For example if-statements are not based on magic, built-in keywords, as in most languages, but are instead just a bunch of immediate words (a.k.a. macros in other languages). Same goes for implementing recursion (via recurse) and even ( <text> ) for comments!

With the standard lib loaded we have most of the basic building block available to write some code. For example a factorial implementation could look something like this:

         ( accumulator int -- result )
         : _factorial
           dup 0 = over 1 = |
           if return then
           swap over *
           swap 1-
           recurse
         ;

         ( int -- result )
         ( Calculates the factorial of the given number. )
         : factorial 1 swap _factorial drop ;

The stack shuffling with swap and over is probably not super nice but I think for a tail-recursive implementation it is not too bad and who knows, maybe the VM gets some addressable stack registers at one point. And that is the exact reason why I'm so excited about that project - there is no notion of how programming should work, everything is mallable and because it is so little code it will hopefully be easy to try out ideas and see if they suck or indeed make programming more enjoyable.