Still very early days for the Forth idea. I’ll report on what I’ve been reading, muse a bit, perhaps try some code, if I can think of anything I want to learn. Progress!

Reading

I think I’d better make a new bookmark folder for Forth, there’s a lot of stuff out there. Much of it isn’t what I want but might be useful later. I’m trying to read to get an understanding of how it works, and a bit about how it’s done, but not so much that I just turn out to be transcribing a solution into Python. I want to discover as much as possible, invent as much as possible.

So far I’ve found read parts of:

Starting Forth by Leo Brodie.
Various things on forth.org, which was there yesterday and not there today. Weird.
Some lessons on wiki.laptop.org

There’s more on my iPad in the other room: I’ll tell you about whatever’s over there next time.

Reflection

Thinking about yesterday’s code, I realized that there’s a tiny issue in this:

def plus():
    x1, x2 = stack.pop(), stack.pop()
    stack.append(x1 + x2)

If we were to give this the “official” Forth-style comment, it would be something like this:

def plus():
    # ( x1 x2 -- x1+x2 )
    x1, x2 = stack.pop(), stack.pop()
    stack.append(x1 + x2)

The rules are that the top of the stack is on the right. So the first thing popped will be x2, and the second x1. I think the code should be this:

def plus():
    # ( x1 x2 -- x1+x2 )
    x2, x1 = stack.pop(), stack.pop()
    stack.append(x1 + x2)

Right? I think so. What did we do about minus? We coded that in line:

def interpret_word(word):
    if is_number(word):
        stack.append(int(word))
    elif word == '+':
        plus()
    elif word == '-':
        x1, x2 = stack.pop(), stack.pop()
        stack.append(x2 - x1)

We should get in the habit of using the Forth comments, because when we start creating words, we’ll need them. Arguably we already need them. Anyway:

def interpret_word(word):
    if is_number(word):
        stack.append(int(word))
    elif word == '+':
        plus()
    elif word == '-':
        x1, x2 = stack.pop(), stack.pop()
        stack.append(x2 - x1)

Grumbling

The morning has gone weird, I had to divert to try to put new batteries in one of those cheap necklaces that looks like flashing Christmas lights. Unfortunately, after taking apart this intricate little thing, I do not have any 3v batteries the thickness of s toothpick. I have lots of 1.5v watch batteries but no 3v ones. Sorry, dear.

I also need some guidance on how to best set up my gitignore if I were ever to commit this Forth code to a repo. PyCharm creates a zillion files to my one, and I don’t know if any of them matter. For now, I’m just putting my own source files in the local repo. I figure that’s safe.

Musing

I was going to muse a bit about how this thing has to work. Casual conversations and the little reading I’ve done so far tell me that the standard way to implement Forth is with “threaded code”, which is not a term I’m prepared to define just now. There is this book: Threaded Interpretive Languages, which I have scarfed a copy of and will skim / peruse / look at.

The big issue, as I see it, is with Forth’s ability to define new words. If we wanted to produce the negative of the value on the stack, we could say this:

# ( x -- -x )
: NEGATE 0 SWAP - ;

In that sequence, the colon begins a definition, which consists of the name of the word being defined, then the words that make up the definition, up to the semicolon. So that code pushes a zero onto the stack, swaps the top two elements on the stack, then does a subtract, subtracting what was originally on top (and now is on top again) from what’s below, now the zero.

So the word ‘:’ needs to somehow package up that sequence and store it under the name, not of Saunders, but NEGATE. And then, later on, when Forth is merrily going along executing code, when it encounters ‘NEGATE’, it has to find that saved stuff, start executing there, and when it reaches the end (how does it know it’s the end), it needs to pick up executing where it was.

Now, it is “easy to see” that we could do this recursively, with a bit of work, if each saved word ended with a return, which of course we could arrange. Every time we read a word, we look up its definition and call it. Our recursion depth might be immense, but however we do it I think we have an address stack to deal with. We might get by with something much smaller than a Python stack frame, if we were more clever. Perhaps.

Note to Self: It would probably be educational to do a spike where we do just that, arrange the saved code so that we recursively call our interpreter. It might work, and we would surely learn something. Well, I would: you may already know all this, in which case do drop me a note with hints. It has been maybe four decades since I last played with Forth.; Perhaps I can rig up a simple test using a hand-crafted NEGATE or something like that.

Through a glass, very very darkly.

My reading suggests that Forth implementations (often, typically?) have two modes, compiling and executing. When compiling, the make an entry in their code table / list, with the name of the word, followed by, I think, the addresses in the table of the words in the definition. They end the entry with an EXIT word, which is the thing that pops back to the previous place where the interpreter was interpreting.

