Forth: Next Try

The Repo on GitHub

Our first experiments went well. Let’s start an implementation that’s more like the kind of code we like to write. [Result: I am delighted!] (Also lambdas!)

In its prime, which was about when I was in my prime as well, a key aspect of Forth was that it was tiny. It was optimized for size and speed, as well as anything could be. The code was full of the kind of assembler and C language tricks one did back then, one routine dropping into another to save a call, that sort of thing. Today, nearing the end of 2024 and possibly civilization as we knew it, we’re writing a Forth-like system in an interpreted language. An interpreter on top of an interpreter. Life is weird.

Last night, while watching the Lions strive and not quite succeed, I wrote a little spike in Pyto, one of the iPad Python apps that I have. This morning, we’ll take what I learned and do something similar, something that I think will be close to what we really want to port back to the robot world.

My guess is, or perhaps it is merely a hope, that what we do this morning will evolve to be what we put into the robot world, but it’s possible that we’ll want to do it one more time. Let me describe my cunning plan.

Plan, sub-type Cunning

• We will have two classes PrimaryWord and SecondaryWord. These are sub-types of an abstract notion of Word, which may or may not be implemented as an abstract class.

• The Forth lexicon will be a list of instances of PrimaryWord and SecondaryWord.

• PrimaryWord will have a name, such as . or DUP, and will contain a python function, code, that implements that primary word.

• SecondaryWord will have a name, and a list of the Words making up that word, represented by the indices of those words in the lexicon.

• Both classes have a do method. Primary do executes the code of the primary. Secondary do loops over the list, fetching each referenced instance from the lexicon, and sending the do message to it.

I believe that this will suffice to support at least the rudiments of Forth. There will be work to do, plenty of it. With any luck at all, everything we need will be possible.

One note

I think that do is going to need to send one or more parameters when it calls down, and that the words may need to return a value. We’ll find out and work up to it.

Let’s create a new test file to contain our work, at least at the beginning.

After only a bit of fumbling, I have my old tests and a new hookup running. Let’s see how I might write a test. One issue comes up right away: how will we provide such useful things as the stack, as we try to build something generally useful with classes and all that jazz?

Too soon to worry, but not very much too soon.

First real test:

    def test_first_word(self):
        word = PrimaryWord('+', plus)

This won’t compile, so we have permission¹ to write code.

class PrimaryWord:
    def __init__(self, name, code):
        self.name = name
        self.code = code

I typed the first two lines, and PyCharm offered the next two. I do love me some PyCharm.

My test still does not compile, because it doesn’t know plus. I think we’ll try something here: I just thought of it. The functions that implement our primaries have to be somewhere. We could write them at the top level, but what if we made them static methods inside Primary? Let’s find out if that will work by trying it.

    def test_first_word(self):
        word = PrimaryWord('+', PrimaryWord.plus)

And:

    @staticmethod
    def plus():
        stack.append(stack.pop() + stack.pop())

Now it won’t compile because there is no stack. I’ll make that global for now:

stack = []

class PrimaryWord:
    def __init__(self, name, code):
        self.name = name
        self.code = code

    @staticmethod
    def plus():
        stack.append(stack.pop() + stack.pop())

class TestFirstClasses:
    def test_hookup(self):
        assert True

    def test_first_word(self):
        word = PrimaryWord('+', PrimaryWord.plus)

The test is passing, but of course it doesn’t do anything. And I’ve written code that was not required by the test. See what I meant about permission? We extend the test a bit:

    def test_first_word(self):
        word = PrimaryWord('+', PrimaryWord.plus)
        stack.append(1)
        stack.append(3)
        word.do()
        assert stack.pop() == 4

Test fails for want of do, which we do-ly provide.

class PrimaryWord:
    def do(self):
        self.code()

Our test passes! Callooh! Callay!

What should we do now? Since it’s not instantly clear to me, let’s reflect a bit.

Reflection

It seems clear to me that we can build as many PrimaryWord instances as we want: we just have to give them whatever stack manipulation code they need. One thing that we are missing, at this stage, is a sensible way to get numbers (and other values) into the scheme of things. I had to just push them in there.

We’ll want something that can interpret a string, such as we had before. We’ll be building the lexicon I spoke of above, a list of definitions. Should we have a lexicon class? We’re object-oriented here, chez Ron, so yes, we’ll want one. Is now the time? Let’s hold off on that for a bit and work up to it.

Let’s do something like this: we’ll define a few more words, enough to let us imagine a useful secondary word using them, and …

No. We have enough now. Let’s do a test for SecondaryWord right now. That will drive out what we need.

Note

I can imagine what we need. I could draw a diagram or write some code on a card or my iPad. It would be pretty nearly right, and it would be somehow not quite right. When we got to code, we’d see the flaws and make them right. Why not get right to that stage?

    def test_double(self):
        w0 = PrimaryWord('+', lambda: stack.append(stack.pop() + stack.pop()))
        w1 = PrimaryWord('DUP', lambda: stack.append(stack[-1]))
        lexicon.append(w0)
        lexicon.append(w1)
        s0 = SecondaryWord('DOUBLE', [1, 0])
        stack.append(2)
        s0.do()
        assert stack.pop() == 4

I went a bit wild here. The lambda definitions won’t hold water long term, but they work for now. (I put the lambda into the previous test and it is working there.)

It remains to write the new class:

class SecondaryWord:
    def __init__(self, name, code):
        self.name = name
        self.code = code

    def do(self):
        for word_index in self.code:
            lexicon[word_index].do()

