# Is it possible to Protect a dynamic programming process?

I wrote a function using dynamic programming to speed up the evaluation. For safety, I also want to protect this function. Take factorial for example:

fac[0] = 1;
fac[n_] := fac[n] = n*fac[n - 1];
Protect@fac;


fac[3] will return a Set::write error and give the right answer 6. Although Quiet@fac[3] or Off[Set::write] seems to work, the sacrifice is the speed, which can be verified by?fac:

Globalfac

Attributes[fac]={Protected}

fac[0]=1

fac[n_]:=fac[n]=n fac[n-1]

i.e. after the evaluation of fac[3], Mathematica does not store the values: fac[1],fac[2],fac[3].(Of course it doesn't, since the fac is protected.)

So what can be done to make Protect and dynamic programming process live with each other?

You could just unprotect and protect on the first call of the recursion.

To avoid checking in every inner call if it's the first or not, you could implement it in a an extra private symbol, and use the public interface as a non-recursive wrapper.

Unprotect[fac]; ClearAll[fac];
Module[{facPvt},

facPvt[1] = 1;
facPvt[n_Integer] := facPvt[n] = n facPvt[n - 1];

fac[n_Integer?Positive] := (
Unprotect[facPvt]; (Protect[facPvt]; #) &@facPvt[n]);

Protect[fac, facPvt];
]


Just don't lock facPvt

• +1. I noticed that what you do with a pure function is very similar to what I did with withCodeAfter. – Leonid Shifrin Dec 18 '13 at 16:42
• Thanks; However, what's the difference between (Unprotect[facPvt]; (Protect[facPvt]; #) &@facPvt[n]) and (Unprotect[facPvt]; facPvt[n]); ? – luyuwuli Dec 19 '13 at 3:18
• @luyuwuli that the latter leaves the symbol unprotected after evaluation. If you don't mind that (I wouldn't, since it's a symbol a common user wouldn't even know), then never protect it in the first place. – Rojo Dec 19 '13 at 3:58
• @Rojo I'm not sure I understand it correctly: Because & has a very low precedence, in (Protect[facPvt]; #) &@facPvt[n]) , facPvt[n] will be evaluated first, then protect it, last return it. If so, why protect facPvt again at the end of the Module ? – luyuwuli Dec 19 '13 at 8:44
• @luyuwuli, this module isn't being used to localize facPvt in the sense that facPvt isn't destroyed after the Module exits. It is used so that facPvt is actually some other local weird name, such as facPvt$34 that hadn't been used so far. When someone does fac[3], that facPvt$34 has to still exist for the function to work. So, between calls, the user could do facPvt\$34[2]="haha" and ruin everything if it is not protected. – Rojo Dec 19 '13 at 13:25

In many cases, memoization helps for a given particular computation, and one can (or even has to) then remove the memoized values. For such cases, protection can nicely coexist with the technique which I call "self-blocking". I will illustrate this using the infamous Fibonacci numbers example:

Unprotect[fib];
ClearAll[fib];
fib[n_] :=
Block[{fib},
fib[0] = fib[1] = 1;
fib[m_?Positive] := fib[m] = fib[m - 1] + fib[m - 2];
fib[n]
];
Protect @ fib;


Now, we can use, for example:

fib[100]

(* 573147844013817084101 *)


while e.g. the following assignment is not allowed:

fib[2] = 1


During evaluation of In[2852]:= Set::write: Tag fib in fib[2] is Protected.

(* 1 *)


The reason this works is that Block removes all global properties of the blocked symbol, including the Protected attribute. Note that this technique also guarantees that the memoized values are removed after the function finishes, since they only exist inside a dynamic environment created using Block.

In more complex cases, some variations of this approach might work as well.

EDIT

To address your question on how to keep the generated definitions, here is another method. First, define this handy macro, which allows us to avoid extra scoping constructs (intermediate variables):

ClearAll[withCodeAfter];
SetAttributes[withCodeAfter, HoldRest];
withCodeAfter[before_, after_] := (after; before);


Now, here is the method (using the same example as before): before all your usual definitions, insert an extra definition:

Unprotect[fib];
ClearAll[fib];

call_fib /; MemberQ[Attributes[fib], Protected] :=
withCodeAfter[Unprotect[fib]; call, Protect[fib]]

fib[0] = fib[1] = 1;
fib[n_] := fib[n] = fib[n - 1] + fib[n - 2];
Protect[fib];


This extra definition allows the function, but only the function, to modify itself during its own execution. So, now:

fib[50]

(* 20365011074 *)


And you can check that the function remains Protected, and the generated definitions are now in the global rule base.

This method is general, so all you have to do is to insert your own symbol in place of fib, to construct a relevant extra definition for your problem / function. It is important that it is the very first one you give, so it should go before your "usual" definitions.

• If I am understanding your " also guarantees that the memoized values are removed after the function finished" (which is in line with the Block[] docs), a subsequent fib[100]` will start blank. Is there a way to persist the memoized downvalues and have the symbol protected? – Dr. belisarius Dec 18 '13 at 13:10
• Thanks a lot. While I have another problem: If the values are removed after the function finishes and someone may use the values (or part of it) again and again. The evaluation will have to start over. The memory for time strategy will somewhat fail. So is it possible to implement this: definitions can be changed when the package evaluate (or in the package), but any change of it in the notebook (or by hand) is forbidden? – luyuwuli Dec 18 '13 at 13:12
• @belisarius Yes! What you said is exactly what I want:) – luyuwuli Dec 18 '13 at 13:15
• @belisarius Yes, this is possible, although by using a different method. See my edit. – Leonid Shifrin Dec 18 '13 at 15:15
• Great! Thanks a lot. – Dr. belisarius Dec 18 '13 at 15:34