13

I am thinking about making currying and variadic functions both available in a dynamically-typed functional programming language, but I wonder if it is possible or not.

Here are some pseudocode:

sum = if @args.empty then 0 else @args.head + sum @args.tail

which is supposedly to sum all its arguments. Then, if sum itself is treated a number, then the result is 0. for example,

sum + 1

is equal to 1, assuming that + can only work on numbers. However, even sum == 0 is true, sum will still maintain its value and functional property no matter how many arguments are given (hence "partially applied" and "variadic" at the same time), for example, if I declare

g = sum 1 2 3

then g is equal to 6, however, we can still further apply g. For example, g 4 5 == 15 is true. In this case, we cannot replace the object g by a literal 6, because although they yield the same value when treated as an integer, they contain different codes inside.

If this design is used in a real programming language, will it cause any confusion or ambiguity?

  • 1
    Strictly speaking, using currying as a fundament of a language means that all functions are unary - not only are there no variadic functions, there aren't even any binary ones! However, programs in that language will still look as if they took multiple arguments, and that goes for variadic functions just as much as for normal ones. – Kilian Foth Jun 9 '15 at 8:17
  • Then my question is simplified to "can an object be a function and a non-function value at the same time?" In the above example, sum is 0 without an argument and recursively calls itself with an argument. – Michael Tsang Jun 9 '15 at 8:29
  • isn't that the job of reduce? – ratchet freak Jun 9 '15 at 9:01
  • 1
    Take a look at the functions you're using on args: empty, head, and tail. Those are all list functions, suggesting that maybe the easier and more straightforward thing to do would be to use a list where the variadic stuff would be. (So, sum [1, 2, 3] instead of sum 1 2 3) – Michael Shaw Jun 9 '15 at 18:06
6

How can varargs be implemented? We need some mechanism to signal the end of the argument list. This can either be

  • a special terminator value, or
  • the length of the vararg list passed as an extra parameter.

Both of these mechanisms can be used in the context of currying to implement varargs, but proper typing becomes a major issue. Let's assume that we are dealing with a function sum: ...int -> int, except that this function uses currying (so we actually have a type more like sum: int -> ... -> int -> int, except that we don't know the number of arguments).

Case: terminator value: Let end be the special terminator, and T be the type of sum. We now know that applied to end the function returns: sum: end -> int, and that applied to an int we get another sum-like function: sum: int -> T. Therefore T is the union of these types: T = (end -> int) | (int -> T). By substituting T, we get various possible types such as end -> int, int -> end -> int, int -> int -> end -> int, etc. However, most type systems do not accommodate such types.

Case: explicit length: The first argument to a vararg function is the number of varargs. So sum 0 : int, sum 1 : int -> int, sum 3 : int -> int -> int -> int etc. This is supported in some type systems and is an example of dependent typing. Actually, the number of arguments would be a type parameter and not a regular parameter – it would not make sense for the arity of the function to depend on a runtime value, s = ((sum (floor (rand 3))) 1) 2 is obviously ill-typed: this evaluates to either s = ((sum 0) 1) 2 = (0 1) 2, s = ((sum 1) 1) 2 = 1 2, or s = ((sum 2) 1) 2 = 3.

In practice, none of these techniques should be used since they are error-prone, and don't have a (meaningful) type in common type systems. Instead, just pass a list of values as one paramter: sum: [int] -> int.

Yes, it is possible for an object to appear as both a function and a value, e.g. in a type system with coercions. Let sum be a SumObj, which has two coercions:

  • coerce: SumObj -> int -> SumObj allows sum to be used as a function, and
  • coerce: SumObj -> int allows us to extract the result.

Technically, this is a variation of the terminator value case above, with T = SumObj, and coerce being a un-wrapper for the type. In many object-oriented languages, this is trivially implementable with operator overloading, e.g. C++:

#include <iostream>
using namespace std;

class sum {
  int value;
public:
  explicit sum() : sum(0) {}
  explicit sum(int x) : value(x) {}
  sum operator()(int x) const { return sum(value + x); }  // function call overload
  operator int() const { return value; } // integer cast overload
};

int main() {
  int zero = sum();
  cout << "zero sum as int: " << zero << '\n';
  int someSum = sum(1)(2)(4);
  cout << "some sum as int: " << someSum << '\n';
}
  • Awesome answer! The drawback with packing varargs up in a list is that you lose the partial application of currying. I was toying with a Python version of your terminator approach, using a keyword argument ..., force=False) to force the application of the initial function. – ThomasH Aug 14 '16 at 10:12
  • You could make your own higher order function that partially applies a function that takes a list, like curryList : ([a] -> b) -> [a] -> [a] -> b, curryList f xs ys = f (xs ++ ys). – Jack Aug 14 '16 at 19:45
2

You may want to look at this implementation of printf in Haskell, along with this description of how it works. There's a link on the latter page to Oleg Kiselyov's paper on doing this kind of thing, which is also worth reading. In fact, if you're designing a functional language, Oleg's web site should probably be compulsory reading.

In my opinion, these approaches are a bit of a hack, but they show that it is possible. If your language features full dependent typing, however, it's much simpler. A variadic function to sum its integer arguments could then look something like this:

type SumType = (t : union{Int,Null}) -> {SumType, if t is Int|
                                         Int,     if t is Null}
sum :: SumType
sum (v : Int) = v + sum
sum (v : Null) = 0

An abstraction for defining the recursive type without needing to give it an explicit name might make writing such functions easier.

Edit: of course, I just read the question again and you said a dynamically typed language, at which point obviously the type mechanics aren't really relevant, and therefore @amon's answer probably contains everything you need. Oh well, I'll leave this here in case anyone comes across this while wondering about how to it in a static language...

0

Here is a version for currying of variadic functions in Python3 that uses the "terminator" approach of @amon, by taking advantage of Python's optional arguments:

def curry_vargs(g):
    actual_args = []
    def f(a, force=False):
        nonlocal actual_args
        actual_args.append(a)
        if force:
            res = g(*actual_args)
            actual_args = []
            return res
        else:
            return f
    return f

def g(*args): return sum(args)
f = curry_vargs(g)
f(1)(2)(3)(4,True) # => 10

The returned function f collects arguments passed to it in successive calls in an array that is bound in the outer scope. Only when the force argument is true the original function is called with all arguments collected so far.

Caveats of this implementation are that you always have to pass a first argument to f so you cannot create a "thunk", a function where all arguments are bound and can only be called with the empty argument list (but I think this is in line with the typical implementation of curry).

Another caveat is that once you pass a wrong argument (e.g. of the wrong type) you have to re-curry the original function. There is no other way to reset the internal array, this is only done after a successful execution of the curried function.

I don't know if your simplified question, "can an object be a function and a non-function value at the same time?", can be implemented in Python, as a reference to a function without parentheses evaluates to the internal function object. I don't know if this can be bent to return an arbitrary value.

It would probably be easy in Lisp, as Lisp symbols can have a value and a function value at the same time; the function value is simply selected when the symbol appears in function position (as the first element in a list).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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