Chapter Twelve (Part 5)
|Table of Content||
Chapter Twelve (Part 7)
PROCEDURES: ADVANCED TOPICS (Part 6)
12.5.1 - Implementing Iterators Using In-Line Expansion
12.5.2 - Implementing Iterators with Resume Frames
An iterator is a cross between a control structure and a function. Although common high level languages do not often support iterators they are present in some very high level languages. Iterators provide a combination state machine/function call mechanism that lets a function pick up where it last left off on each new call. Iterators are also part of a loop control structure with the iterator providing the value of the loop control variable on each iteration.
To understand what an iterator is
consider the following
loop from Pascal:
for I := 1 to 10 do <some statement>;
When learning Pascal you were probably taught that this
i with one
i with 10
executes the statement if
i is less than or equal to 10. After executing the
for statement increments
i and compares it with
repeating the process over and over again until I is greater than 10.
While this description is semantically correct
it's the way that most Pascal compilers implement the
this is not
the only point of view that describes how the
for loop operates. Suppose
that you were to treat the "
to" reserved word as an
operator. An operator that expects two parameters (one and ten in this case) and returns
the range of values on each successive execution. That is
on the first call the "
operator would return one
on the second call it would return two
etc. After the tenth
to" operator would fail which would terminate the loop.
This is exactly the description of an iterator.
In general an iterator controls a loop. Different languages use different names for iterator controlled loops this text will just use the name foreach as follows:
foreach variable in iterator() do statements; endfor;
is a variable whose type is compatible with the return type of the
iterator. An iterator returns two values: a boolean success or failure value and a function result. As long as the iterator returns success the
foreachstatement assigns the other return value to
iteratorreturns failure the foreach loop terminates and executes the next sequential statement following the
foreachloop's body. In the case of failure the
foreachstatement does not affect the value of
Iterators are considerably more complex than normal functions. A typical function call involves two basic operations: a call and a return. Iterator invocations involve four basic operations:
1) Initial iterator call
2) Yielding a value
3) Resumption of an iterator
4) Termination of an iterator.
To understand how an iterator operates consider the following short example from the Panacea programming language:
Range:iterator(start stop:integer):integer; begin range; while (start <= stop) do yield start; start := start + 1; endwhile; end Range;
In the Panacea programming language iterator calls may only appear in the foreach statement. With the exception of the yield statement above anyone familiar with Pascal or C++ should be able to figure out the basic logic of this iterator.
An iterator in the Panacea programming language may return
to its caller using one of two separate mechanisms
it can return to the caller
exiting through the
end Range; statement or it may yield a value by executing
yield statement. An iterator succeeds if it executes the
it fails if it simply returns to the caller. Therefore
statement will only execute its corresponding statement if you exit an iterator with a
foreach statement terminates if you simply return from the iterator. In
the example above
the iterator returns the values
start..stop via a
and then the iterator terminates. The loop
foreach i in Range(1 10) do write(i); endfor;
is comparable to the Pascal statement:
for i := 1 to 10 do write(i);
When a Panacea program first executes the
it makes an initial call to the iterator. The iterator runs until it executes a
yield or it returns. If it executes the
returns the value of the expression following the
yield as the iterator
result and it returns success. If it simply returns
the iterator returns failure and no
iterator result. In the current example
the initial call to the iterator returns success
and the value one.
Assuming a successful return (as in the current example)
foreach statement assigns the iterator return value to the loop control
variable and executes the
foreach loop body. After executing the loop body
foreach statement calls the iterator again. However
this time the
foreach statement resumes the iterator rather than making an initial call. An iterator
resumption continues with the first statement following the last
executed. In the
a resumption would continue execution at the
:= start + 1; statement. On the first resumption
would add one to
producing the value two. Two is less than ten (
value) so the
while loop would repeat and the iterator would yield the value
two. This process would repeat over and over again until the iterator yields ten. Upon
resuming after yielding ten
the iterator would increment start to eleven and then return
rather than yield
since this new value is not less than or equal to ten. When the
iterator returns (fails)
foreach loop terminates.
12.5.1 Implementing Iterators Using In-Line Expansion
The implementation of an iterator is rather complex. To begin with consider a first attempt at an assembly implementation of the foreach statement above:
push 1 ;Assume 286 or better push 10 ; and parms passed on stack. call Range_Initial ;Make initial call to iter. jc Failure ;C=0 1 means success fail. ForLoop: puti ;Assume result is in AX. call Range_Resume ;Resume iterator. jnc ForLoop ;Carry clear is success! Failure:
Although this looks like a straight-forward implementation
there are several issues to consider. First
the call to
above looks simple enough
but there is no fixed address that corresponds to the resume
address. While it is certainly true that this
Range example has only one
in general you can have as many yield statements as you like in an
iterator. For example
the following iterator returns the values 1
OneToFour:iterator:integer; begin OneToFour; yield 1; yield 2; yield 3; yield 4; end OneToFour;
The initial call would execute the
yield 1; statement.
The first resumption would execute the
yield 2; statement
resumption would execute
etc. Obviously there is no single resume
address the calling code can count on.
There are a couple of additional details left to consider.
an iterator is free to call procedures and functions.
If such a procedure or function executes the
yield statement then resumption
foreach statement continues execution within the procedure or function
that executed the
the semantics of an iterator require all
local variables and parameters to maintain their values until the iterator terminates.
yielding does not deallocate local variables and parameters. Likewise
addresses left on the stack (e.g.
the call to a procedure or function that executes the
statement) must not be lost when a piece of code yields and the corresponding
statement resumes the iterator. In general
this means you cannot use the standard call
and return sequence to yield from or resume to an iterator because you have to preserve
the contents of the stack.
While there are several ways to implement iterators in assembly language perhaps the most practical method is to have the iterator call the loop controlled by the iterator and have the loop return back to the iterator function. Of course this is counter-intuitive. Normally one thinks of the iterator as the function that the loop calls on each iteration not the other way around. However given the structure of the stack during the execution of an iterator the counter-intuitive approach turns out to be easier to implement.
Some high level languages support iterators in exactly this fashion. For example Metaware's Professional Pascal Compiler for the PC supports iterators. Were you to create a code sequence as follows:
iterator OneToFour:integer; begin yield 1; yield 2; yield 3; yield 4; end;
and call it in the main program as follows:
for i in OneToFour do writeln(i);
Professional Pascal would completely rearrange your code.
Instead of turning the iterator into an assembly language function and call this function
from within the for loop body
this code would turn the
for loop body into a
expand the iterator in-line (much like a macro) and call the
loop body function on each
yield. That is
Professional Pascal would probably
produce assembly language that looks something like the following:
; The following procedure corresponds to the for loop body ; with a single parameter (I) corresponding to the loop ; control variable: ForLoopCode proc near push bp mov bp sp mov ax [bp+4] ;Get loop control value and puti ; print it. putcr pop bp ret 2 ;Pop loop control value off stk. ForLoopCode endp ; The follow code would be emitted in-line upon encountering the ; for loop in the main program it corresponds to an in-line ; expansion of the iterator as though it were a macro ; substituting a call for the yield instructions: push 1 ;On 286 and later processors only. call ForLoopCode push 2 call ForLoopCode push 3 call ForLoopCode push 4 call ForLoopCode
This method for implementing iterators is convenient and produces relatively efficient (fast) code. It does however suffer from a couple drawbacks. First since you must expand the iterator in-line wherever you call it much like a macro your program could grow large if the iterator is not short and you use it often. Second this method of implementing the iterator completely hides the underlying logic of the code and makes your assembly language programs difficult to read and understand.
12.5.2 Implementing Iterators with Resume Frames
In-line expansion is not the only way to implement iterators. There is another method that preserves the structure of your program at the expense of a slightly more complex implementation. Several high level languages including Icon and CLU use this implementation.
To start with
you will need another stack frame: the
resume frame. A resume frame contains two entries: a yield return address (that is
address of the next instruction after the
yield statement) and a dynamic
which is a pointer to the iterator's activation record. Typically the dynamic link
is just the value in the
bp register at the time you execute the
instruction. This version implements the four parts of an iterator as follows:
call instruction for the initial iterator
call instruction for the
ret instruction for the resume operation
ret instruction to terminate the
To begin with an iterator will require two return addresses rather than the single return address you would normally expect. The first return address appearing on the stack is the termination return address. The second return address is where the subroutine transfers control on a yield operation. The calling code must push these two return addresses upon initial invocation of the iterator. The stack upon initial entry into the iterator should look something like this:
As an example
presented earlier. This iterator requires two parameters
a starting value and an ending
foreach i in Range(1 10) do writeln(i);
The code to make the initial call to the
producing a stack like the one above
could be the following:
push 1 ;Push start parameter value. push 10 ;Push stop parameter value. push offset ForDone ;Push termination address. call Range ;Pushes yield return address.
ForDone is the first statement immediately following the foreach loop that is the instruction to execute when the iterator returns failure. The foreach loop body must begin with the first instruction following the call to Range. At the end of the foreach loop rather than jumping back to the start of the loop or calling the iterator again this code should just execute a ret instruction. The reason will become clear in a moment. So the implementation of the above foreach statement could be the following:
push 1 ;Obviously this requires a push 10 ; 80286 or later processor. push offset ForDone call Range mov bp [bp] ;Explained a little later. puti putcr ret ForDone:
Granted this doesn't look anything at all like a loop. However by playing some major tricks with the stack you'll see that this code really does iterate the loop body (puti and putcr) as intended.
Now consider the Range iterator itself here's the code to do the job:
Range_Start equ word ptr <[bp+8]> ;Address of Start parameter. Range_Stop equ word ptr <[bp+6]> ;Address of Stop parameter. Range_Yield equ word ptr <[bp+2]> ;Yield return address. Range proc near push bp mov bp sp RangeLoop: mov ax Range_Start ;Get start parameter and cmp ax Range_Stop ; compare against stop. ja RangeDone ;Terminate if start > stop ; Okay build the resume frame: push bp ;Save dynamic link. call Range_Yield ;Do YIELD operation. pop bp ;Restore dynamic link. inc Range_Start ;Bump up start value jmp RangeLoop ;Repeat until start > stop. RangeDone: pop bp ;Restore old BP add sp 2 ;Pop YIELD return address ret 4 ;Terminate iterator. Range endp
Although this routine is rather short don't let its size deceive you; it's quite complex. The best way to describe how this iterator operates is to take it a few instructions at a time. The first two instructions are the standard entry sequence for a procedure. Upon execution of these two instructions the stack looks like:
The next three statements in the
implement the termination test of the while
loop. When the
Start parameter contains a value greater than the
control transfers to the
RangeDone label at which point the code
pops the value of
bp off the stack
pops the yield return address off the
stack (since this code will not return back to the body of the iterator loop) and then
returns via the termination return address that is immediately above the yield return
address on the stack. The return instruction also pops the two parameters off the stack.
The real work of the iterator occurs in the body of the
while loop. The
implement the yield statement. The
build the resume frame and then return control to the body of the foreach loop. The call
instruction is not calling a subroutine. What it is really doing here is finishing off the
resume frame (by storing the yield resume address into the resume frame) and then it
returns control back to the body of the
foreach loop by jumping indirect
through the yield return address pushed on the stack by the initial call to the iterator.
After the execution of this call
the stack frame looks like:
Also note that the
ax register contains the
return value for the iterator. As with functions
ax is a good place to
return the iterator return result.
Immediately after yielding back to the
the code must reload
bp with the original value prior to the iterator
invocation. This allows the calling code to correctly access parameters and local
variables in its own activation record rather than the activation record of the iterator.
bp just happens to point at the original
bp value for the
[bp] instruction reloads
as appropriate. Of course
in this example reloading
bp isn't necessary
because the body of the foreach loop does not reference any memory locations off the
but in general you will need to restore
At the end of the foreach loop body the
instruction resumes the iterator. The
ret instruction pops the return address
off the stack which returns control back to the iterator immediately after the call. The
instruction at this point pops
bp off the stack
and then repeats the while loop.
this is a lot of work to create a piece of code
that simply repeats a loop ten times. A simple for loop would have been much easier and
quite a bit more efficient that the foreach implementation described in this section. This
section used the
Range iterator because it was easy to show how iterators
not because actually implementing
Range as an
iterator is a good idea.
 Ada and PL/I support very limited forms of iterators though they do not support the type of iterators found in CLU SETL Icon and other languages.
 Panacea is a very high level language developed by Randall Hyde for use in compiler courses at UC Riverside.
 In Panacea an iterator could also call other types of program units including other iterators but you can ignore this for now.
 Obviously this is a non-standard extension to the Pascal programming language provided in Professional Pascal.
Chapter Twelve: Procedures: Advanced
Topics (Part 6)
27 SEP 1996