Re: Using local variable for memoizing in recursion

Karim,

So, for system functions pointers are marked with ampersand (&) and for user functions pointers are marked with tilde (~) in 2.12 ?

That's great! But a little bit strange if that difference really exist. Will be waiting for 2.12 stable.

As for "cumbersome" way, here is what I has written:

p(n,k) =
{
local(M = Map()); /* Do not use my() here, use local() !! */
my(memo_p = (N,K)-> my(res);
if(N==0 && K==0,return(1));
if(k<1,return(0));
if(mapisdefined(M,[N,K],&res),return(res));
if(K>=N,res=numbpart(N);mapput(M,[N,K],res);return(res));
res=self()(N,K-1)+self()(N-K,K);
mapput(M,[N,K],res);
return(res));
memo_p(n,k);
}

It works! Thank you very much for "self" method. Frankly speaking, I have read through manual as thorough as I could, and I tried self() different ways, but each time M variable was empty in recursion calls.

Combining what you advised with self() usage and what Bill wrote before (to use local() instead of my() ) finally solved the puzzle.

And this function leaves no garbage after it finishes!

Here is a log (fresh session):

(10:29) gp > p(n,k) =
{
local(M = Map());
my(memo_p = (N,K)-> my(res);
if(N==0 && K==0,return(1));
if(K<1,return(0));
if(mapisdefined(M,[N,K],&res),return(res));
if(K>=N,res=numbpart(N);mapput(M,[N,K],res);return(res));
res=self()(N,K-1)+self()(N-K,K);
mapput(M,[N,K],res);
return(res));
memo_p(n,k);
}
(10:29) gp > variables()
%2 = [x, y]
(10:29) gp > p(1000,300)
%3 = 24060233693068843871790330541103
(10:29) gp > variables()
%4 = [x, y]
(10:30) gp >

Regards,

Dmitry.

вт, 16 июл. 2019 г. в 00:02, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>:

* Дмитрий Рыбас [2019-07-15 09:24]:
> As it appered that I did not subscribe (sent request to the wrong address),
> I couldn't answer...
>
> Well, going back to memoizing, Bill wrote:
>
> You can use local():
>
> p(n,k)=
> {
> local(M=Map());
> memo_p(n,k);
> }
>
> Using local() is partial solution: one has to use the same (shared) name of
> variable in both calling and called functions. Is it possible to declare
> local variable in function a() and somehow pass it's name (or other
> reference) to function b() ?

Starting from version 2.12 you can use a call by reference with container
arguments:

memo_p(~M, n, k) = \\ notice the 'tilde', M is modified in place
...

p(n,k)=
{
my(M = Map());
memo_p(~M, n,k); \\ notice the 'tilde' in the caller
}

> Or better, somehow put recursive function b() inside function a() that
> creates map, calls recursive function and the destroys everything except
> returned result?

This is much more cumbersome, but can be made to work:

a(n,k) =
{
my(M = Map());
my(b = (N,K)-> my(z); if(mapisdefined(M,[N,K],&z),return(z));
self()(N-1,K-1)); \\ self() is used for a recursive call
b(n,k);
}

Note that the closure b() has access to variable M which is lexically scoped
to a()'s body. For clarity, I defined b() with two parameters N,K, but it
also had access to n,k from the argument list of a(). So I could equally
have used

my(b = ()->...);
b();

self() is necessary to define an anonymous recursive function [ we can't use
b() for the recursive call because the closure is not yet assigned to b ]

Cheers,

K.B.
--
Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP]
`