Replacing functions with Table Lookups

Question

I've been watching this MSDN video with Brian Beckman and I'd like to better understand something he says:

Every imperitive programmer goes through this phase of learning that functions can be replaced with table lookups

Now, I'm a C# programmer who never went to university, so perhaps somewhere along the line I missed out on something everyone else learned to understand.

What does Brian mean by:

functions can be replaced with table lookups

Are there practical examples of this being done and does it apply to all functions? He gives the example of the sin function, which I can make sense of, but how do I make sense of this in more general terms?

Answer 1

Brian just showed that the functions are data too. Functions in general are just a mapping of one set to another: y = f(x) is mapping of set {x} to set {y}: f:X->Y. The tables are mappings as well: [x1, x2, ..., xn] -> [y1, y2, ..., yn].

If function operates on finite set (this is the case in programming) then it's can be replaced with a table which represents that mapping. As Brian mentioned, every imperative programmer goes through this phase of understanding that the functions can be replaced with the table lookups just for performance reason.

But it doesn't mean that all functions easily can or should be replaced with the tables. It only means that you theoretically can do that for every function. So the conclusion would be that the functions are data because tables are (in the context of programming of course).

Answer 2

There is a lovely trick in Mathematica that creates a table as a side-effect of evaluating function-calls-as-rewrite-rules. Consider the classic slow-fibonacci

fib[1] = 1
fib[2] = 1
fib[n_] := fib[n-1] + fib[n-2]

The first two lines create table entries for the inputs 1 and 2. This is exactly the same as saying

fibTable = {};
fibTable[1] = 1;
fibTable[2] = 1;

in JavaScript. The third line of Mathematica says "please install a rewrite rule that will replace any occurrence of fib[n_], after substituting the pattern variable n_ with the actual argument of the occurrence, with fib[n-1] + fib[n-2]." The rewriter will iterate this procedure, and eventually produce the value of fib[n] after an exponential number of rewrites. This is just like the recursive function-call form that we get in JavaScript with

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  return result;
}

Notice it checks the table first for the two values we have explicitly stored before making the recursive calls. The Mathematica evaluator does this check automatically, because the order of presentation of the rules is important -- Mathematica checks the more specific rules first and the more general rules later. That's why Mathematica has two assignment forms, = and :=: the former is for specific rules whose right-hand sides can be evaluated at the time the rule is defined; the latter is for general rules whose right-hand sides must be evaluated when the rule is applied.

Now, in Mathematica, if we say

fib[4]

it gets rewritten to

fib[3] + fib[2]

then to

fib[2] + fib[1] + 1

then to

1 + 1 + 1

and finally to 3, which does not change on the next rewrite. You can imagine that if we say fib[35], we will generate enormous expressions, fill up memory, and melt the CPU. But the trick is to replace the final rewrite rule with the following:

fib[n_] := fib[n] = fib[n-1] + fib[n-2]

This says "please replace every occurrence of fib[n_] with an expression that will install a new specific rule for the value of fib[n] and also produce the value." This one runs much faster because it expands the rule-base -- the table of values! -- at run time.

We can do likewise in JavaScript

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  fibTable[n] = result;
  return result;
}

This runs MUCH faster than the prior definition of fib.

This is called "automemoization" [sic -- not "memorization" but "memoization" as in creating a memo for yourself].

Of course, in the real world, you must manage the sizes of the tables that get created. To inspect the tables in Mathematica, do

DownValues[fib]

To inspect them in JavaScript, do just

fibTable

in a REPL such as that supported by Node.JS.