Further Forth

The Repo on GitHub

Some Forth planning, and then, I write a POWER word that is hard to understand, and that could have been a trivial primary. Plus Forth comments, because POWER really needs them.

Here’s my list from yesterday, suggesting things we might do, with a bit of elaboration for each:

Change the compiler to be able to compile and run any Forth not just definitions.

Right now, the compile method just checks for its input being enclosed in ‘:’ and ‘;’ and compiles it as a word. The “real” thing to do is to consume the input string, executing it immediately unless and until one meets a compiling word, in which case we go into compiler mode.

I’m concerned that this will be a significant change, because of the IF-ELSE-THEN and possibly DO-UNTIL. Surely we cannot execute the IF without knowing where to leap if the IF condition is false? I guess we could enter a mode where we just eat (or compile?) words until we hit an ELSE or THEN. Anyway it seems that it may require a lot of rework, and since I don’t see what the new design should be, I surely don’t see how to refactor to get there.

It would be embarrassing to have to rewrite something.

Do a REPL, Forth prompt where you can type things in.

It would be really nice to be able to type Forth in interactively. I find that I’m not anywhere near up to speed on writing it correctly, so being able to test and define small bits at a time would be really useful.

I think this will be made a bit more tricky by the fact that in production mode, we want our Forth not to suddenly look to the keyboard input for something, and other times, we do.

Provide for file input of a Forth program.

In developing a Forth program of any size, we’d want to be editing it in a real editor and then have Forth run it. I suspect that if we get #2 above working, this should be fairly simple to set up. Doubtless there’s more to it than I realize just now.

New angle on the robot game.

Instead of a client-server multi-user robot game, we could imagine a one-user version running at home, where you see the screen of the world, and you program your robots in Forth, to get them to do things. Maybe there would be different problems to solve or something.

Doubtless there are other ideas that will come up, but these are more than I know how to do now, so they’ll keep us busy for a while.

I did a couple of things yesterday while you were away, so let me report on them.

I implemented two new words ‘1+’ and ‘1-‘, which are equivalent to ‘1 +’ and ‘1 -‘. Why? To save all those spaces, I guess. I implemented them as primaries, in part because why not and in part because we have no way, yet, to define built-in secondaries. That would, of course, be simple enough, we could just compile their strings after defining the primaries.

The other thing I worked on was using DO-UNTIL to calculate a number to the power of another, like 3 to the 4th power kind of thing. I found it quite difficult. Since DO-UNTIL terminates based on finding a true value at the top of the stack, and since to do the power you need to retain the multiplier on the stack, there’s a lot of rotating and swapping, and it’s difficult to keep track. As you’ll see below.

Let’s try again. I’m going to do it in steps this time. Let’s think about how one might do this looping, on a stack machine.

Let’s assume the input has the partial product and the base on the stack, base on top. In each iteration, we’ll multiply the partial product by the base, and finish with the new partial product and base on the stack. This is what we in the trade call an “invariant”, meaning in this case that the shape of the input and the shape of the output are the same. This means that we can just iterate that function the right number of times and everything will be just fine.

We’ll call that operation POW_STEP.

    def test_pow_step(self):
        f = Forth()
        pow_step = ': POW_STEP ;'
        f.compile(pow_step)
        f.compile(': TEST 9 3 POW_STEP ;').do(f)
        assert f.stack.pop() == 3
        assert f.stack.pop() == 27

You can kind of see here why I’d like to be able to just compile and run any Forth without having to define everything. Of course this test fails. I hope it fails on the 27, seeing 9.

Expected :27
Actual   :9

Life is good. Now How about this for the POW_STEP:

    def test_pow_step(self):
        f = Forth()
        pow_step = ': POW_STEP DUP ROT * SWAP ;'
        f.compile(pow_step)
        f.compile(': TEST 9 3 POW_STEP ;').do(f)
        assert f.stack.pop() == 3
        assert f.stack.pop() == 27

We duplicate the base, giving [prod base base]. ROT, giving [base base prod], *, giving [base prod], SWAP, result as ordered.

Now we “just” need to build a POWER word that uses POW_STEP to do the job. Since we start with base base, if we want the nth power, we’ll iterate n - 1 times.

Assume the input stack we start with is [base power]. We’ll write a test:

    def test_power(self):
        f = Forth()
        # ( prod mul -- prod*mul mul)
        pow_step = ': POW_STEP DUP ROT * SWAP ;'
        f.compile(pow_step)
        # ( base pow -- base^pow)
        f.compile(': POWER ;')
        f.compile(': TEST 3 4 POWER ;').do(f)
        assert f.stack.pop() == 81

