**Exercise 1:**Write a program that returns 1 if run on

**Exercise 1a**

*(extra credit)*

**:**Write a program that

*crashes*or

*doesn't return*if run on

**Exercise 1b, essay**

*(extra extra credit)*

**:**Discuss the implications of your answers to exercises 1 and 1a to the semantics of the programs. In particular, briefly outline what changes to the various semantic models — denotational, operational, and/or axiomatic — take place upon introducing tail recursion.

Louis Reasoner wrote this program to sort numbers:

(define (smallest list predicate) ;; Returns the smallest element of list. (if (null? list) #f (if (predicate (car list) (cadr list)) (smallest (cons (car list) (cddr list)) predicate) (smallest (cdr list) predicate)))) (define (louis-sort list predicate) (do ((remainder list (cdr remainder)) (answer '() (append answer (cons (smallest remainder predicate) '())))) ((null? remainder) answer))) (define test-list (do ((i 0 (+ i 1)) (answer '() (cons i answer))) ((>= i 100) answer)))He complains “I am unable to debug this because

`smallest`

tail calls itself and leaves no trace on the stack. Look!1 ]=> (louis-sort test-list <) ;The object (), passed as an argument to safe-car, is not a pair. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1. 2 error> (debug) There are 9 subproblems on the stack. Subproblem level: 0 (this is the lowest subproblem level) Expression (from stack): (predicate (car list) ###) subproblem being executed (marked by ###): (cadr list) Environment created by the procedure: SMALLEST applied to: ((0) #[arity-dispatched-procedure 39]) The execution history for this subproblem contains 1 reduction. You are now in the debugger. Type q to quit, ? for commands. 3 debug> H H SL# Procedure-name Expression 0 smallest (predicate (car list) (cadr list)) 1 smallest (if (predicate (car list) (cadr list)) (smalle ... 2 do-loop (cons (smallest remainder predicate) (quote ())) 3 do-loop (append answer (cons (smallest remainder predi ... 4 do-loop (do-loop (cdr remainder) (append answer (cons ... 5 %repl-eval (let ((value (hook/repl-eval s-expression envi ... 6 %repl-eval/write (hook/repl-write (%repl-eval s-expression envi ... 7 do-loop (begin (if (queue-empty? queue) (let ((environ ... 8 loop (loop (bind-abort-restart cmdl (lambda () (der ...“I was expecting to see pending stack frames as the program recursively called

`smaller`

, but since they are all tail-recursive calls, I don't have a way of knowing how deep it went. I wish I could selectively enable or disable tail recursion for this one call...”**Exercise 2:**What trivial change can Louis make to his code for

`smaller`

that will disable tail recursion?Louis again has a problem. “I have a stack trace, but, but, well, just LOOK at it!

1 ]=> (louis-sort test-list <) ;The object (), passed as an argument to safe-car, is not a pair. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1. 2 error> (debug) There are more than 50 subproblems on the stack. Subproblem level: 0 (this is the lowest subproblem level) Expression (from stack): (predicate (car list) ###) subproblem being executed (marked by ###): (cadr list) Environment created by the procedure: SMALLEST applied to: ((0) #[arity-dispatched-procedure 39]) The execution history for this subproblem contains 1 reduction. You are now in the debugger. Type q to quit, ? for commands. 3 debug> H H SL# Procedure-name Expression 0 smallest (predicate (car list) (cadr list)) 1 smallest (if (predicate (car list) (cadr list)) (smalle ... 2 smallest (let ((answer (if (predicate (car list) (cadr ... 3 smallest (let ((answer (if (predicate (car list) (cadr ... 4 smallest (let ((answer (if (predicate (car list) (cadr ... 5 smallest (let ((answer (if (predicate (car list) (cadr ... 6 smallest (let ((answer (if (predicate (car list) (cadr ... 7 smallest (let ((answer (if (predicate (car list) (cadr ... 8 smallest (let ((answer (if (predicate (car list) (cadr ... 9 smallest (let ((answer (if (predicate (car list) (cadr ... 10 smallest (let ((answer (if (predicate (car list) (cadr ... 11 smallest (let ((answer (if (predicate (car list) (cadr ... 12 smallest (let ((answer (if (predicate (car list) (cadr ... 13 smallest (let ((answer (if (predicate (car list) (cadr ... 14 smallest (let ((answer (if (predicate (car list) (cadr ... 15 smallest (let ((answer (if (predicate (car list) (cadr ... 16 smallest (let ((answer (if (predicate (car list) (cadr ... 17 smallest (let ((answer (if (predicate (car list) (cadr ... 18 smallest (let ((answer (if (predicate (car list) (cadr ... 19 smallest (let ((answer (if (predicate (car list) (cadr ... 20 smallest (let ((answer (if (predicate (car list) (cadr ... 21 smallest (let ((answer (if (predicate (car list) (cadr ... 22 smallest (let ((answer (if (predicate (car list) (cadr ... 23 smallest (let ((answer (if (predicate (car list) (cadr ... 24 smallest (let ((answer (if (predicate (car list) (cadr ... 25 smallest (let ((answer (if (predicate (car list) (cadr ... 26 smallest (let ((answer (if (predicate (car list) (cadr ... 27 smallest (let ((answer (if (predicate (car list) (cadr ... 28 smallest (let ((answer (if (predicate (car list) (cadr ... 29 smallest (let ((answer (if (predicate (car list) (cadr ... 30 smallest (let ((answer (if (predicate (car list) (cadr ... 31 smallest (let ((answer (if (predicate (car list) (cadr ... 32 smallest (let ((answer (if (predicate (car list) (cadr ... 33 smallest (let ((answer (if (predicate (car list) (cadr ... 34 smallest (let ((answer (if (predicate (car list) (cadr ... 35 smallest (let ((answer (if (predicate (car list) (cadr ... 36 smallest (let ((answer (if (predicate (car list) (cadr ... 37 smallest (let ((answer (if (predicate (car list) (cadr ... 38 smallest (let ((answer (if (predicate (car list) (cadr ... 39 smallest (let ((answer (if (predicate (car list) (cadr ... 40 smallest (let ((answer (if (predicate (car list) (cadr ... 41 smallest (let ((answer (if (predicate (car list) (cadr ... 42 smallest (let ((answer (if (predicate (car list) (cadr ... 43 smallest (let ((answer (if (predicate (car list) (cadr ... 44 smallest (let ((answer (if (predicate (car list) (cadr ... 45 smallest (let ((answer (if (predicate (car list) (cadr ... 46 smallest (let ((answer (if (predicate (car list) (cadr ... 47 smallest (let ((answer (if (predicate (car list) (cadr ... 48 smallest (let ((answer (if (predicate (car list) (cadr ... 49 smallest (let ((answer (if (predicate (car list) (cadr ... 50 smallest (let ((answer (if (predicate (car list) (cadr ... 51 smallest (let ((answer (if (predicate (car list) (cadr ... 52 smallest (let ((answer (if (predicate (car list) (cadr ... 53 smallest (let ((answer (if (predicate (car list) (cadr ... 54 smallest (let ((answer (if (predicate (car list) (cadr ... 55 smallest (let ((answer (if (predicate (car list) (cadr ... 56 smallest (let ((answer (if (predicate (car list) (cadr ... 57 smallest (let ((answer (if (predicate (car list) (cadr ... 58 smallest (let ((answer (if (predicate (car list) (cadr ... 59 smallest (let ((answer (if (predicate (car list) (cadr ... 60 smallest (let ((answer (if (predicate (car list) (cadr ... 61 smallest (let ((answer (if (predicate (car list) (cadr ... 62 smallest (let ((answer (if (predicate (car list) (cadr ... 63 smallest (let ((answer (if (predicate (car list) (cadr ... 64 smallest (let ((answer (if (predicate (car list) (cadr ... 65 smallest (let ((answer (if (predicate (car list) (cadr ... 66 smallest (let ((answer (if (predicate (car list) (cadr ... 67 smallest (let ((answer (if (predicate (car list) (cadr ... 68 smallest (let ((answer (if (predicate (car list) (cadr ... 69 smallest (let ((answer (if (predicate (car list) (cadr ... 70 smallest (let ((answer (if (predicate (car list) (cadr ... 71 smallest (let ((answer (if (predicate (car list) (cadr ... 72 smallest (let ((answer (if (predicate (car list) (cadr ... 73 smallest (let ((answer (if (predicate (car list) (cadr ... 74 smallest (let ((answer (if (predicate (car list) (cadr ... 75 smallest (let ((answer (if (predicate (car list) (cadr ... 76 smallest (let ((answer (if (predicate (car list) (cadr ... 77 smallest (let ((answer (if (predicate (car list) (cadr ... 78 smallest (let ((answer (if (predicate (car list) (cadr ... 79 smallest (let ((answer (if (predicate (car list) (cadr ... 80 smallest (let ((answer (if (predicate (car list) (cadr ... 81 smallest (let ((answer (if (predicate (car list) (cadr ... 82 smallest (let ((answer (if (predicate (car list) (cadr ... 83 smallest (let ((answer (if (predicate (car list) (cadr ... 84 smallest (let ((answer (if (predicate (car list) (cadr ... 85 smallest (let ((answer (if (predicate (car list) (cadr ... 86 smallest (let ((answer (if (predicate (car list) (cadr ... 87 smallest (let ((answer (if (predicate (car list) (cadr ... 88 smallest (let ((answer (if (predicate (car list) (cadr ... 89 smallest (let ((answer (if (predicate (car list) (cadr ... 90 smallest (let ((answer (if (predicate (car list) (cadr ... 91 smallest (let ((answer (if (predicate (car list) (cadr ... 92 smallest (let ((answer (if (predicate (car list) (cadr ... 93 smallest (let ((answer (if (predicate (car list) (cadr ... 94 smallest (let ((answer (if (predicate (car list) (cadr ... 95 smallest (let ((answer (if (predicate (car list) (cadr ... 96 smallest (let ((answer (if (predicate (car list) (cadr ... 97 smallest (let ((answer (if (predicate (car list) (cadr ... 98 smallest (let ((answer (if (predicate (car list) (cadr ... 99 smallest (let ((answer (if (predicate (car list) (cadr ... 100 smallest (let ((answer (if (predicate (car list) (cadr ... 101 smallest (let ((answer (if (predicate (car list) (cadr ... 102 do-loop (cons (smallest remainder predicate) (quote ())) 103 do-loop (append answer (cons (smallest remainder predi ... 104 do-loop (do-loop (cdr remainder) (append answer (cons ... 105 %repl-eval (let ((value (hook/repl-eval s-expression envi ... 106 %repl-eval/write (hook/repl-write (%repl-eval s-expression envi ... 107 do-loop (begin (if (queue-empty? queue) (let ((environ ... 108 loop (loop (bind-abort-restart cmdl (lambda () (der ...“I wish I could start eliminating the tail call from the second call onwards...

**Exercise 3:**What trivial change can Louis make to his code for

`smaller`

that will enable tail recursion on all but the *initial*call to

`smaller`

? *(Hint, the*

**bold**

*text in the following backtrace shows how this differs from the first backtrace.)*

1 ]=> (louis-sort test-list <) ;The object (), passed as an argument to safe-car, is not a pair. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1. 2 error> (debug) There areLouis seems to have gotten his wish and is currently making progress despite the existence of tail recursion. Cy D. Fect, however, is unimpressed. He complains “Sure, it is trivial to disable tail recursion whenever you desire, but I don't like guessing whether the compiler is going to emit a tail call, and I'd simply rather not learn. I'd prefer some sort of10subproblems on the stack. Subproblem level: 0 (this is the lowest subproblem level) Expression (from stack): (predicate (car list) ###) subproblem being executed (marked by ###): (cadr list) Environment created by the procedure: SMALLEST applied to: ((0) #[arity-dispatched-procedure 39]) The execution history for this subproblem contains 1 reduction. You are now in the debugger. Type q to quit, ? for commands. 3 debug> H H SL# Procedure-name Expression 0 smallest (predicate (car list) (cadr list)) 1 smallest (if (predicate (car list) (cadr list)) (smalle ...2 smallest (let ((answer (smallest list predicate))) answer)3 do-loop (cons (smallest remainder predicate) (quote ())) 4 do-loop (append answer (cons (smallest remainder predi ... 5 do-loop (do-loop (cdr remainder) (append answer (cons ... 6 %repl-eval (let ((value (hook/repl-eval s-expression envi ... 7 %repl-eval/write (hook/repl-write (%repl-eval s-expression envi ... 8 do-loop (begin (if (queue-empty? queue) (let ((environ ... 9 loop (loop (bind-abort-restart cmdl (lambda () (der ...

*declaration*or

*decoration*so I can explicitly tell the compiler to

*not*emit a tail call. Something like this:

(define (smallest list predicate) ;; Returns the smallest element of list. (if (null? list) #f (if (predicate (car list) (cadr list)) ;; This branch should leave a backtrace - CDF (disable-tail-recursion (smallest (cons (car list) (cddr list)) predicate)) (smallest (cdr list) predicate))))

**Exercise 4:**Implement

`disable-tail-recursion`

as a macro.**Homework:**Fix Louis's code.