  lua-l archive

• Subject: Re: Functional programming (was Re: Default value in function parameters?)
• From: Rici Lake <lua@...>
• Date: Thu, 21 Sep 2006 23:09:22 -0500

```
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
Fib = 1

= Fib

```
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 = ""
indent = "  "

(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 = ""
Arglist = "a1"

Partial = Memoise(
function(i)
[[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 = 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

```