Re: Proper Tail Recursive C++

I think an example would help. If "properly tail recursive" has the
meaning given to it by the functional programming community (e.g. the
IEEE/ANSI Scheme standard), then a properly tail recursive C++
compiler would have to translate the following program into machine
code that terminates without overflowing the stack, heap, or any other
storage segment, even on a tiny machine with much less than a megabyte
of memory.


#include <iostream.h>
#include <stdlib.h>


int f (int);
int g (int[]);


int f (int n) {
        int A[1000];
        A[0] = n;
        A[999] = n;
        return g (A); // tail-recursive call to g
}


int g (int A[]) {
        const int n = (A[0] + A[999]) / 2;
        if (n > 0)
                return f (n - 1); // tail-recursive call to f
                return 0;
}


void main(void) {
        const n = 1000000;
        if (f (n) == 0)
                cout << "This C++ compiler is properly tail recursive!" << endl;
        else cout << "This can't happen" << endl;
}


It is extremely unlikely that any C++ compiler is properly tail
recursive in this sense. On the other hand, every implementation
of Scheme and Standard ML is required to be properly tail recursive,
so any implementation of those languages can be used to run the
equivalent of the above program.


Will


--------
; Scheme code to demonstrate that implementations of
; Scheme are required to be properly tail recursive.
; On a SPARC-10/51, with a decent Scheme compiler, this program
; takes about two minutes to run, most of which is spent zeroing
; the elements of the newly allocated vectors.


(define (f n)
    (define A (make-vector 1000))
    (vector-set! A 0 n)
    (vector-set! A 999 n)
    (g A))


(define (g A)
    (define n (quotient (+ (vector-ref A 0)
                                                  (vector-ref A 999))
                                            2))
    (if (> n 0)
            (f (- n 1))
            0))


(define (main)
    (define n 1000000)
    (if (= (f n) 0)
            (display "This Scheme compiler is properly tail recursive!")
            (display "This can't happen"))
    (newline))
--

Return to the comp.compilers page.
Search the comp.compilers archives again.