[The first in a series of posts on the evolution of TransForth]
I’ve been enthralled by retro computing recently and have been filling my bookshelf [yes, actual bound paper books] with (nearly) extinct programming language topics: Lisp, Fortran, Smalltalk, APL, Forth, … About this time last year I did a blog series implementing Lisp in F#; a lot of fun and got a lot of hits! (hint: post to reddit!) This time I want to evolve a Forth, also in F# and following the same incremental transformation process - calling it “TransForth”. It should be a great, enlightening journey!
I find it amazing that from the very beginning of programming history with Lisp and Fortran, we established the classic dichotomy – Fortran thinly abstracting up from the hardware out of practicality and Lisp beautifully compiling down from a mathematical basis. I believe that Forth is unique in the spectrum of languages. It is extremely minimal and yet has an amazing breadth, spanning all the way from direct hardware access dipping below even Fortran to layering abstractions, building up to the level of Lisp – complete with a language-oriented mindset similar to Lisp macros!
Forth, like Lisp, is not really a language as much as it is an idea with many dialects. To make it even more confusing, Forth is also a development environment (editor, compiler, assembler) and, in many cases, even stands alone as an operating system (device drivers, file system, …) and is a software design philosophy.
Hopefully I can convey some of the amazing ideas behind Forth as we go. Implementing Forth is right up there with SICP for mind opening learning. We’ll start very simple, building an interpreter with abstracted components. This way we can see how the pieces work together. Slowly, we’ll take away the abstractions and move closer to the metal. In the end, we should have a very tiny implementation with most everything implemented in Forth itself. The kernel can then easily be ported to new hardware.
Forth is ultimately about getting intimate with the hardware. I plan to target a virtual machine at first. Eventually, we’ll move to some real machines. I’m thinking of targeting the Arduino (ATmega chips) and/or the 6809E (on which I cut my assembler teeth). If we still have the energy, we may continue exploring cross compilers and other threading methods such as token threading or (crazy-compact) Huffman threading. As a grand finale we may even implement an SECD machine with garbage collector and all and build a Lisp… in Forth! I’m not kidding. By the way, the reverse has already been done.
In this first cut, we’ll build little more than an RPN calculator. Of course, if this were the sole goal we could do it in much less code (remember the TinyRPN post?). If you want to brush up on your RPN skilz, try playing with my HP-35 microcode emulator. We’re just laying the foundation here. Don’t worry, we’ll get to the good stuff soon enough.
Programming in Forth is done through a classic REPL. Development is very interactive with code/compile/execute rolled into one. At the prompt you can enter sequences of named operations (called words) and literal values, all separated by spaces. Each word has a side effect of manipulating a stack of values or emitting output to the console. For example:
7 42 SWAP / .
This will push 7 and 42 literals to the stack, then SWAP will reverse them and / will divide them (popping off two numbers and pushing back the result), and finally . (dot is a word) will print the top-most stack value – 6 ok is emitted to the console.
In the next post we’ll extend the system to allow user-defined words, but this form of : FOO BLAH BLAH BLAH ; is the syntax for defining a new word (FOO) in terms of other words (BLAH). The basic idea is a bottoms-up construction of a program, each new word building on previous definitions and raising the level of abstraction. At any given point, you may think of the currently defined set of words as primitives in the language. Programs can end up reading almost like English. Here is an example taken from Leo Brodie’s wonderful book, Starting Forth:
: FILL FAUCETS OPEN TILL-FULL FAUCETS CLOSE ;
This defines a new word, FILL, in terms of words expected to have already been defined in the system (FAUCETS, TILL-FULL, OPEN, CLOSE). These words may really be primitives in the system (nativly talking to device drivers) or are more likely themselves defined in terms of lower level words. Eventually, at the lowest level, some words will talk to the hardware (actually gathering sensor data and triggering faucet actuators in this case). Further definitions can build on FILL:
: RINSE FILL AGITATE DRAIN ; : WASHER WASH SPIN RINSE SPIN ;
Finally, a user simply enters WASHER at the interactive prompt and kicks off the process. A program then is the last word defined (MAIN, GO, RUN, or whatever you want to call it) or perhaps a set of words working together constitutes a program with the normal Forth interactive acting as the user interface.
Forth is a stack machine. Words can be thought of as functions from Stack -> Stack. Some words have other side effects, but to a large extent they are functions taking parameters and returning values. Unlike most languages in which parameters are named and passed explicitly, in Forth parameters and return values are threaded through a chain of functions implicitly by way of the stack. This leads to a very succinct programming style in which parameters are not named, but are passed along through a composition of words.
Even before getting into Forth, I have enjoyed transforming programs in F# and Haskell to a so-called “point free” style (some call it “pointless” J). For example, in the Babbage Difference Engine post some time back, the original code read:
let engine =
let uncurry f (a, b) = f a b
let flip f a b = f b a
let next diffs =
|> Seq.map (uncurry (+))
|> (flip Seq.append) 
Seq.unfold (fun diffs -> Some(Seq.head diffs, next diffs))
But, as a friend of mine (Randy Kern) pointed out, why pass in diffs only to pipe it through a series of functions. Why not just define next as a composition of the functions directly (using >> instead of |>):
let next =
>> Seq.map (uncurry (+))
>> (flip Seq.append) 
Seq.unfold (fun d -> Some(Seq.head d, next d))
The next function still expects a parameter, but the name (diffs) is no longer mentioned. Stack based concatenative languages apply this tacit programming style exclusively. If you don’t believe its a viable way to program, you should check out Factor.
Often parameters need to be rearranged, duplicated or dropped in order to glue certain words together. For this purpose there are stack manipulation words: SWAP, DUP, DROP, etc.
Okay finally, here is our first bit of implementation in the TransForth project:
let mutable stack = 
let push value = stack <- value :: stack
let underflow () = failwith "Stack empty"
let pop () = match stack with h :: t -> stack <- t; h | _ -> underflow ()
A simple stack (of integers) represented as a cons list with push/pop operations. You’ll notice that we’re using mutable and a side-effecting imperative style. This will make the transition to running on bare hardware easier. Forth is inherently very imperative. I don’t like this style in general (as I’ve gone off about before - Oh, The Humanity!) but we’re warming up to and embracing the “Forth way.” It looks a little ugly in F# but I wouldn’t call it non-idiomatic F# code given that F# is a multi-paradigm language. But in general, what we’re doing in this series is not very pure. I think you’ll find as we move along though, that imperative programming in a structured way has a certain charm of its own.
The initial set of language primitives are stored in a dictionary (Map), as are user-defined words once we add this feature in the next post. The name is a simple string and can be anything you like (sans whitespace). The code is a simple unit -> unit function (or Action if you’re used to the .NET types). I said earlier that words were Stack -> Stack functions which is true but, like everything in Forth, is accomplished by side effect.
let mutable dict = Map.empty
let define name code = dict <- Map.add name code dict
let find name = Map.tryFind name dict
To kick things off let’s add some primitives for doing basic math, manipulating the stack and interacting with the system:
let dyadic fn () = pop () |> fn (pop ()) |> push // applied in infix order
dyadic (+) |> define "+"
dyadic (-) |> define "-"
dyadic (*) |> define "*"
dyadic (/) |> define "/"
dyadic (%) |> define "MOD"
To get in the mood of speaking like Yoda, I’m already habitualy writing F# code with lots of pipes and forward composition. The above each pop two arguments from the stack, apply a function and push the result back to the stack. Notice that they apply in infix order. That is, 42 6 / means 42 divided by 6.
define "DEPTH" (fun () -> stack.Length |> push)
define "CLEAR" (fun () -> stack <- )
define "PICK" (fun () -> pop () |> List.nth stack |> push)
define "ROLL" (fun () ->
let i = ref (pop ())
match List.partition (fun _ -> i := !i - 1; !i >= 0) stack with
| (h, v :: t) -> stack <- v :: h @ t | _ -> underflow ())
let stk fn () = stack <- fn stack
define "DROP" (stk (function _ :: t -> t | _ -> underflow ()))
define "DUP" (stk (function x :: t -> x :: x :: t | _ -> underflow ()))
define "SWAP" (stk (function x :: y :: t -> y :: x :: t | _ -> underflow ()))
define "OVER" (stk (function (x :: y :: _ as t) -> y :: t | _ -> underflow ()))
define "ROT" (stk (function x::y::z::t -> z::x::y::t | _ -> underflow ()))
These stack-related primitives allow querying the depth (DEPTH) and clearing (CLEAR) the stack as well as dropping (DROP), duplicating (DUP) and generally permuting the values on the stack (SWAP, OVER, ROT). These all are common words in any Forth system. A standard means of documenting the stack effects is to make a ( before – after ) diagram:
DROP ( a -- ) DUP ( a – a a ) SWAP ( a b – b a ) OVER ( a b – a b a ) ROT ( a b c – b c a )
PICK and ROLL are more general. They take a number (n) from the stack and pull from or bury to the nth item. We’ll look more at these later.
let out = new StringBuilder()
let print v = out.Append(v.ToString()).Append(' ') |> ignore
define "." (pop >> print)
define ".S" (fun () -> stack |> List.rev |> List.iter print)
define "WORDS" (fun () -> List.iter (fun w -> print w.Name) dict)
These primitives are for the programmer to inspect the contents of the stack and the dictionary. I think you can figure out what they do. Notice that . is destructive (actually popping the stack) while .S merely prints. If you’re used to RPN calculators you might think of stacks growing from top to bottom but the Forth interactive visualizes them as growing from left to right (hence the List.rev).
On to the so-called outer interpreter - we’ll discover what an “inner interpreter” is once we begin the migration to machine code. First, the tokenizer:
let mutable source = Seq.empty
let token () =
let next = Seq.skipWhile Char.IsWhiteSpace source // trim whitespace
let word = next |> Seq.takeWhile (not << Char.IsWhiteSpace)
source <- Seq.skip (Seq.length word) next // leave remaining
new String(Array.ofSeq word) // as proper string
It can’t get much simpler than that! Tokens are just whitespace separated words. Notice however, that each call to token lops off a single token at a time. If you’re used to a lexer/parser pipeline in which the parser has visibility only at the token-level, then get used to something new! In a future post we will see that in Forth, words themselves may take over parsing and consume characters (not tokens) from the source stream. This makes tokenizing, parsing and compiling a very intertwined process. As just a sneak peek at one example, the dot-quote word (.") parses off a string terminated by a closing double quote. For example: ." this is free text with spaces, not Forth words" Forth doesn’t need to know up front about such parsing anomalies. The ." word (which is user-defined) itself does.
let rep input =
out.Clear() |> ignore
source <- input
while not (Seq.isEmpty source) do
let word = token ()
if word.Length > 0 then
match find word with
| Some(code) -> code () // execute found definition
| None -> // literal?
let number, value = Int32.TryParse word
if number then push value else word + "?" |> failwith
Given a piece of source (generally a line of input from the console), we walk word-by-word, attempting a dictionary lookup. If found, the word is executed. If it’s not found then we attempt to parse it as a literal number and push that to the stack. If it’s not in the dictionary and it’s not a number then it is an error.
let rec repl output =
printf "%s\n>" output
Console.ReadLine() |> rep
out.ToString() |> sprintf "%sok" |> repl
with ex -> ex.Message |> repl repl "Welcome to TransForth"
This closes the loop, taking input from the user and running it through the system. Rinse and repeat.
As we transform TransForth we want to be sure not to break things.
let case source expected =
stack <- 
let result = out.ToString()
if result <> expected then
printfn "FAILURE: %s (Expected: %s, Actual: %s)" source expected result
case "123 ." "123 " // literals
case "1 2 3 .S" "1 2 3 " // stack
case "5 6 + ." "11 " // addition
case "5 6 7 + + ." "18 " // addition
case "10 2 - ." "8 " // subtraction
case "10 2 - 3 - ." "5 " // subtraction
case "10 2 3 - - ." "11 " // subtraction
case "2 3 * ." "6 " // multiplication
case "2 3 4 * * ." "24 " // multiplication
case "5 2 / ." "2 " // division
case "5 2 MOD ." "1 " // modulo
case "1 2 3 DEPTH ." "3 " // stack depth
case "1 2 3 CLEAR .S" "" // clear stack
case "1 2 3 4 3 PICK ." "1 " // pick
case "1 2 3 4 3 ROLL .S" "2 3 4 1 " // roll
case "1 2 3 DROP .S" "1 2 " // drop
case "1 2 3 DUP .S" "1 2 3 3 " // duplicate
case "1 2 3 SWAP .S" "1 3 2 " // swap
case "1 2 3 OVER .S" "1 2 3 2 " // over
case "1 2 3 ROT .S" "2 3 1 " // left rotate