2013-05-20: Efficient Forth in 85 Lines of Racket

Forth is an interesting programming language in the concatenative family. It relies crucially on a data stack, rather than functions with their arguments and return values, as a means of communication.

Last week I wondered, "Could I implement a Forth-like system in Racket, with interoperablitly between the two, with macros?" This post presents the system.

-

1 Basics

In Racket, when you want to add two numbers, you pick the numbers and deliver them to a function that does the addition and returns the result:

In most languages, functions are restricted to returning a single value, like 3 in this example. However, in Racket we do not restrict the arity of continuations and allow you to return many values to the current continuation and create a context that expects many results:

It is awkward to think about n-ary continuations as the reason why multiple return values makes sense, so in Racket we have a function called values that abstracts multiple return:

Now, let’s rewrite these programs in Forth.

In Forth, rather than than picking the numbers and delivering them to the function, you put the numbers in a place the function can get to them. Similarly, rather than the function returning the answer to you, it places the answer in same shared location where the rest of your program can do something with them.

This shared location is the data stack and is the fundamental thing that Forth programs revolve around. A test case for a Forth program is a triple of (1) an input stack, (2) a program, and (3) a result stack.

In this example, simply by writing a number, like 2, we are placing it on the stack, and by simply writing a function like :+, we are jumping to it where it can do its work.

In some sense it more natural to write the second example, because we can more directly place multiple "answers" on the stack. On the other hand, it is more complicated because we have to explicitly copy information that we don’t want to destroy. In Forth, you can do this with functions like :dup that duplicate the thing on top of the stack and :over that duplicate the thing just underneath that.

The example looks like this:

2 Specification

We would like to enable this sort of programming in Racket, but with the additional feature that Racket code should be able to seamlessly call Forth code, provided we specify how many stack locations the Forth code touches. For example, we wouldn’t be able to call :f, because it is not obvious that it expects two things on the stack and adds one. But, we could specify that and then call it:

Similarly, we could give it a different specification that only shows the new value, but that would only affect the Racket interface:

3 Implementation: Data and Tests

The first thing we’ll do is decide to represent the stack as a normal Racket list. Next, we’ll represent Forth functions as special data structure that holds a function that accepts a stack and returns a stack:

For example, we could represent :dup as:

Although, we’ll make definition of things like this easier in a moment.

Next, we’ll write a macro to compose Forth words, calling them as we see them or pushing data when it is not a Forth word:

This macro might look a little meaty, but it just left-associates until it reaches the end, whereupon it returns the stack, and contains an initialization case for the first call.

This lets us write code like:

However, using this directly in tests is a little awkward, because the stack is stored oppositely from our intuitions:

Thus, it would be nice to have a macro that allows us to write the stack in the "natural order", with the top on the right:

There’s a natural way to write this:

However, I think it is ugly to have to reverse the before and after data during evaluation of the program. So I like this version:

4 Implementation: Definitions

Next, let’s revisit the definition of Forth functions. It is ugly to directly expose the forth-word data structure. Instead, we want to support the following notation:

And, in fact, one additional thing is that we don’t really want to force Forth functions to have names, so we’ll really implement forthda as the core:

In other words, define/forth is a trivial macro:

5 Implementation: Definition Macro

The forthda macro uses some advanced macrology and is the crown jewel of this implementation. Its basic structure is to expand each forthda into a stack transformer function, a new sub-struct of forth-word, and an instance of that sub-struct with the given stack transformer:

Even at this level of abstraction, there’s a few tricks. First, we use ~or to combine the three different kinds of definitions. Second, since the identifier used for the stack is only required in the #:lower case, we give it the default #'stack and use a different name for the combined case. Third, notice that the stack effect specification is sometimes required and sometimes optional. Finally, we rely on a definition of the stack-spec syntax class:

The next least complicated piece is the way we define the body of the stack transformer, in the non-lifted cases:

If we are lowering, then we just inject the body, otherwise we use the given stack argument and hand everything over to the forth macro to do the association and evaluation.

The body of a lifted function is more complicated, because we need to read a fixed number stack positions, call the Racket function, get back a fixed number of results, then put them back on the stack. We could use something like take or split-at for that, but it would be expensive, since we know exactly how many positions are needed at compile-time. In addition, we’d have to use apply and call-with-values to invoke the Racket function, which is also expensive.

Given that we know those two numbers, we can generate the appropriate number of temporary identifiers and then put them into two lists: one going forward and one going backward. This enables the following lifted body definition:

We read the input of the stack backwards, then call the function with the input forwards, then read the results forwards, and put them on the stack backwards. For the lifted definition of :+, this looks like:

We use the syntax classes stack-spec and stack-nat to generate these lists of identifiers in their attributes:

Beautiful, isn’t it?

Finally, we have to define the struct for this forthda. The key here is that when the function has a stack specification, then give the new struct the prop:procedure structure property, so Racket code will treat it as a function.

However, we have a dual problem to lifting: Racket will give us a finite number of arguments, which we need to put into a stack and then call the stack transformer, and read off a fixed number of answers.

And, of course, if there is no stack specification, we don’t give it the property, so Racket code can’t call it:

At this point, we’re done. The full version of the system is a tiny bit different and only has 85 lines of code.

I haven’t really used this for anything yet, but I think the macro is beautiful and the :delay/:apply example is really cool too.

If you’d like to run this code at home, you should put it in this order: