Basic Vocabulary and Concepts

It is a good idea to have a solid understanding of the terms imperative and functional before proceeding further with how to think like a functional programmer. But before we do that, we’re going to dive right into two of the terms in functional programming most frequently misunderstood, currying and partial application. A solid grasp of these terms is critical to understanding more advanced concepts developed later in the book. Fasten your seatbelts and get ready for that first 500-foot drop on the functional programming rollercoaster.

Currying vs. partial function application

If you’ve read anything about functional programming, you will have undoubtedly come across the term currying. In the 1960s, Christopher Strachey coined the term currying[14] for what became an important technique in functional programming language implementation:

“In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments (or a tuple of arguments) in such a way that it can be called as a chain of functions, each with a single argument (partial application).”[15]

By contrast, partial application is a process of binding values to parameters:

“In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.”[16] (“Arity” means the number of arguments that a function accepts.)

Currying and partial function application are often conflated.[17] Some of the confusion over currying has to do with use of the term, which is sometimes used to refer to things the programmer does and other times used to refer to things the language implementation does. As J. Storrs Hall wrote in 2007: “I suspect the confusion arises because originally currying was a technique to model multiple-argument functions in a single-argument framework and was a meta-operation. In ML-like languages, the functions are typically already curried, so the only operation you see being done is partial application.”[18] In this quotation, currying refers to something the language implementation does.

On the other hand, F# architect Don Syme et al. say “Currying is the name used when functions take arguments in the iterated form—that is, when the functions can be partially applied” (Expert F# 2.0, p. 559). Multi-argument functions represented as such in the programmer’s code are curried by default in the language implementation, and can be partially applied. By contrast, a multi-argument function could also be represented as a function of a tuple, in which case the tuple will be treated by the language implementation as a single argument, which makes the function a single-argument function. This means that the function cannot be partially applied, because there is no other argument. The choice of representation is up to the programmer, and Syme et al. refer to the programmer’s choice of the representation that is curried by default in the language implementation as currying, in contrast to the earlier quotation which refers to what the language implementation does when the programmer makes that choice. But to say that curried functions can be partially applied is not to identify currying with partial application—it is only to say that the possibility of partial application depends on the language implementation’s support for currying.

1. Since partial application depends on currying, the two often occur together, but they are different because with partial application, you can “bind” more than one parameter to a value, and to evaluate the resulting function all you need are the remaining parameters. There are three things I just stated that define the difference between partial application and currying. Partial application is a process of binding values to parameters that results in a function with fewer parameters. By contrast, currying is a process that replaces a single multi-parameter function with a nested set or chain of single-parameter functions.
2. Partial application can be performed by binding more than one parameter at a time. By contrast, currying always works with one parameter at a time.
3. To fully evaluate a partially applied function, it is only necessary to bind the parameters that have not already been bound. By the definition of partial application, one or more parameters must already have been bound. By contrast, with a curried function, full evaluation requires binding of all parameters, and zero or more parameters may already have been bound.

Partial application

The following example demonstrates partial application (FSI console):

The function Add2More is a function resulting from the partial application of Add5 1 2 3. Add2More can be evaluated as I did in the example by binding the remaining two parameters. Partial application works because Add5 is a curried function. This illustrates the dependency of partial application on currying (noted by Syme et al. in the passage quoted previously). Incidentally, C#’s “partial methods” have nothing to do with partial function application.

Currying

Currying is handled by the F# language implementation and therefore essentially invisible to the programmer, but you can recognize where it will occur. Currying occurs when you call a multi-parameter function in F# without having to do anything special. The following example is a definition of a multi-parameter function, followed by a call to it:

When used at the call site, Add5 1 2 3 4 5 is calling the curried function Add5 a b c d e. F# calls do not use parentheses around the arguments or commas between them. (If the function were defined instead by let Add5 (a, b, c, d, e) = a + b + c + d + e, it would still yield the same result, but the function would have a different type. This would be taken by the language implementation as defining a single-parameter function taking as input a single tuple with five elements, where the parentheses tell the language implementation to evaluate what is inside as a single possibly complex value, and the commas distinguish independent components of that value.)

In the previous example, the language implementation recognizes that Add5 1 2 3 4 5 matches the signature of the previously defined function Add5 a b c d e, and therefore evaluates Add5 1 2 3 4 5 as a function call.

