Friday, April 1, 2011

Exercises

Apparently I was not as clear with my questions as I thought I was. I've edited the questions to make them more precise. The additional text is in this alternative color.

Exercise 1: Write a program that returns 1 if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.  The goal is not to find a program and language implementation pair that exhibit the behavior, but to design a program that can correctly infer whether on not any supplied language implementation supports tail recursion by examining its own behavior.

Exercise 1a (extra credit): Write a program that crashes or doesn't return if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.  The goal is not to find a program and language implementation pair that exhibit the behavior, but to design a program that can correctly infer that any supplied implementation does not support tail recursion (this is a weaker condition because we do not require that the program correctly infer support of tail recursion, but only lack of support).

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 are 10 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 (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 ...
Louis 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 of 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.
Post a Comment