Where Is my Skip?
If we’re to be able to define compiler words with colon definitions, we’ll need better access to the word under construction. I see options, vaguely. And I need information. Design musing here, little more. TL;DR may apply. We have an amazing interlude. We end with a Dangerously Clever Idea.
The objective is itself dubious: do we really need to be able to define compiler words in Forth? But it is an interesting challenge, if nothing else.
The issue I’m struggling with has two aspects:
-
When compiling something like an IF-ELSE-THEN or DO-LOOP, the code needs to execute a conditional branch, forward in the case of IF-ELSE-THEN, backward in the case of DO-LOOP. This is managed by the words that occur later fixing up locations left blank, and expected to contain the number of words to skip.
-
When running those constructs, whatever code is in them needs to be able to fetch the amount to skip from wherever the fix-up left it, and it needs to be able to optionally skip over that fix-up if it was placed in the word definition.
The conventional way is in fact to leave a cell in the word open and to paste in the number of cells to skip, forward or backward. There are, of course, other ways we could do it.
Just now, all this is done with custom-made implementations of IF-ELSE-THEN and DO-LOOP, with associated run-time words *IF, *ELSE, *THEN, *DO, and *LOOP. Let’s look at DO in a bit more detail.
def _define_do_loop(self):
def _do(forth):
forth.compile_stack.push(('DO', len(forth.word_list)))
forth.word_list.append(forth.find_word('*DO'))
def _loop(forth):
key, jump_loc = forth.compile_stack.pop()
loop = forth.find_word('*LOOP')
forth.word_list.append(loop)
forth.word_list.append(jump_loc - len(forth.word_list))
self.append(PrimaryWord('DO', _do, immediate=True))
self.append(PrimaryWord('LOOP', _loop, immediate=True))
We have a stack for the compiler, and currently we stack a python sequence pair on it, naming the word we are compiling, and, in the case of DO, the current length of the current word, which is still being built. When we compile LOOP, we pull out the pair, not checking it, we notice, so why save the key? We compile a *LOOP word and follow it with the distance to jump back, if we do jump back, namely the position of the *DO.
(As usual, plus or minus one, whatever it takes to work. We need a better way of dealing with when we snapshot the length of the word so that the math can always be the same.)
The word *DO is defined in Forth, an achievement from a couple of days ago:
forth.compile(': *DO SWAP >R >R ;')
DO is entered with stack containing loop-limit and starting-index, with the index on top. DO pushes those two value to the return stack, with the index again on top, thus the SWAP. While the loop runs, we’ll keep a running limit, index pair on top of the return stack, as we see in *LOOP:
def _star_loop(forth):
beginning_of_do_loop = _next_word(forth)
index = forth.return_stack.pop()
limit = forth.return_stack.pop()
index += 1
if index < limit:
forth.return_stack.push(limit)
forth.return_stack.push(index)
_active_word(forth).skip(beginning_of_do_loop)
def _next_word(forth):
return _active_word(forth).next_word()
def _active_word(forth):
return forth.active_words[-1]
*LOOP is a primary word, so it does not change execution to a new word, so next_word is in fact the empty space that we filled in up in LOOP so long ago. The _star_loop primary pops the index and limit, updates the index and if index < limit, pushes the limit and new index back onto the return stack, and skips back to the beginning location. (If index >= limit, next_word has consumed the integer skip amount, and we have removed the values from the return stack, so code just carries on with whatever is next.)
Now we can consider the problem of whether we could make *LOOP not a primary word, but a secondary. If we were to do that, the current word would still contain the skip value after what’s inserted for *LOOP, but since *LOOP is now assumed to be a secondary word, when it runs, its next_word would refer to the word containing the *LOOP definition, not the word containing the DO-LOOP we’re running.
Now, it seems to me that the secondary-style *LOOP “knows” that the value it wants to skip is down in the word it was called from, and we do have a stack of active words, so we could do something like fetch the preceding word on the active word stack, fetch its next word, incrementing its program counter, and then we would have the value we need.
Then what would we do? Ah. We’re assuming that we can get at the word that called us. Therefore, if we were able to get its next_word, we can also tell it to skip. Having done that, we could blissfully return from *LOOP, reinstating the updated calling word, which would do the right thing.
Interlude
Let me call your attention to the most amazing juggling video I have ever seen, The Triangle by Michael Moschen.
I feel like I am trying to do that kind of juggling here, when I think about how these words might work, and, frankly, my Forth-juggling mind is not up to Moschen’s standards. I find these levels to be difficult to think about.
When I find my code difficult to think about, my first resort is always to think harder. This sometimes works, and very often does not. It is quite difficult to force oneself to be more intelligent than one is. As Chet puts it, it’s a bit like advising yourself to “be taller”.
My next resort, because I’m not very clever, is too often to keep on digging, writing more and more complex code that I then try to debug. This sometimes works, but always takes a long time, and rarely leads to code that one could really be proud of.
My next resort, and the one that I try to skip to, missing out the “be taller” and “just dig, there might be gold here” ones, is to observe that if something in my programming is hard to understand, the code is not helping me as much as it might. The objects are not helping me as much as they might. Then I try to work out how the code might be more helpful.
I think the key here is in the “active_words” notion. It’s not very robust now: it goes like this:
A SecondaryWord has, among its members, a word list and a program counter pc:
class SecondaryWord:
def __init__(self, name, word_list, immediate=False):
self.name = name
self.words = word_list
self.immediate = immediate
self.pc = 0
When the word is being executed, it calls forth.begin, does its contained words, and calls forth.end:
class SecondaryWord:
def do(self, forth):
forth.begin(self)
self.pc = 0
while self.pc < len(self.words):
w = self.next_word()
w.do(forth)
forth.end()
The begin and end stack the word on Forth’s active_words:
class Forth:
def begin(self, word):
self.active_words.append(word)
def end(self):
self.active_words.pop()
The Forth class does not use this stack, but the “skipper” words do, as we saw above, where we tell the current active word to do next_word and skip. That code is, of course, in SecondaryWord:
class SecondaryWord:
def next_word(self):
word = self.words[self.pc]
self.pc += 1
return word
def skip(self, n):
self.pc += n
Just as one would suspect, those two methods update the program counter pc, and of course next_word returns the word, which is the one with the skip integer in it, but which could in principle be anything.
We must talk about about how a “real” Forth might work. I do not know how a “real” Forth would do this, but we know some general things.
Forth contains words that return the addresses of its key operational variables, and it has operators ‘@’ and “!”. Given an address on the stack,, @ pops that and pushes the contents of that address onto the stack. Given a value and an address on the stack, ! stores the value at the address.
Suppose there was a word PC that pointed to the program counter. Then PC @ @ would fetch whatever the program counter was pointing to, which, during execution of a primary word, would be the next word. And this code:
PC @ 1 + PC !
Would increment the program counter by one and store it back into the program counter.
We don’t need that word, as far as I know. But suppose we had a similar word, 2PC, that instead of the current program counter, gave us access to the program counter in the word that called us. Could we then program something like our *LOOP in Forth?
I can’t quite make the balls come back when I bounce them. And we don’t quite have the ability to return an address anyway, much less increment it.
One More Thing
“Real” Forth systems tend to keep the words in a single long array, one after another, linked together with pointers. That means that the program counter is an address into that single array and it gets fiddled a bit when entering and leaving a word, depending on what is compiled into that word.
Possibly, if our words were all in a single cell-by-cell array, we could better represent a program counter, and better stack it and restore it as words execute. That might make it easier to reach back one word to adjust its program counter.
An Experiment
Let’s see if we can implement something like 2PC. We do not have @ nor !, nor do we have any variables yet, so we’ll have to do something a bit different. Let’s do 2PC@, a word to produce the PC of the second word on the active words list.
class Lexicon:
def define_skippers(self, forth):
def _2_pc_at(forth):
return forth.active_words[-2].pc
...
self.append(PrimaryWord('2PC@', _2_pc_at))
...
And we can test it, something like this:
def test_2_pc_at(self):
f = Forth()
s = ': TEST 2PC@ ;'
f.compile(s)
s = ': FOO 3 4 + TEST 10 20 + ;'
f.compile(s)
f.compile('FOO')
assert f.stack.stack == [7, 6, 30]
This test runs. I pasted in the 6 because it’s what came back. Let’s see if we can determine why it is 6.
*# 3 *# 4 + TEST *3 10 *# 20 +
0 1 2 3 4 5 6 7 8 9 10
That’s what FOO will have compiled to. So since we call next_word to get the word to execute, when a word is executing, the PC is already pointing at the next cell.
Therefore, 6 is in fact correct.
Dangerously Clever Thinking
Suppose we had an class named Address. And suppose that we compiled @ to send at to the item on the top of the stack and push the result to the stack and bang to pop a value from the stack and send it to the Address. And suppose we programmed 2PC to place a PCAddress instance on the stack such that:
class PC_Address(Address):
def __init__(self, word):
self.word = word
def at(self):
return self.word.pc
def bang(self, value):
self.word.pc = value
I think we could make that work, if we were fresh. It might make sense, with a bit more thinking. Let’s sum up before I start trying that. I’m tired from all this thinking.
Summary
What we have here is an example of what I call Design Thinking. If you were here with me, it would be a conversation. We would probably draw some pictures on cards or something like that. We’d bat ideas back and forth, and it would go faster than it goes with just me and my rubber duckie. And we might even have come up with an experiment earlier, when you asked me to quit speculating and show you how it works.
But we come out with a tiny experiment showing that we can access the previous word and its program counter, which opens the door to some kind of Forth words that do what we need. 2PC@ is probably not a desirable word, but if we allow for an Address type on the stack, we can probably make @ and ! work. And then we just need a few special words to access whatever stacks we actually keep for things.
Maybe. I am feeling good about this. If you read through to the end, I admire you and have a bit of sympathy for what you’ve just been through. It wasn’t that bad for me: I’m used to starting confused and becoming less so, but reading my maundering is probably not an ideal way to learn what I’m thinking. It’s just the only way we have.
I think we have a fun experiment coming up for next time. I hope you’ll join me then!