Welcome to the fifth part of the Learn Functional Programming in SML series!

The previous post demonstrated some powerful abstractions that can be built by passing functions as arguments to other functions. The expressive power of the language is further increased by creating functions whose returned values are themselves functions.

The first two sections of this post will explain the basics of writing function returning functions. After that we will look at two important function building techniques - composition and partial application.

Function Returning Functions

Consider the makeAdder function given below:

fun makeAdder x =
    fn (y) => x + y

This function takes an integer x and returns a function which, when called adds x to its argument.

Now we can make as many “adders” as we want:

- val add5 = makeAdder 5;
(* val add5 = fn : int -> int *)

- val add2 = makeAdder 2;
(* val add2 = fn : int -> int *)

- add5 10;
(* val it = 15 : int *)
- add2 10;
(* val it = 12 : int *)

The functions add5 and add2 are new functions dynamically created by makeAdder. Both of them have their own copies of x. In other words, they are objects with their own local state.

How does SML create functions with local state? To answer this question, we need to understand the concepts of free variables and lexical scope.

Free variables and Lexical scope

Let’s look at the body of makeAdder once again:

fn (y) => x + y

You can see two variables in this expression - the bound variable y and the free variable x.

A symbol is bound in an expression if it has been established as a variable, either by appearing as a parameter, or by variable-binding expressions like val or let. Symbols which are not bound are said to be free.

What should be the value of a free variable? To find this out, we need to consider the scope rules used by the language.

In a dynamically scoped language, the value of a free variable is looked up in the context where the expression is evaluated during runtime. If the adding function was bound to a symbol f, if could be evaluated as follows in a dynamically scoped language:

- let val x = 5 in (f 10) end;
(* 15 *)

In a lexically scoped language, instead of the runtime context, the value for a free variable is looked up in the context where the expression is defined. SML is a lexically scoped language. So it captured the binding for x from the parameter of the makeAdder function.

As the function returned by makeAdder can be called from a place where x is not visible, SML must save copies of the local bindings and package them with the returned function. The data structure that keeps track of variable bindings is known as the environment. The combination of a function and the environment that captures the variables bindings in its defining context is known as a closure.

In a language like SML, all functions have a reference to its defining environment. So the terms functions and closures can be used interchangeably.

When a closure is called, its environment is extended with the arguments in the call. Thus the environment becomes the “local state” that is preserved across multiple applications of the closure.

To put things more graphically, this is the closure returned by the call makeAdder 5:

[[x: 5], fn (y) x + y]

This is how the environment in the closure changes, for the calls add5 10 and add5 2:

[[x: 5, y: 10] fn (y) x + y]
[[x: 5, y: 2] fn (y) x + y]

The body of the function x + y evaluated in these two closures will yield the results 15 and 7 respectively.

Complement

A practical application of functions as return values is in creating transformers. A transformer is a function that take another function f as argument and return a new function that in some way transforms the result of f.

A simple but useful transformer is the complement function which takes a predicate p and returns a function that will always return the opposite value of calling p.

fun complement (p) =
  fn (x) => not(p x)

The following program demonstrates the usage of complement:

fun isEven(x) = (x mod 2) = 0
val isOdd = complement isEven

isOdd 5 (* true *)
isEven 5 (* false *)
isEven 4 (* true *)
isOdd 4 (* false *)

This program shows that despite its simplicity, complement is an important building-block. It can enable a library writer to eliminate half of his predicates, because library users can define the other half simply as complements!

Composition

Functional composition allows us to combine multiple functions into a new function. The composition of the functions f and g is c(x) = g(f(x)).

We can define a higher-order function that takes two functions f and g and produce a function c that is the composition of f and g:

fun comp (f, g) =
    fn (x) => g(f(x))
(* val comp = fn : ('a -> 'b) * ('b -> 'c) -> 'a -> 'c *)

A description of the type of comp follows:

  1. The argument is a tuple of two functions - ('a -> 'b) * ('b -> 'c)
  2. The first function takes an argument of type 'a and returns a value of type 'b.
  3. The second function takes a value of type 'b and returns a value of type 'c.
  4. As a consequence of (1) and (2), comp returns a function that takes a value of type 'a and returns a value of type 'c.

Basically, the function returned by comp will send a value of type 'a through the composed calls of f and g to produce a value of type 'c. As we noted in an earlier post, type variables like 'a, 'b and 'c can stand for any type as long as calls to comp satisfy the constraints established by the type signature above.

The following program uses the comp operator to compose the add5 and add2 functions into an add7 function:

val add5 = makeAdder 5
val add2 = makeAdder 2
val add7 = comp(add5, add2)

add7 10
(* val it = 17 : int *)

Composition is so important in functional programming that SML provides the the infix o (lower-case ‘O’) operator to make it easy to compose functions:

val add14 = add5 o add2 o add7

add14 10
(* val it = 24 : int *)

Partials

All the functions we have written so far have a single parameter, sometimes expressed as a tuple written with parenthesis and commas. The tuple data structure is good enough to write functions that look and behave like multi-parameter functions in C or Python.

SML also allows to write functions in a different form where the function name is followed by two or more parameters, without parenthesis or commas. Let us now try to understand the difference between this kind of functions with functions with a tuple parameter. Consider the following two definitions of the exponent function:

fun exponent1 (x, y) =
  if y = 0 then 1.0
  else x * exponent1 (x, y-1)
(* val exponent1 = fn : real * int -> real *)

fun exponent2 x y =
  if y = 0 then 1.0
  else x * exponent2 x (y-1);
(* val exponent2 = fn : real -> int -> real *)

Both functions capture the same computation:

- exponent1 (2.0, 3);
(* val it = 8.0 : real *)

- exponent2 2.0 3;
(* val it = 8.0 : real *)

But their types are different. The function exponent1 has the type fn : real * int -> real, meaning it takes a tuple of a real and int as argument and returns a real.

The second function has the type fn : real -> int -> real. This means exponent2 takes a real as argument and returns a function that takes an int which in-turn produces a real. As a consequence, exponent2 can be partially instantiated - by calling it with only the first argument. This will return a function that can be called later with an int argument so as to finish the computation.

This partial application technique is demonstrated by the following program:

- val f = exponent2 2.0;
(* val f = fn : int -> real *)

- f 3;
(* val it = 8.0 : real *)
- f 10;
(* val it = 1024.0 : real *)

Partial functions like exponent2 allows us to create new functions by applying the function to some, but not all, of its parameters. Partial functions are also known as curried functions, named after the mathematician Haskell Curry, who helped develop this technique.

Conclusion

This post demonstrated some techniques for writing functions that create new functions. At the core of these techniques is the concept of a closure, a function that keeps track of local state.

With this post we have covered all the basic idioms of programming with first-class functions. Now we need to learn to use these techniques for solving large, real-world problems.

But before we can start tackling large problems, we need some more tools to structure and manipulate data more complex than numbers, strings, and tuples. The next few posts will introduce you to these tools.


Note that name and e-mail are required for posting comments