Wednesday, November 12, 2014

The Strange Case of the Branching Dictionary

In which our protagonist tries to convince us that the weird structure of Tali Forth's dictionary is actually an amazingly clever idea.

So the weather in Germany has finally turned horrible again, which means that I can return to indoor pursuits. Ask me again why Autumn is my favorite time of year.

Anyway. Many months ago, we left off with the promise that we'd be examining the dictionary of Tali Forth. This contains the Forth "words" that make up the language, things like DROP or LOOP.

The basic structure is simple: A linked list of entries. When we define a new word, it is added to the dictionary. When we type a word, the dictionary is searched from newest to oldest entries until it is found. Remember the flow chart in the previous entry: If a word is not found, Forth checks to see if it is a number. If that fails, it complains.

If we take a closer look at a single dictionary entry, we see it consists of two parts: A "head" and a "body". The body is the actual "payload" of code that is executed when the word is executed. For example, the DROP instruction in Tali Forth is are simply the 65c02 instructions INX INX plus a RTS at the end. The header provides stuff like the link to the next entry in the list, the string of the word ("DROP"), the length of that string, and some flags.

There are various ways to construct a Forth dictionary entry (Brad Rodriguez has an excellent explanation of what the different parts do, including examples from other Forth versions). The problems are always the same: We need a pointer to the start of the dictionary, so we know where to find the information in the header, and we need a pointer to the code in the body to execute the word the entry represents.

Of course, it would be really cool if those pointers were one and the same, right? Heh. So here is how Tali Forth solves the problem:

Ascii drawing of a the Tali Forth dictionary entry, version ALPHA 004. Including as an image for those of who insist on using fancy-pants variable space fonts instead of monospaced.

We'll get to the first two bytes -- the BRA stuff -- in a moment. The byte after that includes the flags and five bits for the length of the name string. Then, we have a pointer to the next entry in the dictionary, followed by the pointer to the end of our body. This is used for compiling short words directly into machine code. The next to fields are of variable length: The the word as an Ascii string, and the payload of code in the body itself.

Now, notice we do something really ... different: Every entry starts with a BRA instruction. This is only available on the 65c02, not the original 6502, and tells the CPU to jump ahead (or back). Here, we have it set up so it jumps to the beginning of the body.

What this means is that we can execute any Tali Forth word in the dictionary by simply jumping to its first byte. Which just so happens to be where the link from the previous entry points us to. This way, we only have to deal with one 16-bit address and don't have to read or calculate where the body begins. In Forth terms, this is our Execution Token (XT). Pretty cool, right? Well, except that we pay a hefty penalty. Every single dictionary entry is two bytes longer and takes up to four cycles longer.

In the end, I decided to go ahead with the setup because it is simpler than all the others I could think of. Remember, simplicity is a primary goal.

(What I'm more worried about is if we actually need the pointer to the end of the body, or if we can't figure out another way of figuring out where to stop compilation.)

In the source code, an entry looks like this:

Tali Forth source code for the DROP entry in the dictionary. Remember, if this looks different to you than other assembler code, it is because we use the Orphis Assembler 2.0

By the time of the next entry, we'll probably have cleaned up the code enough to have it posted on GitHub like a real project. As long as it keeps raining in Germany, that is.