Currying and why we don't pass arguments as tuples

Over the last few weeks, I've been designing a new programming language, a successor to Fenris. I originally made a number of mistakes in the type system for Fenris, namely not unifying it and not including generics and type inference from the beginning. Designing a new type system that makes sense from the start is pretty hard, but I think it's necessary for a good language. In this article, I'd like to share some of my design work in this new type system with functions and multiple arguments.

When I was first learning functional programming, I was intrigued by the idea of currying. Functions are normally represented in functional languages with a type like this:

a -> b

This says the function takes in an argument of type a and returns a result of type b. For example, a function that parses a string into an integer would have the type:

string -> int

Although a and b may be different for different functions, all functions have the same basic "arrow" type and can be treated the same. The hitch is that you can only take one argument and return one result. This is where currying comes in.

Instead of having a function that accepts multiple arguments, we have a function that accepts the first argument and returns another function that accepts the second argument and so on. The function that accepts the last argument does the actual computation and returns another value. For example, let's say we have a function in Python which adds two numbers:

def add(x, y):
  return x + y

The curried version of this function would look like this:

def add(x):
  return lambda y: x + y

This function can be applied like this:

add(3)(5)

This works because local functions capture parameters and other variables defined in their parent functions. So when add returns the lambda, it includes the value of x in its environment.

Of course, the syntax for this in Python looks a bit ugly because Python functions aren't really intended for currying. However, more pure functional languages will usually curry your functions for you. For instance, the same thing in Haskell would look like this:

add x y = x + y 
add 3 5

This has type Int -> (Int -> Int). Even though add appears to accept two arguments, it actually takes one argument (x) and returns another function of type Int -> Int which takes the second argument (y) and actually does the addition. Since the arrow associates to the right, we can also write this as Int -> Int -> Int.

Currying isn't the only way to simplify functions of multiple arguments into having a plain arrow type. Normally, if we want to return multiple values from a function, we group the values together as a tuple. So why not use the same approach for multiple arguments? Suppose we had a function that converts a two-dimensional vector in rectangular coordinates (x and y) into polar coordinates (angle and magnitude). We could give this the type (Double, Double) -> (Double, Double). Instead of being curried, the arguments are grouped as a tuple. This is appealing, at least to me, because multiple inputs are treated the same way as multiple outputs.

Alas, this seems like a good idea, but it breaks down when we add classes and a subtyping rule to the type system.

Think about this. In Java, List<String> is not a subtype of List<Object>. This is because if we upcast a List<String> to a List<Object>, we can add elements to the list that are not Strings. In general, one generic type cannot be a subtype of another generic type unless all the type parameters are equal and the class is a subclass of the other class.

So what does this have to do with functions? If we want to have a unified type system, then function types must adhere to the same typing rules as class types. That is, functions should be treated as objects of some class. To use some more Java syntax, we might write our function type as:

class Function<A, B>

instead of A -> B. It makes a lot of sense to treat functions this way, although there are some other subtleties I won't go into. We can treat the "apply" operator as a virtual method of this class, overridden by each function object. Lambdas can capture free variables as fields.

If we want to use our tuple technique for passing arguments, we will find that it doesn't work with this system. Tuples, like functions, must be expressed as a generic class type in a unified system:

class Tuple<L, R>

where L and R are the types of the left and right components of the tuple. We normally think of tuples as containing an arbitrary number of elements, but we usually only get to have a finite number of type parameters (unless you get really fancy with variadic type parameters). We can chain tuples with more than 2 elements like this:

Tuple<A, Tuple<B, C>>

So here's the issue: if we have a function that accepts arguments of type Tuple<A, B>, and we want to pass it a tuple of arguments of type Tuple<X, Y>, we can only do this when A = X, and B = Y. If X is a subtype of A or Y is a subtype of B, we will get a type error. Subsumption is broken. Suddenly, you can't pass a String as an argument to a function that accepts Objects.

This is a pretty major problem, and it prevents us from using the tuple technique for passing arguments. This means that we have to go back to currying for passing multiple arguments (or invent some other system that doesn't have this problem).