It's all been a bit "jazz improv" recently as we fought to get ourselves to 100% coverage of z80 opcodes. Hopefully we are now back on track as we queue up /bmad-bmm-create-story 5.1 - finally, the elusive comments!
We kick off development with /bmad-bmm-dev-story 5.
The last sprint (5.0) was a survey to discover how good our z80 opcode coverage, and the results were not so great, with only 86% opcode coverage. So we created a new urgent story story to fix the omissions (5.0.5) and scheduled it for immediate execution.
Implementation
The previous sprint marked the end of epic 4 ("let's add an assembler!"), so I held a retro with the LLM dev team to get a few things off my chest before we move on:
* the LD, register ordering issue was annoying and could have been
There's both an annotated and an un-annotated version in the 'examples' folder, because I just realised that we've come this far without implementing comments... it's not even in the plan! We'll address that in the next retro, which is coming up as we're now at the end of Epic 4.
In this sprint we'll be getting the remainder of the z80 opcodes. These are the "extended" opcodes prefixed by 0xcb, 0xdd , 0xed and 0xfd bytes.
The 0xcb set gives us all of the bit set/clear/test instructions, as well as a few shifts and rotates.
It's an entire sprint of work that we had anticipated, but it's worth nailing this down now before we get to 4.4 which introduces all the extended opcodes, including all the indexed addressing modes, bit operations, and IO. The old scheme wouldn't have coped.
Implementation and code review went smoothly, so let's carry on where we left off.
# looks slightly different:
The assembler is now able to warn you if you forget a #:
There are a bunch of new utility routines for our new tag scheme:
And our condition words get compiled into tags like this:
We also gained ADD,, SUB,, AND,, XOR,, OR, and CP, which all share the same implementation:
RET,, CALL,, JP, and JR, now have full implementations. The DW and DB words got updated to handle the new tagging scheme also.
Testing
Let's take it out for a spin! We'll use our new words to write this definition:
\ >upper — convert ASCII lowercase to uppercase, in Z80 machine code.
CODE >upper ( c -- C )
LABEL done \ forward-reference label (declared before opcodes)
A C LD, \ A = character (low byte of TOS)
97 # CP, \ compare A with 'a'
CS done JR, \ carry set → below 'a', skip conversion
123 # CP, \ compare A with 'z' + 1
NC done JR, \ no carry → above 'z', skip conversion
32 # XOR, \ toggle bit 5: lowercase → uppercase
done FIX \ ← both JR, targets resolve here
C A LD, \ store result back in C (low byte of TOS)
NEXT,
END-CODE
\ Try it:
104 >upper EMIT \ h → H
90 >upper EMIT \ Z → Z (already uppercase)
53 >upper EMIT \ 5 → 5 (not a letter)
In this sprint we'll be getting the bulk of the z80 opcodes including 16 bit loads, conditional jumps, CALL and RET.
We /bmad-bmm-create-story 4.3 to kick things off. Whilst creating the story the agent noted that we have a namespace clash: we can't use C
The more contemporary CollapseOS has quite a peculiar assembler architecture, and for labels they also use the VALUE approach, but with a bunch of special Forth words for using them as a backwards reference (BR) , forward reference (FJR) and for setting them LSET.
To avoid using dict memory in compilation targets, we predeclare label variables here, which means we have a limited number of it. We have 3: L1, L2, L3.
You can define your own labels with a simple "0 VALUE lblname", but you have to do so before you begin spitting opcodes.
It's better, but it's still a bit clumsy. But there are some good ideas we can swipe.
In the end, we came up with this:
a LABEL word that declares a label name, must be start of CODE block
LABEL foo makes foo a plain-old-Forth word that knows how to handle itself (more later)
to define a label we use a new FIX word. foo FIX means "label foo now points to this memory location"
new words like foo get cleaned up during END-CODE so that the system dictionary isn't poluted. They are local to this CODE block.
The onus is on the user to remember to pre-declare labels and to FIX them precisely once, but both of these are enforceable by the interpreter.
I also like that you end up with a mini declarations block at the start of the code block:
I am also particularly pleased with the choice of the word FIX: it has a natural double meaning that fits perfectly. "Fix this label to the current position" and "fix up any pending forward references". Both meanings are simultaneously true whenever you call it, which is exactly the kind of semantic compression Forth is all about.
Best of all, we didn't introduce any hacky nonsense into INTERPRET, one of the most highly used words in the whole interpreter, avoiding a guaranteed source of regressions in the future.
After 4 or 5 design iterations, we could finally let development proceed. Code review identified the usual test gaps, and a bunch of copypasta that was quickly refactored.
assembler.asm
LABEL is the big new word in this file. It's a big routine, so I'm not going to paste it all here, but here's the header:
LABEL does a lot of work:
it creates a "label slot" in the dedicated label sub-dictionary and temporarily redirects HERE to point to the new entry
it writes a code body for the new word that will push the word's "label tag" onto the stack
it remembers a bunch of dictionary hash bucket state so that it can unlike itself on END-CODE
it links its definition into the hash bucket chains so that the word can be located by FIND.
it restores HERE, which hasn't changed because the system dictionary is unmodified.
FIX is a little more succinct:
FIX pulls a "label tag" from teh parameter stack (previously pushed there by the invocation of a label word). It uses the tag to find the slot for the label, and sets its status to resolved with an address equal to HERE. If there are any outstanding "fixups" for the label (a "fixup" is an opcode that referenced the label before it was FIXed) then those are relocated.
Now's probably a good time to mention some limitations of our implementation. Each CODE block:
can have a maximum of 16 labels
can have a maximum of 32 fixups
Here's some example code:
CODE TBLDEMO
LABEL OVER
OVER JR,
1 DW,
2 DW,
3 DW,
OVER FIX
NEXT,
END-CODE
and here it is in action:
The JR word takes a target off the stack that is either a label reference or a 16 bit address literal. It emits the relevant opcode, and if it's a label reference and the label is unresolved it queues a "fixup" for when the label is finally FIXed:
DB is the classic "define a byte":
and DS is the classic "define space":
DW is a little more complex, because unlike DB it will accept either an immediate constant or a label tag on the top of the stack, which lets you do things like:
Of course, the label might be unresolved, in which case a "fixup" for it needs to be queued.
Finally we have the innocuous looking EQU:
EQU has an important restriction: you can only use it outside code blocks. You may think I've taken leave of my senses, but the usage is quote manageable:
EQUs are still close by, just not in the code block. The reason is, they are implemented using the standard Forth CONSTANT machinery, which compiles words, and we don't want Forth words in the middle of our pure, unsullied machine code - it's the same problem that labels faced, but here we can solve it by simply moving EQUs (which are constant anyway) out of the CODE block, and then we don't need all the intricate side-dictionary/fixup mechanisms that labels required.
The interpreter will warn you if you forget the rules:
Not gonna lie, this was the hardest design challenge in AntForth to date. What started as simple whimsy ("just add labels!") turned out to be quite problematic.
The difficulty is in reconciling the sort of two-pass assembler label behaviour that we're used to (think sjasmplus) with
Many original Forths included an inline assembler for their host platform (or even for some other target platform) - one of the reasons that Forth was so popular for bringing up new hardware.
We're going to do the same thing, and we'll base our implementation on
The previous blog post marked the end of epic 3 development, so the "team" had another retro and we all agreed that everything had gone swimmingly. Next up is a built-in assembler! This was a crucial feature of early Forths and was
one of the main reasons Forth
compiler.asm
First up, we have COMPILE, which does the same thing as , from memory.asm - in fact here they are side by side:
The reason for the duplication is that the ANS Forth spec makes a specific distinction between the two: , is a general-purpose memory store ("compile
Last time we had a lot of fun discovering how Forth's simple primitives can be combined to produce sophisticated indefinite loops. This time we'll look at the definite loops, where you know ahead of time how many iterations of the loop there will be.
We start
"sequence": group sequences of code so that they act like and single statement
"selection": decide whether to execute a block based on the state of the program
"iteration": a block can be executed repeatedly until the program reaches a certain state.
We are all over "sequence", but a bit lacking in "selection" and "iteration": this sprint will start to address those shortcomings!
We kick off with a /bmad-bmm-create-story 3.3 and review the story document. The plan is to implement:
IF/THEN: basic conditional
IF/ELSE/THEN: alternating conditional
BEGIN/UNTIL: basic indefinite loop
BEGIN/WHILE/REPEAT: variation on our basic indefinite loop
nested conditional statements
error checking: these are all IMMEDIATE words so they can only be used in compile mode, not interpret mode
Implementation and code review proceed without drama. Let's look at what we have.
control_flow.asm
In this file we have IF, ELSE and THEN:
IF / THEN / ELSE
IF is an immediate wordDEFIMMED "IF": it's used at compile time to help compile a new word, but it executes its own definition right then and there. So the DW instructions you see here aren't being compiled into the new word, they are being executed at compile time.
Here's the dilemna that IF faces:
When Forth is compiling a word and it hits an IF then if the value in TOS is TRUE the execution path is obvious: execute the following word. BUT if the value in TOS is FALSE, Forth needs to jump forward to after the THEN, but the position of the THEN depends on the number of words in Words..., and while the interpreter's sat looking at the IF it doesn't yet have any idea how big a jump that is.
This is also the reason why you can only use branching words in compile mode and not in interpret mode.
So it does something sneaky: it pushes a placeholder value of zero, pushes the address of that placeholder on to the parameter stack, and leaves it to THEN to alter ("patch" as Forthfolk like to call it) the placeholder, because THEN knows where the falsey code is.
So the code above does this: IF pushes the address of ?BRANCH onto the parameter stack with LIT, then uses COMMA to compile it into HERE. Then it calls the HERE word to get the next free compile slot in TOS. Then it compiles a literal 0 placeholder with w_LIT_cf, 0 - this placeholder will be rewritten ("patched") later, and the address left in TOS tells that later entity where to patch.
A quick recap on a couple of important words:
LIT: takes the next value in the thread and pushes it into TOS
?BRANCH: takes the next value in the thread, treats it as an offset and if the value in TOS is FALSE it adds it to the current IP.
BRANCH: takes the next value in the thread, treats it as an offset and adds it to the current IP unconditionally.
So after IF runs, the definition being compiled contains [?BRANCH][0] and HERE has advanced past both cells.
The address of that [0] placeholder is left on the compile-time stack — it's a forward reference that THEN (or ELSE) will patch later.
Why's it on the stack? Because that provides an easy way to nest IF...THEN statements as deeply as you please - memory permitting. The first THEN pops the stack, which is guaranteed to be the address of the placeholder for the matching IF.
THEN resolves IF's forward reference. It calculates offset = HERE - fwd-ref and writes it back into the placeholder that IF left. At runtime, when the ?BRANCH fires (flag was FALSE/zero), it reads that offset from the cell and computes:
new_IP = offset_cell_addr + offset
= fwd-ref + (HERE - fwd-ref)
= HERE ← which is right after the IF clause
So the branch lands at whatever was compiled after THEN.
ELSE is a combination of the two, and has the same problem two times over:
ELSE does two things in one word:
Compile an unconditional BRANCH + placeholder (for the true clause to skip over the else clause)
Resolve IF's forward reference to point here (start of else clause)
Remember that ?BRANCH branches if the condition is FALSE. Mnemonic: "if TRUE do the next bit".
BEGIN/UNTIL
In the same file we have BEGIN, UNTIL, WHILE and REPEAT.
BEGIN is the easy one:
It's just marking a backwards jump target by pushing HERE into TOS. It just remembers where we are in the dictionary so that UNTIL or REPEAT can jump back here.
UNTIL compiles a ?BRANCH which will branch if TOS is false. To do that it pushes its own HERE address, subtracts from the (earlier) address that is in TOS (from BEGIN) to compute a jump offset.
The offset is negative because we're jumping backward. At runtime:
[JP DOCOL]
[LIT][0]
[LIT][1] ← begin-addr points here
[+]
[DUP]
[LIT][5]
[=]
[?BRANCH][neg-offset] ← jumps back to begin-addr when FALSE
[EXIT]
So this code counts 0→1→2→3→4→5, loop exits when 5 = is TRUE.
WHILE/REPEAT
Finally we have WHILE and REPEAT which are used like this:
BEGIN
Words1...
condition
WHILE
words2...
REPEAT
If you picture Words1... as empty for a moment, this is like BEGIN...UNTIL except that now we're testing the condition at the top of the loop rather than at the bottom, and the loop executes Words2.... This is how it's normally used, but Words1... can be as long as you please, giving you a loop that loops over Words1... and then Words2... effectively allowing you to place the condition anywhere in the loop body that you like. Crazy stuff.
WHILE looks like this:
Like IF, it compiles ?BRANCH with a placeholder — but this forward reference will be patched by REPEAT, not THEN.
The SWAP`` at the end puts begin-addr`` back on top so REPEAT can grab it first for the backward jump. The stack ends up as ( while-fwd begin-addr ).
REPEAT looks like this:
REPEAT does two things — the backward jump and the forward patch.
The backward BRANCH sends execution back to the top of the loop (begin-addr). Then it patches WHILE's ?BRANCH placeholder so that when the condition is FALSE, it jumps forward to just past the REPEAT — exiting the loop.
BEGIN...WHILE...REPEAT is used like this:
: TSUM 0 5 BEGIN DUP 0 > WHILE SWAP OVER + SWAP 1 - REPEAT DROP ;
Its compiled form looks like:
[JP DOCOL]
[LIT][0]
[LIT][5]
[DUP] ← begin-addr points here
[LIT][0]
[>]
[?BRANCH][fwd-offset] ← WHILE compiled; REPEAT patched fwd-offset
[SWAP]
[OVER]
[+]
[SWAP]
[LIT][1]
[-]
[BRANCH][back-offset] ← REPEAT compiled; jumps to begin-addr
[DROP] ← fwd-offset lands here (loop exit)
[EXIT]
When counter reaches 0 → ?BRANCH takes the forward jump past REPEAT
DROP removes the zero counter, leaving the sum (15)
In summary:
Structure
Test when?
Loop when...
Exit when...
BEGIN/UNTIL
Bottom
condition FALSE
condition TRUE
BEGIN/WHILE/REPEAT
Top
condition TRUE
condition FALSE
That was an exceedingly long post! Sorry about that: I was keen to demonstrate the sort of complexity and elegance of which Forth is capable, simply by stringing quite basic operations together in creative ways.
Dijkstra teaches us that in order to reach Structured Programming enlightenment we need:
* "sequence": group sequences of code so that they act like and single statement
* "selection": decide whether to execute a block based on the state of the program
* "iteration": a block can
This story is another exciting one, because it will significantly extend AntForth's capabilites by giving it new defining words VARIABLE, CONSTANT and DOES>.
What's a defining word?
A defining word is simply a word that lets us define new words of our own. So far,
