Went to the J WIKI. Found a tacit quicksort.
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?...@#)) ^: (1<#)
See http://www.jsoftware.com/jwiki/Essays/Quicksort for details.
On Fri, Dec 18, 2009 at 4:55 PM, Henry Rich <[email protected]> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
