In which I prematurely exit loops
DO loop is done. Now we need to implement
LEAVE. This is effectively a “go to the end of the loop”. It seems simple enough but there is a problem in that
LEAVE can occur – in fact, almost certainly will occur – inside other control structures, most likely
IF. For example:
: GD5 123 SWAP 0 DO I 4 > IF DROP 234 LEAVE THEN LOOP ;
DO puts both a
.orig and a
.dest on the control stack. The
IF puts another
.orig on, then the
LEAVE also needs to put a
.orig on, and the
THEN will try to resolve the
.orig not the
I decided to resolve this by creating a
.orig for the live and the tucking it under all the other control flow items since the
DO was executed. Here is an example. The below represents the control stack from the above code when
LEAVE is called.
control stack: <4> .dest(12) .orig(10) .orig(22) .orig(28) ^ ^ ^ ^ | | | +-- .orig for LEAVE | | +-- .orig created by IF | +- .orig created from branch in DO to the end of the loop +-- .dest to loop back to after the index test
We need to manipulate the stack to look like this:
control stack: <4> .orig(28) .dest(12) .orig(10) .orig(22)
At the end of the loop, we’ll just be left with a string of
.origs that each represent the forward jump for a
LEAVE and we just resolve them all.
This is relatively simple if we maintain a count of how many
.origs we have and how many items there are on the stack since we entered the
DO loop. The
LEAVE count is easy: in the
DO we put a count on the data stack and increment it each time we encounter
LEAVE. The second part is harder because we don’t know what was on the control stack before we encountered the
I’ve chosen a fairly generic means of achieving remembering the state of the stack when we started the
DO loop. We use the concept of a stack frame. A stack frame is merely a region of the stack relative to one of the elements on it. In practice that means there is a pointer which references a certain element on the stack and other elements may be referenced by means of an offset to the frame pointer.
Stack top +-------------------+ | Newer | | Elements | | | +-------------------+ | old frame pointer | <-- frame pointer +-------------------+ | Older elements | | |
Stack frames may themselves be stacked, for example, in the case of nested
DO loops. It is for this reason that I adopted the convention that the element pointed to by the frame pointer contains the previous frame pointer from before the creation of the stack frame. This effectively sets up a linked list of frame pointers within the stack.
To create a new stack frame, you simply push the current frame pointer onto the stack and set the frame pointer to point to this new element.
To remove a frame, you pop everything above the saved frame pointer element and then pop the saved frame pointer element into the frame pointer.
To make this work, you need to be able to convert the frame pointer (which is an
Int) to and from a stack element. For this reason, I created a protocol called
Frameable which contains functions for converting elements to and from frame pointers. If the
Element type of the stack has adopted this protocol, the stack frame functionality is automatically available.
DO word creates a stack frame on the control stack using a new primitive
.csFrame before it does anything else. It also pushes a zero
LEAVE count. At the end of
DO we have this:
stack: <1> 0 control stack: <1> .frame(old: -1)
Note that the frame pointer is initialised to
-1 which means that it the stack starts with a frame that cannot be popped without a stack underflow.
When we encounter the
LEAVE in the above example Forth code, the stacks look like this:
stack: <1> 0 control stack: <4> .frame(old: -1) .dest(12) .orig(10) .orig(22)
.dest and a
.orig for the
DO and a
.orig for the
LEAVE adds a new
.orig and moves everything after the
.frame to above it. There’s another new primitive to help us with this:
.csFrameSize which tells us how many elements are on the stack above the frame pointer.
LEAVE is compiled, the stacks look like this:
stack: <1> 1 control stack: <5> .frame(old: -1) .orig(28) .dest(12) .orig(10) .orig(22)
LOOP at the end after resolving the
IF and the
DO, we are left with
stack: <1> 1 control stack: <2> .frame(old: -1) .orig(28)
Another new primitive called
.csPopFrame restores the saved frame pointer.
The code for the above is tagged blog-1224.