SICP Section 4.2 Variations on a Scheme -- Lazy Evaluation

Exercise 4.25. Suppose that (in ordinary applicative-order Scheme) we define unless as shown above and then define factorial in terms of unless as
(define (factorial n) (unless (= n 1) (* n (factorial (- n 1))) 1))
What happens if we attempt to evaluate (factorial 5)? Will our definitions work in a normal-order language?

Answer: The expression (factorial 5) leads to the following application of unless:
(unless (= n 1) (* n (factorial (- n 1))) 1)
In an applicative-order language all the arguments to a procedure are evaluated when the procedure is applied. In the case of the above expression the first and third arguments are readily evaluated irrespective of the order of evaluation (left to right or vice-versa). The second argument however requires evaluating (factorial (-n 1)), i.e. (factorial 4) for completion. This is turn requires that (factorial 3) be evaluated and so on. The evaluation never completes even when n becomes 1 as the second argument never gets evaluated. Therefore we are left with an infinite loop.

In a normal-order language evaluation of procedure arguments are delayed until the actual argument values are needed. In the case of the above expression (factorial 4) is invoked as n != 1. The recursive invocation continues until the time n becomes 1. When n = 1, the second argument of the unless expression is not evaluated and 1 is returned. Therefore the program completes and we get the result.

Exercise 4.26. Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of lazy evaluation for implementing things such as unless. Ben points out that it's possible to implement unless in applicative order as a special form. Alyssa counters that, if one did that, unless would be merely syntax, not a procedure that could be used in conjunction with higher-order procedures. Fill in the details on both sides of the argument. Show how to implement unless as a derived expression (like cond or let), and give an example of a situation where it might be useful to have unless available as a procedure, rather than as a special form.

Answer:
(define (unless? exp) (tagged-list? exp 'unless)) (define (unless-condition exp) (cadr exp)) (define (unless-usual-value exp) (caddr exp)) (define (unless-exceptional-value exp) (if (null? (cdddr exp)) 'false (cadddr exp))) (define (analyze-unless exp) (let ((condition (analyze (unless-condition exp))) (usual-value (analyze (unless-usual-value exp))) (exceptional-value (analyze (unless-exceptional-value exp)))) (lambda (env) (if (true? (condition env)) (exceptional-value env) (usual-value env))))) ;; Addition to analyze: ((unless? exp) (analyze-unless exp))
I am not able to come up with any examples of using unless as a higher order procedure. :(

Exercise 4.27. Suppose we type in the following definitions to the lazy evaluator:
(define count 0) (define (id x) (set! count (+ count 1)) x)
Give the missing values in the following sequence of interactions, and explain your answers.
(define w (id (id 10))) ;;; L-Eval input: count ;;; L-Eval value: <response> ;;; L-Eval input: w ;;; L-Eval value: <response> ;;; L-Eval input: count ;;; L-Eval value: <response>
Answer:
(define w (id (id 10))) ;;; L-Eval input: count ;;; L-Eval value: 1 ;;; L-Eval input: w ;;; L-Eval value: 10 ;;; L-Eval input: count ;;; L-Eval value: 2
Explanation: When the preceding statement (define w (id (id 10))) is evaluated only the outer call to id is forced as it is immediately required. This causes count to be incremented once, to 1. The value of w becomes a thunk consisting of the inner call to id and the environment. This can be inspected by calling (lookup-variable-value 'w the-global-environment) after evaluating the expressions.

When w is called the driver-loop forces the actual-value of the thunk to be evaluated before presenting it to the output. This causes the delayed call to (id 10) to be executed. This expression increments count again and returns 10.

As the actual-value of w was forced in the last expression count has become 2.

Exercise 4.28. Eval uses actual-value rather than eval to evaluate the operator before passing it to apply, in order to force the value of the operator. Give an example that demonstrates the need for this forcing.

Answer: Consider the following function. It retruns either of the procedures even? or odd? depending on the input.
(define (choose x) (if (= x 1) even? odd?))
Now invoke this function as shown below
((choose 1) 2)
If the evaluator did not use actual-value to evaluate the operator the operand would have been a thunk representing (choose 1) and not the actual result. Consequently the expression would have thrown an error.

Exercise 4.29. Exhibit a program that you would expect to run much more slowly without memoization than with memoization. Also, consider the following interaction, where the id procedure is defined as in exercise 4.27 and count starts at 0:
(define (square x) (* x x)) ;;; L-Eval input: (square (id 10)) ;;; L-Eval value: <response> ;;; L-Eval input: count ;;; L-Eval value: <response>
Give the responses both when the evaluator memoizes and when it does not.

Answer: The program given below involves two recursive calls to itself. It will be faster with memoization than without.
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))

