Class 28: Translating Loops

Held Monday, April 9, 2001

Summary

Today we consider issues in the translation of looping structures.

Notes

• Rachel wants me to remind you that the second homework was due last week and she'd appreciate copies soon.
• How goes type checking?
• Candidates for the visiting math position will be here this week and next. You may want to consider attending their talks.

Overview

• While Loops
• Repeat-Until Loops
• For Loops

Translating While Loops

• Recall that their are two key parts to a while loop: the test and the body.
• It's helpful to have three extra labels for the translated while loop
  • One will precede the test
  • One will precede the body
  • One will follow the body
• Translate the test
  • If you're doing short-circult evaluation, pass the body label as the true part and the follow label as the false part.
  • Since Pascal does strict evaluation, we'll deal with a result from the translation of the test.
• Translate the body.
• Join together:
  • New label for the test
  • Code for the test
  • Jump-if-zero Result-of-Test End-Loop
  • New label for the body
  • Code for the body
  • Jump test-label
  • New label for the end-of-loop.
• Repeat-until loops are similar, except that the test can be in a different place.
• Another alternative is to exactly the same translation and then precede it with a Jump body-label.

Translating For Loops

• Basic form

  for counter := lower-bound to upper-bound step increment do
    body
  

• At first glance, For loops seem equally simple, since we can treat a for loop as something like the following while loop:

  counter := lower_bound;
  while (counter <= upper-bound) do
    begin
      body;
      counter := counter + increment;
    end
  

• However, Pascal introduces one subtle difference: If the counter variable is an enumerated type, it may be meaningless to increment beyond upper-bound.
  • You can also have this problem if the upper bound is the largest possible integer.
• What's the solution? Do a test for equality after the loop but before the increment.
  • Store lower_bound into counter
  • New label for body
  • Code for body
  • Jump-if-equal counter upper-bound end-label
  • Add increment to counter
  • Copy result into counter
  • Jump body-label
  • New label for end of loop
• Note that this impelmentation requires that the body be executed at least once and that the increment bring you exactly to the result.
  • Careful reading of the Pascal specifications will show the same requirements.