On Thu, 31 Jan 2002, Andrew C. Greenberg wrote:

> Ok, but what exactly are you criticizing here?  The functional semantics
> or the block closure semantics?  Clearly, the standard optimization
> discussed earlier in these threads is no different from the mechanical
> one I suggested, more or less (except that the generated code WOULD
> probably change the parameters)?  Are you observing that present Squeak
> block semantics make that optimization semantically unstable, or
> something else?

I'm expressing a feature request for proper tail recursion. :)

> Indeed, perhaps all we are doing here is observing that the apparent
> tail recursion in this example doesn't actually occur in a tail context
> (and, by at least some definitions, isn't a tail recursion)?  Does the
> new block closure semantics harmonize these issues?

I don't know.

> doing this).  The real culprit in this not doing what YOU intended is
> the lack of genuine blockcontexts

What do you mean about this?

Agreed, tail call can frequently turned into iteration. But, the code
above is fragile in some ways, in that any change to the function
necessitates undoing the mechanical transformation you have made, making
the change, and redoing it.

Its hard to come up with a good, yet simple example.

Ah, how about quickfind?

quickfind: foo :in orderedCollectoin from: start to: end
   start = end ifTrue: [^start]
   ... do some stuff to  partitian the array ...
   foo < key ifTrue: [^self quickfind: foo in: orderedCollection from:
                               start to: keyloc-1]
   foo < key ifFalse: [^self quickfind: foo in: orderedCollection from:
                               keyloc to: end]

Which, can be done in the form of tail recursion, but it would opaquify
the core essence. Another example is quicksort. The worst-case performance
of the naieve quicksort is O(n) stackslots. With tail recursion, the
worst-case performance becomes O(log n). (Recurse on the smaller side,
tail-recurse on the bigger side.)

Other simlar examples are types of combinatorial search problem, where you
break a problem into subproblems, you solve the smaller subproblems
recursively, but tail-recurse on the big subproblem. This can avoid using
excessive stack space.


ALthough instances of tail recursion can be mechanically transformed in
the way you illustrate, instances of mutual tail recursion are not so
straightforwad. For example, mutual tail recursion, especially when the
methods being tail-recursed sit in different, possibly subclassible
classes.  (I cannot come up with an immediate non-contrived example which
cannot be rewritten such that it does not require mutual tail recursion.)


Perhaps the best thing that can be said is that having tail recursion does
allow coding in a different paradigm. And being able to code things in
more than one fashion is always an advantage.


Scott