re: tail recursion

[Dick Gabriel <RPG@SAIL.Stanford.EDU>]

[In reply to message from dyb@iuvax.cs.indiana.edu sent Fri, 20 Apr 90 14:34:47 -0500.]

I'm not sure it's a well-defined term.

    How about this:

    The net (modulo storage reclamation) amount of storage space consumed
    by performing any sequence of tail calls p1 => p2 => ... => pn is no
    more than the amount that would be consumed by performing a direct tail
    call from p1 => pn.

What if the storage space for p1 => ... => pn is the space needed for p1
=> pn + 1? +k? *k? What if it's arbitrarily large, but all infinite tail
call programs loop forever with the right behavior?  How would you test
whether an implementation had this property?

Scheme requires iteration through function call. Other lanaguages have
restrictions on the size of iteration (oh? Consider they cannot be larger
than indexes for those machines.) If my implementation has other
restrictions based on size, why shouldn't this be one of them, especially
if you cannot verify the property *without* looking at the implementation
source?

I've mentioned before that this requirement might prevent certain
implementation choices. For example, a hardware vendor has told me that in
n years, it will support only languages in the ``mainstream'' where
mainstream means that these languages use their common backend. Other
vendors have said the same thing. I am in the process of determining
whether I can convince their compiler backend guys to support tail call
optimizations. If I cannot, I don't have a viable Common Lisp for that
system, because the implementation requires it. Are you so happy to put
Scheme out of the mainstream for that vendor? 

Well, of course you are, because you wouldn't be Scheme-heads otherwise!

(I don't know how to make a smiley face with ASCII characters, so here's a
duck instead. Please take it as a smiley face:

                      ________ 
		     | Quack? |
		      --------
           _           /
          /@@____   _ /
          |  ____]     
\        / /
 \------/ /
  \  <<  /
   \____/
     | |
     <]<]

)

				-rpg-