4.9 Exercise 4.9

while

while is the most primitive iteration construct I’ve done for this exercise, so I will define it first.

A while expression has two parts:

• A predicate, determining whether to execute the body or not

• A body expression that is evaluated multiple times

I will allow for the expression to return a value (which will be what the body evaluated to in the last time it was evaluated), but the primary purpose of a while loop (and of all of the iteration constructs we are defining here) is to do mutations.

Example:

(while (> x 0)

(begin

(displayln x)

(set! x (- x 1))

x))

should translate to:

(let ()

(define while-iter

(lambda (last-value)

(if (> x 0)

(while-iter

(begin

(displayln x)

(set! x (- x 1))

x))

last-value)))

(while-iter false))

(define (while? exp) (tagged-list? exp 'while))

(define (while-predicate exp) (cadr exp))

(define (while-body exp) (caddr exp))

(define (while->combination exp)   (make-let    '()    (make-define 'while-iter                 (make-lambda '(last-value)                              (list (make-if (while-predicate exp)                                             (list 'while-iter (while-body exp))                                             'last-value))))    '(while-iter false)))

until

until is a simple syntactic sugar around while where the predicate is negated. Therefore, we can translate it directly to a while expression.

Example:

(until (= x 0)

(begin

(displayln x)

(set! x (- x 1))

x))

should translate to:

(while (not (= x 0))

(begin

(displayln x)

(set! x (- x 1))

x))

(define (make-while predicate body) (list 'while predicate body))

(define (until? exp) (tagged-list? exp 'until))

(define (until-predicate exp) (cadr exp))

(define (until-body exp) (caddr exp))

(define (until->while exp)   (make-while (list 'not (until-predicate exp)) (until-body exp)))

for

for is also reducible to while, albeit in a more complex way. The for loop contains a body as well as a sequence of three control expressions:

• A sequence of initializing bindings creating scoped definitions with initial values

• A predicate determining whether to evaluate the body

• A continuing expression to be evaluated after the body, before testing the predicate again

The for loop is introduced to account for the pattern seen above, where a value is incremented or decremented at the end of a while loop body. It is easy to write a while loop and forget this, accidentally leaving yourself with an infinite loop; furthermore, for certain kinds of iterations, it is likely the case that the for loop demonstrates intent more precisely, since only some kinds of iterations make more sense when described in this way.

A for loop can be reduced to a while whose body is comprised of the for loop body followed by the for loop continuing expressions and whose predicate is the same, all inside a let expression creating the bindings of the for loop’s initialization sequence.

Like a while expression, the for expression also results in a value even though it is mostly intended for side-effectful computing. Since the while loop evaluates to the last execution of the body, since the last-executed expression in the body is the continuing expression, the last evaluation of the continuing expression of the for expression is the final result. I will be using that below to avoid having to define bindings outside of the for expression in my examples, but the value of the for expression is not its main purpose.

Example:

(for (((x 0) (sum 0))

(< x 5)

(begin (set! x (+ x 1)) sum))

(set! sum (+ sum x y)))

should translate to:

(let ((x 0) (sum 0))

(while (< x 5)

(begin

(set! sum (+ sum x y))

(begin (set! x (+ x 1)) sum))))

(define (for? exp) (tagged-list? exp 'for))

(define (for-control exp) (cadr exp))

(define (for-initialization exp) (car (for-control exp)))

(define (for-predicate exp) (cadr (for-control exp)))

(define (for-continue exp) (caddr (for-control exp)))

(define (for-body exp) (caddr exp))

(define (for->while exp)   (make-let (for-initialization exp)             (make-while (for-predicate exp)                         (list 'begin (for-body exp) (for-continue exp)))))

A longer example

Consider the nested for expression below:

(for (((x 0) (sum 0))

(< x 5)

(begin (set! x (+ x 1)) sum))

(for (((y 0))

(< y 5)

(begin (set! y (+ y 1)) y))

(set! sum (+ sum x y))))

Due to how we have constructed the continuing expressions, the end result of this expression should be the final sum.

If we reduce both for expressions to while expressions, we end up with

(let ((x 0) (sum 0))

(while (< x 5)

(begin

(let ((y 0))

(while (< y 5)

(begin

(set! sum (+ sum x y))

(begin (set! y (+ y 1)) y))))

(begin (set! x (+ x 1)) sum))))

And if we reduce both of these while expressions, we end up with

(let ((x 0) (sum 0))

(let ()

(define while-iter

(lambda (last-value)

(if (< x 5)

(while-iter

(begin

(let ((y 0))

(let ()

(define while-iter

(lambda (last-value)

(if (< y 5)

(while-iter

(begin

(set! sum (+ sum x y))

(begin (set! y (+ y 1)) y)))

last-value)))

(while-iter false)))

(begin

(set! x (+ x 1))

sum)))

last-value)))

(while-iter false)))

We can actually evaluate that and see that we get the correct answer:

> (let ((x 0) (sum 0))     (let ()       (define while-iter         (lambda (last-value)           (if (< x 5)               (while-iter                (begin                  (let ((y 0))                    (let ()                      (define while-iter                        (lambda (last-value)                          (if (< y 5)                              (while-iter                               (begin                                 (set! sum (+ sum x y))                                 (begin (set! y (+ y 1)) y)))                              last-value)))                      (while-iter false)))                  (begin                    (set! x (+ x 1))                    sum)))               last-value)))       (while-iter false)))

100

One may argue that these looping constructs are not necessary. However, if you observe the difference in the clarity of the for expressions compared to what is ultimately evaluated, it is clear that there is, in fact, a use for these. That said, I have committed a sleight of hand here, as there is a much more straightforward solution to the given problem. Consider what the sum actually is:

It is clear that each value is added to the sum 10 times, and thus we can trivially compute it with

> (* 10 (+ 1 2 3 4))

100

It is true that this is only because the actual work being done by the above for expression is trivial and actually not taking advantage of the main power of the construct – that is, concisely being able to describe iterative side effects. But this wouldn’t be the first time that an imperative construct was used when a simpler option exists. This is why it’s important to use these iterative constructs for what they are actually best for – side-effectful computing that can’t be concisely stated as a straightforward evaluation.