OK, let’s see. Let’s assume that pow is at least 2. We’ll see how to deal with smaller powers later. Although … if we start the product at 1, we can avoid the n - 1 thing, perhaps. Let’s try that. We’ll assume pow >= 1 for now. We’ll create the [1, base] input and maintain that invariant in our loop.

    def test_power(self):
        f = Forth()
        # ( prod mul -- prod*mul mul)
        pow_step = ': POW_STEP DUP ROT * SWAP ;'
        f.compile(pow_step)
        f.compile(': 2ROT ROT ROT ;')
        # ( base pow -- base^pow)
        f.compile(': POWER 1 2ROT DO 2ROT POW_STEP ROT 1- DUP 0 = UNTIL DROP DROP ;')
        f.compile(': TEST 3 4 POWER ;').do(f)
        print("final ", f.stack.stack)
        assert f.stack.pop() == 81

It took me a few tries to get that. I seem not to know what ROT does. I was thinking it took top to bottom but it takes bottom to top. I just looked up and that’s the right definition. I know that some Forth implementations use LROT and RROT. I am not sure which way left is, probably top to bottom.

So that code is hard to understand, and I don’t subscribe to the notion that if it was hard to write it should be hard to understand.

What we need here is for our compiler to handle comments.

    def test_comment(self):
        f = Forth()
        f.compile(': TEST ( a b -- b a) SWAP ;')

Yes, comments begin with paren space. We have no other use for parens. Let’s provide for that.

However, we presently loop over words in a stream of tokens. OK, we could read them until we find one with a right paren but that won’t do. I think we have to pre-process the input string.

    def compile(self, text):
        new_text = re.sub(r'\(.*?\)', ' ', text)
        words = new_text.split()
        match words:
            case ':', defining, *rest, ';':
                word_list = self.compile_word_list(rest)
                word = SecondaryWord(defining, word_list)
                self.lexicon.append(word)
                return word
            case _:
                raise SyntaxError(f'Syntax error: "{text}". Missing : or ;?')

That will do for now. Now I want to comment that POWER code, to understand it better and to see what we might do about it.

    def test_power(self):
        f = Forth()
        f.compile(': 2ROT ROT ROT ;')
        pow_step = (': POW_STEP'
                    '(prod base -- prod*base base)'
                    'DUP ROT * SWAP ;')
        f.compile(pow_step)
        f.compile(': POWER'
                  '(base power -- base**power) '
                  '1 2ROT           (1 base power)'
                  'DO 2ROT          (power 1 base)'
                  'POW_STEP         (power product base)'
                  'ROT              (product base power)'
                  '1- DUP 0 = UNTIL (product base power)'
                  'DROP DROP        (product) ;')
        f.compile(': TEST 3 4 POWER ;').do(f)
        print("final ", f.stack.stack)
        assert f.stack.pop() == 81

Meh. We can kind of see the invariants: (product base power) in and out of the loop, and (product base) for POW_STEP. A different kind of looping construct might help us, so that we didn’t have to do quite so much arithmetic just to handle the loop. Something like:

    def test_different_loop(self):
        p = (': POWER'
             '(base power -- base**power) '
             '1 2ROT (1 base power)'
             'DO-N POW_STEP LOOP DROP ;')

Here I’m imagining a DO_N word that accepts an integer on the stack and iterates that many times. I have no good idea how we might build such a thing. Some p-baked ideas, for moderately-sized p might include:

1. Implement variables and somehow save the index in a variable. That seems fraught: nesting might not work;
2. Provide another stack and stack the index over there. That might work if the stack was reserved for this kind of purpose.

One issue is that our DO_N only knows that its end point is on the stack. It does not know how much of the stack will be used by whatever is inside the loop, so it can’t tuck anything away “underneath”.

We’ll think about this, because what we have here is rather hard to use. For very large values of “rather”.

SUMMARY

Be all that as it may, we’ll finish up for now. We have a fragile but working comment handler, we have implemented a horrible but working POWER word (which could be implemented trivially as a primary), and we’ve discovered that we don’t much like our current DO-UNTIL capability.

Just a few tiny steps, with important discoveries and a clear indication that we need to beef up our Forth engine if it is to be useful.

See you next time!