Can we come down from the lofty heights of theory to give a practical
example of how TCO would work in J? I'm having trouble seeing it.
If I write quicksort in C, it looks like
qsort(array,hi,lo) {
do {
bounds = partition(array,hi,lo);
qsort(array,bounds of smaller partition);
hi, lo = bounds of larger partition;
} while (there is more to do);
}
Classic tail recursion.
In tacit J, I wouldn't be able to do it this way. Not for lack of
tail-recursion support, but because there is no way to amend an array in
place tacitly, so the concept of sorting subarrays is stillborn.
But let's ignore that - assume that somehow Roger works out a way to
allow in-place array modification. What would the code look like? I
get something like
qs =: ((($: {.) ($: {:) ]) or...@partition)^:(1< -/@])
where I am assuming that qs is a dyad with x=array and y=hi,lo. 'order'
will create the partitions in the order they are to be applied, as a
shape-2 2 array.
This would benefit from tail-recursion. How hard would it be to write
it using ^:?
To begin with, it would have to be rewritten as a monad:
qsm =: ({. ($:@(, {.) $:@(, }:) ]) or...@part)^:(1<-/@:>@}:)
[I would like to stick in the observation that the tail recursion is the
second $:, and I think that detecting that will be a problem. It's
impossible by analysis, and might be difficult even during the parse:
the ^: conjunction is still in control, and there would have to be
special flags to detect that ^: is going to do nothing more to the
result from $: . Seems Very Difficult at the least.]
Now we can move the tail recursion to the very end and turn it into a loop:
qsmt =: $:@({. ($:@(, {.) (, }:) ]) or...@part)^:(1<-/@:>@}:)
qsmtl =: ({. ($:@(, {.) (, }:) ]) or...@part)^:(1<-/@:>@}:)^:_
Is that all there is to it?
Again, if we were doing qsort in practical J, we would not have in-place
array modification, and we would code
qsp =: (($:@(substr~ {.) , $:@(substr~ {:)) partition)^:(1< -/@])
but here, there's no tail recursion possible, because $: isn't the tail:
, is.
So for quicksort I conclude that tail-recursion elimination is
impractical and perhaps impossible for tacit code; that conversion to
using ^:_ entails the nuisance of converting a dyad to a monad but is
otherwise trivial; and that TCO is best handled in explicit code.
Henry Rich
Raul Miller wrote:
> On Fri, Dec 18, 2009 at 5:20 PM, Dan Bron <[email protected]> wrote:
>>> phase 2: how would you implement this mechanism
>>> in J, given the atomic representations of the sentences
>>> in question.
>> I don't know, how do other functional languages do it? A while loop and a
>> stack?
>
> There are two issues here:
>
> Recognizing TCO -- this winds up being symbolic manipulation
> of the code, and generally winds up with some obscure corner
> cases which most people tolerate and other people get frustrated
> with.
>
> Handling TCO -- this winds up being a while loop without
> a stack. If you need a stack, it is not tail recursion.
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
