Peer Review

The Robot World Repo on GitHub
The Forth Repo on GitHub

FGNO observations suggest a radical change to my ‘Forth’ spec, which should improve the supporting design. We FAFO a bit. Looks good. No great strides.

In this week’s Friday Geeks Night Out, held every Tuesday evening, we had a chance to review the top-levels of code for my Forth, because I don’t like it and wanted ideas. The group all had useful ideas, as I recall, but it was GeePaw Hill, who has actually implemented and used Forth extensively, who had the most radical observation. Let’s look at the code in question before we drill into his idea:

main.py
if __name__ == '__main__':
    forth = Forth()
    prompt = 'Forth> '
    while True:
        line = input(prompt)
        if line == 'bye':
            break
        result = forth.compile(line)
        prompt = 'Forth> '
        if result == '...':
            prompt = '...> '
        else:
            print(result)

class Forth:
    def compile(self, text):
        try:
            self.unsafe_compile(text)
        except Exception as e:
            msg = str(e)
            if msg  == 'Unexpected end of input':
                return '...'
            else:
                self.abend()
                return f'{e} ?'
        return 'ok'

    def unsafe_compile(self, text):
        new_text = re.sub(r'\(.*?\)', ' ', text)
        self.tokens = new_text.split()
        self.token_index = 0
        while self.token_index < len(self.tokens):
            word = self.compile_a_word()
            word(self)

    def compile_a_word(self):
        if self.compile_stack.is_empty():
            self.word_list = []
        while True:
            token = self.next_token()
            if token is None:
                raise ValueError('Unexpected end of input')
            if (definition := self.find_word(token)) is not None:
                if definition.immediate:
                    definition(self)
                else:
                    self.word_list.append(definition)
            elif (num := self.parse_number(token)) is not None:
                self.compile_literal(num, self.word_list)
            else:
                raise SyntaxError(f'Syntax error: "{token}" unrecognized')
            if self.compile_stack.is_empty():
                break
        return Word('nameless', self.word_list)

My main focus is on compile_a_word, which exhibits that jagged layout that Hill calls “slalom code”. It is rife with if and elif and has an infinite loop with a break in it. It does not please anyone, except for one notable thing: it works as intended.

Hill’s focus was on my use of the compile_stack as a flag to determine when to return from compile_a_word. His point—assuming that I have it right—was that the proper Forth behavior is always to interpret a word at a time and that the only exception to that is when it is actually compiling a colon definition.

Note:

I am not convinced that this is quite true. What about CREATE-DOES>? We’ll have to look into that.

But there are many users of the compile stack, not just the colon-semicolon crew. IF and LOOP and all those things also use the stack. And in my Forth, you can type those words at the Forth> prompt, and they work. Hill’s assertion was that, in “real” Forth implementations, those words can only be used inside colon definitions, that is, only when we are already compiling. In my implementation, they trigger compilation state.

Hill would have all those words trigger an error if the system is not already in compile mode. If it is in compile mode, they are “immediate” and would do their actions as needed just fine. In support of his view, I note that the Forth standard says that the behavior of those words is undefined if the system is in interpretation state.

So far so good. I agree that it would be entirely legitimate to modify our Forth’s behavior to make those words only work in compile state. We would, of course, produce some kind of error message if the rules were broken.

But why?

All of this is in aid of simplifying the handling of the word_list used in compilation. We need a place to accumulate words when we are compiling. A classical Forth would have opened a new word definition in the dictionary and would be pushing the words into that definition. Our Words don’t work quite the same, though perhaps they should. We build up a word list and then create a Word instance to contain that list.

We were trying to simplify the word list handling, in particular to get rid of the if statement at the beginning of compile_a_word. All this for that? We felt that it might lead somewhere good, although we may just have been nerd-sniped by the ideas.

Action Time

Enough context. If you were here you could ask a few more questions. You’re not here in the room with me, as far as I know. So let’s create a new member compilation_state and set it appropriately.

Arrgh. I left the system in red bar state last night. OK, no big deal, roll back. Now the flag. Kind of wish I had stashed it but I don’t generally do that.

    def _define_colon_semi(self):
        def _colon(forth):
            forth.compile_stack.push(forth.next_token())
            forth.compilation_state = True

        def _semi(forth):
            definition_name = forth.compile_stack.pop()
            word = Word(definition_name, forth.word_list[:])
            forth.lexicon.append(word)
            forth.word_list.clear()
            forth.compilation_state = False

        self.pw(':', _colon, immediate=True)
        self.pw(';', _semi, immediate=True)

I note that _semi is clearing the word list for us. Recall that our mission, part of it, is to get rid of that clearing of the list at the top of compile_a_word. What happens if we just remove it?

Well, 52 tests break. Let’s see if the common cause is clear. Ah, right, the rollback reverted this change, where we put the definition of primaries after all the lists and stacks are initialized:

