Forth-ISH

The Repo on GitHub

With a little help from my friends, I begin to reach some clarity on what this idea is and is not, and on why Forth has a ‘compiler’. HYPOTENUSE! Gesundheit!

H/T to Bill Wake and Serg Koren for comments that are putting some shape into my understanding of what I’m up to here.

Serg mentioned “DSL”, Domain-Specific Language, which is certainly what I’m up to here: providing a little language for describing Bot behavior to the World server. The idea is to be able to completely describe what a Bot should do in the world, using this DSL, so that instead of programming a client for the server. you could “just” code up a Bot’s behavior in the DSL and give that text to the World, which would embed and run your Bot. Serg also pointed out that a good start for the DSL is the verbs for the atomic functions of the bot. For us, those are step, take, drop, and turn.

Bill has done a subset of Forth earlier this year and shared some observations about threaded code and the structure of the lexicon for Forth. And he pointed to Threaded Interpreted Languages as a possibly useful reference. He also suggested that the Composite Pattern might be useful in representing the lexicon. I can almost see that, but I think I have to be a bit further in before I can assess whether that will apply here or not.

These little conversations have helped me clarify my thinking on this little diversion. Let me try to express that thinking.

My [alleged] Thinking

What is it?

I got this idea while looking for something diverting to do with the Robot World program. None of the things before me, the ones that need to be done, or most of the things that might be done, had much appeal to me. I recalled that Bryan had had some thoughts about giving the Bots’ behavior to the World server and letting them run there. That is, you wouldn’t write a Python or Java program and connect to the server, you could just give the server your bot behavior program and it would run it. I thought at the time that that would be difficult, and said so. My reasoning was that the language of the Bots needs to be pretty complete, able to compute most anything that we could do with our Python or Java program. We’d have to have an interpreter for whatever language we allowed. I had rather hoped that Bryan would take that as a challenge and dig into solving it. But no.

Then, I don’t know why, the notion of Forth came to mind, perhaps something GeePaw Hill said. Forth can compute anything that needs computing, it is simple beyond belief, it is nominally easy to implement, and it is commonly used for control applications like making your Bots explore the world. Well, was commonly used.

So what I’m trying to build here is not a full-fledged ANSI Standard Forth. I am building a Bot control language following the style of Forth. It will be a subset of Forth, enhanced with whatever Bot-specific primitive operations we may need, surely including our standard step, turn, take, drop, and quite possibly a few more.

What isn’t it?

We will not, therefore, be requiring ourselves to implement all the strange character, unsigned, zero-terminated string oddities that made Forth¹ what it was back around 1970. We’ll be building a stack-based postfix language which is based on the concepts of Forth. Because we’re building it in Python, we’ll allow our botForth to put any kind of number or string on the stack. We might actually allow other complex objects on the stack: there’s no reason why we cannot. We’ll have a subset of the Forth bottom-level primitive words, sufficient to the bot-driving purposes of our little language.

Why?

It is appropriate to mention, in fairness, that my purpose in doing this work is to entertain myself and offer opportunities to write about software development as it is done by me. I do not say “as it should be done”. Quite often I do not do the things that I believe I “should” do, or do things that on my wiser days I would advise myself against. I do what I do, observe what happens, and adjust what I do, perpetually. My adjustments are aimed at improving my results, which I measure mostly by the creation of code that looks like I believe code should look, and by the absence of unpleasant surprises like the game not working for two days even though all the tests are running.

I know there are a few readers out there. Once in a while one of them will ask me a question or make a comment. If all a reader gets is entertainment, that’s fine, although I hope that once in a while a reader might get an idea for something to do — or never to do — from seeing what I do and reading what I write.

Insight

Based in part on my reading, and in part of my conversation with Bill, I’ve come to an understanding of why Forth was implemented with its compile mode.

