Forth: Getting Weird
I read about how IF works according to Loeliger. Weird. How should we do it?
Before we begin, a brief report on some small changes I made while you were away. I improved the tests by making a helper method:
class TestCompile:
def define_primaries(self):
lexicon.append(PrimaryWord('+', lambda: stack.append(stack.pop() + stack.pop())))
lexicon.append(PrimaryWord('-', lambda: stack.append(-stack.pop() + stack.pop())))
lexicon.append(PrimaryWord('*', lambda: stack.append(stack.pop() * stack.pop())))
lexicon.append(PrimaryWord('/', lambda: stack.append(1/(stack.pop() / stack.pop()))))
lexicon.append(PrimaryWord('DUP', lambda: stack.append(stack[-1])))
lexicon.append(PrimaryWord('DROP', lambda: stack.pop()))
lexicon.append(PrimaryWord('OVER', lambda: stack.append(stack[-2])))
lexicon.append(PrimaryWord('SWAP', lambda: stack.extend([stack.pop(), stack.pop()])))
lexicon.append(PrimaryWord('SQRT', lambda: stack.append(math.sqrt(stack.pop()))))
I added some words, ‘-‘ and ‘/’. Note that their definitions are a bit odd, because of the limitations of Python lambdas, which can contain only a single statement. Thanks, Guido. I suppose there might be a way to do better than what I did, but I couldn’t think of it.
I wrote tests for the new arithmetic and for DROP and OVER. All good.
Last night, after FGNO1, I read in Loeliger2 about how to do ‘IF’. It’s rather interesting. Let me explain. No, there is too much.
- Let me sum up:
-
Loeliger’s compile mode looks up words by their text names and, generally speaking, appends the address of their code into the program, much as our code appends the index of the word into our SecondaryWord’s list. But some words, like ‘IF’ are “immediate”. Those also have code in them, but instead of putting that address into the output, the compiler executes the word’s code immediately.
-
The ‘IF’ code appends a word ‘*IF’, and its code link. Then it leaves a blank cell in the output code, and puts the address of that blank cell on the stack. (Yes, on the stack!). When, later, an ‘ELSE’ or ‘THEN’ is encountered, they are also immediate, and what they do is pop the address off the stack, subtract that from the current address in the code, and stuff that number into the blank cell by the ‘*IF’.
-
When, at run time, the ‘*IF’ is encountered, it expects to find a flag on the stack, and if it is true, ‘*IF’ just drops on through. But if it is false, the ‘*IF’ picks up its formerly blank cell, and adds it to the current execution address, which causes it to branch to the location of the ‘ELSE’ or ‘THEN’.
-
The ‘ELSE’ immediate works similarly to the ‘IF’, leaving a patch cell and compiling a ‘*ELSE’. The ‘THEN’ immediate patches, but does not compile anything, as no action is needed at run time, just the branch, which will be back to the code either after the IF or after the ELSE.
Wild, huh? Such were our ways back in the days of writing things in assembler. We’ll try to be a bit more modern here. Here’s my rough plan, not necessarily in order:
- Create a new class whose instances are the Forth system, containing stack, lexicon, and whatever we may need;
- Recognize immediate words, either from flags in the lexicon or other means;
- Our ‘IF’ immediate will work similarly to Loeliger’s, probably compiling a similar ‘*IF’, but with a member variable that will get the line number to branch to.
There are options and details to be worked out. We’ll need access in the immediates to the code list and probably the current index in it. And I think that our words will need that access, so that the few that branch can branch.
This is somewhat ambitious, it seems to me. We’ll begin by creating a class to hold the stack and lexicon and such. I think I’ll try to refactor the latest test class TestCompile to use a new Forth class.
Here’s a typical test from that file:
def test_compiler_hyp(self):
clear()
self.define_primaries()
forth_compile(': SQUARE DUP * ;', lexicon)
forth_compile(': HYPSQ SQUARE SWAP SQUARE + ;', lexicon)
forth_compile(': HYP HYPSQ SQRT ;', lexicon)
stack.extend([3, 4])
find_word('HYP', lexicon).do(lexicon)
assert stack.pop() == 5
And here is our compiler:
from forth import stack, lexicon
from tests.test_first_classes import PrimaryWord, SecondaryWord, clear
def forth_compile(text, lex):
words = text.split()
match words:
case ':', defining, *rest, ';':
word_list = [ix for word in rest if (ix := find_word_index(word, lex)) is not None]
lex.append(SecondaryWord(defining, word_list))
case _:
raise SyntaxError(f'Syntax error: "{text}". Missing : or ;?')
def find_word_index(word, lex):
for i in range(len(lex)):
if lex[i].name == word:
return i
raise ValueError(f'cannot find word "{word}"')
def find_word(word, lex):
return lex[find_word_index(word, lex)]
Let’s just enclose those methods in a class, making them receive self
and all that. I think we’ll move the define_primaries
in there as part of the init. If this goes as I intend, all the tests in this file will break for a while and then all work, with minor mods. Let’s find out.
I rather quickly edit to this:
class Forth:
def __init__(self):
self.stack = []
self.lexicon = []
self.define_primaries()
def define_primaries(self):
lex = self.lexicon
stack = self.stack
lex.append(PrimaryWord('+', lambda: stack.append(stack.pop() + stack.pop())))
lex.append(PrimaryWord('-', lambda: stack.append(-stack.pop() + stack.pop())))
lex.append(PrimaryWord('*', lambda: stack.append(stack.pop() * stack.pop())))
lex.append(PrimaryWord('/', lambda: stack.append(1/(stack.pop() / stack.pop()))))
lex.append(PrimaryWord('DUP', lambda: stack.append(stack[-1])))
lex.append(PrimaryWord('DROP', lambda: stack.pop()))
lex.append(PrimaryWord('OVER', lambda: stack.append(stack[-2])))
lex.append(PrimaryWord('SWAP', lambda: stack.extend([stack.pop(), stack.pop()])))
lex.append(PrimaryWord('SQRT', lambda: stack.append(math.sqrt(stack.pop()))))
def forth_compile(self, text):
words = text.split()
match words:
case ':', defining, *rest, ';':
word_list = [ix for word in rest if (ix := self.find_word_index(word)) is not None]
self.lexicon.append(SecondaryWord(defining, word_list))
case _:
raise SyntaxError(f'Syntax error: "{text}". Missing : or ;?')
def find_word_index(self, word):
lex = self.lexicon
for i in range(len(lex)):
if lex[i].name == word:
return i
raise ValueError(f'cannot find word "{word}"')
def find_word(self, word):
return self.lexicon[self.find_word_index(word)]
I pick an easy test and make it work:
def test_minus(self):
forth = Forth()
forth.stack.extend([4, 2])
forth.find_word('-',).do(forth.lexicon)
assert forth.stack.pop() == 2
We notice a glitch here, namely that the Word classes expect that do
will pass them a lexicon. We’ll want to pass them the Forth instance, I expect, for access to the other nifty things in there. That will mean that we have to fix up the other tests that use those classes.
In fact, I’m sort of wondering how these are working even now. Ah, they aren’t. Let me change that test so that it doesn’t have the answer already on stack.
def test_minus(self):
forth = Forth()
forth.stack.extend([5, 2])
forth.find_word('-',).do(forth.lexicon)
assert forth.stack.pop() == 3
It still runs! Oh … I understand … the PrimaryWord instances are given lambdas that are bound to the stack in the Forth instance. We’re good.
I’ll fix up the rest of the tests. Quickly done, all entirely rote. Commit: compiler moved to new Forth class.
Reflection
So that went very smoothly. We’re about an hour in and have a new class and probably 1500 words of article written, so that’s quite nice. The changes needed all consisted of just sending the messages to a Forth instance, and removing lexicon parameters from the calls that formerly had them. The squiggles in PyCharm pointed to all the changes, which was certainly helpful.
I think the next step will be to pass the Forth instance to the Word classes. That will break the tests in at least one other file. No worries, we’ll fix them up. I have a cunning plan.
After review of the play, the tests in the other file are redundant and will be removed.
That results in that file containing only the PrimaryWord and SecondaryWord classes. We’ll rename the file accordingly, to word.py.
We’re down a few tests but all green. Commit: remove redundant tests, rename file. There’s a file with a stack and lexicon list defined in it. That can go. Commit: remove useless forth.py file.
Let’s move our Forth class to a new file, named—what else—forth.py. Commit: move Forth class to forth.py.
Summary
I’ve been at this a couple of hours, with some interruptions for other purposes, so I am inclined to take a break. We’re at a perfect breaking point, with a new Forth class handling computation, and our Word classes using it. There will be more, but this is enough.
Because of my learning process, we created the Forth class a bit later than I would have preferred. It just felt too speculative to create it in anticipation of need, although I’m sure it would have gone fine. I just wasn’t ready. Refactoring it in later was easy enough but did require changing or removing all our recent tests. There are still some earlier tests that just practiced manipulating stacks and such, that weren’t related to the Word classes nor to the eventual Forth class.
We were at most two or three days late creating the class. Not a big deal. We’d have a bigger problem if we had waited weeks or months to notice the issue.
I think we’re set up well for beginning to work on the conditionals and looping. I foresee creating some small helper classes to support the stack, lexicon, and perhaps a new one to help in dealing with the branches we’ll need for the new operations. We’ll see.
I have a secret reason for wanting a stack class. I have so far been able to create all my primary Words using lambda and I can’t think of a way to do the ROT with lambda. ROT moves the third item on the stack to the top. If there’s a way to do that in one statement using list operations, I haven’t been able to think of it.
Unless … we could do it with slices … must think about that.
Anyway, all that is for next time. See you then!
-
Friday Geeks Night Out, our weekly Tuesday evening Zoom session. ↩
-
Threaded Interpretive Languages. Please chip in at the Archive, if you can. ↩