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 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.
10 comments:
I may be wrong, but it seems to me that anything you do to defeat tail recursion, short of calling write-char, can be removed by a compiler that does interprocedural optimization and effects analysis. For example, you can rewrite (f x) in tail position as (let ((y (f x))) (cons 'a 'b) y), but the SSC will see that the result of this cons is garbage no matter what silly procedures you nest it in, and remove the call to it. (I'll agree that even a SSC can't notice that the write-char is being done to a junk output file and remove it!)
John: You could easily set up a situation where, to determine whether the optimization is possible, the compiler would need to solve the halting problem. So any optimizer would have to give up in some cases.
Can your sufficiently smart compiler™ solve the halting problem?
If not, how can it ‘remove the call to [cons]’ without proving that every ‘silly procedure you nest it in’ does in fact halt?
Consider this code:
(define (solution-exists? solution-finding-program)
(let ((test-program
(sufficiently-smartly-compile
`(define (test)
(forward-reference
,solution-finding-program)
#t))))
(assembly-code/contains-call?
test-program
'forward-reference)))
If the SSC™ can optimize this, then we can solve the halting problem. On the other hand, if the SSC™ cannot optimize it, then we have a suitable mechanism for reliably and predictably defeating tail recursion.
GCC can optionally optimize tail calls using the -foptimize-sibling-calls switch.
I wrote a C function, is_tail_recursive,
that compares the addresses of local variables in different invocations. It works, at least for GCC 4.4.5.
So that solves exercise 1. Given the predicate is_tail_recursive, exercise 1a is trivial, so I'm not sure why that's an extra credit problem. (-:
Here it is.
https://gist.github.com/898702
kbob said...
I wrote a C function, is_tail_recursive,
that compares the addresses of local variables in different invocations. It works, at least for GCC 4.4.5.
Please post! (Convert leading space characters to chars for indentation.)
Why do you think it works?
/*
* In a separate compilation unit, save is defined as:
*
* void save(int *p)
* {
* *p = (int)&p;
* }
*/
extern void save(int *);
void recurse(int n, int *p)
{
if (n == 0)
return;
save(p);
recurse(n - 1, p + 1);
}
int is_tail_recursive(void)
{
int a[2];
recurse(2, a);
return a[0] == a[1];
}
This code tests if the addresses of the arguments change during a recursive call. But you need two additional assumptions:
1. Without tail recursion a compiler is prohibited from moving stack frames.
2. With tail recursion, a compiler is required to use stack frames in a particular order.
It is unlikely someone would write a compiler that did not optimize tail recursion but nevertheless moved stack frames around, so the test for non tail recursion is unlikely to fail. (But it isn't inconceivable.) However, a compiler like Chicken, which most definitely supports tail recursion, would not pass this test.
Can you write a test that depends solely on the language definition and not on the quirks of a particular implementation of the compiler?
In the spirit of your 1a exercise and kbob's suggestion, here's a program that should work, but would crash if a compiler tried to naively apply TCO:
http://pastebin.com/c8QbsqYm
Happily, GCC is pretty smart! On -O2 and -O3, it will tail-call optimize acc_normal_rec, but it will refuse to tail-call optimize acc_evil_rec -- presumably it has a heuristic like "don't do TCO if the call takes any references to local variables."
mquander said...
here's a program that should work, but would crash if a compiler tried to naively apply TCO
You're adding the additional assumption that your compiler has a particular kind of bug. Can you write a test that depends solely on the language definition and not on the quirks of a particular implementation of the compiler?
Assume this: I have an ANSI C interpreter that is very pedantic and perverse. It rigidly follows the defined semantics of ANSI C, but it handles `unspecified behavior' (according to the language spec) by silently modifying memory in an undocumented way. (I believe that `unspecified behavior' covers that possibility.)
So why do you think your program would properly distinguish a tail-recursive interpreter from a non-tail-recursive one?
If tail-call optimization is defined only in terms of space used, then Exercise 1 requires a way to detect space usage without crashing unrecoverably. In a sufficiently underspecified language, this is impossible; e.g. in R5RS Scheme, memory might be infinite, and memory usage might vary arbitrarily for reasons unrelated to your program, and there's no way to ask about memory usage or catch out-of-memory errors — and any of these possibilities makes tail-recursion potentially unobservable. But anything is impossible in a sufficiently underspecified language, so this interpretation isn't very interesting. Given the realistic assumptions of upper and lower bounds on available memory, no arbitrary memory use (e.g. no more than a naive interpreter), and a way to catch out-of-memory errors, can't we always detect TCO by recursing to a depth exceeding the maximum possible memory, and catching out-of-memory errors? Or by measuring the maximum possible depth by nontail recursion, and seeing whether it varies when wrapped in different depths of tail recursion?
I think the argument that a SSC could rewrite the program to run in constant space is not a problem, because a compiler that does so is a tail-recursive compiler, as far as is observable. We can't determine the implementation's behavior on *all* programs, only what it does for specific programs.
It is odd that Scheme requires a space optimization without specifying anything else about space. Is the point you're trying to make here that tail-call optimization is meaningful only wrt the informal operational semantics?
Post a Comment