Multi-parameter functions are automatically curried by the language implementation. To see the currying, we have to go beneath the covers.

Let’s use dotPeek[19] to decompile this simple F# program:

Note how the function Add5 is cast as curried functions (as in, each function has one parameter, ending with the final function where the second parameter is a literal):

And there you have it, Add5 a b c d e has been curried to the type FSharpFunc<’T, ‘U’>[20] such that it can be used in the form value, function.

What is important to understand here is that F# syntax is defined so that any function that specifies its parameters with white space is automatically curried, and merely by using this syntax you are using the currying built into the language implementation.

Another example: Since Add x y will be evaluated as a curried function (its parameters are separated by white space), we can use partial application directly or by pipelining, which more explicitly creates partial function applications:

Lessons

• The F# language implementation creates a curried function whenever you represent multiple parameters individually rather than as a tuple or other complex argument.
• You are creating a partial function application when you bind values for only the first n parameters of a multi-parameter function.

What is imperative programming?

Now that we have demystified one of the most commonly misunderstood terms in functional programming, let’s take a big step back and survey the landscape of imperative and functional programming.

“In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state…imperative programs define sequences of commands for the computer to perform.”[21] In an object-oriented language context, I will specialize this definition slightly—“imperative programming is a programming paradigm that describes computation in terms of statements that change the object state.”

This is a fundamental feature of imperative programming. For example, this C# code alters the state of Point p:

This code, because of its simplicity, is an excellent example of how often we use mutable objects that exhibit side effects.

What are classes?

One way to think about a class is that it is nothing more than a container for fields, some of which are exposed to the outside world, and methods which return results, affect the state of the class’ fields, or both. This is the definition of encapsulation. When we write object-oriented code, every class we write:

• Describes everything necessary to maintain the state of the fields in the class.
• Describes how state is altered using methods such as property getters and setters.
• Describes computations (methods) that utilize the current state, and those computations may have side effects resulting in state change.

This may seem like an overly narrow description because it ignores other OO features like inheritance and polymorphism, and the concept that a class describes a type, but fundamentally, the description is true for every imperative class, whether it’s a super-class or a derived class.

The C# example at the end of the previous section illustrates each of these points:

• The class Point consists of two fields, X and Y.
• The statements p.X = 1 and p.Y = 2 are property setter functions that change the state of p and illustrate that the object is mutable.
• The statement p.ToString() can be considered a computation on the current state, converting X and Y to a string representation.
• The statement p.Offset(11, 12) is a computation that alters the current state, illustrating the side effect of the computation, in that it mutates the object’s state.

This illustrates two features of imperative programming: mutability and side effects.

• Mutability is the ability to change an object’s state directly and usually explicitly.
• In a side effect, the object is mutated (its state changes) indirectly and usually implicitly. Side effects however are not limited to changing the object’s state—side effects can also change the state of another object, a data store, and so forth.

A good example of a useful mutable object with side effects is a file reader that needs to keep track of the position in the data stream and set an end-of-file flag when the end of the file is reached. This creates problems for pure functional programming languages and is handled in interesting ways, which we’ll look at later.

In addition to the previous narrow description, object-oriented programming, and specifically classes, offer a couple additional features:

• Unifies behavior patterns with polymorphism (including default values).
• Associates with other classes to create a rich composition of objects utilizing the object-oriented principles of inheritance and membership.

These illustrate the strengths of imperative programming, and in “impure” functional programming languages such as F#, one can continue to utilize these features, but carefully.

Lessons

• Imperative code has mutability “coded” into it very naturally.
• Imperative code very frequently has side effects.
• Bonus lesson: Imperative methods are not curried—the compiler does not support implicit partial application; you have to do this yourself.

What is functional programming?

“In computer science, functional programming is a programming paradigm, a style of building the structure and elements of computer programs that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming emphasizes functions that produce results that depend only on their inputs and not on the program state—i.e. pure mathematical functions.”[22]

In functional programming we are defining terms, not giving orders. Terms are defined by equations that may, for instance, explain how to construct a complex structure from simpler structures. The work of programming is essentially setting up systems of equations so they can be solved automatically by appropriate substitution during execution.

Immutability

