On 12/22/09, Raul Miller <[email protected]> wrote:
> On Tue, Dec 22, 2009 at 6:44 PM, Dan Bron <[email protected]> wrote:
>> If I were interested in specific examples of RTCs in J (as opposed to
>> supporting TCO as general, special code) I might think of tree
>> applications,
>> where trees are represented by nested boxes. Of course, trees can be
>> adequately represented by (sparse) open arrays and handled as such, but at
>> least my first instinct in processing trees is boxes and $: . I would
>> call that the "natural approach", and it is the sort of thing I would like
>> to see optimized (so that I don't have to come up with insightful new
>> approaches).
>>
>> I might also search the Forum archives for instances of the phrase "stack
>> error", or $: more generally (which won't be too overwhelming, as $:
>> doesn't see much use in J, for the reasons previously discussed).
>
> My problem is not finding recursive code.
>
> My problem is finding tail recursive code.
>
> So, ok, let's just work with factorial.
>
> This is a recursive implementation of factorial which is not
> tail recursive:
> 1:`(* $:@<:)@.* 3
>
> This is a recursive implementation of factorial which is
> tail recursive:
> 1 ([`(* $: <:@])@.(*...@])) 3
>
> (Note, by the way, that the $: mechanism means that
> I can not incorporate the required left argument (1)
> into the definition of this verb.)
>
> Anyways, with just these two verbs as examples,
> the task of recognizing (and automatically
> rewriting) tail recursive verbs seems potentially
> challenging.
Hopefully to spark some ideas and creativity I present this:
1:`(] * $:@<:)@.* NB. Raul's first verb but with a fork instead of hook
┌─ 1:
│ ┌─ ]
┌───┤ ├─ *
│ └────┤ ┌─ $:
── @. ─┤ └─ @ ─┴─ <:
└─ *
([`(* $: <:@])@.(*...@])) NB. the second verb
┌─ [
│ ┌─ *
┌─────┤ ├─ $:
│ └───┤ ┌─ <:
── @. ─┤ └─ @ ─┴─ ]
│ ┌─ *
└─ @ ─┴─ ]
In terms of recognition the second case has $: at the center of the
fork and thus at the tail. As far as automatically re-writing the
first as the second, it seems like science fiction in the general case
(I would like to know if anyone knows of any papers on this subject)
but in specific cases there may be some possibilities. In the above
example we replaced (] g $:@:h) y with x (g $: h@:]) y. I wonder if
this holds in general or for some specific class of verbs. Of course
we would also need to be able to deduce the correct initial value of
the accumulator.
>
> --
> Raul
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
