slopfront
Reddit, read-only. No JavaScript. No cookies. No tracking.
preferences

Currying in Lua

7 points · submitted Sep 2017 by u/flappypengujn

I'm pretty new to Lua so please excuse any obvious oversights.

  1. Is there a consensus on the right way to curry an existing function (and I don't mean nested partial applications like curry(curry(f,1),2), but curry(f)(1)(2)). Are there any good libraries that do this?
  2. Is there any possibility of curried functions being built into Lua? Or does it conflict with other fundamental language constructs, like varargs or something.
  3. One particular case that drives me crazy it that it seems really annoying to pass methods around, e.g. as a callback. It’s very easy to carry a function a.f around, but it seems in order to pass the method a:f you have to write function(args) a:f(args) end. With currying, this wouldn’t be a problem since a:f would be syntax sugar for a.f(a) . This seems to be far more intuitive and (at least to me) the “obvious” way the language should behave. Without currying, is there a simple way around this?

9 comments · 90% upvoted · other discussions

comments

otikik 6 points · Sep 2017

If you know the number of arguments a function uses, you can curry it the obvious way:

function curry2(f)
  return function(a)
    return function(b)
      return f(a, b)
    end
  end
end

And use it like so:

local add = function(a,b) return a+b end
print(curry2(add)(1)(2)) -- 3

You could define a curry5 or curry10 similarly, if you needed to. But you need to know how many arguments you are going to curry.

Is there any possibility of curried functions being built into Lua? Or does it conflict with other fundamental language constructs, like varargs or something.

I see no problem with that, other than the one I mentioned before: there's no standard way to know the number of arguments a given function uses (you could do that using the debug library, but that is not supposed to be used in production code).

One particular case that drives me crazy it that it seems really annoying to pass methods around, e.g. as a callback. It’s very easy to carry a function a.f around, but it seems in order to pass the method a:f you have to write function(args) a:f(args) end

The way I usually overcome that particular problem is by allowing not only a callback, but also some arguments. Then I can pass the function and its "self". In other words, I end up passing a.f, a.

With currying, this wouldn’t be a problem since a:f would be syntax sugar for a.f(a)

I'm not certain I agree with that. a:f only exists in Lua on the syntax layer; when it reaches the semantic layer the call is already indistinguishable from a.f(a, ...).

smog_alado 2 points · Sep 2017

I could see a:f being syntactic sugar for function (...) return a.f(a, ...) end.

I the reason this wasn't added to the language yet is that it is too "magical" and would require some clever tricks on the compiler to avoid slowing down regular method calls.

flappypengujn [OP] 1 points · Sep 2017

You could define a curry5 or curry10 similarly, if you needed to. But you need to know how many arguments you are going to curry.

I was hoping there would be a way to avoid defining special curry functions for every case, or passing in the argument length into the function. Now that I think about it though, as you mention that's probably impossible because Lua functions don't have a fixed argument list length.

I'm not certain I agree with that. a:f only exists in Lua on the syntax layer; when it reaches the semantic layer the call is already indistinguishable from a.f(a, ...).

I agree with what you said, but I'm arguing that a:f should syntactically mean something else instead of a.f(a, ...). Namely, the following seems sensible to me:

function a:f( [params] ) [body] end

should expand to

function a.f(self)
    return function( [params] ) [body] end
end

(where [ ] is a placeholder for code),

and a:f should expand to a.f(a).

Not only is this way more intuitive (you can use a:f everywhere in the same way you would use a.f), but it also seems to capture the semantics of methods better: methods are just regular functions that can be "interpreted" as first being bound to an object, then accepting arguments like a normal function. That's exactly when currying should be used.

smog_alado 2 points · Sep 2017

That proposed function a:f syntax would be a breaking change (unlike just adding the a:f syntax sugar) but I imagine you already know that...

I am not sure that having methods be automatically curried is more intuitive or natural in Lua-land. For example when we call string methods like s:sub(1,2) it will end up calling string.sub(s,1,2) and string.sub is a function implemented in C that just happens to take s as its first argument and it doesn't do currying or know how to do so.

BTW, this reminds me of another thing. For Lua it is very important that all language features are available for C functions using the C-API. If we were to add currying to Lua and modify the VM to better support currying we would also have to think of a way to support currying on the C side of things. (one example of this philosophy is how Lua has pcall instead of try/catch blocks)

smog_alado 2 points · Sep 2017

Is there a consensus on the right way to curry an existing function?

I don't know out of the top of my head what libraries have a currying function but this is how I would do it:

function curry(min_args_n, func)

    function make_curry(old_args_n, old_args)
        local function curryed(...)
            local extra_args = table.pack(...)
            local extra_args_n = extra_args.n

            local args = {}
            table.move(old_args, 1, old_args_n, 1, args)
            table.move(extra_args, 1, extra_args_n, old_args_n + 1, args)
            local args_n = old_args_n + extra_args_n

            if args_n >= min_args_n then
                return func(table.unpack(args, 1, args_n))
            else
                return make_curry(args_n, args)
            end
        end
        return curryed
    end

    return make_curry(0, {})
end

-- Simple example
local add = curry(2, function(x, y) return x + y end)
local plus1 = add(1)
print(plus1(10), plus1(20))

Conceptually, the tricky part is defining what currying means in Lua. How are nil par The tricky part is actually defining precisely what currying means in Lua (since every function in Lua is technically a vararg function). I chose to force you to explicitly specify the number of parameters to curry and to pass on extra parameters that you pass after that.

In the implementation, the first tricky bit is taking care of nil arguments (I use the ".n" feature of table.pack and keep track of the number of arguments passed by hand instead of relying on #). The second tricky bit is making sure that we create immutable copies of the argument arrays, instead of mutating them.

Is there any possibility of curried functions being built into Lua? Or does it conflict with other fundamental language constructs, like varargs or something.

I think that would be very unlikely. It is not imediately obvious how currying should interact with varargs functions and it also doesn't fit super well with Lua's "function argument adjusting" semantics, where extra arguments are thrown away and missing arguments are set to nil.

Another more general problem is that in dynamically-typed programming languages curried functions are prone to hiding errors when you pass the wrong number of parameters to a function or pass an argument of the wrong type to a curried function. In Haskell, if you pass the wrong arguments to a function you get a compile-time type error but in Lua you would just have your curried function silently return a partially-applied function and you will only notice the problem much later. And when it does blow up, the stack trace is going to point to curry and make_curry and won't tell you what lines are the ones actually responsible for the wrong arguments.

(Although now that I think of it, the debugability problem could be made a bit better if curried functions were built in instead of created as a library)

Without currying, is there a simple way around this?

Not really, other than keep bugging Roberto to add the a:f syntactic sugar in Lua 5.4 :)

(Assuming you meant ... instead of args, of course)

flappypengujn [OP] 1 points · Sep 2017

Conceptually, the tricky part is defining what currying means in Lua. How are nil par The tricky part is actually defining precisely what currying means in Lua (since every function in Lua is technically a vararg function).

This is a good point, and it's apparent to me now that generically converting existing functions to a curried version is pretty much impossible.

As for varargs, that doesn't seem to be a fundamental barrier to currying by itself. As an exercise I tried to make a function such that sum() = 0, sum(1)() = 1, sum(1)(2)() = 3 etc., and I think the following works

sum = (function()
    local sum_accum = function(acc) 
        return function(a)
            if a == nil then
                return acc
            else return sum_accum(acc+a)
        end
    end
    return sum_accum(0)
end)()

(There may be uses for variable length arguments that can't be taken care of like this, but I'm having trouble coming up with an example of a good reason to use varargs that doesn't involve a fold.)

Although, it is way easier to just have varargs be handled through a table. Similarly with nil.

Actually, it seems that Lua functions are more or less equivalent to a 1-argument function accepting a table argument. There is nothing wrong with this, but I guess what I'd really like to see is better support for (from the language) and more explicit use of (from the community) currying where appropriate. For example if your function has 2 mandatory arguments and a bunch of vararg/possibly nil arguments, then I see no downside to explicitly write it as a curried function with 3 arguments where the last is a table.

Unfortunately, right now coding that would be a pain because of having to nest anonymous function declarations. But that just seems to be simple syntax fix: just have function(a)(b) return a+b end be syntax sugar for function(a) return function(b) return a+b end end, and so on. This type of change should be easy to make and can only make life easier for programmers.

I guess the problem with this is that the way Lua is currently implemented might make the latter more inefficient than function(a,b) return a+b end when calling add(a)(b) vs add(a,b). Do you know whether this is true?

The second tricky bit is making sure that we create immutable copies of the argument arrays, instead of mutating them.

This is another good point. I haven't thoroughly thought through the details but it seems that currying in imperative languages can be quite tricky to get right.

And when it does blow up, the stack trace is going to point to curry and make_curry and won't tell you what lines are the ones actually responsible for the wrong arguments.

Why would it point to curry instead of the underlying function (e.g. in your code, wouldn't it step into return func(table.unpack(args, 1, args_n)) and then error inside func)? I agree that if the function was applied partially though that it'd be hard to tell at which step a bad argument was passed.

Not really, other than keep bugging Roberto to add the a:f syntactic sugar in Lua 5.4 :) (Assuming you meant ... instead of args, of course)

Yeah, although I actually think that a:f should be syntax sugar for something else (see my other response in this thread).

smog_alado 1 points · Sep 2017

As for varargs, that doesn't seem to be a fundamental barrier to currying by itself.

It is not a barrier but it is a bit awkward because there is more than one way to do it. (choosing a fixed number of arguments, expanding until receiving nil, etc)

then I see no downside to explicitly write it as a curried function with 3 arguments where the last is a table.

I would argue that this doesn't have to do with varargs actually. A lot of the time, things get much simpler if we use a table argument instead of varargs. :)

Do you know whether this is true?

Yes, right now Lua is going to create an intermediate closure value if you call add(a)(b). I think fixing this would require nontrivial changes to the virtual machine to add low-level support for curried functions and a new bytecode that can do the two curried function calls all at once (similar to the concatenation bytecode, which can do a .. b .. c in one step).

But those optimizations would only help for cases where currying can be trivially removed, like add(1)(2), which we might has as well called as add(1,2) directly. For code that is using lots of higher order combinators (like map, filter, and so on) you need some more aggressive compiler optimizations (such as inlining), which are tricky to do in a highly dynamic scripting language.

I haven't thoroughly thought through the details but it seems that currying in imperative languages can be quite tricky to get right.

Functional languages can also have mutable state :)

and then error inside func

I probably could have been clearer but the real problem is that the line that calls the curried function doesn't show up in the stack trace.

In the following example, the first line is responsible for the bug but it doesn't show up in the stack trace.

local f = add(false) -- this line is to blame (can't make arithmetic on booleans)
local result = f(1)  -- but this is the line that appears in the stack trace

Again, I think the debugability could be improved if the Lua VM were modified to treat curried functions specially and keep track of this info but it would be nontrivial to do so.

TotesMessenger 1 points · Sep 2017

I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:

If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / Contact)

ilo_kali 1 points · Jul 2022

Here's how I would do it:

function add(a,b)
    return a+b
end
function curry(fn, args, arg, first) 
    args = args or {} 
    args[#args+1] = arg 
    return (arg or not first) and function(arg)return curry(fn,args,arg,1)end or fn(table.unpack(args)) 
end

print(curry(add)(2)(3)()) --> 5

It simply recursively returns functions to collect each argument in a table until it is called with no arguments, then calls the passed function with the unpacked table.