The reason for any procedure (say looping) is to pass a small number of
arguments to a lot of code. recursion can bring the advantages/feature of
local variables, and a chunk of code/lego that could be called by something
else. It is not really an advantage that it will use the stack for storage.
Consider the toy sum example
([: {: (('<:';'>:') apply&> ])^:(0<{.)^:_) 5 2
7
or
([: {: (<:@:{. , >:@:{:)^:(0<{.)^:_) 5 2
7
consider these 2 definitions
Guard =: 2 : 'u ^:v^:_'
Cleanup =: 2 : '[: v u'
can rewrite top definition to:
(<:@:{. , >:@:{:) Guard (0<{.) Cleanup {: 6 2
8
ignoring whether this is a loop or recursion, in a recursive algorithm you
generally want to recurse while/until a Guard condition, and then there may be
a Cleanup function to get the final result.
You could define Guard to use $: instead, but cleanup has to be a bit
different, because $: executes the full verb again (including cleanup). But
that definition:
GuardR =: 2 : '$:@:u`(@.v)' NB. does recurse until instead of "recurse while"
{: (<:@:{. , >:@:{:) GuardR (0={.) NB. GuardR returns an adverb that picks
up cleanup code
$:@:(<:@:{. , >:@:{:)`{:@.(0 = {.)
{:(<:@:{. , >:@:{:) GuardR (0={.) 5 2
7
even though you can use $: as the implementation, its not obvious you would
want to. You just want a convenient way of accessing a repeating function
until some condition with application of cleanup code after that condition.
Its my understanding that TCO optimizing lisps, optimize by creating C loops
when possible.
I think quicksort
quicksort=: (] ($:@(< # [) , (= # [) , $:@(> # [)) (] {~ ?@#) )^:(1 < #)
is a sensible use of $:, but I'm not sure there is full TCO (completely in
place sort), even though it doesn't crash the stack on medium data.
----- Original Message -----
From: Joe Bogner <[email protected]>
To: [email protected]
Cc:
Sent: Tuesday, August 26, 2014 6:10:28 AM
Subject: Re: [Jprogramming] Adler-32
On Mon, Aug 25, 2014 at 9:51 PM, Raul Miller <[email protected]> wrote:
> http://www.integralist.co.uk/posts/understanding-recursion-in-functional-javascript-programming/#the-solution
> looks like it is describing this:
>
> trampoline=:3 :0
> try.
> while. 1 do.
> y=. y`:6''
> end.
> catch.
> y
> end.
> )
>
The linked url includes a sum function that is applied against the
trampoline. How would that be done in J? I tried some things and could
not figure out how to bind the x/y to the gerund, which is what I
assumed I needed to do
Don't run this code as it will crash J
trampoline=:3 :0
try.
while. 1 do.
y=. y`:6''
end.
catch.
y
end.
)
NB. warning, crashes J
recur=: 4 : 0
if. y > 0
do. trampoline recur&(y+1)`''
else. x
end.
)
sum=: 4 : 0
trampoline (x recur y)
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
