Memoizer 3 – Lua

Continuing on the dynamic/scripting languages front, I’m squeezing some time on Lua in parallel with experimenting with Python.  From background reading and other research, it looks like Lua is strong but might not have as many libraries as Python does.  It seems to have a lot of popularity in the gaming world, and is also a smaller language, which may be good for my desires to tinker with languages and runtimes.

If you’d like to learn more, you can start with a visit Lua.org

Memoizer

Bear with me as this experiment was conducted entirely from the interactive shell, and formatted with codepad.org:

function memoize(f)
  -- create a new associative table to record results
  store = {}
  function anon(x)
    if store[x] then
      return store[x]
    else
      y = f(x)
      store[x] = y
      return y
    end
  end
  return anon
end

If you read the last entry on the topic, this should looks very familiar.  Lua also has associative containers, also supports nested functions, also supports function closures.  The syntax is a bit different, and Lua uses nil (which evaluates to false) to represent empty slots in an associative container — so ‘if A[B]’ roughly means ‘if the key B appears in table A’.

Otherwise, it behaves identically to the Python version I wrote previously (with the caveat that floating point or fixed sized integes are used by Lua instead of Python’s unbounded precision integers)

function fib(x)
  if x < 2 then
    return 1
  else
    return fib(x-1) + fib(x-2)
  end
end

fib = memoize(fib)

This code, like the Python example, also takes advantage of functions being first class objects — variables they are assigned to can be later re-assigned.  Also like the Python example, the call to ‘fib(x-1)’ is late bound, or dynamically bound.  It’s not until the function is invoked that the ‘fib’ function call is looked up — which allows us to easily inject memoization after the fact.

Functions as expressions

We can do one better though.  In Lua, like some functional languages such as Scheme and JavaScript, you can define anonymous functions inline, as part of an expression.  As a result, we can define and memoize a function in one go without a special-purpose syntax:

-- this:
function fib(x) ... end
fib = memoize(fib)

-- is the same as this:
fib = memoize(function(x) ... end)

The full demonstration with instrumentation is up on code pad — I encourage you take a look and try it yourself, or download the (very fast and small) Lua runtime from Lua.org. 

Lua ends up using tables for everything — which is not entirely unlike Python where attributes are mostly a special dictionary named __dict__, but the syntax and structure is simpler.  This can be good thing (smaller, more generic language) and bad thing (when everything is the same, it’s hard to see the classes, namespaces, and models through the tables).

I apologize if this code looks very rough — it is.  I started Lua today (no, really!), and mostly translated the Python version.  I’ll try a bit harder on the next Lua post.