I’ve mentioned Currying and partial function application already. The idea is that given a function with more than one argument:
|
1 2 3 |
fn add (x, y) { x + y } |
if we call it with less than the arguments it expects, then it will return a function that accepts the rest:
|
1 2 3 |
def add2 = add(2,); add2(4); // 6 |
(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):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Closure { private List<Symbol> fargs; private Env env; private Expr body; Expr apply(List<Expr> actual_args) { Map<Symbol, Expr> dictionary; List<Symbol> formal_args = this.fargs; while(formal_args.isNotNull() && actual_args.isNotNull()) { dictionary.put(formal_args.head(), actual_args.head()); formal_args = formal_args.tail(); actual_args = actual_args.tail(); } return this.body.eval(this.env.extend(dictionary)); } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Closure { private List<Symbol> fargs; private Env env; private Expr body; Expr apply(List<Expr> actual_args) { Map<Symbol, Expr> dictionary; List<Symbol> formal_args = this.fargs; while(formal_args.isNotNull() && actual_args.isNotNull()) { dictionary.put(formal_args.head(), actual_args.head()); formal_args = formal_args.tail(); actual_args = actual_args.tail(); } if (formal_args.isNotNull()) { return new Closure(formal_args, this.body, this.env.extend(dictionary)); } else { return this.body.eval(this.env.extend(dictionary)); } } } |
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:
|
1 2 3 4 5 |
fn add (x, y) { x + y } def anotheradd = add(,); |
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:
|
1 |
add()()(2)()()(3) |
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:
|
1 2 3 |
fn adder(x) { fn(y) { x + y } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Closure { private List<Symbol> fargs; private Env env; private Expr body; Expr apply(List<Expr> actual_args) { Map<Symbol, Expr> dictionary; List<Symbol> formal_args = this.fargs; while(formal_args.isNotNull() && actual_args.isNotNull()) { dictionary.put(formal_args.head(), actual_args.head()); formal_args = formal_args.tail(); actual_args = actual_args.tail(); } if (formal_args.isNotNull()) { return new Closure(formal_args, this.body, this.env.extend(dictionary)); } else if (actual_args.isNotNull()) { return this.body.eval(this.env.extend(dictionary)).apply(actual_arguments); } else { return this.body.eval(this.env.extend(dictionary)); } } } |
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:
|
1 2 3 |
fn adder(x) { fn (y) { x + y } } |
and call it like adder(2, 3) or adder(2)(3), and we can have:
|
1 |
fn add(x, y) { x + y } |
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:
|
1 2 3 4 5 6 7 8 9 |
fn bigfn (a) { if (expensive_calculation(a)) { fn (b) { cheap_op_1(b) } } else { fn (b) { cheap_op_2(b) } } } map(bigfn(x), long_list); |
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:
|
1 2 3 4 5 6 7 8 9 |
fn bigfn (a, b) { if (expensive_calculation(a)) { cheap_op_1(b) } else { cheap_op_2(b) } } map(bigfn(x,), long_list); |
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.