Chapter 6, Problem 35E

Explanation of Solution

(a). Multilevel returns using common Lisp:

• The multilevel returns uses catch and throw statement to implement the problem.
• The following shows the program instruction to use of multilevel returns.
• The program incorporate different catch rules based on both syntax rule and dynamic wind.
• While defining the catches () the stack initially leads to empty.
• Then the syntax rule function is defined and it checks catch from wrapper class, the output become the old-catches.
• The dynamic wind uses call-with-current-continuation wrapper.
• Then throw is used to the print the errors.

$\begin{array}{l}\text{(define catches '()) ; catch stack initially empty}\\ \text{(define-syntax catch}\\ \text{(syntax-rules ()}\\ \text{((catch tag form }\mathrm{...}\text{)}\end{array}$

$\begin{array}{l}\text{(let* ((old-catches catches)}\\ \text{(wrapper (lambda (c)}\\ \text{(set! catches (cons (cons tag c) old-catches))}\\ \text{form }\mathrm{...}\text{))) ; real work is done here}\end{array}$

$\begin{array}{l}\text{(dynamic-wind}\\ \text{(lambda ()'())}\\ \text{(lambda () (call-with-current-continuation wrapper))}\\ \text{(lambda () (set! catches old-catches)))))))}\\ \end{array}$

$\begin{array}{l}\text{(define throw (lambda (tag v)}\\ \text{(let ((pop-catches (assq tag catches)))}\\ \text{(if pop-catches}\\ \text{((cdr pop-catches) v)}\end{array}$

$\begin{array}{l}\text{(begin}\\ \text{(display "no matching catch!")}\\ \text{(newline)}\\ \text{('())))))) ; fatal error}\end{array}$

• The above code can be used in the following manner.

  $\begin{array}{l}\text{(define index}\\ \text{(lambda (k l)}\\ \text{(letrec ((helper (lambda (l i)}\\ \text{(cond}\end{array}$

    $\begin{array}{l}\text{((null? l) '())}\\ \text{((equal? (car l) k) (throw 'found i))}\\ \text{(\#t (helper (cdr l) (+ 1 i)))))))}\\ \text{(helper l 0))))}\end{array}$

$\text{(catch 'found (index "blind" '("three" "blind" "mice"))) =) 1}$

Explanation of Solution

(b). Implementing the uptoby function with macro iterator and yield function:

• The Exercise 6.35 uses lazy evaluation to implement the iterator objects.
• Implement this to with macro iterator and yield function based on tail recursive leads to improve the performance of program.
• Tail recursion is a special kind of recursion function, in which the last operation of a function is a recursive call.
• This recursion may optimized away by executing the call in current stack space and it will return the result, rather than storing it in a new stack frame.
• The following program explains the lazy evaluation with yield() and macro function with tail recursive manner.

  $\begin{array}{l}\text{(define yield '()) ; initial implementation is empty}\\ \text{(define-syntax iterator (syntax-rules ()}\\ \text{((iterator args stmt }\mathrm{...}\text{)}\\ \text{(lambda args}\end{array}$

  $\begin{array}{l}\text{(lambda (cont)}\\ \text{(let ((old\_yield yield))}\\ \text{(dynamic-wind}\\ \text{(lambda ()}\end{array}$

  $\begin{array}{l}\text{(set! yield ; redefine yield for}\\ \text{(lambda (v) ; dynamically nested code}\\ \text{(let ((return-thunk}\\ \text{(lambda (p) (cont (cons v p)))))}\end{array}$

  $\begin{array}{l}\text{(set! cont (call-with-current-continuation}\\ \text{return-thunk))))))}\\ \text{(lambda () stmt }\mathrm{...}\text{)}\\ \text{(lambda () (set! yield old\_yield)))))))))}\end{array}$

  $\begin{array}{l}\text{(define for-iter (lambda (f iter)}\\ \text{(let* ((p (call-with-current-continuation iter))}\\ \text{(more (pair? p)))}\\ \text{(if more}\end{array}$

  $\begin{array}{l}\text{(let ((v (car p))}\\ \text{(c (cdr p)))}\\ \text{(f v) (for-iter f c))}\\ \text{'()))))}\end{array}$