The Repo on GitHub

I think I’ll invent the famous Forth return stack and use it to create a new looping kind of thing. Curiously that’s almost exactly what actually happens. I even do R> and >R, and then don’t use them.

Forth generally has at least two stacks, the regular every day one that we’ve been using right along, and a “return stack”, which is used by the compiler and which can be used carefully in real code, so long as you never leave anything on it nor remove anything you didn’t add.

I think we’ll add that, and the two words that access it.

    lex.append(PrimaryWord('R>', lambda f: f.return_stack.push(f.stack.pop())))
    lex.append(PrimaryWord('>R', lambda f: f.stack.push(f.return_stack.pop())))

I suppose I should have written tests for those.

    def test_return_stack(self):
        f = Forth()
        s = ': TEST 3 R> 4 5 + >R + ;'
        f.compile(s).do(f)
        assert f.return_stack == []
        assert f.stack.pop() == 12

Enough, it clearly works. Now I’d like to have a looping construct that is not atypical. I’ll remove the one we have. Ah here is one from forth.org, e.g.:

10 0 DO ... LOOP

The above will iterate from 0 up to and not including 10. 0 through 9, as it were. Very consistent with Python.

And you can access the index via the word I, in the innermost loop, J, K as you go outward. We can do that.

I’ll replace our current DO with BEGIN, which is what Loeliger used anyway, then I can use DO and LOOP freely.

The first part is just replacing ‘DO’ with ‘BEGIN’ a lot.

Now let’s see what this thing needs to do.

We will need to compile something for the do. We could have a *DO word, or maybe just compile in line. Let’s assume a word, it is more our style. Let’s see … we could push a pair onto the return stack, nothing says we have to just push numbers. So our *DO can pop the stack twice, and push the limit and (current) index as a pair onto the return stack. The LOOP or *LOOK, when we encounter it, will have the loop location patched in, and will pull the pair from the return stack, increment, check limit, and either push the new pair back and loop or leave them off and exit skipping.

Make sense? I think so.

I think it’s time for print. We’ll implement ‘.’ and CR, the standard Forth word that prints a value and a space, and the one that prints a return. I’ll use them to debug the loop, though I’ll still want a better test of some kind.

    def test_initial_do(self):
        f = Forth()
        s = ': TEST 5 0 DO I . LOOP CR ;'
        f.compile(s).do(f)
        assert False

    lex.append(PrimaryWord('*DO', lambda f: f.star_do()))
    lex.append(PrimaryWord('*LOOP', lambda f: f.star_loop()))

    def star_do(self):
        pass

    def star_loop(self):
        pass

Just putting in enough code to break things. I’m failing on attempt to compile I. I can do that:

    lex.append(PrimaryWord('I', lambda f: f.i_word()))

    def i_word(self):
        limit, index = self.return_stack[-1]
        self.stack.push(index)

I’m making a lot of changes with no green. This may turn out to be a spike, with some smaller steps required. We’ll see. Getting close, I think. Maybe.

    def star_do(self):
        start = self.stack.pop()
        limit = self.stack.pop()
        self.return_stack.push((limit, start))

My test is passing. Here’s what I have:

class Forth:
        lex.append(PrimaryWord('.', lambda f: print(f.stack.pop(), end=' ')))
        lex.append(PrimaryWord('CR', lambda f: print()))
        lex.append(PrimaryWord('*#', lambda f: f.stack.push(f.next_word())))
        lex.append(PrimaryWord('*LOOP', lambda f: f.star_loop()))
        lex.append(PrimaryWord('I', lambda f: f.i_word()))

    def compile_word_list(self, rest):
        word_list = []
        for word in rest:
            if word == 'IF':
                self.compile_conditional('*IF', word_list)
            ...
            elif word == 'DO':
                self.stack.push(('DO', len(word_list)))
                word_list.append(self.find_word('*DO'))
            elif word == 'LOOP':
                key, jump_loc = self.stack.pop()
                if key != 'DO':
                    raise SyntaxError(f'LOOP without DO')
                loop = self.find_word('*LOOP')
                word_list.append(loop)
            ...

    def i_word(self):
        limit, index = self.return_stack[-1]
        self.stack.push(index)

    def star_do(self):
        start = self.stack.pop()
        limit = self.stack.pop()
        self.return_stack.push((limit, start))

    def star_loop(self):
        jump = self.next_word()
        limit, start = self.return_stack.pop()
        start += 1
        if start < limit:
            self.return_stack.push((limit, start))
            self.active_word.skip(jump)
                word_list.append(jump_loc - len(word_list))

So that’s about 35 or 40 lines of code, rather a lot to type in without the tests running, but I just kind of followed the existing patterns. There was one actual mistake, I originally had the skip off by one, which seems kind of traditional. Let’s make the test do something semi-testable:

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

And commit: DO-LOOP working. Needs refinement.

Let’s reflect.

Reflection

This was too much code in one go. I’d rather see a test working every ten lines rather than every 40. That said, many of the individual changes were very rote, entries to the lexicon and the . and CR words. But I do think we could have gone in smaller steps, perhaps by hand-compiling a loop and doing *DO and *LOOP first, and then Do and LOOP.

Doing ‘R>’ and ‘>R ‘seems to have been a digression: I didn’t use them. They might come in handy, and are legitimate Forth: I’ll leave them in.

Doing’ CR’ and ‘.’ was also a digression: I could have written the test as it is above right off the bat. I was just thinking that I’d want to see a trace or something first. Fact is, the print didn’t buy me anything much, because as soon as the DO was in, the test crashed executing the number behind *LOOP, so I had to do *LOOP, and then it crashed by jumping back to the *DO, one too far, which crashed because the stack was empty, and after I removed the spurious -1, it worked.

So my steps were all pretty good, just the usual things that a micro-test would catch. I don’t think I was delayed at all by not having the smaller tests, but I wouldn’t have had to keep so many ideas in my head had I gone a different way.

But we go the way we go, and this way was OK this time. Had things not gone so smoothly, I’d have rolled back, and gone in smaller steps. I’d have been happier with smaller steps, but I was not, and am not unhappy.

We have more that should be done. We should be checking the return stack a bit more carefully. Maybe it isn’t the return stack: maybe it’s just the looping stack. We’re free to implement things as we see fit. Our actual return stack is in Python, in the recursive calls to do that we execute.

We need to implement ‘J’ and ‘K’, which will be like ‘I’ except looking at -2 and -3 on the return stack instead of -1.

Other than that, I think we can get back to thinking about this morning’s other topics:

  1. Change the compiler to be able to compile and run any Forth not just definitions.
  2. Do a REPL, Forth prompt where you can type things in.
  3. Provide for file input of a Forth program.
  4. New angle on the robot game.

I do really want to get to a REPL: I think it will be convenient. But for this afternoon, I give myself a hearty “well done”, and a whispered “and you could use a little improvement”. Same as every day, I guess.

See yo unext time!