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