What we have now is a small interpreter. It reads a list of words. Some of the words are primitives that manipulate a stack. They typically take one or two numbers off the stack, do a little computation, and put the answer back. Some of them manipulate the stack. DUP puts a copy of the stack top on the stack, converting ‘b a’ to ‘b a a’. And so on.

Other words are currently implemented as lists of words:

    elif word == 'DUP':
        x1 = stack.pop()
        stack.append(x1); stack.append(x1)
    elif word == 'NEGATE':
        s = '0 SWAP -'
        interpret(s)
    elif word == 'SQUARE':
        interpret('DUP *')

Above we see a key difference between the primitives and the um non-primitives². When we hit a primitive, we execute the code for it. When we hit a non-primitive, we interpret the string that defines that word. Now, it’s true that I think of NEGATE as doing something, but in fact it does nothing at all. It’s the ‘0’ and ‘SWAP’ and ‘-‘ that do something. All the time we spend in our interpret method is overhead: it’s just trekking through the string looking for words that do something, and otherwise just fetching words, digging down into them, and so on.

In Forth, the only words that actually do anything are the primitives. All the others are just there to choreograph the order in which the primitives do whatever they do. Let’s gin up a test that will better demonstrate what I mean. We’ll add a square root primitive and then implement a word that calculates the hypotenuse of a right triangle.

    def test_sqrt(self):
        clear()
        s = '4 SQRT'
        interpret(s)
        assert stack.pop() == 2

    def test_hyp(self):
        clear()
        s = '3 4 HYPOTENUSE'
        interpret(s)
        assert stack.pop() == 5

I implemented SQRT:

    elif word == 'SQRT':
        stack.append(math.sqrt(stack.pop()))

Now we need HYPOTENUSE, which I am already wishing I had spelled HYP. Given A and B, the sides of a right triangle, the hypotenuse why the HELL did we call it that is the square root of the sum of the squares of A and B. In our little Forth:

    elif word == 'HYPOTENUSE':
        s = 'SQUARE SWAP SQUARE + SQRT'
        interpret(s)

And the tests are green. Square root of the sum of the squares.

OK, I had a point here, which was to demonstrate how we spend a lot of time fetching words and then fetching more words and only rarely doing anything.

If we print ‘interpret’ and the string whenever we call interpret, and ‘do’ and the word when we actually execute an operation that manipulates the stack, we get this:

interpret 3 4 HYPOTENUSE
 do 3
 do 4
interpret SQUARE SWAP SQUARE + SQRT
interpret DUP *
 do DUP
 do *
 do SWAP
interpret DUP *
 do DUP
 do *
 do +
 do SQRT

Compare that to what we would get if we were to do hypotenuse longhand:

    def test_hyp_longhand(self):
        clear()
        s = '3 4 DUP * SWAP DUP * + SQRT'
        interpret(s)
        assert stack.pop() == 5

We get this trace:

interpret 3 4 DUP * SWAP DUP * + SQRT
 do 3
 do 4
 do DUP
 do *
 do SWAP
 do DUP
 do *
 do +
 do SQRT

Same sequence of operations, but much less time interpreting strings and words. And there’s more, because our simple interpreter is going through comparing all the words every time they’re encountered:

def interpret_word(word):
    if is_number(word):
        stack.append(int(word))
    elif word == '+':
        plus()
    elif word == '-':
        # ( x1 x2 == x1 - x2
        x2, x1 = stack.pop(), stack.pop()
        stack.append(x1 - x2)
    elif word == '*':
        x2, x1 = stack.pop(), stack.pop()
        stack.append(x1 * x2)
    elif word == 'SQRT':
        stack.append(math.sqrt(stack.pop()))
    elif word == 'SWAP':
        # ( x1 x2 -- x2 x1 )
        x2, x1 = stack.pop(), stack.pop()
        stack.append(x2); stack.append(x1)
    elif word == 'DUP':
        x1 = stack.pop()
        stack.append(x1); stack.append(x1)
    elif word == 'NEGATE':
        s = '0 SWAP -'
        interpret(s)
    elif word == 'SQUARE':
        interpret('DUP *')
    elif word == 'HYPOTENUSE':
        s = 'SQUARE SWAP SQUARE + SQRT'
        interpret(s)
    else:
        raise ValueError(f'Invalid word {word}')

