G7400 F'10
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Set 10

Problem Set 8: Abstract Register Machine and Control in Redex

Due date: 11/12 @ at the beginning of class

The goal of this problem set is to study control constructs in the context of CEK machines for ISWIM. Warning: The second problem relies on the solution for the first problem.

Problem 1:

Add a loop construct with the following grammar to the ISWIM variant of problem 7(1):

  (loop x_loop (x_init e_init) e_body)
The variables x_init and x_loop are bound in the e_body subexpression. Semantically, x_loop is a recursive function of one argument (x_init), which is initialized to the value of e_init. Hence the function body, e_body, may call x_loop on one argument, and such a call starts another "iteration" of the "loop".

Why are the words "iteration" and "loop" in quotes? Show with an example that loop isn't what one would call a loop in a traditional language, say Java or C++.

Problem 2:

Equip the ISWIM extension of problem 1 with a break construct. That is, the body of a loop may contain expressions of the form:

  (break x_loop e_xt)
where x_loop is the loop variable bound by loop. The expression evaluates e_xt and returns it as the value of the loop expression.

Note: the break construct contains a lexical reference to the loop identifier. This is NOT a dynamic notion.

The design of loop raises several questions, e.g.,

  • It is possible that a break expression refers to a loop that has finished its evaluation. How?
  • What does your looping construct do in this case?
How does your design answer these questions. Can you think of another design question?

last updated on Sun Nov 21 19:38:23 EST 2010generated with PLT Scheme