Currying in Lua

Question

Just whipped up this quick curry function in Lua, as a building block for partial application and memoization. Any feedback is appreciated.

It takes two arguments; n is the number of parameters in the function being curried, and func is the function to curry.

Code generation is used to create the curried functions. Because the same code is generated for any given n, the generated functions are cached to offset the runtime cost of code generation.

local curryCache = {}

local function curryGenerate(n)
    if curryCache[n] then return curryCache[n] end
    local src = 'return func(a1%s)'
    for i = 2, n do
        src = src:format((', a%i%%s'):format(i))
    end
    src = src:format('')
    for i = n, 1, -1 do
        src = ('return function(a%i) %s end'):format(i, src)
    end
    src = ('local func = ...; %s'):format(src)
    curryCache[n] = load(src)
    return curryCache[n]
end

local function curry(n, func)
    return n < 2 and func or curryGenerate(n)(func)
end

Testing it out:

local p4 = curry(4, print)
p4 'a' 'b' 'c' 'd' -- prints "a   b   c   d"

Looking at some other questions about currying on this site, I noticed some use a more loose definition of the term, where any number of arguments can be passed to the curried function. I'm shooting for a more strict interpretation here, where the curried function, and each function returned by it, only takes a single argument.

I'm also more concerned with the performance of the curried functions than the performance of curry, so code generation seems like a logical approach. But of course the performance of curry is also something worth considering for some use cases, so I'm open to alternate suggestions that do away with code generation, as long as the performance of the curried functions isn't impacted too drastically.

Answer 1

Overall a solid approach.

Here's a few options to consider though:

First of all, you could eliminate the separate curry function and just use the generateCurry function directly, after all, it's already curried itself ;)

An approach that's maybe a bit more in line with Luas metaprogramming philosophy would be to replace your memoized function with a table that generates missing keys on the flies using the __index metamethod, so you'd write code like curry[4](print)

Choosing code generation was probably the right choice. For one you say that you care more about the speed of the curried function than the speed of curry; but even then, Lua has one of the quickest parsers among all scripting languages and memoization can get you a long way too.

The one critical thing in your code is that you interpolation strings a lot. Repeated string interpolation and concatenation in Lua are slow because 1) it needs to constantly allocate new space and 2) it needs to hash every intermediate result.

A better solution would be either string.rep(str, n, sep), which repeats a string n times and puts sep in between each pair of strings; or table.concat(tab, sep) which concatenates all the values of a sequence with sep in between.

Both of these are implemented in C and only hash the end result once all the strings are concatenated together. It also lets Lua allocate space for the entire result string from the start, though I am not sure if it does that for string.concat.

Even this would only be an issue with very large numbers of arguments though, and even then only for the first time, since you cache the generated functions.

Overall I'd say it's a pretty solid implementation.

---

I quickly whipped up an example of how I'd do it, mostly out of boredom, but maybe you can steal the one or other useful idea from it ;)

local function seq(n, ...)
    if n>0 then
        return seq(n-1, n, ...)
    else
        return ...
    end
end

local curry = setmetatable({}, {
    __index = function(self, key)
        if type(key) == 'number' then
            self[key] = assert(load(table.concat{
                "local fn = ...; return "
                .. string.rep("function(arg_%i) return ", key):format(seq(key))
                .. "fn("
                .. string.rep("arg_%i", key, ", "):format(seq(key))
                .. ")"
                .. string.rep(" end", key)
            }))
            return self[key]
        end
    end
})

---

Further reading on Lua otimizations:

• http://lua-users.org/wiki/OptimisationTips
• https://www.lua.org/gems/sample.pdf
• http://wiki.luajit.org/Numerical-Computing-Performance-Guide
• http://wiki.luajit.org/NYI