So, if you had a slow computer, and believe me, in the 60’s and 70’s we had slow computers, you didn’t want to spend a lot of time looking up words in a table or a series of else statements. So a language like Forth would have each defined word in a table. A table entry would include the string for the word, followed by the definition of the word. If the word was a primitive, the actual code would be there. If the word was not a primitive, then it is a list of words, and what would be in the word’s table would not be those words, but the addresses of those words’ table entries.

And not just the top address, no sir, the address would be inside the entry, pointing to a patch of code that would push the current location onto the return stack and set the point of interest to whatever sequence of addresses was in the new word. Execution would just oops suddenly be running down that word’s definition except that it would either immediately be the address of a primitive which we’d then jump into and out of, or another defined secondary word, in which case push the return and branch there.

Sound confusing? It kind of is. Sound error-prone? Oh yes, because all you have to do is miss one push or pop or have someone leave something on the return stack yes your Forth code was allowed to use the return stack as temp storage please be sure to clean up before you go or get one address wrong and suddenly you’re executing no one knows what this is possibly a string arrgh³.

But when it works, it flies and it is a marvel to behold. Truly lovely, threaded code. And something most of us will never do again, and in fact in most modern languages we cannot do at all because for some reason we’re not allowed to pick up an integer and branch to it.

We can, however, get close, and I think we’ll probably do something similar as we experiment with Forth and work our way to a Forth-style DSL for our robots.

Winging it a bit here.

Suppose we were to keep our Forth words in a table, an old style core memory table where everything is packed up tight and all we really have is the address or index of a machine word in the table. (We would almost never do such a thing today.) Because our Forth words are of variable length, with variable length names and variable length definitions, we might store them a bit like a linked list, but allocated all at once, so that the last list item points to the previous, to the previous, etc:

100 0 (link (end))
101 D (name)
102 U
103 P
104 LOAD TOP
105 PUSH
106 EXIT

107 100 (link)
108 * (name)
109 POP
110 POP
111 * (multiply operation)
112 PUSH
113 EXIT

114 107 (link)
115 S (name)
116 Q
117 call
118 104 (address of code for DUP)
119 call
120 109 (address of code for *)
121 EXIT

Well, weak sauce picture there, but maybe you can begin to see how one could fill in a table with code, and pointers to code, so that we’d have the ability to have a compile “phase” where we’d define a word, not in terms of other words, but with direct links to the “code” that defined that word, so that we’d link link link do something return and replace a table lookup with a direct link.

I would have to either draw a much more detailed picture, or program something that did the job. We’ll work toward a solution, keeping this threading in mind, but also mindful that we have far more flexible structures and operations available to us in Python.

We could certainly build a table, even a variable length one. But would we? I suppose we might. We could have a list of lists, perhaps. Or a dictionary. The dictionary lookup of a word by name would be O(1), but still probably 10X slower than a direct indexed lookup into a list of lists.

I’m not ready to write a test for that this morning. I think what we’ll do, guessing here, is first move our existing big long if statement into a dictionary, then see how it looks. We’re dealing with a 3gHZ cheap laptop here, not a 10 or 100 microsecond cycle time. We’re dealing with 16 gig of memory, not 8192 bytes or 512 or whatever you had with your little Forth controller.⁴ It could be fun, to drop down to assembler, but it wouldn’t be all that useful.

Anyway I am really not sure quite how far we’ll push toward threaded code. Our mission is to come up with a fast-enough little language for our bots. We’re not trying to recapitulate all of computer history.

That’s my story, and I’m sticking to it. See you next time!