Lua and the space/time duality (1 Viewer)

Functions f(x) use a fixed amount of space and who knows how much time, whereas tables t[x] use a fixed amount of time and who knows how much space. The traditional speed-up, trading space for time, is called memoization:

memoize = function (f)
             local t = { }
             return function (x)
                local a = t[x]
                if not a then
                   a = f(x)
                   t[x] = a
                end -- if
                return a
                end -- function
           end -- function

For example, the traditional Fibonacci function:

fib = function (n)
         if n < 2 then return n end -- if
         return f(n-1) + f(n-2)
         end -- function

is hopelessly inefficient, but memoize (fib) is much better.
But Lua, uniquely I suspect, lets us trade in the other direction, delaying the filling of a table:

local t = setmetatable ( { 0, 1}, {
   __index = function (f,x)
             local a = f[x-1] + f[x-2]
             f[x] = a
             return a
             end -- function
      })
newfib = function (x) return t[x] end -- function

The function newfib is better still. Are there other languages that make this space/time duality so explicit?

 

[gaurami]

I had to make a correction in the third example:

local t = setmetatable ( { 1, 1}, {
...

to make it produce the same results as the first two examples, but I can't figure out why it works much faster than the "memorized" Fibonacci. Could somebody explain it in the plain Beginnerish?

 

[GavinW]

Thanks for the correction. Why is newfib faster? I think it is because table-lookup is faster than function-calling. The point of memoization is to obey the adage "never calculate the same value twice". Ask yourself how many Lua function calls does it take to calculate the n-th Fibonacci number, using these methods? Table-lookup obviously involves a C-function, as does addition, but these are the only operations after the first call to newfib, which calls a Lua function only once. On the other hand memoize(fib) needs to call n Lua-functions, one for each of the numbers less than its argument. Is that any help?

 

[gaurami]

Thanks! It's getting clearer: newfib delegates almost all work to C-functions (O( n ) calls of the lookup and the addition functions), while memoize(fib) does almost the same but calling repeatedly Lua functions - correct?

 

[GavinW]

Yes. From the mathematical point of view f(x) and f[x] are the same, but computationally they are different. Lua's meta(tables/methods) are very interesting, I think. On the face of it, they seem only to be about tweaking notation, but in fact they give the programmer more flexibility with evaluation strategies. That was really the point I was trying to get across. But meta-magic is an aspect of Lua that is probably fairly frightening for newcomers to the language. It took a while to evolve to its present generality, and I do not know of any other languages with anything similar.