Evaluating Partial Function Application

I’ve mentioned Currying and partial function application already. The idea is that given a function with more than one argument:

if we call it with less than the arguments it expects, then it will return a function that accepts the rest:

(The trailing comma is just a syntactic convention that I’ve come up with that lets the compiler know that we know what we are doing, and lets the reader know that there is Currying going on.) Now setting aside how we might type-check that, it turns out that it’s actually pretty easy to evaluate.

Normal application of a closure looks something like this (Java-ish pseudocode):

For those of you that don’t know Java, List<Symbol> means List of Symbol. And yes, we’re ignoring the possibility that we’re passed the wrong number of arguments, the type checker should deal with that.

Now if we are expecting that we might get fewer than the full set of arguments, we can instead create a new closure that expects the rest:

Note that the dictionary that we have been building is used to extend the environment of the new closure with the values we know already, and that the formal_args we’ve been chaining down is now precisely the remaining arguments that we haven’t seen yet.

Of course this allows for silly definitions like:

But presumably our type checker (if not our grammar) would disallow that sort of thing, because there’s nothing to put a trailing comma after.

[Edit] You could alternatively add a guard clause to  apply() that says if this closure is expecting arguments and doesn’t get any, just return the original closure. That way, something like:

while still silly, would at least not be unnecessarily inefficient.

Addendum – over-complete function application

So I got the above working in F♮ easily enough, then I noticed an anomaly. The type of:

is definately int → int → int, which means that the type checker is allowing it to be called like:  adder(2, 3). Why can’t I call it like that? It turns out I can:

Assuming the type checker has done its job, then if we have any actual arguments left over then they must be destined for the function that must be the result of evaluating the body. So instead of just evaluating the body in the new env, we additionally call  apply()  on the result, passing in the left-over arguments.

This is pretty cool. We can have:

and call it like  adder(2, 3) or  adder(2)(3), and we can have:

and call it like  add(2, 3) or  add(2)(3).

One or the Other, or Both?

The question arises: if we have implicit Currying, (partial function application) then do we need explicit Currying (explicitly returning a function from a function)? The answer is a resounding yes! Consider:

We’ve only called  bigfn once, when evaluating the first argument to map, so expensive_calculation only got called once, and the explicit closure calling either cheap_op_1 or  cheap_op_2 gets called on each element of the list.

If instead we had written:

Then the call to  expensive_calculation would get deferred until the  map actually called its argument function, repeatedly, for each element of the  long_list.

Leave a Reply

Your email address will not be published. Required fields are marked *