Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 12 down vote accepted

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.

share|improve this answer
    
Of course what Leonid did is much better... :) –  sebhofer Mar 14 '13 at 22:37
    
Leonid, can you comment on the obviously wrong things that I did? It would help developing a better intuition for how Options are handled. –  Ryogi Mar 14 '13 at 22:47
1  
@AlbertRetey See my update with a meta-programming code - it takes care of that as well (as of many other things). –  Leonid Shifrin Mar 14 '13 at 23:25
1  
@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. –  Leonid Shifrin Mar 14 '13 at 23:28
3  
@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. –  Leonid Shifrin Mar 14 '13 at 23:34
show 7 more comments

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}*)
share|improve this answer
    
The problem here is, this is not correct as written, since you have to also pass options down to the recursive calls. –  Leonid Shifrin Mar 14 '13 at 22:42
    
@oops... I checked the results against the original post, and they are the same. You are correct of course. –  sebhofer Mar 14 '13 at 22:44
    
Yes, you are right. The OP did not get it right, in the first place. –  Leonid Shifrin Mar 14 '13 at 22:54
    
Didn't mean to fool you sebhofer, i fooled myself ... –  Ryogi Mar 15 '13 at 0:19
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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