class Forth:
    def __init__(self):
        self.active_words = []
        self.compile_stack = Stack()
        self.compilation_state = False
        self.heap = Heap()
        self.lexicon = Lexicon()
        self.return_stack = Stack()
        self.stack = Stack()
        self.tokens = None
        self.token_index = 0
        self.word_list = []
        self.lexicon.define_primaries(self)

Now “only” 14 tests are failing. I think these will be the ones that Hill would have us disallow.

A review of the tests makes me think that I know what is happening. The word list is not getting cleared, so it gets longer and longer and words are not correctly defined.

This change, at the bottom of the method, gets us green:

    def compile_a_word(self):
        while True:
            token = self.next_token()
            if token is None:
                raise ValueError('Unexpected end of input')
            if (definition := self.find_word(token)) is not None:
                if definition.immediate:
                    definition(self)
                else:
                    self.word_list.append(definition)
            elif (num := self.parse_number(token)) is not None:
                self.compile_literal(num, self.word_list)
            else:
                raise SyntaxError(f'Syntax error: "{token}" unrecognized')
            if self.compile_stack.is_empty():
                break
        word = Word('nameless', self.word_list[:])  # <===
        self.word_list.clear()                      # <===
        return word

The [:] is there to copy the word list. Otherwise, we pass a pointer to the one we clear, and the resulting word has nothing to do because it finds an empty list. (We were setting it explicitly to [] elsewhere. That created a new list instance each time, with the effect that the one we build into the Word remains untouched.)

I wanted to know what the list has in it when we get here. I put in some prints, looked at them, wrote about them. Waste of my time and yours. Move along, nothing to see here.

OK, let’s see how we could use our compile_state flag. We just change that final if:

    def compile_a_word(self):
        while True:
            token = self.next_token()
            if token is None:
                raise ValueError('Unexpected end of input')
            if (definition := self.find_word(token)) is not None:
                if definition.immediate:
                    definition(self)
                else:
                    self.word_list.append(definition)
            elif (num := self.parse_number(token)) is not None:
                self.compile_literal(num, self.word_list)
            else:
                raise SyntaxError(f'Syntax error: "{token}" unrecognized')
            if not self.compilation_state:  # <===
                break
        word = Word('nameless', self.word_list[:])
        self.word_list.clear()
        return word

That’s checking compilation_state and used to be testing the compile_stack. Three tests break:

    def test_begin_until_inline(self):
        f = Forth()
        s = ' 2 5 BEGIN SWAP 2 * SWAP 1- DUP 0 >= UNTIL '
        f.unsafe_compile(s)
        assert f.stack.pop() == 0
        assert f.stack.pop() == 64

According to Hill’s notion, that one should error. The next one is:

    def test_initial_do(self):
        f = Forth()
        s = ' 5 0 DO I 10 * LOOP '
        f.unsafe_compile(s)
        assert f.stack.stack == [0, 10, 20, 30, 40]

That, too, should fail according to GeePaw. Good so far. Next:

    def test_compiled_star_loop(self):
        f = Forth()
        f.unsafe_compile(': JUMP_BACK ;')
        f.unsafe_compile(': SKIP ;')
        star_loop = ': *LOOP R> R> SWAP 1 + 2DUP < IF SWAP >R >R JUMP_BACK ELSE DROP DROP SKIP THEN ;'
        # f.compile(star_loop)
        s = ' 5 0 DO I 10 * LOOP '
        f.unsafe_compile(s)
        assert f.stack.stack == [0, 10, 20, 30, 40]

Again, a loop outside a definition. This is a bit of a spurious test anyway. I was trying to create a compiled definition of the *LOOP word and never did get it right. The test used to run, but according to GeePaw it should not.

Let’s take a step back. I think this is good and I want to explain why, in order to find out why I think that.

Reflection

If we fix up these tests to show proper errors, or fix them up do embed the tested bits in colon definitions, our use of compilation_state will be righteous. On the face of it, that seems not to be a big deal. But the thing is this:

When we compile a word, we return an empty word from compile_a_word. And if we’re not in compilation state, we’ll always return after just one token, either the definition we found in the lexicon or the code to push a number to the stack. So we can surely simplify compile_a_word.

I do not see that simplification yet, but I’m sure it’s there. And I am also sure that I need a break. Let’s mark those tests to ignore, but not commit yet. I’m pretty sure this is the path, but not quite ready to commit to it.

Summary

We fooled around with GeePaw’s idea, and we found out that it (or what we made of it) seems to hold water. So far the improvements are slight but real. We have people who care about the word list maintaining it. We have no conditionals affecting it. We have removed at least one maybe two conditionals from compile_a_word, depending on when you start counting.

And my intuition, which I am inclined to trust as it is founded on over six decades of thoughtful programming, tells me that we’re on a good path to simpler code. So, I’ll take a break to clear my head and eyes, and to rustle up an ice chai latte. I’ll come back in the sequel to push on.

So far so good! See you next time!