Dynamic programming and Module

Question

In the following example of the dynamic programming, why does f[n] is written at the end of the Module?

fib[n_] :=
 Module[{f},
  f[1] = f[2] = 1;
  f[i_] := f[i] = f[i - 1] + f[i - 2];
  f[n]
  ]

Further f[n] is protected? Why f[n] is not written at the end of the programing. Thanks.

Example: In[6]:= fib[5]

Out[6]= 5

In[7]:= f[5]

Out[7]= f[5]

Answer 1

---

Outline of sections below

(See summary section below for a shorter answer)

Feel free to skip around as the sections are somewhat independent

• 1) Experiment to see what Mathematica is doing.

Content: Showing that the f in Module is actually something like f$6729.

• 2) Why changing the variable inside Module is important.

Content: A common example, see references for more scenarios.

• 3) Somewhat fun example.

Content : Using Module to prevent index clashes when multiplying sums.

• 4) Can we trick Module ?

Content : Module supposedly works by incrementing $ModuleNumber. Can we use $ModuleNumber and maybe Block to trick Module into reproducing the same local variable twice ?

• 5) Why localize a function when storing values ?

Content How could the local function in the Module of the example from the question be useful ?

• References

Content 2 references. The first to an answer that distinguishes Module, With and Block to have a better idea of the design choice for Module. The second is a tech note for Module in the documentation that has a discussion on local variables and in particular Module.

Summary of the discussion below

• The f that is written inside the module is not the f that Mathematica sees. Mathematica sees something similar to the output of Unique[f] which will be something like f$6729 but possibly with different numbers. That is used to ensure that the f inside the module is different than an f that is outside the module.

• The local function and Module in the example given is useful as it has the attribute Temporary which means that, in the example given, the information that it has will be erased once the computation is over. This can be useful for problems that require using a lot of memory. That method has the drawback however of recomputing everything each time fib is called as the temporary storage of values in the definition of f is lost at the end of the computation.

---

1) Experiment to see what Mathematica is doing.

To see what Mathematica is doing let's consider a "functional" fib2 where fib2 outputs a function generating the fib sequence rather than a number:

fib2 := Module[{f}, f[1] = f[2] = 1;
f[i_] := f[i] = f[i - 1] + f[i - 2];
f]

Why would you do that ? Well, we can see what is f rather than the output of f evaluated on an integer. In the last section before the references we will see this is one of the worst choices to make in terms of memory and time efficiency.

First, we can test that the function still works:

fib2[8]

Out: (* 21 *)

If we use the fib in your question:

fib[n_] := Module[{f}, f[1] = f[2] = 1;
f[i_] := f[i] = f[i - 1] + f[i - 2];
f[n]]

we find the same result:

fib[8]

Out: (* 21 *)

Ok, now let's see what Mathematica was hiding by outputting f directly. A possible expectation is that fib2 will output f, lets check:

fib2

 (* f$6778 *)

As mentioned in the summary f inside a module is not f but f plus random looking numbers.

2) Why changing the variable inside Module is important.

Consider a very long project where on the 3rd cell there is:

b=4

then on the 42nd cell there is

r[x]:=Module[{b},b=0;Do[b=b^2+1,5];b]

If the b inside the Module was not different than the b outside then the value of the initial b at line 3 would be lost after setting b=0 inside Module.

3) Somewhat fun example.

There is a tensor manipulation package that uses Module to ensure that the indices between tensors are different when they are multiplied. For example, consider a Mathematica function that writes the expansion of the product of two sums :

$$\sum_i{a_i}\sum_i{b_i}=\sum_{i,j}{a_i b_j}$$

A first approach might be to encode:

$$\sum{a_i}$$ as

sum[a[i]]

then maybe define a sum product function like this:

sumprod[prodsum_] := prodsum /. sum[x_] :> x // sum

test:

sum[a[i]]*sum[b[i]] // sumprod

Out: (* sum[a[i] b[i]] *)

That is almost what we would like but it should be something like sum[a[i] b[j]] or sum[a[r] b[s]] the indices do not matter as they are summed over. A possible solution might be:

sumprodgood[prodsum_] := prodsum /. sum[x_] :> Module[{i}, Head[x][i]] // sum

sum[a[i]]*sum[b[i]] // sumprodgood

Out: (* sum[a[i$8662] b[i$8663]] *)

The indices might not look nice but at least the two indices are different. Alternatively one could use Unique

sumprodgoodunique[prodsum_] := 
prodsum /. sum[x_] :> Head[x][Unique@i] // sum

test:

sum[a[i]]*sum[b[i]] // sumprodgoodunique

Out: (* sum[a[i$8665] b[i$8666]] *)

Notice that the indices are not the same as with sumprodgood which means that indeed each instance of i in a Module or in Unique has a different output.

4) Can we trick Module ?

TL;DR: I did not find any way to make Module[{x},x] output the same result twice even after changing $ModuleNumber inside and outside Block

The discussion above explained that Module[{x},x] gives a different x each time. How does it do that ?

According to the documentation on Module

Module creates a symbol with name xxx$nnn to represent a local variable with name xxx. The number nnn is the current value of $ModuleNumber. The value of $ModuleNumber is incremented every time any module is used.

If we then check the documentation on $ModuleNumber we have the example:

