Is it possible to have currying and variadic function at the same time

curryingfunctional programming

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?

Best Answer

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';
}

Related Solutions

Java – Does reflection in Java make its functions “first class”

A first class function is one where the function is available on its own. C, C++, and Ruby allow this approach. Java requires the function to be tied to a class and only provides a metadata representation of it, even if that class is merely a static collection of functions. C# supports first class functions with lambdas (which are based off of lambda calculus) and delegates.

Ruby is one of the languages that truly supports first class functions. The difference is that not only can you define functions on their own, but you can pass them as arguments and invoke methods on them. Check out Ruby's Proc object which is used to represent an arbitrary block of code.

The end result of having first class functions is the fact that it lends to some very powerful and flexible coding constructs. This is distinctly different than hacking around first class functions using the reflection API.

Java doesn't have full support of first class functions. The reflection API can give you some semblance of first class functions if the Method object is referencing a static method. In essence you can invoke a static method like this:

Method reference = mathClass.getMethod("sqrt");

// NOTE: the first parameter is for the object instance,
// but for static methods it is ignored
double answer = (double)reference.invoke(null, 4);

As soon as you are working with an instance method, you lose that first class function ability. You might be able to hack together some reflection based delegate support similar to C#, but the resulting code will be much slower. The "delegate" would take care of keeping the object reference for future invocations.

The advantage of currying

With curried functions you get easier reuse of more abstract functions, since you get to specialize. Let's say that you have an adding function

add x y = x + y

and that you want to add 2 to every member of a list. In Haskell you would do this:

map (add 2) [1, 2, 3] -- gives [3, 4, 5]
-- actually one could just do: map (2+) [1, 2, 3], but that may be Haskell specific

Here the syntax is lighter than if you had to create a function add2

add2 y = add 2 y
map add2 [1, 2, 3]

or if you had to make an anonymous lambda function:

map (\y -> 2 + y) [1, 2, 3]

It also allows you to abstract away from different implementations. Let's say you had two lookup functions. One from a list of key/value pairs and a key to a value and another from a map from keys to values and a key to a value, like this:

lookup1 :: [(Key, Value)] -> Key -> Value -- or perhaps it should be Maybe Value
lookup2 :: Map Key Value -> Key -> Value

Then you could make a function that accepted a lookup function from Key to Value. You could pass it any of the above lookup function, partially applied with either a list or a map, respectively:

myFunc :: (Key -> Value) -> .....

In conclusion: currying is good, because it lets you specialize/partially apply functions using a lightweight syntax and then pass these partially applied functions around to higher order function such as map or filter. Higher order functions (which take functions as parameters or yield them as results) are the bread and butter of functional programming, and currying and partially applied functions enable higher order functions to be used much more effectively and concisely.

Best Answer

Related Solutions

Java – Does reflection in Java make its functions “first class”

The advantage of currying

Related Topic