(square (id 10)) 100
This result is the same with or without memoization.
count 1 ;; with memoization 2 ;; without memoization.
When (square (id 10)) is called, the evaluation of (id 10) is delayed until it is actually needed. The need for forcing (id 10) happens when (* x x) is evaluated. Without memoization the procedure id is invoked twice, once for each argument to *, causing count to be incremented twice. With memoization id is only invoked once. The return value is used without calling it again for the second argument to *. Therefore count is incremented only once with memoization.

Exercise 4.30. Cy D. Fect, a reformed C programmer, is worried that some side effects may never take place, because the lazy evaluator doesn't force the expressions in a sequence. Since the value of an expression in a sequence other than the last one is not used (the expression is there only for its effect, such as assigning to a variable or printing), there can be no subsequent use of this value (e.g., as an argument to a primitive procedure) that will cause it to be forced. Cy thus thinks that when evaluating sequences, we must force all expressions in the sequence except the final one. He proposes to modify eval-sequence from section 4.1.1 to use actual-value rather than eval:
(define (eval-sequence exps env) (cond ((last-exp? exps) (eval (first-exp exps) env)) (else (actual-value (first-exp exps) env) (eval-sequence (rest-exps exps) env))))
a. Ben Bitdiddle thinks Cy is wrong. He shows Cy the for-each procedure described in exercise 2.23, which gives an important example of a sequence with side effects:
(define (for-each proc items) (if (null? items) 'done (begin (proc (car items)) (for-each proc (cdr items)))))
He claims that the evaluator in the text (with the original eval-sequence) handles this correctly:
;;; L-Eval input: (for-each (lambda (x) (newline) (display x)) (list 57 321 88)) 57 321 88 ;;; L-Eval value: done
Explain why Ben is right about the behavior of for-each. b. Cy agrees that Ben is right about the for-each example, but says that that's not the kind of program he was thinking about when he proposed his change to eval-sequence. He defines the following two procedures in the lazy evaluator:
(define (p1 x) (set! x (cons x '(2))) x) (define (p2 x) (define (p e) e x) (p (set! x (cons x '(2)))))
What are the values of (p1 1) and (p2 1) with the original eval-sequence? What would the values be with Cy's proposed change to eval-sequence?

c. Cy also points out that changing eval-sequence as he proposes does not affect the behavior of the example in part a. Explain why this is true.

d. How do you think sequences ought to be treated in the lazy evaluator? Do you like Cy's approach, the approach in the text, or some other approach?

Answer: a. The lambda procedure used with for-each uses two primitive procedures, newline and display. As apply does not delay the arguments in the case of primitive procedures, newline and display are executed immediately. Hence Ben is able to predict that the original evaluator can handle the operation correctly.

b.
(p1 1) returns (1 2) with the original eval-sequence.
(p2 1) returns 1 with the original eval-sequence.
The set! expression is passed to the internal procedure p in the form of a thunk. As this thunk is not forced, the value of x remains unchanged. Hence (p2 1) returns 1.

After implementing Cy's changes the behaviour of (p1 1) remains unchanged. However (p2 1) will return (1 2). This is a consequence of forcing all expressions in eval-sequence. The set! expression passed on to the internal procedure p as a thunk gets forced, thereby changing the value of x. Hence (p2 1) returns (1 2).

c. The example in part a uses primitive procedures for display. As arguments to primitive procedures were not delayed to begin with, the behavior remains unchanged.

d. Both approaches have their own trade offs. I prefer Cy's approach where assignment is involved. However this approach can slow things down where long sequences are involved.

Exercise 4.31. The approach taken in this section is somewhat unpleasant, because it makes an incompatible change to Scheme. It might be nicer to implement lazy evaluation as an upward-compatible extension, that is, so that ordinary Scheme programs will work as before. We can do this by extending the syntax of procedure declarations to let the user control whether or not arguments are to be delayed. While we're at it, we may as well also give the user the choice between delaying with and without memoization. For example, the definition
(define (f a (b lazy) c (d lazy-memo)) ...)
would define f to be a procedure of four arguments, where the first and third arguments are evaluated when the procedure is called, the second argument is delayed, and the fourth argument is both delayed and memoized. Thus, ordinary procedure definitions will produce the same behavior as ordinary Scheme, while adding the lazy-memo declaration to each parameter of every compound procedure will produce the behavior of the lazy evaluator defined in this section. Design and implement the changes required to produce such an extension to Scheme. You will have to implement new syntax procedures to handle the new syntax for define. You must also arrange for eval or apply to determine when arguments are to be delayed, and to force or delay arguments accordingly, and you must arrange for forcing to memoize or not, as appropriate.

Answer:
;; Changes to procedure-parameters. ;; Input (a (b lazy) c (d lazy-memo)) ;; Returns (a b c d) (define (procedure-parameters p) (map (lambda (x) (if (pair? x) (car x) x)) (procedure-parameters-with-tags p))) ;; Returns procedure parameters with tags (define (procedure-parameters-with-tags p) (cadr p)) ;; New form of delay-it for memo (define (delay-it-memo exp env) (list 'thunk-memo exp env)) (define (thunk-memo? obj) (tagged-list? obj 'thunk-memo)) ;; Force-it does not memoize if thunk does not indicate that it has to be memoized (define (force-it obj) (cond ((thunk-memo? obj) ;; Memoized thunk. (let ((result (actual-value (thunk-exp obj) (thunk-env obj)))) (set-car! obj 'evaluated-thunk) (set-car! (cdr obj) result) (set-cdr! (cdr obj) '()) result)) ;; Thunk has already been evaluated. ((evaluated-thunk? obj) (thunk-value obj)) ;; Orinary thunk ((thunk? obj) (actual-value (thunk-exp obj) (thunk-env obj))) (else obj))) ;; Changes to list-of-delayed-args ;; The procedure parameters are also passed in. ;; Arguments are delayed if the corresponding parameter is tagged lazy. (define (list-of-delayed-args parameters exps env) (define (operation-type parm) (cond ((lazy? parm) delay-it) ((lazy-memo? parm) delay-it-memo) (else actual-value))) (if (no-operands? exps) '() (let ((first-parm (car parameters)) (first-arg (first-operand exps))) (cons ((operation-type first-parm) (first-operand exps) env) (list-of-delayed-args (cdr parameters) (rest-operands exps) env))))) ;; Decide if parameter is lazy, lazy-memo or not. (define (ends-with-tag? exp tag) (if (pair? exp) (eq? (cadr exp) tag) false)) (define (lazy? exp) (ends-with-tag? exp 'lazy)) (define (lazy-memo? exp) (ends-with-tag? exp 'lazy-memo)) ;; Changes to apply. (define (apply procedure arguments env) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure (list-of-arg-values arguments env))) ; changed ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (procedure-parameters procedure) (list-of-delayed-args (procedure-parameters-with-tags procedure) arguments env) ; changed (procedure-environment procedure)))) (else (error "Unknown procedure type -- APPLY" procedure))))
This was a truly fascinating exercise. It looked intimidating but I came to enjoy doing it.

Exercise 4.32. Give some examples that illustrate the difference between the streams of chapter 3 and the ``lazier'' lazy lists described in this section. How can you take advantage of this extra laziness?

Answer: The ability to delay both car and cdr operation allows us to create data structures that behave like streams w.r.t car as well as cdr. One such structure would be an infinite tree. If we recall how trees were implemented as lists earlier we can see how lazy car and cdr allow us to convert those to infinite trees.

Exercise 4.33. Ben Bitdiddle tests the lazy list implementation given above by evaluating the expression
(car '(a b c))
To his surprise, this produces an error. After some thought, he realizes that the ``lists'' obtained by reading in quoted expressions are different from the lists manipulated by the new definitions of cons, car, and cdr. Modify the evaluator's treatment of quoted expressions so that quoted lists typed at the driver loop will produce true lazy lists.

Answer: The key change is in the way quoted expressions are evaluated. The eval procedure is changed to construct and evaluate lazy lists if the quoted text contains a list. Lazy lists are constructed using a utility procedure text-list->lazy-list.
(define (text-list->lazy-list exp) (cond ((null? exp) '()) ((symbol? exp) (list 'quote exp)) (else (list 'cons (text-list->lazy-list (car exp)) (text-list->lazy-list (cdr exp)))))) ;; Changes to eval. ((quoted? exp) (let ((text (text-of-quotation exp))) (if (pair? text) (eval (text-list->lazy-list text) env) text)))
Exercise 4.34. Modify the driver loop for the evaluator so that lazy pairs and lists will print in some reasonable way. (What are you going to do about infinite lists?) You may also need to modify the representation of lazy pairs so that the evaluator can identify them in order to print them.

Answer: In order to print lazy lists we should first identify them as such. Ideally there should be a tag, say 'lazy-list or some such for the same. Right now I am using a make shift solutions, identifying them by matching them with the structure of cons. i.e. (lambda (m) (m x y))
(define (lazy-list? object) (and (compound-procedure? object) (equal? (procedure-parameters object) (list 'm)) (equal? (procedure-body object) (list (list 'm 'x 'y)))))
Next, driver-loop should be modified to check if the output is a lazy list. If so it invokes a special procedure to print the output. The first 5 elements of a list are printed followed by "..." if there are more. This number is arbitrary.
(define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (let ((output (actual-value input the-global-environment))) (announce-output output-prompt) (if (lazy-list? output) (display (display-lazy-pair input 5)) (user-print output)))) (driver-loop))
Finally a special procedure to print a lazy list.
(define (display-lazy-pair exp count) (define (get-actual-value op exp) (actual-value (list op exp) the-global-environment)) (if (> count 0) (let ((first (get-actual-value 'car exp)) (rest (get-actual-value 'cdr exp))) (append (if (lazy-list? first) (display-lazy-pair (list 'car exp) (- count 1)) (list first)) (if (lazy-list? rest) (display-lazy-pair (list 'cdr exp) (- count 1)) (list rest)))) '(...)))