{$ModuleNumber, Module[{x}, x], $ModuleNumber}

Out: (* {14562, x$14562, 14563} *) (you will probably see different numbers)

So it seems that basically at the end of each Module call the $ModuleNumber is increased by 1. That sounds like it is simple to trick so that Module gives the same result twice. For example,

$ModuleNumber = 1;
xa = Module[{x}, x]
$ModuleNumber = 1;
xb = Module[{x}, x];
{xa, xb}

Out: (* {x$1, x$2} *)

So it seems that Module does more. It ensures that there is no other name in Names["x$*"] with the the same name as what it was told to output. Outside of these potential cases, it does do what is requested :

$ModuleNumber = 1;
ya = Module[{y}, y]
$ModuleNumber = 3;
yb = Module[{y}, y];
{ya, yb}

Out: (* {y$1, y$3} *)

One can also use Block to reset global constants to another value within the body of the block, for example:

$ModuleNumber = 1; {{$ModuleNumber, Module[{w}, w], 
  Unique[w], $ModuleNumber}, 
 Block[{$ModuleNumber = 5}, {$ModuleNumber, Module[{w}, w], 
   Unique[w], $ModuleNumber}]}

Out: (* {{1, w$1, w$2, 3}, {5, w$5, w$6, 7}} *)

Can one use Block to obtain the same output twice from Module ?

$ModuleNumber = 1; {{$ModuleNumber, Module[{u}, u], 
  Unique[u], $ModuleNumber}, 
 Block[{$ModuleNumber = 1}, {$ModuleNumber, Module[{u}, u], 
   Unique[u], $ModuleNumber}]}

Out: (* {{1, u$1, u$2, 3}, {1, u$3, u$4, 5}} *)

Module is able to ensure that the the output from a local variable is never the same.

Ok, one last try.

Module[{x}, Print[x]; Module[{x}, Print[x]]]

The x variable in the second Module is highlighted in a different color in Mathematica. Hovering over the x variable, Mathematica shows a warning that a Nested Module could lead to an error. The first Print outputs x$38 and the second outputs x$39.

5) Why localize a function when storing values ?

TL;DR: The purpose of the Module and the local function in fib is to erase the values stored during a computation once the computation is over. The reason it erases that information is because local variables in Module have the attribute Temporary which means they are removed once they are no longer needed.

This section can be read independently from the other sections.

Let's compare the fib in the question with the more usual fib function that does not use a local function:

fib3[1] = fib3[2] = 1;
fib3[i_] := fib3[i] = fib3[i - 1] + fib3[i - 2];

We can check that fib and fib3 have the same values and the timing is about the same when evaluating fib[10^3] for example. However, fib3 stores the values of fib3[i] for all i between 1 and 10^3 whereas fib does not. The reason why fib does not is because the information about the computation was stored in the DownValues of the local variable f and not fib.

That statement can be checked by considering:

fibcheck[n_] := Module[{g, f}, f[1] = f[2] = 1;
f[i_] := f[i] = f[i - 1] + f[i - 2];
g = f[n];
Print[DownValues[f]]; g]

and then evaluating

fibcheck[5]

and checking

DownValues[fibcheck]//Length

Out; (* 1 *)

After evaluating fib3 on 10^3 one can check that

DownValues[fib3] // Length

Out (* 1001 *)

Thus it seems like fib uses less memory than fib3 but one might argue that the memory is stored in the local variable f. However, local variables in Module have attribute Temporary and the DownValues of f are lost after the evaluation was completed.

This is not the case with fib2 that outputs the local function. That can be checked by evaluating fib2[10^3], looking for the last element in the list given by Names["f*"], and evaluating the Length of the DownValues of this element. Finally to be sure that fib is not using any extra memory one can check MemoryInUse[] before and after in each case of fib,fib2 and fib3: First we ensure that Mathematica retains all the calculations (that is the default behavior by some people change this in their init.m file)

$HistoryLength = Infinity;

then we evaluate

mem = MemoryInUse[];
fib[10^3];
Print[MemoryInUse[] - mem];
mem = MemoryInUse[];
fib2[10^3];
Print[MemoryInUse[] - mem];
mem = MemoryInUse[];
fib3[10^3];
Print[MemoryInUse[] - mem];

Out: (* 2960 221048 218752 *)

It is clear that fib uses the least amount of memory and outputting the local function looses the memory efficiency. Evaluating the above sequence a second time leads to the output:

Out: (* 3088 220088 1728 *)

Only fib2 added a significant amount of memory. That is because it saved all the information from the computation but in a new local function that will note even be used. Moreover, checking AbsoluteTiming shows that the timing is very small upon re-evaluation except for fib2 that computes everything again.

Hence, the function fib2 that outputs the local function is neither memory efficient nor time efficient.

So is fib better than the usual fib3 ? That depends on whether memory is important. If the usual fib3 requires too much memory then one might want to use fib. The drawback is that since fib does not permanently store all of the information from prior calculations, fib will re-evaluate the entire computation each time whereas the usual fib3 will use prior computations. Thus it is a question of time vs memory.

References

• I personally like this answer on stack exchange in this link. It refers to the differences between Module, Block and With but the other answers might be useful too.

• A tech note in the documentation that offers an explanation on how Module (and Block) works and some examples of its use.