Um, the test is green. I am almost surprised: it would have been easy to do something wrong. But I didn’t.

Let’s do another, really hard test.

Ah, perfect! This is why you never jump this far, if you’re wise:

    def test_hypotenuse(self):
        def swap():
            top, under = stack.pop(), stack.pop()
            stack.append(top); stack.append(under)

        clear()
        w_plus = PrimaryWord('+', lambda: stack.append(stack.pop() + stack.pop()))
        w_dup = PrimaryWord('DUP', lambda: stack.append(stack[-1]))
        w_swap = PrimaryWord('SWAP', swap)
        w_times = PrimaryWord('*', lambda: stack.append(stack.pop() * stack.pop()))
        w_sqrt = PrimaryWord('SQRT', lambda: stack.append(math.sqrt(stack.pop())))
        w_square = SecondaryWord('SQUARE', [1, 3])
        w_hypsq = SecondaryWord('HYPSQ', [1, 3, 2, 3, 0])
        w_hyp = SecondaryWord('HYP', [6, 5])
        lexicon.extend([w_plus, w_dup, w_swap, w_times, w_sqrt, w_square,w_hypsq, w_hyp])
        stack.append(3)
        stack.append(4)
        w_hyp.do()
        assert stack.pop() == 5

The test runs and gets the value 6.0 Which I have no idea how that’s even a possible result.

And the thing is, with this too-clever test, I have nowhere to toss in a print, and I have no real certainty that my intermediates work.

I will add a comment to help me, and then I think that HYPSQ needs a second look.

    def test_hypotenuse(self):
        def swap():
            top, under = stack.pop(), stack.pop()
            stack.append(top); stack.append(under)

        clear()
        w_plus = PrimaryWord('+', lambda: stack.append(stack.pop() + stack.pop()))
        w_dup = PrimaryWord('DUP', lambda: stack.append(stack[-1]))
        w_swap = PrimaryWord('SWAP', swap)
        w_times = PrimaryWord('*', lambda: stack.append(stack.pop() * stack.pop()))
        w_sqrt = PrimaryWord('SQRT', lambda: stack.append(math.sqrt(stack.pop())))
        w_square = SecondaryWord('SQUARE', [1, 3])
        w_hypsq = SecondaryWord('HYPSQ', [1, 5, 2, 1, 5, 0])
        w_hyp = SecondaryWord('HYP', [6, 5])
        lexicon.extend([w_plus, w_dup, w_swap, w_times, w_sqrt, w_square,w_hypsq, w_hyp])
        #               0       1      2       3        4       5                  6
        stack.append(3)
        stack.append(4)
        w_hyp.do()
        assert stack.pop() == 5

I did change HYPSQ. I think it now says DUP * SWAP DUP * +. I’ll try a print in the do of SecondaryWord, it might give me enough of a clue. What I really need is some finer-grain tests, but I’m too bull-headed for that.

After more debugging than I want to admit to, consisting of printing out every level of the recursion and seeing that a) it was recurring correctly and b) that I had bad code in my secondaries, the test is written correctly and runs:

    def test_hypotenuse(self):
        clear()
        w_plus = PrimaryWord('+', lambda: stack.append(stack.pop() + stack.pop()))
        w_dup = PrimaryWord('DUP', lambda: stack.append(stack[-1]))
        w_swap = PrimaryWord('SWAP', lambda: stack.extend([stack.pop(), stack.pop()]))
        w_times = PrimaryWord('*', lambda: stack.append(stack.pop() * stack.pop()))
        w_sqrt = PrimaryWord('SQRT', lambda: stack.append(math.sqrt(stack.pop())))
        w_square = SecondaryWord('SQUARE', [1, 3]) # DUP *
        w_hypsq = SecondaryWord('HYPSQ', [5, 2, 5, 0]) # SQUARE SWAP SQUARE +
        w_hyp = SecondaryWord('HYP', [6, 4]) # HYPSQ SQRT
        lexicon.extend([w_plus, w_dup, w_swap, w_times, w_sqrt, w_square, w_hypsq, w_hyp])
        #               0       1      2       3        4       5         6        7
        stack.append(3)
        stack.append(4)
        w_hyp.do()
        assert stack.pop() == 5

My defects were two: I had duplicated calls to DUP because I forgot that SQUARE does DUP, and I had a call to SQUARE where I needed a call to SQRT.

I couldn’t resist this change to the SWAP, in case you didn’t notice:

        w_swap = PrimaryWord('SWAP', lambda: stack.extend([stack.pop(), stack.pop()]))

Guido would kick me out of the Python club for that. He really dislikes lambda and that’s a terrible way to do the swap anyway, so I deserve it, but I also deserve a treat for making this all work.

Reflection

What that long final test does is just demonstrate that the recursive primary / secondary do works as intended. I think it also demonstrates that we need a Lexicon class with some construction and lookup methods. We’ll address that next time.

The main thing is to observe how simple the two Word classes are, for all the power they have just demonstrated:

class PrimaryWord:
    def __init__(self, name, code):
        self.name = name
        self.code = code

    def do(self):
        self.code()

class SecondaryWord:
    def __init__(self, name, code):
        self.name = name
        self.code = code

    def do(self):
        for word_index in self.code:
            word = lexicon[word_index]
            word.do()

I think that’s just delicious. Using those two methods and a few simple constructors, we have built a tiny language that can compute, among other things, the hypotenuse of a right triangle.

This pleases me inordinately. I’m even mostly over the debugging I had to do, which, I hasten to point out, was debugging Forth statements that were hand compiled. The Python was just fine!

See you next time!