Forth Next: Loops

In which I go loopy

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

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

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 IFELSETHEN instead of branches. The old program now gives the following results

Time of run: 1.886290887s, words executed: 4685369, mips: 2.4839058664232416

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 IFELSETHEN 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: (DOLOOP) and loops with tests e.g. BEGINtest UNTIL and BEGINtest WHILEREPEAT. 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 WHILEREPEAT 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:

      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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.