|
Table of Content | |
|
Table of Content | |
| CHAPTER TWELVE: PROCEDURES: ADVANCED TOPICS (Part 7) |
| 12.6 -
Sample Programs 12.6.1 - An Example of an Iterator 12.6.2 - Another Iterator Example |
| 12.6 Sample Programs |
The sample programs in this chapter provide two examples of iterators. The first example is a simple iterator that processes characters in a string and returns the vowels found in that string. The second iterator is a synthetic program (i.e., written just to demonstrate iterators) that is considerably more complex since it deals with static links. The second sample program also demonstrates another way to build the resume frame for an iterator. Take a good look at the macros that this program uses. They can simplify the user of iterators in your programs.
12.6.1 An Example of an Iterator
The following example demonstrates a simple iterator. This piece of code reads a string from the user and then locates all the vowels (a, e, i, o, u, w, y) on the line and prints their index into the string, the vowel at that position, and counts the occurrences of each vowel. This isn't a particularly good example of an iterator, however it does serve to demonstrate an implementation and use.
First, a pseudo-Pascal version of the program:
program DoVowels(input,output);
const
Vowels = ['a', 'e', 'i', 'o', 'u', 'y', 'w',
'A', 'E', 'I', 'O', 'U', 'Y', 'W'];
var
ThisVowel : integer;
VowelCnt : array [char] of integer;
iterator GetVowel(s:string) : integer;
var
CurIndex : integer;
begin
for CurIndex := 1 to length(s) do
if (s [CurIndex] in Vowels) then begin
{ If we have a vowel, bump the cnt by 1 }
Vowels[s[CurIndex]] := Vowels[s[CurIndex]]+1;
( Return index into string of current vowel }
yield CurIndex;
end;
end;
begin {main}
{ First, initialize our vowel counters }
VowelCnt ['a'] := 0;
VowelCnt ['e'] := 0;
VowelCnt ['i'] := 0;
VowelCnt ['o'] := 0;
VowelCnt ['u'] := 0;
VowelCnt ['w'] := 0;
VowelCnt ['y'] := 0;
VowelCnt ['A'] := 0;
VowelCnt ['E'] := 0;
VowelCnt ['I'] := 0;
VowelCnt ['O'] := 0;
VowelCnt ['U'] := 0;
VowelCnt ['W'] := 0;
VowelCnt ['Y'] := 0;
{ Read and process the input string}
Write('Enter a string: ');
ReadLn(InputStr);
foreach ThisVowel in GetVowel(InputStr) do
WriteLn('Vowel ',InputStr [ThisVowel],
' at position ', ThisVowel);
{ Output the vowel counts }
WriteLn('# of A''s:',VowelCnt['a'] + VowelCnt['A']);
WriteLn('# of E''s:',VowelCnt['e'] + VowelCnt['E']);
WriteLn('# of I''s:',VowelCnt['i'] + VowelCnt['I']);
WriteLn('# of O''s:',VowelCnt['o'] + VowelCnt['O']);
WriteLn('# of U''s:',VowelCnt['u'] + VowelCnt['U']);
WriteLn('# of W''s:',VowelCnt['w'] + VowelCnt['W']);
WriteLn('# of Y''s:',VowelCnt['y'] + VowelCnt['Y']);
end.
Here's the working assembly language version:
.286 ;For PUSH imm instr.
.xlist
include stdlib.a
includelib stdlib.lib
.list
; Some "cute" equates:
Iterator textequ <proc>
endi textequ <endp>
wp textequ <word ptr>
; Yield is a macro which emits the necessary code for the YIELD operation.
Yield macro
mov dx, [bp+2] ;Place to yield back to.
push bp ;Save Iterator link
mov bp, [bp] ;Get ptr to caller's A.R.
call dx ;Push resume address and rtn.
pop bp ;Restore ptr to our A. R.
endm
; Necessary global variables:
dseg segment para public 'data'
; As per UCR StdLib instructions, InputStr must hold
; at least 128 characters.
InputStr byte 128 dup (?)
; Note that the following statement initializes the
; VowelCnt array to zeros, saving us from having to
; do this in the main program.
VowelCnt word 256 dup (0)
dseg ends
cseg segment para public 'code'
assume cs:cseg, ds:dseg
; GetVowel- This iterator searches for the next vowel in the
; input string and returns the index to the value
; as the iterator result. On entry, ES:DI points
; at the string to process. On yield, AX returns
; the zero-based index into the string of the
; current vowel.
;
; GVYield- Address to call when performing the yield.
; GVStrPtr- A local variable which points at our string.
GVYield textequ <word ptr [bp+2]>
GVStrPtr textequ <dword ptr [bp-4]>
GetVowel Iterator
push bp
mov bp, sp
; Create and initialize GVStrPtr. This is a pointer to the
; next character to process in the input string.
push es
push di
; Save original ES:DI values so we can restore them on YIELD
; and on termination.
push es
push di
; Okay, here's the main body of the iterator. Fetch each
; character until the end of the string and see if it is
; a vowel. If it is a vowel, yield the index to it. If
; it is not a vowel, move on to the next character.
GVLoop: les di, GVStrPtr ;Ptr to next char.
mov al, es:[di] ;Get this character.
cmp al, 0 ;End of string?
je GVDone
; The following statement will convert all lower case
; characters to upper case. It will also translate other
; characters to who knows what, but we don't care since
; we only look at A, E, I, O, U, W, and Y.
and al, 5fh
; See if this character is a vowel. This is a disgusting
; set membership operation. See Chapter Ten to learn how
; to do it right.
cmp al, 'A'
je IsAVowel
cmp al, 'E'
je IsAVowel
cmp al, 'I'
je IsAVowel
cmp al, 'O'
je IsAVowel
cmp al, 'U'
je IsAVowel
cmp al, 'W'
je IsAVowel
cmp al, 'Y'
jne NotAVowel
; If we've got a vowel we need to yield the index into
; the string to that vowel. To compute the index, we
; restore the original ES:DI values (which pointer at
; the beginning of the string) and subtract the current
; position (now in AX) from the first position. This
; produces a zero-based index into the string.
; This code must also increment the corresponding entry
; in the VowelCnt array so we can print the results
; later. Unlike the Pascal code, we've converted lower
; case to upper case so the count for upper and lower
; case characters will appear in the upper case slot.
IsAVowel: push bx ;Bump the vowel
mov ah, 0 ; count by one.
mov bx, ax
shl bx, 1
inc VowelCnt[bx]
pop bx
mov ax, di
pop di ;Restore original DI
sub ax, di ;Compute index.
pop es ;Restore original ES
yield
push es ;Save ES:DI again
push di
; Whether it was a vowel or not, we've now got to move
; on to the next character in the string. Increment
; our string pointer by one and repeat the process
; over again.
NotAVowel: inc wp GVStrPtr
jmp GVLoop
; If we've reached the end of the string, terminate
; the iterator here. We need to restore the original
; ES:DI values, remove local variables, pop the YIELD
; address, and then return to the termination address.
GVDone: pop di ;Restore ES:DI
pop es
mov sp, bp ;Remove locals
add sp, 4 ;Pop YIELD/S.L.
pop bp
ret
GetVowel endi
Main proc
mov ax, dseg
mov ds, ax
mov es, ax
print
byte "Enter a string: ",0
lesi InputStr
gets ;Read input line.
; The following is the foreach loop. Note that the label
; "FOREACH" is present for documentation purpose only.
; In fact, the foreach loop always begins with the first
; instruction after the call to GetVowel.
;
; One other note: this assembly language code uses
; zero-based indexes for the string. The Pascal version
; uses one-based indexes for strings. So the actual
; numbers printed will be different. If you want the
; values printed by both programs to be identical,
; uncomment the INC instruction below.
push offset ForDone ;Termination address.
push bp ;Static link.
call GetVowel ;Start iterator
FOREACH: mov bx, ax
print
byte "Vowel ",0
mov al, InputStr[bx]
putc
print
byte " at position ",0
mov ax, bx
; inc ax
puti
putcr
ret ;Iterator resume.
ForDone: printf
byte "# of A's: %d\n"
byte "# of E's: %d\n"
byte "# of I's: %d\n"
byte "# of O's: %d\n"
byte "# of U's: %d\n"
byte "# of W's: %d\n"
byte "# of Y's: %d\n",0
dword VowelCnt + ('A'*2)
dword VowelCnt + ('E'*2)
dword VowelCnt + ('I'*2)
dword VowelCnt + ('O'*2)
dword VowelCnt + ('U'*2)
dword VowelCnt + ('W'*2)
dword VowelCnt + ('Y'*2)
Quit: ExitPgm ;DOS macro to quit program.
Main endp
cseg ends
sseg segment para stack 'stack'
stk db 1024 dup ("stack ")
sseg ends
zzzzzzseg segment para public 'zzzzzz'
LastBytes db 16 dup (?)
zzzzzzseg ends
end Main
12.6.2 Another Iterator Example
One problem with the iterator examples appearing in this
chapter up to this point is that they do not access any global or intermediate variables.
Furthermore, these examples do not work if an iterator is recursive or calls other
procedures that yield the value to the foreach loop. The major problem with
the examples up to this point has been that the foreach loop body has been
responsible for reloading the bp register with a pointer to the foreach
loop's procedure's activation record. Unfortunately, the foreach loop body has to assume
that bp currently points at the iterator's activation record so it can get a
pointer to its own activation record from that activation record. This will not be the
case if the iterator's activation record is not the one on the top of the stack.
To rectify this problem, the code doing the yield operation
must set up the bp register so that it points at the activation record of the
procedure containing the foreach loop before returning back to the loop. This
is a somewhat complex operation. The following macro accomplishes this from inside an
iterator:
Yield macro
mov dx, [BP+2] ;Place to yield back to.
push bp ;Save Iterator link
mov bp, [bp] ;Get ptr to caller's A.R.
call dx ;Push resume address and rtn.
pop bp ;Restore ptr to our A. R.
endm
Note an unfortunate side effect of this code is that it
modifies the dx register. Therefore, the iterator does not preserve the dx
register across a call to the iterator function.
The macro above assumes that the bp register points at the
iterator's activation record. If it does not, then you must execution some additional
instructions to follow the static links back to the iterator's activation record to obtain
the address of the foreach loop procedure's activation record.
; Iterator example.
;
; Roughly corresponds to the example in Ghezzi & Jazayeri's
; "Programming Language Concepts" text.
;
; Randall Hyde
;
;
; This program demonstrates an implementation of:
;
; l := 0;
; foreach i in range(1,3) do
; foreach j in iter2() do
; writeln(i, ',', j, ',', l):
;
;
; iterator range(start,stop):integer;
; begin
;
; while start <= stop do begin
;
; yield start;
; start := start+1;
; end;
; end;
;
; iterator iter2:integer;
; var k:integer;
; begin
;
; foreach k in iter3 do
; yield k;
; end;
;
; iterator iter3:integer;
; begin
;
; l := l + 1;
; yield 1;
; l := l + 1;
; yield 2;
; l := l + 1;
; yield 0;
; end;
;
;
; This code will print:
;
; 1, 1, 1
; 1, 2, 2
; 1, 0, 3
; 2, 1, 4
; 2, 2, 5
; 2, 0, 6
; 3, 1, 7
; 3, 2, 8
; 3, 0, 9
.xlist
include stdlib.a
includelib stdlib.lib
.list
.286 ;Allow extra adrs modes.
dseg segment para stack 'data'
; Put the stack in the data segment so we can use the small memory model
; to simplify addressing:
stk byte 1024 dup ('stack')
EndStk word 0
dseg ends
cseg segment para public 'code'
assume cs:cseg, ds:dseg, ss:dseg
; Here's the structure of a resume frame. Note that this structure isn't
; actually used in this code. It is only provided to show you what data
; is sitting on the stack when Yield builds a resume frame.
RsmFrm struct
ResumeAdrs word ?
IteratorLink word ?
RsmFrm ends
; The following macro builds a resume frame and the returns to the caller
; of an iterator. It assumes that the iterator and whoever called the
; iterator have the standard activation record defined above and that we
; are building the standard resume frame described above.
;
; This code wipes out the DX register. Whoever calls the iterator cannot
; count on DX being preserved, likewise, the iterator cannot count on DX
; being preserved across a yield. Presumably, the iterator returns its
; value in AX.
ActRec struct
DynamicLink word ? ;Saved BP value.
YieldAdrs word ? ;Return Adrs for proc.
StaticLink word ? ;Static link for proc.
ActRec ends
AR equ [bp].ActRec
Yield macro
mov dx, AR.YieldAdrs ;Place to yield back to.
push bp ;Save Iterator link
mov bp, AR.DynamicLink ;Get ptr to caller's A.R.
call dx ;Push resume address and rtn.
pop bp ;Restore ptr to our A. R.
endm
; Range(start, stop) - Yields start..stop and then fails.
; The following structure defines the activation record for Range:
rngAR struct
DynamicLink word ? ;Saved BP value.
YieldAdrs word ? ;Return Adrs for proc.
StaticLink word ? ;Static link for proc.
FailAdrs word ? ;Go here when we fail
Stop word ? ;Stop parameter
Start word ? ;Start parameter
rngAR ends
rAR equ [bp].rngAR
Range proc
push bp
mov bp, sp
; While start <= stop, yield start:
WhlStartLEStop: mov ax, rAR.Start ;Also puts return value
cmp ax, rAR.Stop ; in AX.
jnle RangeFail
yield
inc rAR.Start
jmp WhlStartLEStop
RangeFail: pop bp ;Restore Dynamic Link.
add sp, 4 ;Skip ret adrs and S.L.
ret 4 ;Return through fail address.
Range endp
; Iter2- Just calls iter3() and returns whatever value it generates.
;
; Note: Since iter2 and iter3 are at the same lex level, the static link
; passed to iter3 must be the same as the static link passed to iter2.
; This is why the "push [bp]" instruction appears below (as opposed to the
; "push bp" instruction which appears in the calls to Range and iter2).
; Keep in mind, Range and iter2 are only called from main and bp contains
; the static link at that point. This is not true when iter2 calls iter3.
iter2 proc
push bp
mov bp, sp
push offset i3Fail ;Failure address.
push [bp] ;Static link is link to main.
call iter3
yield ;Return value returned by iter3
ret ;Resume Iter3.
i3Fail: pop bp ;Restore Dynamic Link.
add sp, 4 ;Skip return address & S.L.
ret ;Return through fail address.
iter2 endp
; Iter3() simply yields the values 1, 2, and 0:
iter3 proc
push bp
mov bp, sp
mov bx, AR.StaticLink ;Point BX at main's AR.
inc word ptr [bx-6] ;Increment L in main.
mov ax, 1
yield
mov bx, AR.StaticLink
inc word ptr [bx-6]
mov ax, 2
yield
mov bx, AR.StaticLink
inc word ptr [bx-6]
mov ax, 0
yield
pop bp ;Restore Dynamic Link.
add sp, 4 ;Skip return address & S.L.
ret ;Return through fail address.
iter3 endp
; Main's local variables are allocated on the stack in order to justify
; the use of static links.
i equ [bp-2]
j equ [bp-4]
l equ [bp-6]
Main proc
mov ax, dseg
mov ds, ax
mov es, ax
mov ss, ax
mov sp, offset EndStk
; Allocate storage for i, j, and l on the stack:
mov bp, sp
sub sp, 6
meminit
mov word ptr l, 0 ;Initialize l.
; foreach i in range(1,3) do:
push 1 ;Parameters.
push 3
push offset iFail ;Failure address.
push bp ;Static link points at our AR.
call Range
; Yield from range comes here. The label is for your benefit.
RangeYield: mov i, ax ;Save away loop control value.
; foreach j in iter2 do:
push offset jfail ;Failure address.
push bp ;Static link points at our AR.
call iter2
; Yield from iter2 comes here:
iter2Yield: mov j, ax
mov ax, i
puti
print
byte ", ",0
mov ax, j
puti
print
byte ", ",0
mov ax, l
puti
putcr
; Restart iter2:
ret ;Resume iterator.
; Restart Range down here:
jFail: ret ;Resume iterator.
; All Done!
iFail: print
byte cr,lf,"All Done!",cr,lf,0
Quit: ExitPgm ;DOS macro to quit program.
Main endp
cseg ends
; zzzzzzseg must be the last segment that gets loaded into memory!
; This is where the heap begins.
zzzzzzseg segment para public 'zzzzzz'
LastBytes db 16 dup (?)
zzzzzzseg ends
end Main
Chapter Twelve: Procedures: Advanced
Topics (Part 7)
27 SEP 1996