Forth Next: Loops

In which I go loopy

In Forth if, while, and similar control flow constructs are not builtin but implemented. Implement them in your Forth.

http://beza1e1.tuxen.de/articles/forth.html

Since the last blog, I’ve fixed the comment unit test failure and I’ve moved stackTop from being a local variable to being a property of the Forth engine. Looking at the timed run:

Time of run: 2.371679444s, words executed: 6199400, mips: 2.613928292747812
["121393"]

it seems to be about as fast in terms of mips as before, but the run time is significantly longer. This is misleading because I changed the test program to use IF … ELSE … THEN instead of branches. The old program now gives the following results

Time of run: 1.886290887s, words executed: 4685369, mips: 2.4839058664232416
["121393"]

which represents similar performance to before, even though the stack top is a property of the Forth engine. Although accessing stackTop ought to be slower, it no longer as to be flushed when recursively calling the interpretation function. That cuts out some code. From now on, we’ll be using the new code that uses IF … ELSE … THEN because it looks like a proper Forth program and is easier to understand.

Anyway, now we need some loops. Standard Forth seems to have counted loops: (DO … LOOP) and loops with tests e.g. BEGIN … test UNTIL and BEGIN … test WHILE … REPEAT. The loops with tests will be easiest because we don’t have to deal with loop counters. So, below is the control flow that needs to be compiled.

The UNTIL loop is easiest. All we need to do is push the destination (a .dest) onto the control flow stack when we encounter the BEGIN and branch back to it if the top of stack is all zeros when we encounter the UNTIL.

The WHILE … REPEAT loop is more tricky. BEGIN causes a .dest to be placed on the control flow stack as before. The WHILE needs to push a .orig onto the control flow stack so it knows where to branch to if the test is false. Then the REPEAT needs to resolve both the .orig and the .dest in that order, because the .orig will be at the top of the control flow stack. Or alternatively, the WHILE needs to put the .orig underneath the .dest since there seems to be an expectation that you can put multiple WHILEs in and have a ELSEs to consume the extras. See this code from the ANS test suite, for example:

T{ : GI5 BEGIN DUP 2 > WHILE 
      DUP 5 < WHILE DUP 1+ REPEAT 
      123 ELSE 345 THEN ; -> }T 

The REPEAT needs to resolve the destination (where the BEGIN was) and do an unconditional branch to it. In this respect, it is just like an UNTIL. It then needs to resolve the .orig from the WHILE.

The code for this is tagged blog-1094.

During the course of implementing the above, I made some other changes. The most significant is the addition of a “branch if zero” conditional branch. The conditionalBranch I had created was the wrong way around for every single control structure implemented so far. Adding 0=branch saved a lot of extra code in every control structure logically inverting the test results.