Functional programming, at its core, emphasizes immutability. Mathematical definitions, after all, do not change. Without mutable objects, there are no side effects. This is achieved by creating a new object every time there is a “state change”—the old object remains unaffected and a new object is created instead to reflect the result of the computation.

In F#, the preferred implementation of the previous C# example would be immutable. The = sign in a functional language indicates an equation, not an assignment.

In this example, p2 is not the same instance as p nor is it equal to p. The reason is because the function Offset does not change (mutate) p; it creates a new instance of a point.

Let’s encapsulate the function Offset in an F# class type, again preserving immutability:

(From here on, we’ll omit the terminator ;; in many examples. Just add it at the end as in the previous example to get the examples to evaluate in the console.)

We can see that the Offset function explicitly constructs a new Point object, thus p <> p2.

The only way to update the X and Y members is to explicitly declare them to be mutable using:

• The member val keywords to automatically create a backing store.
• The with get, set keywords to create the property getter and setter.

In this example, we have created the equivalent of the C# Point class, and the result is that p2 equals p and in fact, p2 is the same instance of p because the Offset function returns itself.

This is not functional programming, so if you’re going to program like this, stick with C# or some other imperative programming language. It does however illustrate why F# is called an “impure” functional programming language.

First-class and higher-order functions

“In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. Specifically, this means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.”[23]

Higher-order functions[24] are functions that can either take other functions as arguments or return them as results. Higher-order functions are a key feature of a functional programming language. “A defining characteristic of functional programming languages is the elevation of functions to first-class status. You should be able to do with a function whatever you can do with values of the other built-in types, and be able to do so with a comparable degree of effort.”[25] What makes first-class functions “first class” is that the language implementation allows them to be treated as a kind of value, so you can do with them all the things you can do with other values.

In imperative languages, we usually don’t pass functions as parameters or return functions. Traditionally, where functions were supported, imperative language implementations did not allow them to be treated as values. Only recently, for example with C#’s Action and Func classes and lambda support, are there explicit language capabilities (beyond delegates) for passing functions as parameters and returning functions. These features are in fact borrowed from functional languages. Older imperative languages such as Pascal, Fortran, BASIC, and so forth have no facilities for passing functions as parameters or returning functions. For example:

Functions in structures

With C# and the Func<T, U> class, we can create a list of functions having the same signature:

(For the C# audience, I am intentionally refraining from using constructs like var funcList.)

In F#, we can implement this more naturally:

Functions as parameters

We can pass functions to other functions. Again, in C#, this might be written like this:

In F#, this can be written as:

Note the explicit use of the fun keyword to define lambda expressions.

Functions returning functions

In C#, we can return functions:

And in F#:

Does this mean C# is a functional programming language?

The previous example illustrates how C# supports functional programming behaviors, so the answer is “sort of, yes.” We will see later that there are distinctions between imperative languages that support function programming constructs, and functional languages that support imperative programming constructs.

C# falls in the first category, and F# falls in the second category. A “pure” functional programming language will fall outside of both categories.

Where C# and F# start to diverge

We can do some interesting things with function binding and functions as parameters, like writing “generic” operators. In C#, this would look like:

Here the compiler infers the type from the values, which must all be of the same type. We can use it with different types because the lambda expression is evaluated when needed, and hence the type is at that point known. We can do something similar in F# using the inline keyword:

Here adder is a function that takes two parameters, a and b of type T, and returns a type T.

There is an interesting difference: in C# we cannot create a generic delegate that is assigned the lambda expression without specifying the type when the delegate is assigned. For example, this does not work:

If we specify del<int>, then the previous code works. Note that in F#, we can definitely assign the function to a name and use that function later with type inference.

We can go even further, providing the operation to perform at the call site:

This is something you cannot do in an imperative language—not even in C#, without some significant workarounds. Granted, my example is a bit esoteric, but it does well to serve as an example of where a functional language like F# enables you to do things you otherwise could not do at all.

Lessons

• Functional programming avoids mutability (which can be annoying at times).
• Immutable objects cannot be affected by side effects. (Because F# is “impure,” though, an object with all immutable fields could still have methods that cause side effects somewhere else, e.g., for display.)

• At some point, the syntax of C# simply becomes too unwieldy and F# starts to look syntactically more attractive.
• At some point the support for functional programming fails in C#, whereas F#, being a functional programming language, supports “the last mile.”