Quarter: A Minimalist Forth

In the previous article we saw how we might bootstrap a Forth system using a minimalistic language where computation was directed by individual characters instead of blank-delimited words. Quarter is that language. This article gives examples of coding in Quarter, highlights how it is similar to Forth and how it differs.

Initially the spartan nature of Quarter might seem overly cryptic, but it is worth remembering that we don’t choose to be cryptic just for the sake of it. Our purpose is to allow a full Forth system to be bootstrapped in an Asm-independent way. We shall only write as much Quarter code as necessary to get us to a working Forth system. The current definition of Quarter has 36 primitives. These are just the primitives which are needed to write a Forth text interpreter. Not all primitives defined in a Forth kernel need be available to Quarter.

Quarter primitives are accessed via a flat dispatch table, indexed by an Ascii character. This allows a maximum of 128 primitives although it is probably wise to restrict ourselves to just the printable characters 33 (!) to 126 (~).

In practice, we use just uppercase and symbolic characters for the kernel primitives, leaving lowercase for use by user definitions. The names are chosen to be as suggestive as possible to their Forth counterparts although this is difficult when everything is named by just a single character.

We increase readability by defining space and newline as no-ops.

First example: square

In many introductions to Forth, an early motivating example is the user definition for the word which squares a number.

: square   dup * ;

Let’s do that in Quarter. As in Forth, : and ; are used to make a new definition. Given primitives to dup (D) the top stack element and multiply (*) together the top two values on the stack, perhaps the following is how we define square in Quarter?

:s D* ; ( nope )

:s does create a new entry in the Quarter dispatch table for a definition under construction and ; does terminate the code with whatever is required to return to the caller. But D* doesn’t work quite as we need.

D* does call dup then multiply, but these are executed right now as the definition is being created. What we want is to generate code which sequences the calls to D and * when a call is made to s. To do this in Quarter, we can write the following definition.

:s ^D?> ^*?> ;

This makes use of three important primitives: get, dispatch and compileComma

^ and > are the standard Forth words get and compile, exposed as Quarter primitives. ?, which is pronounced dispatch, is the Quarter level version of find. It performs lookup in the flat dispatch table of Quarter primitives.

Running the code quad ^D?> has three steps:

The code quad ^*?> is executed similarly, but for the multiplication primitive.

Constructing definitions in Quarter is like being in Forth but being forced to switch to interpreter-mode using [ immediately following the definition start. If we did this in Forth, the definition of square would look like this:

: square [ word dup find compile, word * find compile, ] ;

Bootstrapping

Much of the tedium of writing these get-X-dispatch-compileComma code quads can be alleviated if we bundle up the three stages into their own definition, which we choose to name ~.

:~ ^^?> ^??> ^>?> ;

Now our squaring example can be simplied as:

:s ~D~* ;

The definition of ~ makes writing Quarter code much more palatable. And we can make further definitions for all the tools we need to write more complicated functions.

:' ^^?> ^??> ;
:# 'L ~L, ~> ~, ;
:i ~L ^B?, ~>~H~@ 0# ~, ;
:t ~D~H~@~W~-~W~! ;

The above four definitions give us tick, literal, if and then making use of various Quarter primitives:

With some Forth experience, it is easy to guess what these primitives do. For details see here. How exactly they are being composed takes a little more study.

Comments

We can define support for comments in Quarter, just as we did for Forth in the first article in this series using the following line of squiggles:

H@^(`0`E :( ~^ ^)# ~= i ~X t '(#~J ;

This defines comment support both in Quarter, via the definition :(, but it also constructs an entry in the Forth dictionary with H@^(`0`E so comments will be available in Forth once we enter the bootstrap interpreter being defined.

Second example: type

Now we have the basic tools for programming available, let’s see a real example.

:p ~D~C~D i ~.~1~+ jp t ~P~P ;

This code defines p to print a string. This would be called type in Forth. It prints each character of a string until the null terminator is reached. Quarter Forth uses null-terminated strings, as opposed to the counted strings of a more traditional Forth system. The loop structure is setup by the tail-recursive call jp. The definition uses primitives dup (D), char-fetch (C), emit (.), drop (P), one (1) and plus (+).

For comparison, here is the equivalent definition for type in Forth.

: type ( a -- )
dup c@ dup if emit 1 + recurse
then drop drop ;

This highlights the second main difference between Forth and Quarter:

When we write Forth definitions, we are in compile-mode by default, returning to interpret-mode only when explicitly directed by [. To have words like if and then execute whilst compiling, they are marked as special immediate words.

In contrast, Quarter executes everything right now whilst compiling. It’s just that a common thing we do right now is to compile code to be run in the future by using ~.

Third example: interpreter

As a final example, let’s see a Forth interpreter written in Quarter.

h ^]`0` h^[`0`E :[# ~w~W~O~q i ~P~X t ~D~f~D i ~W~P~V j[ t ~P~p ^?#~.~M~A j[;

I’ll be honest. This isn’t easy to parse. But now we know the basics, we can see the structure emerge. We see runs of regular code, i.e. ~D~f~D separated by control flow constructs i and t. Branches either fall through to the next branch, or end with exit (~X) or recurse (~j[)

This interpreter does not handle numeric literals, but only words which are looked up in the Forth dictionary. The core functionality for reading a blank-delimited word and dictionary lookup is defined in sub-definitions for w and f. But we can see the overall structure of the interpreter here.

Let’s break into 7 lines to allow reference:

h ^]`0`
h ^[`0`E :[
# ~w~W~O~q
i ~P~X
t ~D~f~D
i ~W~P~V j[
t ~P~p ^?#~.~M~A j[;

You might compare this Quarter definition of a Forth interpreter with the Forth definition given in the previous article.

Answers

To summarize, let’s answer the questions posed at the end of the previous article.

What primitives are provided by Quarter? The short answer is whatever we need, and no more, to implement a Forth Interpreter and compiler. Currently, there are 36 primitives which can be seen listed here in my x86 implementation. And also here in my Haskell port/emulation. In the next article, we shall see why there is a Haskell version of Quarter Forth.

How does Quarter differ from conventional Forth? The most obvious difference is that programs are composed from single character primitives instead of words. This might be a significant difficulty if we planned to write very much Quarter code, but since we shall only write what we need to bootstrap Forth, it is not such a big obstacle. The second main difference is that we don’t have the modal state of Forth. There is no compile-mode. We are always in interpret-mode. This makes our code more verbose when compiling definitions or to give a positive spin: the code is more explicit.

What does Quarter code look like? We’ve looked at a few examples in this article. For more, see the full implementation of the bootstrap interpreter and compiler for Quarter Forth. It runs to just 32 lines, including comments and whitespace, and currently makes up 100% of all Quarter Code in existence!

Next time

In a future article I’d like to explore how we might type-check Forth code.

But in the next article we explore some different implementations of Quarter Forth.