« Partial function application in F#, part 3: precomputing partial results | Main | Partial function application in F#, part 5: design considerations »

June 19, 2011

Partial function application in F#, part 4: underlying concepts

In previous parts, I discussed what partial application means and why it’s so important in F# programming.  Because partial application is so idiomatic, it’s important to design your own functions to play nicely with partial application, and that means you need to have some idea of the conceptual model that underlies it.

A closer look at F# functions

Here’s a dead simple F# function, declared in F# Interactive.

> let inc x = x + 1;;
val inc : int –> int

F# Interactive’s response tells us that inc is a function from int to int.  It represents this using the arrow notation.  That is, a –> b is a type meaning ‘function which takes an a and returns a b.’  It’s roughly equivalent to Func<T, TResult> in C#:

Func<int, int> inc = x => x + 1;

So far so good.  Now obviously F# also allows us to declare functions of more than one argument.  In previous parts I used a trivial example I called incby.  Let’s review its declaration and its type:

> let incby x y = x + y;;
val incby : int -> int –> int

As you can see, incby takes two integers, x and y, and returns another integer.  So it’s a function from int and int to int.

But look closely at the way F# Interactive represents this function of two arguments.  That notation looks really ambiguous, because you could also read it as:

int –> (int –> int)

which would mean ‘takes an int and returns an int –> int,’ i.e. a function of one argument which returns another function.

So what is the int –> int –> int function type?  “Function which takes two int arguments and returns an int’ or ‘function which takes one int argument and returns an int –> int function’?

A difference that makes no difference is no difference

It turns out that this difference is no difference.  int –> int –> int is unambiguous, because the two readings are conceptually the same.  Partial application is the realisation of this.

Recall that partial application means that you can provide incby with only one argument instead of its full complement of two:

> incby 2 3;;
val it : int = 5
> incby 2;;
val it : (int -> int) = <fun:it@6>
> it 3;;
val it : int = 5

Look at the first line again.  It’s natural to think of this as applying incby to 2 and 3.  But it’s also correct to think of it as evaluating (incby 2) and applying that to 3:

> (incby 2) 3;;
val it : int = 5

It even turns out that if we specifically write a single-argument form of incby, we can apply it to two arguments using exactly the same syntax:

> let incbyc x = fun y -> x + y;;
val incbyc : int -> int –> int
> incby2 2;;
val it : (int -> int) = <fun:it@11-1>
> incbyc 2 3;;      // Same calling syntax as incby
val it : int = 5    // Same result

At the F# language level, we just can’t tell the difference between incby and incbyc.  They have the same type, and we can apply them in the same way, and in both cases we can apply them to one or two arguments and get the same result.

One way to think of this is that partial application resolves the ambiguity of the a –> b –> c type, by allowing an a –> b –> c to be used interchangeably with an a –> (b –> c).  Another way to think of it is that the a –> b –> c type unambiguously means a –> (b –> c), and that the multiple-argument syntax we used in incby is just a handy way to avoid writing and thinking about the fiddly lambda we see in incbyc.

Which is the right way to think of it?  Mathematically and conceptually, the second way is correct.  Pragmatically, however, it’s often easier to think the first way.  Lots of functions have more than two arguments, and trying to think of these all the time as functions that return functions that return functions that return functions will just make your brain turn to custard.

Let’s see that again in C#

It’s instructive to compare F#’s ‘ambiguity’ – though, as we’ve seen, ‘unification’ would be a better word – with the C# equivalent.  C# represents functions of multiple arguments quite differently from functions which return functions.

Func<int, int, int> incby = (x, y) => x + y;
Func<int, Func<int, int> incbyc = x => (y => x + y);

In C#, the two versions have completely different types.  Similarly, they are applied in different ways:

int sum = incby(2, 3);
int sumc = incbyc(2)(3);
// shorthand for
// Func<int, int> temp = incbyc(2);
// int sumc = temp(3)

F#’s trick is to always pretend that you wrote the second version, but provide a syntax for doing so that looks like the first version.

Enter the mathematicians

The trick of always pretending that the programmer wrote the second version is called currying.  It’s an important technique to understand if you’re interested in the conceptual underpinnings of functional programming, but I’m not going to go into it any further here.  Suffice it to say that it’s basically no more than the trick of interpreting (x, y) => something as being equivalent to x => (y => something) – and similarly of course for further arguments.  In short, exactly what we’ve already seen F# doing automatically and what we were able to do explicitly in C#.

Does F# really do this?

So does F# really curry all your multi-argument functions to single-argument functions full of chains of lambdas?  No, it doesn’t.  The easiest way to see this is to call a multi-argument F# function from C#: you’ll see that you have to use the C# multiple argument syntax, not the C# repeated application syntax.

// In FSharpTest module
let incby x y = x + y

// In C#
var sum = FSharpTest.incby(2, 3);  // Not incby(2)(3)

The way F# really implements partial application at the compiler level is more like what I described in the first part of this series: when the F# compiler sees you using a function in a partial way, it generates a private function which represents the partially-applied form.  You can see how this works by compiling some F# code that performs partial application, then opening the compiled assembly in a C# decompiler such as Reflector.

What does all this mean for me?

If you find the mathematical and conceptual underpinnings a bit intimidating, don’t worry about it too much.  You can pretty much get away with thinking about F# function signatures and application the ‘pragmatic’ way, and in fact you’ll be closer to the implementation reality than people who think about them the ‘mathematical’ way.  The important thing to understand is that there are two ways of reading a function type like a –> b –> c –> d, and that you can read it whichever way is more convenient for the job at hand.  F# doesn’t force you to make a choice the way C# does.

Nevertheless, it’s useful to have an appreciation for the meaning of the intermediate partial forms of a function, even if that’s not how they’re represented in the compiled code.  We’ll see why when we talk about what partial application means for designing F# functions.

June 19, 2011 in Software | Permalink

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d8341c5c9b53ef0154331a1e55970c

Listed below are links to weblogs that reference Partial function application in F#, part 4: underlying concepts:

Comments

The following line of code,
Func incbyc = x => (y => x + y);
might be better written as
Func> incbyc = x => (y => x + y);

In other words, there can be two '>' symbols to close the generic delegate definition.

Posted by: Babak at Aug 30, 2012 5:57:53 AM

Well, what I wrote in the comments section, and that which was posted were not the same.

Let's try it again:

Consider adding a second '>' symbol to the second code example in the, "Let’s see that again in C#" section.

Posted by: Babak at Aug 30, 2012 6:01:35 AM