> I do not believe that there is anything meaningful about FB@:FT
> relevant to tail recursion.
You are right, of course, FB@:FT, as stated in my petty claim, has little,
if anything, to do with tail recursion. Indeed, the claim does not say
much because no restrictions on the nature of FB and FT are imposed.
Consequently, even recursive verbs which are not in tail recursive form can
be trivially written as FB@:FT. Remember the quicksort troublemaker verb
[0]?
quicksort=. (($:@(< # [) , (= # [) , $:@(> # [)) ({~ ?@#))^:(1 < #)
one can readily rewrite it as quicksort=. FB@:FT,
quicksort=. ]@:((($:@(< # [) , (= # [) , $:@(> # [)) ({~ ?@#))^:(1 < #))
However, that is precisely my point, your claim, as originally stated, is
not very different (it does not say much either) because no restrictions on
the nature of FB and FT were imposed. One can define quicksort as
FB^:FT^:_ by choosing FT as 1:. Do you see how FB can be defined to
fulfill your claim? A version of FT (named tricky) for this case is shown
later in this post to avoid a spoiler for those who might like to write
their own versions. Indeed,
qs=. tricky^:1:^: _
(qs -: quicksort) 6 5 9 8 5 2 7 5 4 0 1 2 7 4 9
1
You wrote: "I would be interested in seeing a counter-example that destroys
my belief, if counter examples exist." However, how can one try to think
about a possible counterexample if even recursive verbs, which are not in
tail recursion form, can be written in such fashion?
Perhaps entertaining another example might bring some clarity. Remember
the verb evolve [1] which is in tail recursive form? Not surprisingly,
changing what needs to be changed in tricky results in,
tricky^:1:^:_ 'METHINKS IT IS LIKE A WEASEL'
METHINKS IT IS LIKE A WEASEL
Surely the definitions for FB and FT that you might have in mind for this
case are quite different. Are they not? Can you tell us what those
definitions are?
References
[0] [Jprogramming] Tacit Expressions with Explicit J Syntax
http://www.jsoftware.com/pipermail/programming/2017-October/049085.html
[1] [Jprogramming] Recursive tail calls (WAS: Tacit exercise)
http://www.jsoftware.com/pipermail/programming/2009-December/017529.html
The verb tricky can be defined (wickedly) as follows,
o=. @:
c=. "_
rank=. (;:'"')(0:`)(,^:) NB. Verbing " (dyadic verb)
lrw=. (_2 }. ":) o (rank&_) NB. Linear representation (monadic
verb)
k=. ] [ (". o ([ , '=. ' , lrw @:])) NB. Keep (monadic verb)
tricky=. R_tricky_ c :: ('R_tricky'&k) o (quicksort f.)
On Tue, Jan 9, 2018 at 8:11 PM, Raul Miller <[email protected]> wrote:
> I do not believe that there is anything meaningful about FB@:FT
> relevant to tail recursion.
>
> A tail recursive function has the characteristic that no matter how
> deep you nest the stack, the result returned from the final result
> will be the result of all routines which called it.
>
> This matches how inductive verbs work. The difference, of course, is
> that there is no stack (which is all that tail recursion was about in
> the first place).
>
> The requirement imposed by induction is that you refactor the original
> recursive function so that the test (for whether you enter recursion)
> be separable in some way from the rest of the code.
>
> How does FB@:FT have anything to do with any of this?
>
> Thanks,
>
> --
> Raul
>
>
> On Tue, Jan 9, 2018 at 6:51 PM, Jose Mario Quintana
> <[email protected]> wrote:
> > I am not entirely sure what you are trying to convey either. Apparently,
> > you are implying that "F=: FB^:FT^:_" would be, in some sense, simpler
> than
> > the original F but that might not be necessarily the case (depending on
> the
> > nature of FB and FT; which you did not specify).
> >
> > Your claim, to me (so far), is not much different than, for example,
> >
> > If I have a recursive verb (F y) implemented in J, which satisfies the
> > constraints for tail recursion, I believe that there is always a pair
> > of companion functions (FB y) (FT y) such that an F workalike can be
> > written:
> >
> > F=: FB@:FT y
> >
> > (So what?)
> >
> >
> > On Mon, Jan 8, 2018 at 7:45 PM, Raul Miller <[email protected]>
> wrote:
> >
> >> I'm not entirely sure what issue you are trying to raise here, so I will
> >> guess:
> >>
> >> In languages which support tail recursive optimizations for recursive
> >> functions, those optimizations can still be deployed if the function
> >> in question contains an expression which uses some different recursive
> >> function. Why should J's induction be any different?
> >>
> >> Thanks,
> >>
> >> --
> >> Raul
> >>
> >>
> >>
> >> On Mon, Jan 8, 2018 at 7:08 PM, Jose Mario Quintana
> >> <[email protected]> wrote:
> >> > The claim [2], as written, does not impose any restrictions on FN or
> FT
> >> > apart from being monadic; thus, F itself could be embedded in FB and
> >> could
> >> > provide an opportunity to cheat and defeat its purpose.
> >> >
> >> > Surely you mean something more substantial. Can you elaborate your
> >> claim?
> >> >
> >> >
> >> > On Wed, Jan 3, 2018 at 8:09 AM, Raul Miller <[email protected]>
> >> wrote:
> >> >
> >> >> [1]
> >> >>
> >> >> If I have a tail recursive function F, which calls function G, there
> >> >> is normally no problem with G signaling that F needs to exit. Just
> >> >> return a distinguished value from G and in F have an if statement
> >> >> which returns when that happens. Since F is tail recursive, nothing
> >> >> more needs done.
> >> >>
> >> >> So I would like to see an example of how this description:
> >> >>
> >> >> >> I have a deeply embedded function that discovers that it has
> >> completed
> >> >> the
> >> >> >> task set before it. ...
> >> >> >>
> >> >> >> This function was not part of the initial design.
> >> >>
> >> >> has anything to do with tail recursion.
> >> >>
> >> >> [2]
> >> >>
> >> >> If I have a recursive verb (F y) implemented in J, which satisfies
> the
> >> >> constraints for tail recursion, I believe that there is always a pair
> >> >> of companion functions (FB y) (FT y) such that an F workalike can be
> >> >> written:
> >> >>
> >> >> F=: FB^:FT^:_ y
> >> >>
> >> >> which satisfies the "bounded stack usage" guarantee of tail
> recursion.
> >> >> And this form has an additional advantage, which is that a rewrite
> >> >> which removes the bounded stack character requires work on the part
> of
> >> >> the developer which is quite significant - it's unlikely that you
> will
> >> >> have someone making such changes without realizing that they are
> doing
> >> >> so.
> >> >>
> >> >> But I would be interested in seeing a counter-example that destroys
> my
> >> >> belief, if counter examples exist.
> >> >>
> >> >> Thanks,
> >> >>
> >> >> --
> >> >> Raul
> >> >>
> >> >>
> >> >> On Wed, Jan 3, 2018 at 5:44 AM, Erling Hellenäs
> >> >> <[email protected]> wrote:
> >> >> > Try to remove all references to persons from your postings.
> >> >> >
> >> >> > I don't think my post is in any way strange. According to my
> >> judgement no
> >> >> > further explanation is needed.
> >> >> >
> >> >> > /Erling
> >> >> >
> >> >> >
> >> >> > Den 2018-01-02 kl. 13:18, skrev Raul Miller:
> >> >> >>
> >> >> >> If you would answer those two questions we could do that.
> >> >> >>
> >> >> >> Thanks,
> >> >> >>
> >> >> >
> >> >> > ------------------------------------------------------------
> >> ----------
> >> >> > For information about J forums see http://www.jsoftware.com/
> >> forums.htm
> >> >> ------------------------------------------------------------
> ----------
> >> >> For information about J forums see http://www.jsoftware.com/
> forums.htm
> >> >>
> >> > ------------------------------------------------------------
> ----------
> >> > For information about J forums see http://www.jsoftware.com/
> forums.htm
> >> ----------------------------------------------------------------------
> >> For information about J forums see http://www.jsoftware.com/forums.htm
> >>
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
