Re: Functional programming (was Re: Default value in function parameters?)

[Rici Lake <lua@...>]

On 21-Sep-06, at 8:50 PM, Luis Carvalho wrote:

> > Fib = Memoise(function(n)
> >   return Fib(n-1) + Fib(n-2)
> > end)
> > Fib[1] = 1
> > Fib[2] = 1
> >
> > = Fib[200]
> >
> > The definition of Memoise I use has been left abandoned on the Lua 
> > Wiki
> > at http://lua-users.org/wiki/FuncTables since January 17, 2003 :) so I
> > won't bother repeating it here.
> >
> > By the way, the above example won't work with values larger than
> > 200 unless you recompile Lua with a larger C recursion limit
> > (LUAI_MAXCCALLS in luaconf.h)
>
> You could also avoid the C recursion limit by having a memoization 
> scheme that
> does not use functables:

Sure. My original point was simply that Lua is capable of expressing 
patterns, albeit with a limitation (increasing LUAI_MAXCCALLS is 
perfectly fine on most systems, in fact.)

Actually, the fibonacci recursion can be written so as to use neither 
the Lua nor the C stack:

local function fibaux(k, a, b)
  if k == 1 then return a
  else return fibaux(k-1, a+b, a)
  end
end
function fib(k) return fibaux(k, 1, 0) end

Memoizing is mostly of use when the range of the function is not large 
and values either occupy space or are difficult to compute (or both). A 
simple example is this function which could be used to replace 
string.rep for constant strings:

indent = Memoise(function(n) return indent[(n - n%2) / 2]..indent[(n + 
n%2) / 2] end)
indent[0] = ""
indent[1] = "  "

(Did I mention how useful an integer division operator would be :) )

Of course, that's just showing off because in a typical application, 
the range of arguments to indent would be rather small, and a more 
naive recursion would be just as good. As written, it's capable of 
handling fairly large arguments without coming close to exceeding the c 
stack limit, although it might exceed the heap in such cases.

Even though string.rep is very fast, the memoised version is 
significantly faster in what might be a common profile:

function time(n, fn)
  local was = os.clock(); for i = 1, n do fn() end; print (os.clock() - 
was)
end
> time(1e5, function() local a = ("  "):rep(math.random(1, 32)) end)
0.1171875
> time(1e5, function() local a = indent[math.random(1, 32)] end)
0.0546875

As another example, consider the higher-order function 'partial' which 
takes a function f and some arguments, and returns a new function f' 
with initial arguments "filled in". This is tricky, and I don't claim 
this to be the best solution:

function partial(f, ...)
  local a = {n = select('#', ...), ...}
  return function(...)
    local b = {n = select('#', ...), ...}
    local c = {}
    for i = 1, a.n do c[i] = a[i] end
    for i = 1, b.n do c[a.n + i] = b[i] end
    return f(unpack(c, 1, a.n+b.n))
  end
end

> p = partial(print, 1, nil, 4)
> p(2, nil, nil, 5)
1       nil     4       2       nil     nil     5
>

Ok, so that works, at least, but it's hardly a speed demon.

On the other hand, it's trivial to write partial for any known number 
of arguments:

function partial3(f, a1, a2, a3)
  return function(...)
    return f(a1, a2, a3, ...)
  end
end

Unsurprisingly, this is much faster, like a factor of 25:

> function I(...) return ... end
> p = partial(I, 1, nil, 4)
> return p(2, nil, nil, 5)
1       nil     4       2       nil     nil     5
> p3 = partial3(I, 1, nil, 4)
> return p3(2, nil, nil, 5)
1       nil     4       2       nil     nil     5
> time(1e5, function() p(2, nil, nil, 5) end)
1.3515625
> time(1e5, function() p3(2, nil, nil, 5) end)
0.0546875

-- Almost exactly 25 times as fast
> time(25e5, function() p3(2, nil, nil, 5) end)
1.359375


Ok, so how do we get the speed of partial3 with the flexibility of 
partial? One solution is to generate the code for each partialk, and 
compile it. That's a clear case where memoisation is going to be a big 
win:

Arglist = Memoise(
  function(i) return Arglist[i-1]..", a"..i end
)
Arglist[0] = ""
Arglist[1] = "a1"

Partial = Memoise(
  function(i)
    return loadstring(
      [[return function(f, ]]..Arglist[i]..[[)
         return function(...) return f(]]..Arglist[i]..[[, ...) end
      end]]
    ) ()
  end
)

-- Special case for no arguments, also saves worrying about commas
Partial[0] = function(f) return f end

function memo_partial(f, ...)
  return Partial[select("#", ...)](f, ...)
end

memo_p3 = memo_partial(I, 1, nil, 4)
-- This is exactly the same function as p3
time(25e5, function() memo_p3(2, nil, nil, 5) end)
1.3515625