DO LIVE 1 UNTIL
Today is my birthday. To celebrate, I think we’ll implement DO-UNTIL.1
Brief Report
Yesterday while you were away, I implemented some comparison words:
@staticmethod
def define_comparators(lex):
lex.append(PrimaryWord('=', lambda f: f.stack.push(1 if f.stack.pop() == f.stack.pop() else 0)))
lex.append(PrimaryWord('>', lambda f: f.stack.push(1 if f.stack.pop() > f.stack.pop() else 0)))
lex.append(PrimaryWord('<', lambda f: f.stack.push(1 if f.stack.pop() < f.stack.pop() else 0)))
lex.append(PrimaryWord('>=', lambda f: f.stack.push(1 if f.stack.pop() >= f.stack.pop() else 0)))
lex.append(PrimaryWord('<=', lambda f: f.stack.push(1 if f.stack.pop() <= f.stack.pop() else 0)))
As you might guess from that, I factored out several groups, so that at the top:
def define_primaries(self):
lex = self.lexicon
self.define_skippers(lex)
self.define_stack_ops(lex)
self.define_arithmetic(lex)
self.define_comparators(lex)
lex.append(PrimaryWord('SQRT', lambda f: f.stack.push(math.sqrt(f.stack.pop()))))
I’ll break out SQRT into define_math or something, if and when another one comes up. I couldn’t bring myself to add a one-line method, though perhaps I should have.
And I did write a test for all those comparators, and it is well that I did. I duplicated an existing line to make the first one, edited it, duplicated, etc. When I was done all those operators did an initial swap_pop, which made all of them wrong except for ‘=’. It took me quite a while to spot the error, but the bruise on my forehead where I whacked myself feels better today.
Looping
I propose to implement two words, DO and UNTIL. DO marks the beginning of a loop. UNTIL pops the stack and jumps to the beginning of the loop “until” the popped value is non-zero, i.e. true.
Let’s write a test.
def test_do_until_hard(self):
f = Forth()
f.compile(': DOUBLE 2 * ;')
f.compile(': DOUBLE_UNDER SWAP DOUBLE SWAP ;')
s = ': TEST 2 5 DO DOUBLE_UNDER 1 - DUP 0 <= UNTIL ;'
f.compile(s).do(f)
assert f.stack.pop() == 0
assert f.stack.pop() == 32
This is the most complex Forth I’ve written in the past four decades, so it may be wrong, but with an inordinate amount of luck, it will compute two to the fifth2 power. There is surely a better way, but if and when this test, or its descendant works, DO-UNTIL will be done.
Let’s do it.
The cunning plan is that DO will just stack one of those pairs (‘DO’, location) and UNTIL will compile something that fetches that value and does a skip back if stack pop is zero. I think we can do this.
I have this much:
elif word == 'DO':
self.stack.push(('DO', len(word_list)))
elif word == 'UNTIL':
key, jump_loc = self.stack.pop()
if key != 'DO':
raise SyntaxError(f'UNTIL without DO')
until = self.find_word('*UNTIL')
word_list.append(until)
word_list.append(jump_loc - len(word_list))
I think that’s the right shape if not the right numbers in the final append. As usual, it’s within plus or minus one, I expect.
I need *UNTIL.
@staticmethod
def define_skippers(lex):
lex.append(PrimaryWord('*IF', lambda f: f.star_if()))
lex.append(PrimaryWord('*ELSE', lambda f: f.star_else()))
lex.append(PrimaryWord('*UNTIL', lambda f: f.star_until()))
lex.append(PrimaryWord('*#', lambda f: f.stack.push(f.next_word())))
Now With luck the test is failing for want of star_until:
> lex.append(PrimaryWord('*UNTIL', lambda f: f.star_until()))
E AttributeError: 'Forth' object has no attribute 'star_until'
And …
def star_until(self):
# if pop is true, skip one else skip in word + 1
to_check = self.stack.pop()
skip_back = self.next_word()
if not to_check:
self.active_word.skip(skip_back)
I had high hopes, but the test is failing. Let’s see why:
s = ': TEST 2 5 DO DOUBLE_UNDER 1 - DUP 0 <= UNTIL ;'
f.compile(s).do(f)
> assert f.stack.pop() == 0
E assert 4 == 0
Interesting. It quit immediately. I need a bit more info here, so I print the compiled TEST word:
[*#, 2, *#, 5, DOUBLE_UNDER, *#, 1, -, DUP, *#, 0, <=, *UNTIL, -9]
0 1 2 3 4 5 6 7 8 9 10 11 12 13
The word to skip back to is 4, DOUBLE_UNDER. (Recall, as I did not, that the DO does not compile any code.)
I think 9 is correct. Did we do the check wrong?
It’s definitely exiting on the first iteration. It sees 1 for true. Ha. My final check is 0 <= 4 which it is.
The Forth is wrong.
def test_do_until_hard(self):
f = Forth()
f.compile(': DOUBLE 2 * ;')
f.compile(': DOUBLE_UNDER SWAP DOUBLE SWAP ;')
s = ': TEST 2 5 DO DOUBLE_UNDER 1 - DUP 0 >= UNTIL ;'
word = f.compile(s)
word.do(f)
print(word.words)
print(f.stack.stack)
assert f.stack.pop() == 0
assert f.stack.pop() == 32
The test still fails. The loop is running 5 times, exiting on the fifth. The doubling isn’t working.
I want a direct test.
def test_double_under(self):
f = Forth()
f.compile(': DOUBLE 2 * ;')
f.compile(': DU SWAP DOUBLE SWAP ;')
s = ': TEST 2 5 DU DU DU DU ;'
word = f.compile(s)
word.do(f)
assert f.stack.pop() == 5
assert f.stack.pop() == 32
This passes. Note that I only need 4 DU to do the job since 2 is 2 to the 1 already. So the other test should get 64 if we leave it at 5 but it gets 4. DOUBLE_UNDER works.
I need a debug word.
lex.append(PrimaryWord('DUMP', lambda f: f.dump_stack()))
def dump_stack(self):
print(self.stack.stack)
I’ll improve that shortly. But it gives me this:
[4, 5]
[4, 4]
[4, 3]
[4, 2]
[4, 1]
final: [4, 0]
So we get a 4 in there and keep it. But how?
Let’s dump in a few other places. I can see that we need an ability to put some text in there but not yet.
Ah. The jump is one short of what it needs to be!
elif word == 'UNTIL':
key, jump_loc = self.stack.pop()
if key != 'DO':
raise SyntaxError(f'UNTIL without DO')
until = self.find_word('*UNTIL')
word_list.append(until)
word_list.append(jump_loc - len(word_list) - 1)
And the test corrected, is green:
def test_do_until_hard(self):
f = Forth()
f.compile(': DOUBLE 2 * ;')
f.compile(': DOUBLE_UNDER SWAP DOUBLE SWAP ;')
s = ': TEST 2 5 DO DOUBLE_UNDER 1 - DUP 0 >= UNTIL ;'
word = f.compile(s)
word.do(f)
assert f.stack.pop() == 0
assert f.stack.pop() == 64
I told you it was +/- 1, and it was. It’s always a bit confusing and counting things was never my strength anyway.
Let’s reflect and sum up:
Reflection and Summary
So despite the long period spent figuring out that I was off by one, this went well. The code in our compile-time operators is getting a bit messy even given yesterday’s long refactoring:
def compile_word_list(self, rest):
word_list = []
for word in rest:
if word == 'IF':
self.compile_conditional('*IF', word_list)
elif word == 'THEN':
self.patch_the_skip(['*IF', '*ELSE'], -1, word_list)
elif word == 'ELSE':
self.patch_the_skip(['*IF'], 1, word_list)
self.compile_conditional('*ELSE', word_list)
elif word == 'DO':
self.stack.push(('DO', len(word_list)))
elif word == 'UNTIL':
key, jump_loc = self.stack.pop()
if key != 'DO':
raise SyntaxError(f'UNTIL without DO')
until = self.find_word('*UNTIL')
word_list.append(until)
word_list.append(jump_loc - len(word_list) - 1)
elif (definition := self.find_word(word)) is not None:
...
It appears to me that yesterday’s terms won’t quite apply to today’s work, but I’m tired now and not going to deal with it. DO-UNTIL does work and is, I think, solid if not pretty. Tomorrow, I’ll look to see whether there’s a better refactoring for all this.
I have some changes of direction in mind, but I’ll just list them briefly and discuss another time:
- Change the compiler to be able to compile and run any Forth not just definitions.
- Do a REPL, Forth prompt where you can type things in.
- Provide for file input of a Forth program.
- New angle on the robot game.
For today, happy birthday to me, many happy returns. See you next time!