20
$\begingroup$

Consider the following modified fibonacci function:

tempHist = $History
$History = 0
ClearAll[fibon]
Options[fibon] = {k -> 1}
fibon[0] = 0;
fibon[1] = 1;
fibon[n_, OptionsPattern[]]:= fibon[n-1] + OptionValue[k] * fibon[n-2]

fibon[30] // Timing           (* {4.111894, 832040} *)
fibon[30, k -> 2] // Timing   (* {4.161676, 1149851} *)

The modification involves a coefficent that multiplies the second term of the recursive definition. Can the idiom f[x_]:=f[x]= ... be used to implement memoization in this case?

I tried with no luck the following naive approaches for c-aching fibon

ClearAll[cfibon]
Options[cfibon] = {k -> 1}
cfibon[0] = 0;
cfibon[1] = 1;
cfibon[n_, OptionsPattern[]]:= cfibon[n, OptionsPattern[]] = cfibon[n-1] + OptionValue[k] * cfibon[n-2]

cfibon[30] // Timing          (* {2.1999999997746045*^-5, 832040} *)
cfibon[30, k -> 2] // Timing  (* {2.899999999961267*^-5, 832040} *)

Something is being memoized, but this is not the wanted behavior (note that the two calls return the same value 832040, the second call is meant return 1149851). Here is another try:

ClearAll[cfibon]
Options[cfibon] = {k -> 1}
cfibon[0] = 0;
cfibon[1] = 1;
cfibon[n_, OptionsPattern[]]:= cfibon[n, k -> OptionValue[k]] = cfibon[n-1] + OptionValue[k] * cfibon[n-2]

cfibon[30] // Timing
(* {10.664260999999998, 832040} *)

cfibon[30, k -> 2] // Timing
(* {10.677505, 1149851} *)

Now, the results are as expected, by the computation is slower than the non-cached version! So...

How to memoize a function with Options?

$\endgroup$

3 Answers 3

20
$\begingroup$

The case at hand

Here is one possibility:

ClearAll[fibon]
Options[fibon] = {k -> 1}
fibon[0, OptionsPattern[]] = 0;
fibon[1, OptionsPattern[]] = 1;

fibon[n_, opts : OptionsPattern[]] /; ! OrderedQ[{opts}] :=
   fibon[n, Sequence @@ Sort[{opts}]];
fibon[n_, opts : OptionsPattern[]] :=
   fibon[n, opts] = 
       fibon[n - 1, opts] + OptionValue[k]*fibon[n - 2, opts]

So, for example:

fibon[30]

(*  832040  *)

fibon[30,k->2]

(* 357913941 *)

Note that I added a rule which sorts the options, and I explicitly assumed the two sets of options the same when they are only different by the order of options. This assumption could be improved by accounting for some options not present explicitly but being the same due to defaults.

General meta-programming solution

The above version has the following limitations:

  • Default option values not accounted for
  • Has to explicitly pass the options to inner calls to self
  • It is not general enough (which is ok for a specific problem, but not for a general approach). Although one can see that some of the code does not really depend on the specifics of the problem, the above form does not allow one to easily factor that out.

Here I will address these limitations of the previous version, and show how we can achieve a fairly complete automation of this task for a wide class of problems by using meta-programming and code generation.

Here is a code-generating function that would generate the full memoizing code from simpler version not involving options:

