Leaving the land of ML

(Or: How making a simple design decision took me almost two months.)

The language so far has been a subset of ML, with a different syntax. The plan was to also follow the ML (or Haskell, or other languages in that family) model of function application. In that model, these two functions can be used in exactly the same way:

def direct x y -> x + y
def indirect x -> fn y -> x + y

When you call them simply by applying them to two arguments, without caring about the question whether these arguments are consumed by a single function, or whether that function takes one argument, returning a function that takes the second. This is very convenient, and makes for an elegant type system.

You call a function directly by name, as in indirect 4 5, the compiler can see what the actual function you are calling looks like, and generate code that provides the right amount of arguments. However, in other contexts this is more difficult.

def apply_to_ones f ->
  f 1 1

Now, when compiling the body of this function, it is a complete mystery what the function value looks like. The type system tells us it is a function of at least two arguments, but either direct or indirect above would qualify. So to actually call it, run-time negotiation has to happen. The call site know the amount of arguments it has, and the function knows the amount it wants. This is not a very complicated thing to do, but it has to happen on every call to every unknown function. In a program written in a functional style, that's a lot of calls.

At first I was wondering whether I was crazy to have this problem, but OCaml's assembly output also calls a subroutine to call unknown functions, and yesterday I finally found a paper that properly describes the issue.

There are two problems with supporting this. Firstly, performance. It is such a shame to require a bunch of instructions (including a branch) for a simple function call. Higher-order functions calling their arguments inside an inner loop shouldn't be a potential performance problem. Secondly, it muddles up the calling conventions, which not only makes the compiler itself more complicated, but also the garbage collector, which has to make sense of more complicated stack frames and register shuffling when it tries to find pointers.

So I have decided to avoid the issue altogether by requiring function applications to always pass the right amount of arguments. I've never found this requirement particularly troublesome in non-ML-style languages (everything from C to Scheme).

The upshot is that instead of writing indirect 1 2, you'll have to be aware of its arity and write (indirect 1) 2. Still looks relatively good, and brings back fond memories of Lisp.

I was afraid that this would wreak terrible havoc on the viability of pointfree function definitions, but in fact it only complicates things for definitions in which some of the arguments are left out. I.e. this is not a problem:

let concat = foldr (++) []

Because the resulting definition of concat takes no arguments you don't have to worry about 'split arity'. However, look at this function:

def remove x -> filter (/=x)

(Removes an element from a sequence, where filter is a function of two arguments that filters out elements not satisfying a predicate.)

With explicit arity, you have to write (remove 3) [1, 2, 3, 4], which is decidedly less elegant.

Finally, when you have to always provide the correct amount of arguments, straight-forward partial application is sacrificed. You can't apply a function to less arguments than it needs without confusing the type system. To still allow relatively light-weight partial application, I came up with the following monstrosity:

let concat = foldr (++) [] _

The underscore (in a function application) indicates a 'hole', an argument that is not supplied. This is a bit uglier than just leaving arguments off, but has the advantage that you can also put it before supplied arguments, and tricks with flip to get the correct argument in front aren't needed anymore.

let mod16 = mod _ 16

I'll probably change the parser to use the same tricks with operators (_+5 instead of (+5), which also solves the (-3) ambiguity), but haven't gotten around to that yet.