by vijay | tags: [ learn-fp-in-sml functional-programming functional SML OCaml tutorial ]
Functional Programming in SML - Higher order Functions
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 functions 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:
- The argument is a tuple of two functions -
('a -> 'b) * ('b -> 'c)
- The first function takes an argument of type
'a
and returns a value of type'b
. - The second function takes a value of type
'b
and returns a value of type'c
. - 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