6
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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:

\$\endgroup\$
7
  • \$\begingroup\$ Interesting ideas here! I'm targeting LuaJIT and wasn't aware that it had picked up that last argument to string.rep from 5.2. That's good to know. Interesting idea about using the cache directly, but I think I prefer the curry(n, func) style over curry[n](func). Also I believe you meant to put commas in that table there, instead of concat ops (the result is the same, but the table concat and string concat operators are redundant, one or the other would do). Also unsure about the assert, maybe would suffice to add a check to make sure key is positive to that type check. Nice review! \$\endgroup\$ Jul 9, 2019 at 21:04
  • \$\begingroup\$ Another thing I'm curious about now: I was aware of the table.concat trick, but tend to avoid disposable tables because of gc load. It doesn't really matter here, since results are cached, but now I wonder what gc overhead looks like for table.concat vs string concats without a table. Intuitively it seems that at some high number of strings, getting rid of the table would be cheaper than getting rid of the strings, and at some low number, getting rid of the strings would be cheaper. But now I want to test this. \$\endgroup\$ Jul 9, 2019 at 21:17
  • \$\begingroup\$ @user11536834 Interesting that you ask about garbage-collection; consider that closures (aka. functions) are also garbage-collected functions, so calling something like curried_print('a')('b')('c') will create 2 closures on the fly. Also, know that LuaJIT can't JIT-compile function closing, so your curried functions will always run interpreted until the last function call. string.rep can easily be replaced with table.concat, with a small speed decrease. For small numbers of arguments, the cost of the GC may be higher than the concatenation though, you'd have to benchmark that. \$\endgroup\$ Jul 10, 2019 at 4:44
  • \$\begingroup\$ (Updated my answer with two links) \$\endgroup\$ Jul 10, 2019 at 4:47
  • \$\begingroup\$ Hmm, I was aware that closures were GC'd, but had somehow missed the fact that they don't JIT (yet?). That is a serious concern, may have to scrap this approach entirely -- guess I should keep up with LJ's issue tracker. \$\endgroup\$ Jul 10, 2019 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.