Class 36: Translating Loops

Held: Monday, 26 April 2004

Summary: Today we consider issues in the translation of looping structures.

Related Pages:

Overview:

• While Loops
• Repeat-Until Loops
• For Loops

Kinds of Loops

• Pascal has three key looping constructions (if you don't count recursion): while loops, repeat-until loops, and for loops.
• For loops repeat their bodies a fixed number of times and have an associated counter.
• While and repeat-until loops repeat their bodies an indefinite number of times.
• While loops may never execute their bodies; repeat-until loops execute their bodies at least once.
• Most languages include some variant of these three kinds of loops, with varying interpretations.

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
• 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.
• Some other considerations
• What happens if the counter exceeds the upper bound?
• How often should the expression for the upper-bound be executed?

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 5 11:47:15 2004.
The source to the document was last modified on Tue Jan 20 23:06:46 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.36.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu