Pascal, you are right. I would say that it is "generally accepted" that in J, power is the way to do iteration. I would bet very few people use $: much given that (^:) and (/), (\) etc. can easily model most problems. But for some people using recursion is more (or equally) instinctive. So, this was merely an exercise on implementing a stack-less $: . That being said, I think once tested and made robust, the speed boost and avoidance of the function call stack will lead to some benefits of ($:) over (^:). One is that it is, in my opinion, cleaner to implement algorithms that need to stop early. Another is that wider adoption will hopefully lead to recursion being added to the toolbox of "tools of thought" of J programmers.
I am actually more encouraged now about the prospects of O. given your examples, as the tail recursive version runs in roughly the same amount of time and less space than the power version. Of course this is just one simple example. Here are the timings on my computer: ts '50000 fibtac O. 0 1x' 1.212615105792 84352 ts 'fib 50000 0 1x' 1.252843949962 233216 On Wed, Aug 27, 2014 at 3:39 PM, 'Pascal Jasmin' via Programming < [email protected]> wrote: > also if you really wanted to call it dyadically, > > fib =: (<:X, {:Y , +/Y)Guard (0 < {.) Cleanup {: (@:,) > or > fib =: (<:X, {:Y , +/Y) Guard(0 < {.) Cleanup{: @:, > 10 fib 0 1x > 89 > > > ----- Original Message ----- > From: 'Pascal Jasmin' via Programming <[email protected]> > To: "[email protected]" <[email protected]> > Cc: > Sent: Wednesday, August 27, 2014 3:28:35 PM > Subject: Re: [Jprogramming] Trampolining (was Adler-32) > > The technique of placing all parameters on left hand side and using ^: is > stackless > X=.@{. > Y > =.@}. > > fib =: (<:X, {:Y , +/Y)Guard (0 < {.) Cleanup {: NB. using previous > definitions, that aren't really necessary, as it gets compiled to: > > fib > [: {: (<:@{. , {:@}. , +/@}.)^:(0 < {.)^:_ > > but for clarity: > Guard > 2 : 'u ^:v^:_' > Cleanup > 2 : '[: v u' > > > fib 10000 0 1x > 544383731135652813387342609937503801353891845546959670262477158412... > > timespacex 'fib 10000 0 1x' > 0.0630729 128896 > timespacex '1e4 fibtco 0 1x' > 0.273644 42752 > > > Can't explain why it uses more mem though, though my machine is apparently > much slower than yours. > > > ----- Original Message ----- > From: Thomas Costigliola <[email protected]> > To: J Programming Forum <[email protected]> > Cc: > Sent: Wednesday, August 27, 2014 2:18:35 PM > Subject: [Jprogramming] Trampolining (was Adler-32) > > I am starting a new thread specific to the tail call optimizations > discussed in the Adler-32 thread ( > > http://www.jsoftware.com/pipermail/programming/2014-August/thread.html#38966 > ). > > I have an initial implementation of a primitive trampoline adverb (O.) that > works in conjunction with ($:). A link to a patch can be found at the end > of the post. > > v O. causes any $: appearing in v to save its arguments and return control > immediately back to O. which calls v on the saved arguments in a while > loop. In other words, O. trampolines $: within v, preventing the function > call stack from growing. > > I call it an initial implementation because it does not gracefully handle > the case where v is not tail recursive, i.e., it will crash. I believe the > proper behavior would be to detect this and either signal a domain error or > fall back to the non-trampolined version. > > Here is an example use, comparing it with Raul's tco explicit adverb: > > NB. ============================== > NB. Fibonacci function with Raul's tco adverb > > tco=:(0 :0)(2 :0) > : > context=. cocreate'' NB. context > active__context=: 0 > accumulated__context=: '' > v 2 :m context > ) > : > accumulated__n=: x,&<y > if. 0=active__n do. > active__n=: 1 > while. #accumulated__n do. > pair=. accumulated__n > accumulated__n=:'' > value__n=: u&>/pair > end. > active__n=. 0 > value__n > end. > ) > > fib=: 4 : 0 > if. x do. (<:x) fib ({: , +/) y > else. {:y end. > ) > > fibtco=: (4 : 0) tco > if. x do. (<:x) fibtco ({: , +/) y > else. {:y end. > ) > > NB. e.g., the 10th Fibonacci number > 10 fib 0 1 > 89 > > 1e4 fib 0 1 > |stack error: fib > | (<:x) fib({:,+/)y > > 1e4 fibtco 0 1 > _ > > 1e4 fibtco 0 1x > 54438373113565281338734260993750... > > NB. ======================= > NB. Primitive tacit version > > x=. @[ > y=. @] > fibtac=: ({:y) ` (<:x $: {:y , +/y) @. (*x) > > 10 fibtac 0 1 > 89 > > 1e4 fibtac 0 1 > |stack error: fibtac > | 10000 fibtac 0 1 > |[-0] > > 1e4 fibtac O. 0 1x NB. Use a trampoline > 54438373113565281338734260993750... > > NB. ===================== > NB. Time space comparison > ts=. 6!:2 , 7!:2@] > > ts '1e4 fibtco 0 1x' > 0.1716307124258 21440 > ts '1e4 fibtac O. 0 1x' > 0.0628310244257 22912 > > > Keep in mind that this has not been extensively tested and will crash if > your function is not tail recursive. Use only if you like to take risks or > want to check if your function is tail recursive! A possible optimization > would be to update the arguments in place if you could infer something > about a bound on their size. Also, currently, a new verb array, used as a > marker, is generated each iteration, this could be easily optimized away. > Hopefully this will be useful or interesting to enough people that is > further developed. The patch can be found here: > http://www.2bestsystems.com/foundation/j/#Trampoline > ---------------------------------------------------------------------- > 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
