I Do Forth

In which I go loopy trying to implement do loops

Do loops are control structures that require a bit more thought than the ones implemented s far. The main problem is the existence of a loop variable, or, in the case of nested do loops, multiple loop variables. We’ll deal with that in a minute. However, we need to think about the overall structure of the loop. Here is what needs to happen (note, all the saves and retrieves are considered to be destructive i.e. they are moves rather than copies):

    save indexes to return stack 
start:
    retrieve indexes from return stack
    if index has reached the end, jump to exit
    save indexes to return stack
 
    loop content

    retrieve indexes from return stack
    add one to index
    save indexes on return stack
    jump back to start
exit:
    clean up of indexes
    rest of code

There are two possible optimisations here.

  1. We could eliminate the initial save, the first retrieve and the save at the end of the loop.
  2. There’s a trick well known in compiler design that involves moving the test to the end and jumping to it immediately from the start. The version above has a conditional branch and an unconditional branch that executes for every iteration of the loop. If we move the test to the end, the unconditional branch is eliminated.

Applying optimisation 2, we get

    save indexes to return stack 
    jump to test
start:
    save indexes to return stack
 
    loop content

test:
    retrieve indexes from return stack
    add one to index
    if index has not reached the end, jump to start
exit:
    clean up of indexes
    rest of code

We can still sort of apply the first optimisation by moving the location of the test label

    jump to test
start:
    save indexes to return stack
 
    loop content

    retrieve indexes from return stack
test:
    add one to index
    if index has not reached the end, jump to start
exit:
    clean up of indexes
    rest of code

There’s a bug here though. We have an off by one error because we add one to the index before doing any iteration of the loop. It needs to be moved before the test label.

   jump to test
start:
    save indexes to return stack
 
    loop content

    retrieve indexes from return stack
    add one to index
test:
    if index has not reached the end, jump to start
exit:
    clean up of indexes
    rest of code

This is our final code. LOOP will differ from +LOOP in that instead of adding one, we will add whatever was on the stack before we retrieve the indexes. In fact, the only difference between LOOP and +LOOP is that we push 1 onto the data stack before we start.

So DO does the following:

  • create a .orig for the jump to test
  • create a .dest for the loop
  • swap the .orig and the .dest because the .orig will get resolved first.
  • Create code to push the index information onto the return stack

+LOOP does the following:

  • Create code to retrieve the indexes from the return stack
  • Create code to rotate the previous stack top to the top
  • Create code to add the new stack top to the index value
  • Resolve the .orig
  • Create code to do the test (note that this must be non destructive of the index information)
  • Resolve the .dest with a conditional branch
  • Clean up the data stack

LOOP does the following:

  • Create code to push 1 onto the stack
  • Same as +LOOP

We need two new primitives .loopToReturn and .returnToLoop to move a loop index and loop end to and from the return stack but then everything else can be constructed from existing primitives. We probably should also create primitives to implement I and J because they likely need to be fast. However, for now, we will implement them using the primitives defined above.

Note that, at some point, we may be able to make these primitives go away once we get a more generalised return stack.

The code for the above is tagged blog-1189-1.

Unfortunately, the code above has some problems. The main one is that it has to work with signed and unsigned numbers. This is fine for LOOP. We just keep adding one to the index and testing for equality with the end. It’s no god for +LOOP though, because, not only can the index jump over the end value, it can go in reverse direction too i.e. the increment might be negative. And, if the increment is negative, when we land on the end value, we need to go round again, as exemplified by these unit tests:

T{ : GD2 DO I -1 +LOOP ; -> }T
T{ 1 4 GD2 -> 4 3 2 1 }T
T{ -1 2 GD2 -> 2 1 0 -1 }T

For a positive loop increment, if the end is in the range index ... (index + loopIncrement) we need to exit the loop. Unfortunately, if the arithmetic wraps round, the end might be less than index and so might index + loopIncrement. However, we can “normalise” it by subtracting index from itself and end. Then we just need to test if normalisedEnd is in the range 0 ... loopIncrement and this will not cause a signed overflow if we use an unsigned comparison.

Given circular unsigned arithmetic, the above algorithm also works for negative increments except the test is reversed i.e. we exit the loop if the normalisedEnd is not in the range 0 ... (loopIncrement - index)

0         i            i + d                                UInt.max
|         |            |                                    |
|-----------------------------------------------------------|
     |          |                 |
     e1         e2                e3

In the above, i is the index, d is the delta; e1, e2 and e3 represent possible end indexes. Only e2 would result in the loop terminating. Subtract i from everything using wrap around unsigned arithmetic.

0         d                                                 UInt.max
|         |                                                 |
|-----------------------------------------------------------|
     |               |                     |
     e2-i            e3-i                  e1-i

Clearly, if the difference between the end and the current index is less than or equal to the delta, we exit the loop, or, to put it another way, if the difference between the end and the current index is greater than the delta (using an unsigned comparison) we carry on with the loop.

If the delta is negative we have a different scenario. Firstly, we must clearly assume signed arithmetic. It’s probably enough to ensure index is greater than or equal to end before adding the delta on but taking care of overflow situations.

The code is tagged blog-1189-2. Two of the unit tests are still failing but that is due to a signed overflow that I can’t be bothered to resolve and, in fact, I like my behaviour better.

Leave a Reply

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

WordPress.com Logo

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

Google photo

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

Twitter picture

You are commenting using your Twitter 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.