ClearAll[optionMemo];
SetAttributes[optionMemo, HoldAll];
optionMemo[sym_Symbol, {defs___}, defOptions : {___?OptionQ}] :=
  Module[{},
    ClearAll[sym];
    Options[sym] = defOptions;
    sym[args : Except[_?OptionQ] ..., opts : OptionsPattern[]] :=
      With[{
        newopts =
          Sort @ DeleteDuplicates[
             {opts}~Join~Options[sym], 
             First@#1 == First@#2 &]
         },
         sym[args, Sequence @@ newopts] /; newopts =!= {opts}
      ];
    sym[args : Except[_?OptionQ] ..., opts : OptionsPattern[]]/;!OrderedQ[{opts}] :=
       sym[args, Sequence @@ Sort[{opts}]];

    sym[args : Except[_?OptionQ] ..., opts : OptionsPattern[]] :=
      Block[{sym, options = Options[sym]},
         Options[sym] = options;
         defs;
         sym[args]
      ]
  ];

It takes the name of the symbol, the list of code statements which produce the relevant definitions, and the list of options for this symbol. It works by generating the boilerplate code, but also it relies on a rather interesting technique where a function Block-s itself and creates some definitions locally inside Block. What we buy by this construct here:

  • We don't have to pass options to inner recursive calls
  • We can still globally call OptionVaulue as before, with a single argument, and this will work.
  • The memoization only happens during the computation, to speed it up, but all the memoized values are cleared by Block at the end, automatically;

So, here is how we use it: first generate the boilerplate code

optionMemo[
  fibon,
  {
     fibon[0] = 0,
     fibon[1] = 1,
     fibon[m_] := fibon[m] = fibon[m - 1] + OptionValue[k]*fibon[m - 2]
  },
  {k -> 1, i -> 2}
]

and now use it as before:

fibon[30]

(*  832040  *)

fibon[30,k->2]

(* 357913941 *)

The optionMemo construct should be general enough to handle many similar problems.

$\endgroup$
12
  • $\begingroup$ Of course what Leonid did is much better... :) $\endgroup$
    – sebhofer
    Mar 14, 2013 at 22:37
  • 1
    $\begingroup$ @AlbertRetey See my update with a meta-programming code - it takes care of that as well (as of many other things). $\endgroup$ Mar 14, 2013 at 23:25
  • 1
    $\begingroup$ @Ryogi Your biggest problem was that you did not pass options down to recursive calls, but you used the option in the memoized part as cfibon[n, k -> OptionValue[k]] = ..., so your memoized definitions were actually never used. $\endgroup$ Mar 14, 2013 at 23:28
  • 3
    $\begingroup$ @AlbertRetey But this is the first problem I have seen where the self-blocking technique brings more than just convenience to not pass some arguments explicitly - here also one can globally call single-argument OptionValue across the full recursive execution stack. I think this is pretty cool. $\endgroup$ Mar 14, 2013 at 23:34
  • 1
    $\begingroup$ @AlbertRetey Thanks :-). I use self-blocking from time to time, when I want to avoid tedious passing of some arguments. Basically, a function blocks itself inside its external call, then defines itself there inside Block, and then executes. This allows me to embed those arguments which don't change,right to the body of those definitions, so they can be simpler. But, as I said, here we have an extra bonus of global access to all OptionValue-s (one - arg "magical" form of them) across the execution stack, which seems pretty neat to me. $\endgroup$ Mar 14, 2013 at 23:43
3
$\begingroup$

This should do what you want:

ClearAll[cfibon]
Options[cfibon] = {k -> 1};
cfibon[0,OptionsPattern[]] = 0;
cfibon[1,OptionsPattern[]] = 1;
cfibon[n_, options : OptionsPattern[]] := cfibon[n, options] = 
  cfibon[n - 1,options] + OptionValue[k]*cfibon[n - 2,options];

cfibon[30] // Timing
(*{0., 832040}*)
cfibon[30, k -> 2] // Timing
(*{0., 357913941}*)
$\endgroup$
0
1
$\begingroup$

This addresses your title more than your content. FWIW I have found options memoization occasionally useful in interfaces. For example if you have a control that recalculates something, with the control selection being an option value, there may be no real need to keep redoing the calculation. So memoization with this option can be implemented. There may be other options that will not change after evaluation so these can be left as is.

Here is an example:

DynamicModule[{x = 1, g},

 Column[{

   PopupMenu[
    Dynamic[x], {1 -> "choice 1", 2 -> "choice 2", 3 -> "choice 3"}],

   Dynamic[
    Information[g];
    g[2, Opt -> x]
    ]

   }],
 Initialization :> {g[x_, OptionsPattern[{Opt -> 1, Colour -> Red}]] :=
     g[x, Opt -> OptionValue[Opt]] = 
     Framed[OptionValue[Opt]*x^2, FrameStyle -> OptionValue[Colour]]}]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.