Abstract Heresies: 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.

10 comments:

John CowanApril 1, 2011 at 11:38 AM
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!)
mquanderApril 1, 2011 at 11:58 AM
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.
Joe MarshallApril 1, 2011 at 12:07 PM
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.
kbobApril 1, 2011 at 12:22 PM
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. (-:
kbobApril 1, 2011 at 12:30 PM
Here it is.

https://gist.github.com/898702
Joe MarshallApril 1, 2011 at 12:31 PM
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?
Joe MarshallApril 1, 2011 at 1:37 PM
/*
* 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?
mquanderApril 1, 2011 at 4:12 PM
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."
Joe MarshallApril 1, 2011 at 4:51 PM
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?
Arcane SentimentApril 4, 2011 at 7:15 PM
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?

Friday, April 1, 2011

Exercises

10 comments: