Re: Using local variable for memoizing in recursion

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Дмитрий Рыбас [2019-07-16 09:44]:
> So, for system functions pointers are marked with ampersand (&) and for
> user functions pointers are marked with tilde (~) in 2.12 ?

Not quite: we don't have true user function pointers (hence the tilde
instead of the customary ampersand). It's really a mutable *container*
(we're allowing to modify in place an object of list/vector/matrix-type),
this is not a side effect changing a variable value. Compare:

? f(~x) = x = 1;
? x = 0; f(~x); x    \\ x didn't change
%2 = 0

? g(~x) = x[1] = 1;
? x = [0]; g(~x); x  \\ but the *content* of a container type x would change
%4 = [1]

This can also be used to make sure that a given bulky argument is
*never* copied by user functions. GP's copy optimizer is usually clever
enough but it sometimes errs on the paranoid side to survive problematic
constructs (usually involving global variables). E.g.,
  x = [1]; /* global; no lexical scoping */
  f(y) = /*...complicated code...*/;
  f(x)

Must must we make a deep copy of 'x' in case some user subroutine called by
f messes with it, or is a shallow copy safe enough ? [ In fact it's
rarely safe because GP is not compiled: global subroutines called by f may be
redefined at any time... ]

With 
  f(~y) = ...
  f(~x)
there's no problem: no copy.

> 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));
            ^--- you mean K here

>        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);
>   }

You can simplify this a little:

p(n,k) =
  {
    local(M = Map()); /* yes, local is needed: sorry... */
    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));
       res = if(K>=N, numbpart(N), self()(N,K-1)+self()(N-K,K));
       mapput(M,[N,K],res); return(res));
    memo_p(n,k);
  }

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]
`