I may not have an accurate understanding of the relationship between
function-level iteration in J and tail recursion. I'm particularly interested in Power (^:) but several other primaries may apply, most obviously Self. Up to now I've thought that tail recursion is not applicable to J. Thus in a discussion of functional programming on Twitter I've said that J provides a counterexample which refutes the claim that tail-call optimization (TCO) is necessary and important to a "functional programming" computer language. As I've studied more on the topic of TCO it occurred to me that perhaps J's memory-management may rightly be labeled TCO in the cases I have in mind. As examples, consider f1a and f1b here: http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence My questions, then, are: Does J sometimes involve tail recursion? If yes, but not in all recursions, how can we differentiate? Is ^: best thought of as non-recursive? Does such categorization matter? Thanks, Tracy ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
Tail recursion is a strategy for optimization.
If a language already has recursion then tail recursion does not add to its expressiveness. Currently J does not exploit tail recursion. If/when appropriate the strategy can be implemented. It'd be another implementation trick like those already in Appendix B (Special Code) of the dictionary. I believe M. (memo) offers greater benefits for recursive functions than tail recursion. I don't see much advantage to thinking of f^:n as a recursion. It is not implemented as a recursion (does not use the call stack), and it's not defined recursively. What is function-level iteration? ----- Original Message ----- From: Tracy Harms <[hidden email]> Date: Wednesday, May 13, 2009 14:48 Subject: [Jprogramming] tail recursion/TCO? To: Programming forum <[hidden email]> > I may not have an accurate understanding of the relationship between > function-level iteration in J and tail recursion. I'm particularly > interested in Power (^:) but several other primaries may apply, most > obviously Self. > > Up to now I've thought that tail recursion is not applicable to J. > Thus in a discussion of functional programming on Twitter I've said > that J provides a counterexample which refutes the claim that > tail-call optimization (TCO) is necessary and important to a > "functional programming" computer language. > > As I've studied more on the topic of TCO it occurred to me that > perhaps J's memory-management may rightly be labeled TCO in the cases > I have in mind. As examples, consider f1a and f1b here: > http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence > > My questions, then, are: > > Does J sometimes involve tail recursion? > > If yes, but not in all recursions, how can we differentiate? > > Is ^: best thought of as non-recursive? Does such categorization > matter? > Thanks, For information about J forums see http://www.jsoftware.com/forums.htm |
I made up the phrase "function-level iteration" in an attempt to point
to iteration that is built into primaries such as ^: not done through recursive techniques nor built through a conventional control-word structure (such as for-next, do-while, and repeat-until). (The term doesn't seem to communicate that idea well.) Thank you for confirming what I had initially understood to be the case, that (to date) J has not exploited tail recursion. My confidence is bolstered that J therefore stands as disproof of the idea, common in some circles, that in order to be a "serious" "functional" language a programming language must implement tail recursion optimization. If there is a term that categorizes ^: along with other non-recursive techniques for iteration on immutable entities, I'm eager to add it to my vocabulary. Apparently this sort of thing is scarce outside the APL family. On Wed, May 13, 2009 at 7:24 PM, Roger Hui <[hidden email]> wrote: > Tail recursion is a strategy for optimization. > If a language already has recursion then tail > recursion does not add to its expressiveness. > Currently J does not exploit tail recursion. > If/when appropriate the strategy can be > implemented. It'd be another implementation > trick like those already in Appendix B (Special > Code) of the dictionary. > > I believe M. (memo) offers greater benefits > for recursive functions than tail recursion. > > I don't see much advantage to thinking of f^:n > as a recursion. It is not implemented as > a recursion (does not use the call stack), > and it's not defined recursively. > > What is function-level iteration? > > > > ----- Original Message ----- > From: Tracy Harms <[hidden email]> > Date: Wednesday, May 13, 2009 14:48 > Subject: [Jprogramming] tail recursion/TCO? > To: Programming forum <[hidden email]> > >> I may not have an accurate understanding of the relationship between >> function-level iteration in J and tail recursion. I'm particularly >> interested in Power (^:) but several other primaries may apply, most >> obviously Self. >> >> Up to now I've thought that tail recursion is not applicable to J. >> Thus in a discussion of functional programming on Twitter I've said >> that J provides a counterexample which refutes the claim that >> tail-call optimization (TCO) is necessary and important to a >> "functional programming" computer language. >> >> As I've studied more on the topic of TCO it occurred to me that >> perhaps J's memory-management may rightly be labeled TCO in the cases >> I have in mind. As examples, consider f1a and f1b here: >> http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence >> >> My questions, then, are: >> >> Does J sometimes involve tail recursion? >> >> If yes, but not in all recursions, how can we differentiate? >> >> Is ^: best thought of as non-recursive? Does such categorization >> matter? >> 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 |
IMO as I write most of the loops with the lots of looping builtins
like rank, insert, and power etc, I rarely use recursion, so it does not really matter if the interpreter does tail recursion or not. Ambrus ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
On Wed, May 13, 2009 at 10:39 PM, Zsbán Ambrus <[hidden email]> wrote:
> IMO as I write most of the loops with the lots of looping builtins > like rank, insert, and power etc, I rarely use recursion, so it does > not really matter if the interpreter does tail recursion or not. > Whether the language implement TCO does have an impact on the tendency to use recursion or not(for the fear of stack overflow). That said, I found Haskell's lazy evaluation having a greater benefit for writing recursive style function. As writing 'TCOtable' function is not that simple. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by Roger Hui
On Wed, May 13, 2009 at 10:24 PM, Roger Hui <[hidden email]> wrote:
> I believe M. (memo) offers greater benefits > for recursive functions than tail recursion. I agree with you, but M. currently only offers support for a rather limited domain. Perhaps we could get someday get some 9!: foreigns to manage M.'s cache properties? -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by gary ng-2
> Whether the language implement TCO does have an impact on the
> tendency to use recursion or not(for the fear of stack > overflow). I didn't realize this was the implication. Then, yes, (lack of) TCO has influenced how I use J. I rarely reach for $: as a first solution because it bottoms out so quickly. -Dan ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by Tracy Harms-3
On Wed, May 13, 2009 at 7:56 PM, Tracy Harms <[hidden email]> wrote:
> Thank you for confirming what I had initially understood to be the > case, that (to date) J has not exploited tail recursion. My confidence > is bolstered that J therefore stands as disproof of the idea, common > in some circles, that in order to be a "serious" "functional" language > a programming language must implement tail recursion optimization. > J has loop construct and is not pure so not having TCO is not much an issue as there are alternatives. For a functional language that is pure like Haskell, no TCO may make certain algorithm very difficult to implement if not impossible. That said, I seldom use recursion in Haskell but most likely some form of foldl or foldr. This is also the case I found in Python or F#. So if by 'serious' you mean coding in 'pure' style(i.e. no fallback to loop), I am curious to know how can one implement algorithms that needs recursion in J. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
On Thu, May 14, 2009 at 2:10 PM, gary ng <[hidden email]> wrote:
> J has loop construct and is not pure so not having TCO is not much an issue > as there are alternatives. For a functional language that is pure like > Haskell, no TCO may make certain algorithm very difficult to implement if > not impossible. ... > So if by 'serious' you mean coding in 'pure' style(i.e. no fallback to > loop), I am curious to know how can one implement algorithms that needs > recursion in J. For example: 1 2 3 + 4 5 6 7 -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
On Thu, May 14, 2009 at 11:20 AM, Raul Miller <[hidden email]> wrote:
> > So if by 'serious' you mean coding in 'pure' style(i.e. no fallback to > > loop), I am curious to know how can one implement algorithms that needs > > recursion in J. > > For example: > 1 2 3 + 4 > 5 6 7 > This is an example that no recursion is needed. The text book example would be fibonacci number. Even in language like F# which has TCO, it needs to be twisted a bit to make it 'TCOtable'. Haskell solution is elegant and simple due to its laziness not that it has TCO. How would that be implemented in J without recursion and while loop ? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
Fibonacci is a bad example because it has a closed-form solution. In J:
*fibonacci*=: 3 : 0"0 b=. - a=: % sqrt5=. %: 5 (a * (-:1+sqrt5) ^ y) + b * (-:1-sqrt5) ^ y ) (from my essay "Fibonacci Fun": http://www.jsoftware.com/jwiki/DevonMcCormick/FibonacciFun) Ackermann's function is a better example but this is coded in a recursive manner on the J wiki: ack=: c1`c1`c2`c3 @. (#.@(,&*)) c1=: >:@] NB. if 0=x, 1+y c2=: <:@[ ack 1: NB. if 0=y, (x-1) ack 1 c3=: <:@[ ack [ ack <:@] NB. else, (x-1) ack x ack y-1 (from http://www.jsoftware.com/jwiki/Essays/Ackermann's Function). I also would be interested in seeing this done without recursion as it looks to be so fundamentally recursive that it may be impossible to do it otherwise. On Thu, May 14, 2009 at 2:38 PM, gary ng <[hidden email]> wrote: > On Thu, May 14, 2009 at 11:20 AM, Raul Miller <[hidden email]> > wrote: > > > > So if by 'serious' you mean coding in 'pure' style(i.e. no fallback to > > > loop), I am curious to know how can one implement algorithms that needs > > > recursion in J. > > > > For example: > > 1 2 3 + 4 > > 5 6 7 > > > This is an example that no recursion is needed. The text book example would > be fibonacci number. Even in language like F# which has TCO, it needs to be > twisted a bit to make it 'TCOtable'. Haskell solution is elegant and simple > due to its laziness not that it has TCO. > > How would that be implemented in J without recursion and while loop ? > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
On Thu, May 14, 2009 at 12:07 PM, Devon McCormick <[hidden email]>wrote:
> Fibonacci is a bad example because it has a closed-form solution. In J: > > *fibonacci*=: 3 : 0"0 > b=. - a=: % sqrt5=. %: 5 > (a * (-:1+sqrt5) ^ y) + b * (-:1-sqrt5) ^ y > ) > When I used this as an example, I was meant to say how to solve it in a 'loop' manner not the closed form solution as most language would take that route as a demonstration of how that kind of problem would be tackled. > Ackermann's function is a better example but this is coded in a recursive > manner on the J wiki: > > ack=: c1`c1`c2`c3 @. (#.@(,&*)) > c1=: >:@] NB. if 0=x, 1+y > c2=: <:@[ ack 1: NB. if 0=y, (x-1) ack 1 > c3=: <:@[ ack [ ack <:@] NB. else, (x-1) ack x ack y-1 > > (from http://www.jsoftware.com/jwiki/Essays/Ackermann's Function). So woul this boom when it exceed the recursion limit of J ? > > > I also would be interested in seeing this done without recursion as it > looks > to be so fundamentally recursive that it may be impossible to do it > otherwise. > Is this the reason why I read on wikipedia(may be some where else) that this is not solvable in J ? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by gary ng-2
The question really is, can you code it recursively
without paying severe performance penalty? (Why else would you avoid recursion if a recursive solution is shorter, simpler, more robust, etc.) Answer: yes. fib=: 3 : 0 M. if. 2>y do. y else. (fib y-1) + (fib y-2) end. ) fib1=: 3 : 0 if. 2>y do. y else. (fib1 y-1) + (fib1 y-2) end. ) 6!:2 'fib 25' 0.000897321 6!:2 'fib1 25' 1.52873 See http://www.jsoftware.com/jwiki/Essays/Fibonacci_Sequence Another example is found in the M. dictionary page and the for. page. http://www.jsoftware.com/help/dictionary/dmcapdot.htm http://www.jsoftware.com/help/dictionary/cfor.htm comb=: 4 : 0 M. if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end. ) comb1=: 4 : 0 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb1&.<: y),1+x comb1 y-1 end. ) comb2=: 4 : 0 k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z ) 6!:2 '10 comb 20' NB. double recursion with M. 0.170501 6!:2 '10 comb1 20' NB. double recursion without M. 4.38387 6!:2 '10 comb2 20' NB. iterative 0.118327 comb and comb1 are easier to understand and have been known since the 1960s (in Gilman & Rose); comb2 has been worked on for about 30 years. Yet the simple recursive defn, with an assist from M., is within a factor of 2 of the highly worked over version. ----- Original Message ----- From: gary ng <[hidden email]> Date: Thursday, May 14, 2009 11:38 Subject: Re: [Jprogramming] tail recursion/TCO? To: Programming forum <[hidden email]> > On Thu, May 14, 2009 at 11:20 AM, Raul Miller > <[hidden email]> wrote: > > > > So if by 'serious' you mean coding in 'pure' style(i.e. no > fallback to > > > loop), I am curious to know how can one implement algorithms > that needs > > > recursion in J. > > > > For example: > > 1 2 3 + 4 > > 5 6 7 > > > This is an example that no recursion is needed. The text book > example would > be fibonacci number. Even in language like F# which has TCO, it > needs to be > twisted a bit to make it 'TCOtable'. Haskell solution is elegant > and simple > due to its laziness not that it has TCO. > > How would that be implemented in J without recursion and while > loop ? For information about J forums see http://www.jsoftware.com/forums.htm |
On Thu, May 14, 2009 at 12:48 PM, Roger Hui <[hidden email]> wrote:
> The question really is, can you code it recursively > without paying severe performance penalty? > (Why else would you avoid recursion if a recursive > solution is shorter, simpler, more robust, etc.) > > Answer: yes. > > fib=: 3 : 0 M. > if. 2>y do. y else. (fib y-1) + (fib y-2) end. > ) > > fib1=: 3 : 0 > if. 2>y do. y else. (fib1 y-1) + (fib1 y-2) end. > ) > > 6!:2 'fib 25' > 0.000897321 > 6!:2 'fib1 25' > 1.52873 > > See http://www.jsoftware.com/jwiki/Essays/Fibonacci_Sequence > 10000' or whatever number that exceed the recursion limit. Python has this limit though Guido has expressed that he is of no interest in implementing TCO. So naturally, I tend not to code in this style but use the 'generator' idiom and Memoization still benefits. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by Roger Hui
On Thu, May 14, 2009 at 12:48 PM, Roger Hui <[hidden email]> wrote:
> The question really is, can you code it recursively > without paying severe performance penalty? > (Why else would you avoid recursion if a recursive > solution is shorter, simpler, more robust, etc.) > > Answer: yes. > > fib=: 3 : 0 M. > if. 2>y do. y else. (fib y-1) + (fib y-2) end. > ) > > fib1=: 3 : 0 > if. 2>y do. y else. (fib1 y-1) + (fib1 y-2) end. > ) > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by gary ng-2
> Is this the reason why I read on wikipedia(may be some where
> else) that this is not solvable in J ? No, the problem with Ackermann's function is not so much the call stack but that the function value grows extremely quickly, and you'd have problems representing the result in any general programming language. x ack y is limited to x<:5 for all practical purposes, and for such x and y: 0&ack = >:&.(3&+) NB. >: 1&ack = 2&+&.(3&+) NB. 2&+ 2&ack = 2&*&.(3&+) NB. 3&+@(2&*) 3&ack = 2&^&.(3&+) 4&ack = ^/@(#&2)&.(3&+) 5&ack = 3 : '^/@(#&2)^:(1+y)&.(3&+) 1' http://www.jsoftware.com/jwiki/Essays/Ackermann's_Function ----- Original Message ----- From: gary ng <[hidden email]> Date: Thursday, May 14, 2009 12:44 Subject: Re: [Jprogramming] tail recursion/TCO? To: Programming forum <[hidden email]> > On Thu, May 14, 2009 at 12:07 PM, Devon McCormick > <[hidden email]>wrote: > > Fibonacci is a bad example because it has a closed-form > solution. In J: > > > > *fibonacci*=: 3 : 0"0 > > b=. - a=: % sqrt5=. %: 5 > > (a * (-:1+sqrt5) ^ y) + b * (-:1-sqrt5) ^ y > > ) > > > > When I used this as an example, I was meant to say how to solve > it in a > 'loop' manner not the closed form solution as most language > would take that > route as a demonstration of how that kind of problem would be tackled. > > > > Ackermann's function is a better example but this is coded in > a recursive > > manner on the J wiki: > > > > ack=: c1`c1`c2`c3 @. (#.@(,&*)) > > c1=: > >:@] NB. if 0=x, 1+y > > c2=: <:@[ ack > 1: NB. if 0=y, (x-1) ack 1 > > c3=: <:@[ ack [ ack > <:@] NB. > else, (x-1) ack x ack y-1 > > > > (from http://www.jsoftware.com/jwiki/Essays/Ackermann's Function). > > > So woul this boom when it exceed the recursion limit of J ? > > > > > > > > I also would be interested in seeing this done without > recursion as it > > looks > > to be so fundamentally recursive that it may be impossible to > do it > > otherwise. > > > > Is this the reason why I read on wikipedia(may be some where > else) that this > is not solvable in J ? For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by gary ng-2
On Thu, May 14, 2009 at 2:38 PM, gary ng <[hidden email]> wrote:
> On Thu, May 14, 2009 at 11:20 AM, Raul Miller <[hidden email]> wrote: >> > So if by 'serious' you mean coding in 'pure' style(i.e. no fallback to >> > loop), I am curious to know how can one implement algorithms that needs >> > recursion in J. >> >> For example: >> 1 2 3 + 4 >> 5 6 7 >> > This is an example that no recursion is needed. This gets into concepts of "need" and concepts of "recursion". If the language implements primitive recursion in most primitives (J does), can we really say that no recursion is needed? http://en.wikipedia.org/wiki/Primitive_recursive_function Alternatively, if the algorithm itself only requires primitive recursion is full recursion really needed? -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
In reply to this post by gary ng-2
On Thu, May 14, 2009 at 1:09 PM, gary ng <[hidden email]> wrote:
> Memoization helps though the question would be what happens if I say 'fib > 10000' or whatever number that exceed the recursion limit. Python has this > limit though Guido has expressed that he is of no interest in implementing > TCO. So naturally, I tend not to code in this style but use the 'generator' > idiom and Memoization still benefits. > To answer my own question, 'fib 10000' caused stack overflow. Though it hits the numeric system limit at around 'fib 1200' which gives '_'. So like the Ackermann case, stack overflow is a lesser concern. In general, I would agree with Roger that M. is more important as that usually is the first real world constraint(exponential computation time) we encounter for non-trivial problem. For reference, below is the the Haskell solution : let fib = 0:1: zipWith (+) fib (tail fib) I can get fib 150000 before I run out of memory as Haskell now supports big integer just like Python. A nice thing about the above Haskell solution is that M. comes free. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
On Fri, May 15, 2009 at 12:10 PM, gary ng <[hidden email]> wrote:
> I can get fib 150000 before I run out of memory as Haskell now supports big > integer just like Python. A nice thing about the above Haskell solution is > that M. comes free. Borrowing from http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence f7=: 3 : 0 mp=. +/ .* {.{: mp/ mp~^:(I.|.#:y) 2 2$0 1 1 1x ) f7 200000 1508568355798893899263687894817313444... -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
On Fri, May 15, 2009 at 1:33 PM, Raul Miller <[hidden email]> wrote:
> f7 200000 > 1508568355798893899263687894817313444... Or, for that matter (but takes a few minutes on my current machine): f7 1500000 12908921681187395161278531776694736120150441703840096220999... -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm |
Free forum by Nabble | Edit this page |