forloop from Pascal:
for I := 1 to 10 do <some statement>;When learning Pascal you were probably taught that this statement initializes
iwith one, compares
iwith 10, and executes the statement if
iis less than or equal to 10. After executing the statement, the
iand compares it with 10 again, repeating the process over and over again until I is greater than 10.
forloop, this is not the only point of view that describes how the
forloop operates. Suppose, instead, 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 "
to" operator would return one, on the second call it would return two, etc. After the tenth call, the "
to" operator would fail which would terminate the loop. This is exactly the description of an iterator.
foreach variable in iterator() do statements; endfor;
Variableis 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
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.
end Range;statement or it may yield a value by executing the
yieldstatement. An iterator succeeds if it executes the
yieldstatement, it fails if it simply returns to the caller. Therefore, the
foreachstatement will only execute its corresponding statement if you exit an iterator with a
foreachstatement terminates if you simply return from the iterator. In the example above, the iterator returns the values
yieldand 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
foreachstatement, it makes an initial call to the iterator. The iterator runs until it executes a
yieldor it returns. If it executes the
yieldstatement, it returns the value of the expression following the
yieldas 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.
foreachstatement assigns the iterator return value to the loop control variable and executes the
foreachloop body. After executing the loop body, the
foreachstatement 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
yieldit executed. In the
rangeexample, a resumption would continue execution at the
start := start + 1;statement. On the first resumption, the
Rangeiterator would add one to
start,producing the value two. Two is less than ten (
stop's value) so the
whileloop 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
rangeiterator returns (fails), the
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 project, there are several issues to consider. First, the call to
Range_Resumeabove looks simple enough, but there is no fixed address that corresponds to the resume address. While it is certainly true that this
Rangeexample has only one resume address, in general you can have as many yield statements as you like in an iterator. For example, the following iterator returns the values 1, 2, 3, and 4:
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, the second resumption would execute
yield 3;, etc. Obviously there is no single resume address the calling code can count on.
yieldstatement then resumption by the
foreachstatement continues execution within the procedure or function that executed the
yield. Second, the semantics of an iterator require all local variables and parameters to maintain their values until the iterator terminates. That is, yielding does not deallocate local variables and parameters. Likewise, any return addresses left on the stack (e.g., the call to a procedure or function that executes the
yieldstatement) must not be lost when a piece of code yields and the corresponding
foreachstatement 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.
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
forloop body into a function, expand the iterator in-line (much like a macro) and call the
forloop 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 ForLoopCodeThis 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.
yieldstatement) and a dynamic link, which is a pointer to the iterator's activation record. Typically the dynamic link is just the value in the
bpregister at the time you execute the
yieldinstruction. This version implements the four parts of an iterator as follows:
callinstruction for the initial iterator call,
callinstruction for the
retinstruction for the resume operation, and
retinstruction to terminate the iterator.
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, consider the
Range iterator presented earlier.
This iterator requires two parameters, a starting value and an ending value:
foreach i in Range(1,10) do writeln(i);The code to make the initial call to the
Rangeiterator, 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.
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 endpAlthough 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
Range iterator, at label
RangeLoop, implement the termination test of the while loop.
Start parameter contains a value greater than the
Stop parameter, control transfers to the
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
The real work of the iterator occurs in the body of the while loop. The
implement the yield statement. The
instructions 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
foreach loop, the code
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. Since
bp just happens to point at the
bp value for the calling code, executing the
bp, [bp] instruction reloads
bp 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
register, but in general you will need to restore
At the end of the foreach loop body the
ret 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,
Start variable, and then repeats the while loop.
Of course, 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 work using
Range, not because actually implementing
Range as an iterator is a good idea.