Branching
The Robot World Repo on GitHub
The Forth Repo on GitHub
Our CASE-ENDCASE only needs its branches hooked up to work, I believe. I’d like to find a simple test for the actual branching words.
Tests that we’ve seen before show that we’re patching one the branches in OF-ENDOF correctly. The other requires us to put branching into CASE-ENDCASE. I expect that to go easily, because the OF-ENDOF ones have beaten down a decent path that we can use. Before we proceed with that, I want to implement the two new branching words, 0BR and BR, the conditional and unconditional branch, respectively.
A branch instruction as we’re using them in CASE, consists of a word, 0BR or BR, followed by a location in the current word, the equivalent of an address in memory, or to be stuffed into the program counter. In our Forth, we will put it into the program counter.
We already have a similar concept for IF and BEGIN, except that it uses the distance to be skipped, forward or back. It was done that way, probably, because it was the best idea I had at the time. I think a direct branch will be better. So we’ll do that, and then probably retrofit IF and BEGIN to work the same way.
In aid of that, there are a couple of changes that need to be made. Here’s some code in Lexicon:, showing just the relevant bits:
class Lexicon:
def define_skippers(self, forth):
def _next_word(forth):
return forth.active_word.next_word()\
def _zero_branch(forth):
branch_distance = _next_word(forth)
if forth.stack.pop() == 0:
forth.active_word.skip(branch_distance)
self.pw('*IF', _zero_branch)
self.pw('*UNTIL', _zero_branch)
The *IF and *UNTIL words are calling _zero_branch. That function should be called _zero_skip. We can see that in fact it calls skip on the active word, not something like goto or branch.
We’ll rename _zero_branch. Green. Commit: rename function. Now let’s look at the skip method itself.
class Word:
def skip(self, n):
self.pc += n
We might want to minimize the code that changes the program counter pc, but for now, let’s just provide the branch method:
def branch(self, word_address):
self.pc = word_address
Horrors, Ron! You just wrote two whole lines of code without a test that demands them. Heretic!
They’re more guidelines than actual rules, you know.
Let’s do write a test for branch, though, which will wind up using this branch, unless I miss my guess.
def test_branch(self):
f = Forth()
test = ': TEST 5 BR BR_TARGET DUP + 3 + ;'
# 0 1 2 3 4 5 6
ok = f.compile(test)
assert ok == 'ok'
w = f.find_word('TEST')
words = w.words
assert words[2] == f.find_word('BR_TARGET')
words[2] = 5
f.process_line('TEST')
assert f.stack.pop() == 8
This somewhat intricate test patches the BR_TARGET cell in the TEST word to 5, which is the 3. My intention is that this word will return 8 on the stack, because it skips over the DUP +. If it did not skip, it would return 13.
The test fails now with this somewhat obscure message:
while self.pc < len(self.words):
w = self.next_word()
> w(forth)
E TypeError: 'int' object is not callable
This occurs because BR is just a pass now, so we fall onto the integer. Let’s make the test fail by having BR at least skip the subsequent word.
class Lexicon:
def _br(f):
f.active_word.next_word()
...
self.pw('BR', _br)
...
Test fails as expected:
Expected :8
Actual :13
Now do the correct branch:
def _br(f):
address = f.active_word.next_word()
f.active_word.branch(address)
Test is green. Commit: BR word implemented. Refactoring needed.
Why do we think refactoring is needed? Well, the _br function is ripping the active word out of Forth and talking to it. That’s not ideal. We do that all over the place, so there is definitely some improvement possible. But we are here for bigger game now.
Let’s drive out 0BR as well, since we need it.
def test_zero_branch_branches(self):
f = Forth()
test = ': TEST 5 0 0BR BR_TARGET DUP + 3 + ;'
# 0 1 2 3 4 5 6 7
ok = f.compile(test)
assert ok == 'ok'
w = f.find_word('TEST')
words = w.words
assert words[3] == f.find_word('BR_TARGET')
words[3] = 6
f.process_line('TEST')
assert f.stack.pop() == 8
I think that will be failing on the message about trying to execute an integer. Yes:
while self.pc < len(self.words):
w = self.next_word()
> w(forth)
E TypeError: 'int' object is not callable
We need to implement 0BR. I’ll follow the same flow, first making it skip but not branch, which will give us the wrong value, and then fix it to check and branch.
def _0br(f):
address = f.active_word.next_word()
I don’t get the error that I expect:
Expected :8
Actual :3
I am surprised and confused. I don’t see how we can get a 3 out of that code.
Not much point rolling back, that line can’t be causing the problem. Let’s assert what it gets, ensuring that it is in fact getting the expected 6.
def _0br(f):
address = f.active_word.next_word()
assert address == 6
OK, that’s as expected. Can we trace? After brief confusion, I realize that 0BR must pop the stack, even if it intends (briefly) to ignore what’s there.
def _0br(f):
value = f.stack.pop()
address = f.active_word.next_word()
OK, now I expect 13 not 8.
Expected :8
Actual :13
And now finish the implementation:
def _0br(f):
value = f.stack.pop()
address = f.active_word.next_word()
if value == f.false:
f.active_word.branch(address)
Green. Commit: 0BR works in the zero case. Now we can easily test the non-zero case using the same test shape:
def test_zero_branch_no_branch(self):
f = Forth()
test = ': TEST 5 1 0BR BR_TARGET DUP + 3 + ;'
# 0 1 2 3 4 5 6 7
ok = f.compile(test)
assert ok == 'ok'
w = f.find_word('TEST')
words = w.words
assert words[3] == f.find_word('BR_TARGET')
words[3] = 6
f.process_line('TEST')
assert f.stack.pop() == 13
Green. Commit: 0BR works both ways.
Reflection
So that went pretty well. I was briefly confused when 0BR didn’t consume the stack top. In a rare case, I suspect that if I had not tried to take quite such a tiny bite, I might have done it right.
Let’s just look around for code improvements.
def _0br(f):
value = f.stack.pop()
address = f.active_word.next_word()
if value == f.false:
f.active_word.branch(address)
def _br(f):
address = f.active_word.next_word()
f.active_word.branch(address)
We can improve this a bit, first inlining the value:
def _0br(f):
address = f.active_word.next_word()
if f.stack.pop() == f.false:
f.active_word.branch(address)
def _br(f):
address = f.active_word.next_word()
f.active_word.branch(address)
Then inlining address:
def _0br(f):
address = f.active_word.next_word()
if f.stack.pop() == f.false:
f.active_word.branch(address)
def _br(f):
f.active_word.branch(f.active_word.next_word())
We can’t inline in the _0br, since we must unconditionally skip the word containing the address. Commit: tidying.
Glance at or scan the whole case handling definitions, noting how we rarely say anything to Forth and often say something to an object that Forth knows:
def define_case_of_endof_endcase(self):
def _get_c_stack_top(f):
f.c_stack_top = f.compile_stack[-1]
def _case(f):
f.compile_stack.push(CompileInfo('CASE', f.word_list))
def _endcase(f):
f.word_list.append(f.find_word('DROP'))
ci = f.compile_stack.pop()
assert ci.name == 'CASE', f'expected CASE on compile stack, found {ci.name}'
def _of(f):
f.word_list.append(f.find_word('OVER'))
f.word_list.append(f.find_word('='))
f.word_list.append(f.find_word('0BR'))
f.compile_stack.push(CompileInfo('OF', f.word_list, len(f.word_list)))
f.word_list.append(f.find_word('BR_TARGET'))
f.word_list.append(f.find_word('DROP'))
def _endof(f):
f.word_list.append(f.find_word('BR'))
f.word_list.append(f.find_word('BR_TARGET'))
f.compile_stack.pop().patch('OF')
def _0br(f):
address = f.active_word.next_word()
if f.stack.pop() == f.false:
f.active_word.branch(address)
def _br(f):
f.active_word.branch(f.active_word.next_word())
def _br_target(f):
msg = f'branch not patched in {f.active_word}'
raise NotImplementedError(msg)
self.pw('OF', _of, immediate=True)
self.pw('ENDOF', _endof, immediate=True)
self.pw('CASE', _case, immediate=True)
self.pw('ENDCASE', _endcase, immediate=True)
self.pw('GET_C_STACK_TOP', _get_c_stack_top, immediate=True)
self.pw('0BR', _0br)
self.pw('BR', _br)
self.pw('BR_TARGET', _br_target)
If Forth, or f as we call it here, knew next_word and perhaps append or append_word, we could simplify a lot of this code.
Let’s see how we might readily do that. PyCharm doesn’t understand what we want to do. Let’s just put a method on Forth and then search for the people using the accessors for things like word_list and fix them.
class Forth:
def next_word(self):
return self.active_word.next_word()
The replace worked. I just did things in Lexicon, I believe :)
Let’s do append_word
class Forth:
def append_word(self, word):
self.word_list.append(word)
That went smoothly as well. I should have committed, will do so now: using forwarding words in Forth rather than reaching into Demeter’s um pockets.
We have a lot of lines that call forth twice to append a word, like the one here that compiles *UNTIL:
def _define_begin_until(self):
def _until(forth):
forth.append_word(forth.find_word('*UNTIL'))
jump_loc = forth.compile_stack.pop()
forth.append_word(jump_loc - len(forth.word_list) - 1)
Let’s provide compile_word on Forth and use that.
def compile_word(self, word_name):
self.append_word(self.find_word(word_name))
I plug that in everywhere. This will suffice for the morning’s overall code improvements. Let’s sum up.
Summary
The day’s real progress was to test and implement the 0BR and BR words, which are needed in the CASE code, and which I anticipate we’ll also use in conditionals and looping, replacing the earlier and more complicated code that was the best I had in me back when those were done.
But then, seeing a vast swath of calls fetching members out of forth and manipulating them, we created helper methods in Forth to do those jobs, reducing something like this:
forth.append_word(forth.find_word('*UNTIL'))
To this:
forth.compile_word('*UNTIL')
Shorter, more clear, less prone to errors. Pleasing.
We have a nice new capability, a good step toward CASE, and we have cleaned up the campground a bit. A good morning.
See you next time!