Today in CS362: Translating Loops

Admin
  Today's fun 151 question: Can you make every recursive
    procedure tail recursive?
  I'm very sorry about how long the parsers are taking
  How did yesterday's lab go?
  Type checker IS NOW EXTRA CREDIT

Overview
  Kinds of loops
  Translating while loops
  Translating repeat-until loops (do-while)
  Translating Pascal-like for loops
  Other notes

Favorite oddities from our pascal compiler

  movl %eax %eax

  addl $-8,%esp
  subl $8,%esp

  Both are artifacts of folks dealing with interesting
  issues of translation separately.

  Here's the code that surrounds the odd movl

	call Increment
	addl $16,%esp
	movl %eax,%eax
	movl %eax,Result

  Translation of part of

    result := increment(inval)

  Thought one:
    To move a value into a global variable, it needs to
    be in a register.  Hence, my translation of
    "assign to global X" is
      movl thing_to_assign %eax
      movl %eax,X

Main focus: Translating loops

Review: Kinds of loops we're likely to see
  For loop
    In Pascal: 
     FOR <counter> := <exp-initial> [TO|DOWNTO] <exp-final> 
       <statement>
  While loops
    Pascal: WHILE <boolean-exp> DO <statement>
    C: WHILE (<boolean-exp>) <statement>
  Repeat loop
    Pascal: REPEAT <statement> UNTIL <boolean-exp>
    C: DO <statement> WHILE (not <boolean-exp>)
    Repeat loops evaluate the statement at least once.
  Foreach <ID> in <collection-expression>

Translating While Loops

  translate(WHILE <boolean-exp> DO <statement>)

In a short-circuit evaluation language
BEGIN_LOOP:
BEGIN_CONDITIONAL:
  translate(<boolean-exp>, BEGIN_BODY, END_LOOP)
BEGIN_BODY:
  translation of <statement>
  JUMP BEGIN_LOOP
END_LOOP:

or 

BEGIN_LOOP:
  JUMP BEGIN_CONDITIONAL
BEGIN_BODY:
  translation of <statement>
BEGIN_CONDITIONAL:
  translate(<boolean-exp>, BEGIN_BODY, END_LOOP)
END_LOOP:

IN a strict evaluation language

BEGIN_LOOP:
BEGIN_CONDITIONAL:
  translation of <boolean-exp>
  JUMP-IF-ZERO "address of result" END_LOOP
BEGIN_BODY:
  translation of <statement>
END_LOOP:

Repeats are equally straightforward.

Pascal-like for loops
FOR <counter> := <exp-initial> TO <exp-final> <statement>

One approach for translation:
  rewrite the parse tree to
<counter> := <exp-initial>
while <counter> LESS_THAN <exp-final> DO 
  BEGIN
    <statement>
    <counter> := increment(<counter>)
  END

Observations:
* How efficient is this solution?
* If exp-initial and exp-final are known at compile time,
  it's possible to unroll the loop.

type
  weekday = (Monday,Tuesday,Wednesday,Thursday,Friday)
var
  today: weekday;
for today := Monday to Friday do ...
for i := 1 to MAX_INT do

BEGIN_LOOP
  translation of <initial-exp>
  MOV result "address of <counter>"
BEGIN_BODY
  translation of <statement>
BEGIN_TEST
  translation of <final-exp>
  JUMP-EQUAL "address of that" "address of counter" END_LOOP
  INCREMENT "address of <counter>"
  JUMP BEGIN_BODY
END_LOOP

Formal Specs for Pascal say that the body of the for loop
is always executed once.

What happens if you can specify the inctrement?

for i := 1 to 100 step 2
* The 100 is an upper bound, so stop when i is greater than
  the 100.

for i := 1 to MAX_INT step MAX_INT