> compilers ... replace the computational algorithm, written by a human, by a more asymptotically efficient one. Andrew Appel in Compiling with Continuations g

> compilers ... replace the computational algorithm, written by a human, by a more asymptotically efficient one. Andrew Appel in Compiling with Continuations gave an example of this. I forget exactly how it went, but it was something like this: (define (range a b) (if (> a b) '() (cons a (range (+ a 1) b)))) (define (sum xs) (if (null? xs) 0 (+ (car xs) (sum (cdr xs))))) (define (triangle-sum n) (if (= n 0) 0 (let* ((xs (range 1 n)) (triangle (sum xs))) (+ triangle (triangle-sum (- n 1)))))) The triangle-sum program, which adds the triangular numbers from 1 to n, will, as written, consume O(n^2) space, because it creates the list "xs" of length n before recursing down to n-1, and the list will not be freed until the entire computation terminates. An optimizing compiler might discover that, once it's computed "triangle", it can discard the list "xs"; this would reduce the required space to O(n). Hoisting a computation like (length <list-of-length-n>) out of a loop can similarly reduce the time taken from O(n^2) to O(n).