Brian Denheyer <briand@deldotd.com> wrote:
+---------------
| It seems to me that tail1 is NOT tail-recursive because you must "wait"
| for the procedures to return to accumulate the result. It seems to me
| that tail2 IS tail recursive because it doesn't _have_ to return, i.e. I
| can create the new values and call loop without ever having to look back.
| I believe this to be the "goto with parameters style".
+---------------
So far so good...
+---------------
| (define tail2
| (lambda (proc ls)
| (let loop ((ls ls)
| (accum '()))
| (if (null? ls)
| accum
| (loop (cdr ls) (cons (proc (car ls)) accum))))))
...
| The only thing is, it seems like tail2 is going to cons a lot
| more, because it is creating a new list on every iteration.
+---------------
Say what? Which "new list"? "Tail2" does the same explicit cons the other
one does, only before the tail call instead of after the non-tail call.
In both cases the "new" generated list shares structure (all but the new
first pair) with the result of the previous iteration.
But "tail2" doesn't do the implicit/hidden consing that the non-tail
version needs (to know where to come back to). [Let's ignore for the
moment issues of linear stacks vs. heap-based stacks...]
By the way, remember that the "proper tail call" property *doesn't* mean
that hidden consing won't happen, only that the tail calls will not result
in a *net* increase in "live" storage, given a reasonable garbage collector.
+---------------
| Do I have this right ? Should I therefore maintain a coding style
| which uses tail2 form instead of tail1 form ?
+---------------
The tail-recursive version should not "blow the stack" no matter how long
the input data is; the non-tail one may, if the input is long enough.
Both versions may (or may not, depending on the degree of optimization
in the implementation) generate anonymous temporary variables (especially
activation records) which quickly become garbage, but the GC should take
care of these.
-Rob
-----
Rob Warnock, 8L-855 rpw3@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-933-0511
Mountain View, CA 94043 PP-ASEL-IA