by vijay | tags: [ learn-fp-in-sml functional-programming functional SML OCaml tutorial ]
Learn Functional Programming in SML - 3
Welcome to the third part of the series!
This post will introduce the basic techniques of programming with functions.
Pure Functions
Functions in a functional language closely resemble functions in mathematics.
Let’s call these pure functions. A pure function, whenever called with the same arguments,
will return the same result. For example, squareRoot 4
will always return 2
, no matter where or when you call it.
To achieve this deterministic behavior, a function must be:
- Independent - no dependencies other than its arguments.
- Stateless - no state is preserved between calls.
The following C program shows a counter example (literally). The function defined here is neither independent nor stateless.
static int count;
int f(int x) {
static int y;
++count;
y += 2;
return x * y;
}
The function f
keeps track of the number of times it was called by updating the global variable count
.
It also maintains an internal state in the local variable y
. This has the effect that two calls to f
with the same argument will result in different results.
printf("%d\n", f(20)); /* 40 */
printf("%d\n", f(20)); /* 80 */
But many real-world problems do require maintaining state across calls. The good news is that there are techniques for programming with state without losing the nice properties of pure functions.
Why pure functions are important
Pure functions can be implemented and tested independently of other parts of the system and of its own history (previous calls). This makes it easy to design programs as compositions of functions.
As each function is dependent solely on its inputs, it can be understood on its own, without having to understand the rest of the program. This facility is lost if we introduce shared mutable state. Then the interaction between the functions become more intimate and the program could be understood only as a whole.
As pure functions compute only values and perform no side-effects, its easier to reason about them using simple algebraic and logical techniques.
The lack of side-effects results in a property known as referential transparency. This means
“equals can be replaced by equals”. For example, if we know that f a = a + 1
, then we can replace all occurrences of
f a
with a + 1
. Referential transparency helps with reasoning about programs. It can also lead to compiler optimizations
that may not be possible in imperative languages.
All these properties make the functional paradigm ideal for programming both in the small and the large.
Basic Techniques
The basic techniques for writing functional programs are recursion and higher-order programming.
A recursive function is one that refers to itself either directly or indirectly. In other words a recursive function is defined in terms of itself.
In higher-order programming functions can have other functions as arguments and as results.
These two techniques underlie all advanced functional abstractions and idioms.
In this post we will meet recursion in all its forms. We start by studying the general pattern for writing recursive functions. Then we introduce two extensions to simple recursion - tree recursion (or nonlinear recursion) and mutual recursion.
We will also learn a technique for transforming recursions to iterations, thereby eliminating wastage of stack space.
Recursion
Let’s start with a very simple recursive function which finds the sum of the first n
positive integers.
fun sum n =
if n = 0 then 0
else n + sum (n - 1)
The sum
function demonstrates the general pattern of all recursive functions.
The first point to keep in mind is that the recursive call should get a value smaller than the current argument.
The sum
function achieves this by decrementing n
by 1
. This causes the function to reach a basis,
where the argument is sufficiently small that the result can be computed directly.
In this example, the basis is reached when n
becomes zero.
The conditions where we call the function recursively is known as inductive steps. As we saw in the preceding paragraph, the inductive steps should eventually reach a basis, making sure that the function return a result, instead of infinitely looping.
Now let us spend some time understanding how recursive calls are evaluated.
We shall do this with an actual invocation of sum
:
sum 5;
(* val it = 15 : int *)
To find the result 15
, the following sequence of calls were made:
sum 5;
5 + (sum 4)
5 + 4 + (sum 3)
5 + 4 + 3 + (sum 2)
5 + 4 + 3 + 2 + (sum 1)
5 + 4 + 3 + 2 + (sum 0)
5 + 4 + 3 + 2 + 0
15
The steps of evaluation reveals that the recursive calls build up a chain of suspended computations. The operations in this chain are actually performed only after the basis case is reached. Until then these operations are held in memory, in the function’s call stack. With deeper recursions, the program will eventually run out of stack space and will raise a runtime error.
Note: For recursive functions defined on integers, you may actually see an integer-overflow
error before you reach the
stack-overflow
error. This largely depends on the SML implementation you are running.
There is a simple technique to make recursive functions to execute in constant stack space. But before we go there, let’s study two extensions to basic recursion.
Tree recursion
The sum
function generates a list of suspended computations. There are also recursive functions that can generate a tree of
such computations.
Consider a function for computing the sequence of Fibonacci numbers. A number in the Fibonacci sequence is the sum of the preceding two.
The rules for generating Fibonacci numbers is captured by the following recursive function:
fun fib n =
if n = 0 then 0
else if n = 1 then 1
else fib (n - 1) + fib (n - 2)
Consider the call fib 5
. To compute fib 5
, the two recursive calls branches for computing fib 4
and fib 3
. Each of these
calls create more “branches”, until the call ends at “leaves” that return 0
and 1
. Basically, the call-paths generated by the
recursion looks like a tree.
Though the definition of fib
is simple and straightforward it is not efficient. It duplicates a lot of work, almost half of it.
It uses a number of steps that grows exponentially with the input. It also shares the growing stack problem with the sum
function.
Don’t be discouraged with what I just said! We will figure out ways to solve all these problems.
Though tree recursion may not be efficient for numeric computations, it is useful for processing other forms of complex data.
Mutual recursion
Sometimes we need to write two or more functions that are mutually recursive, where each calls at least one other in the group. Many languages place restrictions on defining such functions, requiring forward declarations and so on. SML offers a simple mechanism for declaring mutually recursive functions.
An example of mutual recursion is shown below. These functions checks whether a non-negative integer is even or odd.
fun isEven n =
if n = 0 then true
else isOdd (n - 1)
and isOdd n =
if n = 0 then false
else isEven (n - 1)
The implementation of these functions are based on the fact that isEven 4
is equivalent to isOdd 3
,
which in turn is equivalent to isEven 2
, and so on down to 0
. This is a rather
inefficient way to figure out if a number is odd or even, but it demonstrates mutual recursion
very well.
The mutually recursive functions are connected together by the and
keyword. The keyword fun
need to appear only once, at the very beginning of the definitions.
More practical applications of mutual recursion can be found in the implementations of recursive descent parsers and finite-state machines.
Iteration
As we saw earlier, recursive functions create chains or trees of deferred computations. This means, for large inputs, they may run out of stack space.
It should be possible to fix this problem if recursive functions are defined in a way no deferred computations need to be built-up. Instead we can keep track of the result computed so far in the form of an additional parameter to the function. This extra value is often called an aggregate.
Let us try to apply this idea to the sum
function defined earlier.
To avoid confusion, we will call the new definition sum2
:
fun sum2 (n, s) =
if n = 0 then s
else sum2 (n-1, n+s)
The sum2
function will not create a chain of deferred computations, as the result is accumulated in the second
component of the argument (s
). This has the consequence that, we have to always call sum2
with 0
as the initial value of s
.
sum2 (5, 0)
(* val it = 15 : int *)
These are the recursive calls that just happened:
sum2 (5, 0)
sum2 (4, 5)
sum2 (3, 9)
sum2 (2, 12)
sum2 (1, 14)
sum2 (0, 15)
15
As we can see, the recursive calls to sum2
does not cause the stack to grow. SML guarantees that functions
like sum2
will be executed in constant stack space. A language with this property is known as tail recursive.
The name derives from the fact that this optimization can be only applied to recursive calls at a tail
position in the function’s body. In other words, the recursive call must be the last action performed by the function.
Functions with only tail-recursive calls are described as being iterative. The state of an iteration can be inferred from the arguments of the active call.
We have seen how to transform a linear recursion into iteration by adding an extra state-parameter to the function. The same technique can be applied to functions that generate a tree recursive process. This is exemplified by the following iterative definition of the Fibonacci function:
fun fib2 (a, b, n) =
if n = 0 then b
else fib2 (a + b, a, n - 1)
The recursive call to fib2
has been moved to the tail position by adding the pair of integers a
and b
to the
parameter list. While calling the function, these should be initialized to 1
and 0
respectively.
fib2 (1, 0, 10)
(* val it = 55 : int *)
The following transformations are applied repeatedly:
a <- a + b
b <- a
After applying these transformations n
times, a
and b
will be equal, respectively, to fib(n + 1)
and fib(n)
.
Local definitions
There is one problem with the iterative functions defined in the preceding section - they leak an implementation detail in the form of the aggregate parameter. This also makes the functions difficult to use and open up opportunities for bugs.
For instance, a user of the sum2
function must always remember to pass 0
as the second component of the parameter. If by mistake,
another value is passed, sum2
will return a wrong result.
The sum2
function fails to provide the right level of abstraction. It should hide the details of how
the result is calculated. The user should be able to reason about the function in terms of the parameter n
alone.
We can achieve this higher level of abstraction with the help of local definitions. Any variable or function that is part of the
implementation detail should be declared locally in the function. This can be achieved by the let .. in .. end
expression.
One or more val
or fun
declarations can appear between let
and in
. The expression that follows in
can refer to these variables.
This expression is known as the body
of the let
. The variables introduced by let .. in
will not be visible outside the body.
fun sum n =
let
fun sumIter (n, s) =
if n = 0 then s
else sumIter (n-1, n+s)
in
sumIter (n, 0)
end
The definition and call to sumIter
is an internal implementation detail that makes sure that sum
will never lead to a stack overflow error. The user of sum
is oblivious to the existence of sumIter
.
sum 10000
(* val it = 50005000 : int *)
Exercise 3.1 Write an iterative version of fib
in terms of a local fibIter
function.
Conclusion
In this post we learned about pure functions and their advantages. We also explored the general patterns for writing recursive and iterative functions.
The next couple of posts will continue to explore functions.
We will look at the second major functional technique, i.e higher-order programming. We will learn about interesting abstractions that can be built by the composition and partial application of functions.
After these, we will study functions that manipulate complex data like lists and records.
See you soon!
Note that name and e-mail are required for posting comments