When interpreting, I think it’s something like: the interpreter is pointing at the entry for some word. It pushes that address onto an execution stack and then branches to the first entry in the word’s code list. (I freely grant that I do not see this clearly.) Anyway, now it’s looking at the code for the word it was just looking at. Sooner or later someone hits a primitive, which actually returns. So it steps to the next entry, repeat until finally it hits EXIT which will pop its value off the execution stack and return to whatever its caller was doing.

I’d guess that when a primitive returns, it is essentially doing EXIT, just like everyone else.

I really only have just the tiniest grip on how that might work.

I wonder if I could do a sort of definition of our NEGATE with the code we have.

I start by implementing SWAP in the obvious code. Then I sketch this test:

    def test_negate(self):
        def negate():
            s = '0 SWAP -'
            interpret(s)

        clear()
        s = '100 NEGATE'
        interpret(s)
        assert stack.pop() == -100

This fails, of course but since there is no penalty for not finding NEGATE, it just stops with 100 on the stack.

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 == 'SWAP':
        # ( x1 x2 -- x2 x1 )
        x2, x1 = stack.pop(), stack.pop()
        stack.append(x2); stack.append(x1)
    else:
        raise ValueError(f'Invalid word {word}')

Now I get the exception:

        else:
>           raise ValueError(f'Invalid word {word}')
E           ValueError: Invalid word NEGATE

OK, what we really want might be something like this:

Put the string for NEGATE in a table or dictionary or something, indexed by the name.
If the word is not a primitive, look it up in the table.
If you don’t find it, drop into the value error.
If you do find it, interpret it.

If that would work more or less, then so should this:

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 == 'SWAP':
        # ( x1 x2 -- x2 x1 )
        x2, x1 = stack.pop(), stack.pop()
        stack.append(x2); stack.append(x1)
    elif word == 'NEGATE':
        s = '0 SWAP -'
        interpret(s)
    else:
        raise ValueError(f'Invalid word {word}')

And that does work! Fascinating!

Let’s do another. I need another two primitives, * and DUP. I don’t see how to do those given what I’ve got. Anyway new tests:

    def test_swap(self):
        clear()
        s = '1 2 SWAP'
        interpret(s)
        assert stack.pop() == 1
        assert stack.pop() == 2

    def test_dup(self):
        clear()
        s = '100 DUP'
        interpret(s)
        assert stack.pop() == 100
        assert stack.pop() == 100

    def test_times(self):
        clear()
        s = '5 6 *'
        interpret(s)
        assert stack.pop() == 30

    def test_negate(self):
        clear()
        s = '100 NEGATE'
        interpret(s)
        assert stack.pop() == -100

    def test_square(self):
        s = '10 SQUARE'
        interpret(s)
        assert stack.pop() == 100

These all run, supported by this:

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 == '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 *')
    else:
        raise ValueError(f'Invalid word {word}')

Note that the last two words, NEGATE and SQUARE, are implemented in “Forth” statements, not Python code. We have liftoff.

The morning is gone, between starting late and disassembling a tiny battery box, so let’s reflect and sum up.

Reflection

We do not have a “threaded code interpreter”. What we do have, however, is an interpreter. It’s pretty clear, I think, that we can readily build a dictionary or table of these strings, and search it, calling interpret on whatever we find. That will unquestionably work.

It will also be flawed in some important ways. It will not support the Forth style of redefinition. In Forth, you can undefine a word and the word’s prior definition is reinstated … and you lose everything you defined since you created the current word. (You might have used it, but it appears, as I read the material, that it just removes everything you defined after the word you’re dropping.) Not a problem, we can make a list and search from the hot end, or something of that nature.

In addition, we’ll want to do something to ensure that when you do a new definition, all the words you use are already defined. Shouldn’t be a big deal, we can look in our table.

Our own operations, as written now, are not in the table. That would mean we’d have to check differently to see whether ‘+’ is a word than how we’d check for ‘NEGATE’. The thing to do is to have two kinds of definitions in the table (or two tables?) and check accordingly.

Summary

I think that we could “ship” a rudimentary programming language for our robot world Real Soon Now. We need more primitives, and we need a way to define words based on those primitives, but both of those are well in hand.

Right now, interpretation time is proportional to the number of items in the if-elif, and to the number in the lookup table, unless we make it hashed. We might be concerned about that, but until I see a problem I’m not terribly worried.

We’d have to bullet-proof the interpreter just a bit, but we can do it with a simple try-except kind of thing, with error logging as we’ve done it. We’d probably want to provide some amount of detail as to where the error was in the Forth script. All doable.

But what about “threaded code”? Do we want to learn about that, at least a bit? Or are we here to provide a simple-enough, powerful-enough, scripting language for our robots?

My guess is that we’re here to learn a bit more. Join me next time to see what happens!