As quicksort is not tail recursive, I do not see how tail recursion should be relevant to quicksort.
As for evolve - my memory is unclear and the only working examples I see for it are equivalent to the identity function, so I do not know how I could test my work for correctness. (Though I doubt you would be happy with FB=: ] and FT=:0:) Perhaps you could shed a bit more light on whatever it is that you are trying to talk about? Thanks, -- Raul On Wed, Jan 10, 2018 at 7:39 PM, Jose Mario Quintana <[email protected]> wrote: >> 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
