5. Functional Programming

You are probably familiar with at least one imperative language. Languages like C, C++, Java, Python, and Ruby are considered imperative languages because the fundamental construct is the assignment statement. In each of these languages we declare variables and assign them values, updating those variables as a program’s execution progresses.

Imperative languages are heavily influenced by the von Neumann architecture of computers that includes a store and an program counter; the computation model has control structures that iterate over instructions that make incremental modifications of memory. Assignment of values to variables, for loops, and while loops are all part of imperative languages. The principal operation is the assignment of values to variables. Programs are statement oriented, and they carry out algorithms with statement level sequential control. In other words, computing is done by side-effects.

Sometimes problems with imperative programs stem from these side-effects. It is difficult to reason about a program that relies on side-effects. If we wish to reuse the code of an imperative program then we must be sure that the same conditions are true before the reused code executes since imperative code relies on a certain machine state. As programmers we sometimes forget which preconditions are required and what postconditions result from executing a segment of code. That can lead to bugs in our programs.

Functional languages are based on the mathematical concept of a function and do not reflect the underlying von Neumann architecture. These languages are concerned with data objects and values instead of variables. The principal operation is function application.

Functions are treated as first-class objects that may be stored in data structures, passed as parameters, and returned as function results. Primitive functions are generally supplied with the language implementation. Functional languages allow new functions to be defined by the programmer. Functional program execution consists of the evaluation of an expression, and sequential control is replaced by recursion.

There is no assignment statement. Values are communicated primarily through the use of parameters and return values. Without variables, loop statements don’t have a purpose and so they also don’t exist in pure functional languages.

Pure functional languages have no side-effects other than possibly reading some input from the user. Scheme is a pure functional language. In general, functional languages avoid or at least isolate code with side-effects. Even input and output operations in functional languages do not update the state of variables within a program.

What is amazing is that it has been proven that exactly the same things can be computed with functional languages as can be computed with imperative languages. This is known because a Turing machine, the theoretical basis for imperative programming and the design of the computer, have been proven equivalent in power to the Lambda Calculus, the basis for all functional programming languages.

You might be surprised by the number and types of languages that support functional programming. Of course, Standard ML was designed as a functional language from the ground up, but languages like C++, Java, and Python also support functional programming. While C++, Java, and Python are also object-oriented imperative languages, they all support functional programming as well. Functional programming does not depend so much on the language, but how you use the language. The rest of this chapter will introduce the functional style of programming. It all started with the lambda calculus, which is briefly considered next.

All functional programming languages are derived either directly or indirectly from the work of Alonzo Church and Stephen Kleene. The lambda calculus was defined by Church and Kleene in the 1930s, before computers existed. At the time, mathematicians were interested in formally expressing computation in some written form other than English or other informal language. The lambda calculus was designed as a way of expressing those things that can be computed. It is a very small, functional programming language. In the lambda calculus, a function is a mapping from the elements of a domain to the elements of a codomain given by a rule. Consider the function . What is the value of the identifier in the definition ? Can this function be defined without giving it a name?

defines the function that maps each in the domain to . We can say that this definition or lambda abstraction, , is the value bound to the identifier . We say that is the body of the lambda abstraction. Every lambda abstraction in lambda notation is a function of one identifier. However, lambda expressions may contain more than one identifier.

The expression can be expressed as a lambda abstraction in one of two ways:

In the first lambda abstraction the is the first parameter to be supplied to the expression. In the second lambda abstraction the is the parameter to get a value first. In either case, the abstraction is often abbreviated by throwing out the extra . In abbreviated form the two abstractions would become and .

Standard ML (or just SML) is a functional language based on Lisp which in turn is based on the lambda calculus. Important ML features are listed below.

There are several implementations of Standard ML. Standard ML of New Jersey and Moscow ML are the most complete and certainly the most popular. There is also a SML.NET implementation that targets the Microsoft .NET run-time library and can be integrated with other .NET languages. There is an MLj implementation that targets the Java Virtual Machine. Poly/ML is another implementation that includes support for Windows programming. While many implementations exist, they all support the same definition of SML. If you write a Standard ML program that runs in one environment, it’ll run on any other implementation as long as you are not using platform specific functions.

SML has been successfully used on a variety of large programming projects. It was used to implement the entire TCP protocol on the FOX Project at Carnegie Mellon. It has been used to implement server side scripting on web servers. It was originally designed as a language to write theorem provers and has been used extensively in this area. It has been used in hardware design and verification. It has also been used in programming languages research.

The rest of this chapter introduces SML. By the end of the chapter you should understand and be able to use many of the important features of the language. This text is based on the Standard ML of New Jersey implementation. You can download SML of New Jersey from smlnj.​org. SML of New Jersey is available for most platforms so you should be able to find an implementation for your needs.

Once you’ve installed SML you can open a terminal window and start the interpreter. Typing sml at the command-line will start the interactive mode of the interpreter. Typing ctl-d will terminate the interpreter. You can type expressions and programs directly in at the interpreter’s prompt or you can type them in a file and use that file within SML. To do this you type the word use as follows: SML will take whatever you have typed in the file and evaluate it just as if you had typed it directly into the interpreter.

The examples and practice problems in this chapter introduce SML. The following sections introduce important aspects of SML and ready the reader to write more complicated programs in the next chapter.

Functional programming focuses on the evaluation of expressions. In SML you can evaluate expressions right in the intepreter. When evaluating an expression you will notice that type information is displayed along with the result of the expression evaluation. The dialog below contains some interactive expression evaluations in the SML interpreter.

In SML the identifier it is bound to the result of the last successfully evaluated expression. This is convenient if you want to use the result in a subsequent expression. The last expression result can be referred to as it in the subsequent, interactively entered expression.

The interaction presented in Fig. 5.3 contains a negative one written as ^~ 1 in SML. While a little unconventional, ^~ is the unary negation operator in SML, distinguishing it from the binary subtraction operator.

SML has a very rigorous type system. In fact, the type system for SML has been proved sound. That means that any correctly typed program is guaranteed to be free of type errors. SML is statically typed like C++ and Java. That means that all type errors are detected at compile-time and not at run-time. Robin Milner proved this for Standard ML. ML is the only widely distributed language whose type system has been formally defined and proven type correct.

While being formally defined and rigorous, the type system of ML is remarkably flexible. It is polymorphic. We’ll see what this means for us soon. Many of the types in ML are also implicitly expressed. In C++ and Java the type of every variable and function must be declared. You may notice in Fig. 5.3 that the programmer never entered any types for the expressions given there. In most cases Standard ML’s type system frees the programmer from having to specify types in a program since they are mostly determined automatically.

You may have also noticed that there is a type error in Fig. 5.3. ML is polymorphic but it is also strongly typed. Since 5 is an integer in SML and 3.0 is a real, the two cannot be multiplied together. If you should have the need to multiply an integer and a real it can be done, but you must explicitly convert one of the types. The intepreter interaction below show some code to multiply an integer and a real, producing a real number. The integer 5 is converted to 5.0 by calling a function called fromInt in the structure called Real. A Structure in SML is a grouping of functions and types. A structure is like a module in Python or an include in C++. There are several structures that make up the Basis Library for Standard ML. The basis library is available in SML when the interpreter is started. The structures in the basis library include Bool, Int, Real, Char, String, and List. Appendix B or the website http://​standardml.​org/​Basis contain descriptions of many of these structures.

A function in SML takes one or more arguments and returns a value. The signature of a function is the type of the function. In other words, a function’s type is its signature. The signature of the function fromInt in the Real structure is

This signature indicates that fromInt takes an int as an argument and returns a real. From the name of the function, and the fact that it is part of the Real structure, we can ascertain that it creates a real number from an int.

The type on the left side of the arrow (i.e. the ->) is the type of the arguments given to the function. The type on the right side of the arrow is the type of the value returned by the function. The fromInt function takes an int as an argument and returns a real.

Recursion is the way to get things done in a functional language. Recursion happens when a function calls itself. Because of the principle of referential transparency a function must never call itself with the same arguments. If it were to do that, then the function would do exactly what it did the last time, call itself with the same arguments, which would then.... Well, you get the picture!

To spare ourselves from this problem we insist on two things happening. First, every recursive function must have a base case. A base case is a simple subproblem that we are trying to solve that doesn’t require recursion. We must write some code that checks for the simple problem and simply returns the answer in that case.

The second rule of recursive functions requires them to call themselves on some simpler or smaller subproblem. In some way each recursive call should take a step toward the base case of the problem. If each recursive call advances toward the base case then by the mathematical principle of induction we can conclude the function will work for all values on which the function is defined! The trick is not to think about this too hard. The recursive case is often referred to as the inductive case.

Writing functional programs is much more declarative than the prescriptive programming of assembly and imperative programming in languages like C++, Python, and Java. What this statement is really saying is that when writing recursive functions we think much less about how it works and more about the structure of the data. This leads to a few simple steps that can be applied to writing any recursive function. Memorize these steps and practice them and you can write any recursive function.

One important expression in SML is the if-then-else expression. This is not an if-then-else statement. Instead, it’s an if-then-else expression. An if-then-else expression gives one of two values and those values must be type compatible. The easiest way to understand if-then-else expressions is to see one in practice.

The Babylonian method of computing square root of a number, x, is to start with an arbitrary number as a guess. If we are done. If not, then let the next guess be . To write this as a recursive function we must find a base case and be certain that our successive guesses will approach the base case. Since the Babylonian method of finding a square root is a well-known algorithm, we can be assured it will converge on the square root. The base case has to be written so that when we get close enough, we will be done. Let’s let the close enough factor be one millionth of the original number.

The SML code in Fig. 5.4 implements this function. Looking at the code there are two things to observe. The base case comes first. If the guess is within one millionth of the right value then the function returns the guess as the square root. The other observation is the recursive call brings us closer to the solution.

Strings in SML are not simply sequences of characters as they are in some languages. A string in SML is its own primitive type. There are functions for converting between strings and characters of course. You can consult Appendix B for a list of those functions. A string literal is text surrounded by double quotes. The backslash character (i.e. \) is an escape character in strings. This means to include a double quote in a string you can write ” as part of the string. A \n is the newline character in a string and \t is the tab character as they are in many languages.

Perhaps the most powerful data structure in SML is the list. A list is polymorphic meaning that there are many list types in SML. However, the list functions all work on any type of list. Since it is impossible to determine all the types in SML (because programmers may define their own types), a list’s type is parameterized by a type variable. A list’s type is written as ‘a list. When the type of the list is known, the type variable ‘a is replaced by the type it represents. So, a list of integers has type int list. You may have figured this out already, but lists in SML must be homogeneous. This means all the elements of a list must have the same type. This is not like some languages, but there is a good reason for this restriction. Requiring lists to be homogeneous makes static checking of the types in SML possible and the type checker sound and complete.

A list is constructed in one of several ways. First, an empty list is represented as nil or by the empty list (i.e. []). A list may be represented as a literal by putting a left bracket and a right bracket around the list contents, as in [1,4,9,16]. A list may also be constructed using the list constructor which is written  ::, and pronounced cons. In the functional language Lisp the same list construction operator is written cons so it is called the cons operator by many functional programmers. The cons operator takes an element on the left side of it and a list on the right side and constructs a new list of its two arguments. A list may be constructed by concatenating two lists together. List concatenation is represented with the @ symbol. The following are all valid list constructions in SML.

The third example works because the  :: constructor is right-associative. So the right-most constructor is applied first, then the one to its left, and so on. The signatures of the list constructor and some list functions are given in Fig. 5.5.

You can select elements from a list using the hd and tl functions. The hd (pronounced head) of a list is the first element of the list. The tl is the tail or all the rest of the elements of the list. Calling the hd or tl functions on the empty list will result in an error. Using these two functions and recursion it is possible to access each element of a list. The code in Fig. 5.6 illustrates a function called implode that takes a list of characters as an argument and returns a string comprised of those characters. So, implode([#”H”,#”e”,#”l”,#”l”,#”o”]) would yield “Hello”.

When writing a recursive function the trick is to not think too hard about how it works. Think of the base case or cases and the recursive cases separately. So, in Fig. 5.6 the base case is when the list is empty (since a list is the parameter). When the list is empty, the string the function should return should also be empty.

The recursive case is when when the list is not empty. In that case, there is at least one element in the list. If that is true then we can call hd to get the first element and tl to get the rest of the list. The head of the list is a character and must be converted to a string. The rest of the list is converted to a string by calling some function that will convert a list to a string. This function is called implode! We can just assume it will work. That is the nature of recursion. The trick, if there is one, is to trust that recursion will work. Later, we will explore exactly why we can trust recursion.

The code in Fig. 5.7 contains a couple more examples of list functions. The length function counts the number of elements in a list. It must be a list because the tl function is used. The append function appends two lists by taking each element from the first list and consing it onto the result of appending the rest of the first list to the second list.

Frequently, recursive functions rely on several recursive and several base cases. SML includes a nice facility for handling these different cases in a recursive definition by allowing pattern matching of the arguments to a function. Pattern matching works with literal values like 0, the empty string, and the empty list. Generally, you can use pattern matching if you would normally use equality to compare values. Real numbers are not equality types. The real type only approximates real numbers. The code in Fig. 5.4 shows how two real numbers are compared for equality.

You can also use constructors in patterns. So the list constructor  :: works in patterns as well. Functions like the append function (i.e. the infix @) and string concatenation (i.e. ⌃) don’t work in patterns. These functions are not constructors of values and cannot be efficiently or deterministically matched to patterns of arguments.

Append can be written using pattern-matching as shown in Fig. 5.8. The extra parens around the recursive call to append are needed because the  :: constructor has higher precedence than function application.

A tuple type is a cross product of types. A two-tuple is a cross product of two types, a three-tuple is a cross product of three types, and so on. (5,6) is a two-tuple of int * int. The three tuple (5,6,”hi”) is of type int * int * string.

You might have noticed the signature of some of the functions in this chapter. For instance, consider the signature of the append function. Its signature is

In many other languages we think of writing function application as the function followed by a left paren, followed by comma separated arguments, followed by a right paren. In Standard ML (and most functional languages) function application is written as a function name followed by the value to which the function is applied. This is just like function application in the lambda calculus. So, we can think of calling a function with zero or more values, but in reality every function in ML is passed on argument, which may be a tuple. In Standard ML rather than writing

it is more appropriate to write

Let expressions are simply syntax for binding a value to an identifier to later be used in an expression. They are useful when you want to document your code by assigning a meaningful name to a value. They can also be useful when you need the same value more than once in a function definition. Rather than calling a function twice to get the same value, you can call it once and bind the value to an identifier. Then the identifier can be used as many times as the value is needed. This is more efficient than calling a function multiple times with the same arguments.

Consider a function that computes the sum of the first n integers as shown in Fig. 5.9. Let expressions define identifiers that are local to functions. The identifier called sum in Fig. 5.9 is not visible outside the sumupto function definition. We say the scope of sum is the body of the let expression (i.e. the expression given between the in and end keywords). Let expressions allow us to declare identifiers with limited scope.

Limiting scope is an important aspect of any language. Function definitions also limit scope in SML and most languages. The formal parameters of a function definition are not visible beyond the body of the function.

Binding values to identifiers should not be confused with variable assignment. A binding of a value to an identifier is a one time operation. The identifier’s value cannot be updated like a variable. A practice problem will help to illustrate this.

Bindings are not the same as variables. Bindings are made once and only once and cannot be updated. Variables are meant to be updated as code progresses. Bindings are an association between a value and an identifier that is not updated.

SML and many modern languages use static or lexical scope rules. This means you can determine the scope of a variable by looking at the structure of the program without considering its execution. The word lexical refers to the written word and lexical or static scope refers to determining scope by looking at how the code is written and not the execution of the code. Originally, LISP used dynamic scope rules. To determine dynamic scope you must look at the bindings that were active when the code being executed was called. The difference between dynamic and static scope can be seen when functions may be nested in a language and may also be passed as parameters or returned as function results.

The difference between dynamic and static scope can be observed in the program in Fig. 5.10. In this program the function a, when called, declares a local binding of x to 1 and returns the function b. When c, the result of calling a, is called it returns a 1, the value of x in the environment where b was defined, not a 2. This result is what most people expect to happen. It is static or lexical scope. The correct value of x does not depend on the value of x when it was called, but the value where the function b was written.

While static scope is used by many programming languages including Standard ML, Python, Lisp, and Scheme, it is not used by all languages. The Emacs version of Lisp uses dynamic scope and if the equivalent Lisp program for the code in Fig. 5.10 is evaluated in Emacs Lisp it will return a value of 2.

It is actually harder to implement static scope than dynamic scope. In dynamically scoped languages when a function is returned as a value the return value can include a pointer to the code of the function. When the function b from Fig. 5.10 is executed in a dynamically scoped language, it simply looks in the current environment for the value of x. To implement static scope, more than a pointer to the code is needed. A pointer to the current environment is needed which contains the binding of x to the value at the time the function was defined. This is needed so when the function b is evaluated, the right x binding can be found. The combination of a pointer to a function’s code and its environment is called a closure. Closures are used to represent function values in statically scoped languages where functions may be returned as results and nested functions may be defined. Chapters 3 and 4 introduced closures and Fig. 5.10 provides an example in Standard ML showing why they are necesssary for statically scoped languages.

The word datatype is often loosely used in computer science. In ML, a datatype is a special kind of type. A datatype is a tagged structure that can be recursively defined. This type is powerful in that you can define enumerated types with it and you can define recursive data structures like lists and trees.

Datatypes are user-defined types and are generally recursively defined. There are infinitely many datatypes in Standard ML. Defining a datatype is like creating a class in C++ without any methods and only public data. In C/C++ we can create an enumerated type by writing the declaration found in Fig. 5.11. This defines a type called TokenType of eleven values: identifier is 0, keyword is 1, number is 2, etc. You can declare a variable of this type as follows.

However, until C++11 there was nothing preventing you from executing the statement

In this example, even though t is of type TokenType, it could be assigned an integer with compilers prior to C++11. This is because the TokenType type was just another name for the integer type in C++ prior the C++11. Assigning t to 1 didn’t bother C++ in the least. In fact, assigning t to 99 wouldn’t bother C++ either prior to C++11. In Standard ML, and now in C++, we can’t use integers and datatypes (or enums) interchangeably.

Datatypes allow programmers to define their own types. Normally, a datatype includes other information. Datatypes are used to represent structured data of some sort. By adding the keyword of, a datatype value can include a tuple of other types as part of its definition. A datatype can represent any kind of recursive data structure. That includes lists, trees, and other structures that are related to lists and trees. In Fig. 5.12 we have a tree definition with a mix of unary and binary nodes.

Datatypes allow a programmer to write a recursive function that can traverse the data given to it. Functions can use pattern matching to handle each case in a datatype with a pattern match in the function.

In the datatype given in Fig. 5.12 the add’ value can be thought of as a node in an AST that has two children, each of which are ASTs. The datatype is recursive because it is defined in terms of itself. The code in Fig. 5.12 is the entire definition of abstract syntax trees for expressions in a calculator language. Store nodes in the tree store their value in the one memory location of the calculator. Recall nodes recall the memory location of the calculator. The negate’ node represents unary negation of the value we get when evaluating its child. So ~6 is a valid expression if we let the tilde sign represent unary negation as it does in Standard ML.

The abstract syntax tree for ~6S+R is drawn graphically in Fig. 5.13. The value add’(store’(negate’(integer’(6))), recall’) is the SML way of representing the AST shown in Fig. 5.13. A function can be written to evaluate such an abstract syntax tree based on the patterns in a value like this and this is done later in the chapter.

You can use pattern matching on datatypes. For instance, to evaluate an expression tree you can write a recursive function using pattern-matching. Each pattern that is matched in such a function corresponds to processing one node in the tree. Each subtree can be processed by a recursive call to the same function. In Fig. 5.14, the parameter min is the value of the memory before evaluating the given node in the abstract syntax tree. The value mout is the value of memory after evaluating the node in the abstract syntax tree.

This example code in Fig. 5.14 illustrates how to use pattern-matching with datatypes and patterns in a let construct. This is one way to write the evaluate function to evaluate the abstract syntax trees defined in Fig. 5.12. mout1 is the value of memory after evaluating e1. This is passed to evaluating e2 as the value of the memory before evaluating e2. The value of memory after evaluating e2 is the value of memory after evaluating the sum/difference of the two expressions. This pattern of passing the memory through the evaluation of the tree is called single-threading the memory in the computation.

There is one type of data that is mutable in Standard ML. A reference is a reference to a value of a determined type. References may be mutated to enable the programmer to program using the imperative style of programming. References are discussed in more detail later in this chapter. The array type in Standard ML is a list of references so by arrays are generally considered mutable data types as well, but only because arrays are lists of references.

Once you get used to it, writing recursive functions isn’t too hard. In fact, it can be easier than writing iterative solutions. But, just because you find a recursive solution to a problem, doesn’t mean it’s an effficient solution to a problem. Consider the Fibonacci numbers. The recursive definition leads to a very straightforward recursive solution. However, as it turns out, the simple recursive solution is anything but efficient. In fact, given the definition in Fig. 5.15, fib(42) took six seconds to compute on a 2.66 GHz MacBook Pro with 8 GB of RAM. Fib(43) took a third longer, jumping to nine seconds.

The Fibonacci numbers can be computed with the function definition given in Fig. 5.15. This is a very inefficient way of calculating the Fibonacci numbers. The number of calls to fib increases exponentially with the size of n. This can be seen by looking at a tree of the calls to fib as in Fig. 5.16. The number of calls required to calculate fib(5) is 15. If we were to enumerate the calls required to calculate fib(6) it would be everything in the fib(5) call tree plus the number of nodes in the fib(4) call tree, 15 9 25. The number of calls grows exponentially.

From this analysis you have probably noticed that there is a lot of the same work being done over and over again. It may be possible to eliminate a lot of this work if we are smarter about the way we write the Fibonacci function. In fact it is. The key to this efficient version of fib is to recognize that we can get the next value in the sequence by adding together the previous two values. If we just carry along two values, the current and the next value in the sequence, we can compute each Fibonacci number with just one call. The code in Fig. 5.17 demonstrates how to do this. With the new function, computation of fib(43) is instantaneous.

Using a helper function may lead to a better implementation in some situations. In the case of the fib function, the fibhelper function turns an exponentially complex function into a linear time function. The code in Fig. 5.17 uses a helper function that is private to the fib function because we don’t want other programmers to call the fibhelper function directly. It is meant to be used by the fib function. We also wouldn’t want to have to remember how to call the fibhelper function each time we called it. By hiding it in the fib function we can expose the same interface we had with the original implementation, but implement a much more efficient function.

The helper function uses a pattern called an accumulator pattern. The helper function makes use of an accumulator to reduce the amount of work that is done. The work is reduced because the function keeps track of the last two values computed by the helper function to aid in computing the next number.

One criticism of functional programming centers on the heavy use of recursion that is seen by some critics as overly inefficient. The problem is related to the use of caches in modern processors. Depending on the block size of an instruction cache, the code surrounding the currently executing code may be readily available in the cache. However, when the instruction stream is interrupted by a call to a function, even the same function, the cache may not contain the correct instructions. Retrieving instructions from memory is much slower than finding them in the cache. However, cache sizes continue to increase and even imperative languages like C++ and Java encourage many calls to small functions or methods given their object-oriented nature. So, the argument in favor of fewer function calls has certainly diminished in recent years.

It is still the case that a function call takes longer than executing a simple loop. When a function call is made, extra instructions are executed to create a new activation record. In addition, in pipelined processors the pipeline is disrupted by function calls. Standard ML of New Jersey, Scheme, and some other functional languages have a mechanism where they optimize certain recursive functions by reducing the storage on the run-time stack and eliminating calls. In certain cases, recursive calls can be automatically transformed to code that can be executed using jump or branch instructions. For this optimization to be possible, the recursive function must be tail recursive. A tail recursive function is a function where the very last operation of the function is the recursive call to itself.

The factorial function is presented in Fig. 5.18. Is factorial tail recursive? The answer is no. Tail recursion happens when the very last thing done in a recursive function is a call to itself. The last thing done in Fig. 5.18 is the multiplication.

When factorial 6 is invoked, activation records are needed for seven invocations of the function, namely factorial 6 through factorial 0. Without each of these stack frames, the local values of n, n=6 through n=0, will be lost so that the multiplication at the end can not be carried out correctly.

At its deepest level of recursion all the information in the expression, is stored in the run-time execution stack.

The factorial function can be written to be tail recursive. The solution is to use a technique similar to the fib function improvement made in Fig. 5.17. An accumulator is added to the function definition. An accumulator is an extra parameter that can be used to accumulate a value, much the way you would accumulate a value in a loop. The accumulator value is initially given the identity of the operation used to accumulate the value. In Fig. 5.19 the operation is multiplication. The identity provided as the initial value is 1.

The function presented in Fig. 5.19 is the tail recursive version of the factorial function. The tail recursive function is the tailfac helper function. Note that although tailfac is recursive, there is no need to save it’s local environment when it calls itself since no computation remains after the call. The result of the recursive call is simply passed on as the result of the current function call. A function is tail recursive if its recursive call is the last action that occurs during any particular invocation of the function.

A binary function, for example, or @, takes both of its arguments at the same time. ab will evaluate both a and b so that values can be passed to the addition operation. There can be an advantage in having a binary function take its arguments one at a time. Such a function is called curried after Haskell Curry. ML functions take their parameters one at a time because all functions take exactly one argument. A curried function takes one argument as well. However, that function of one parameter may in turn return a function that takes a single argument. This is probably best illustrated with an example. Here is a function that takes a pair of arguments as its input via a single tuple.

The function plus takes one argument that just happens to be a tuple. Calling the function means providing it a single tuple.

ML functions can be defined with what looks like more than one parameter:

Observe the signature of the function cplus. It appears to take two arguments, but takes them one at a time. Actually, cplus takes only one argument. The cplus function returns a function that takes the second argument. The second function has no name.

Function application is left associative. The parens below show the order of operations.

The result of (cplus 5) is a function that adds 5 to its argument.

We can give this function a name.

The beginning of this chapter describes the lambda calculus. In that section we learned that functions can be characterized as first class objects. Functions can be represented by a lambda abstraction and don’t have to be assigned a name. This is also true in SML. Functions in SML don’t need names. The anonymous function + can be represented in ML as

The anonymous function can be applied to a value in the same way a named function is applied to a value. Function application is always the function first, followed by the value.

We can define a function by binding a lambda abstraction to an identifier:

This mechanism provides an alternative form for defining functions as long as they are not recursive; in a val declaration, the identifier being defined is not visible in the expression on the right side of the arrow. For recursive definitions a val rec expression is required. To define a recursive function using the anonymous function form you must use val rec to declare it.

This val rec definition of a function is the way all functions are defined in SML. The functional form used when the keyword fun is used to define a function is translated into val rec form. The fun form of function definition is called syntactic sugar. Syntactic sugar refers to another way of writing something that gets treated the same way in either case. Usually sugared forms are the nicer way to write something.

The unique feature of functional languages is that functions are treated as first-class objects with the same rights as other objects, namely to be stored in data structures, to be passed as a parameter, and to be returned as function results. Functions can be bound to identifiers using the keywords fun, val, and val rec and may also be stored in structures. These are examples of functions being treated as values.

Notice each of these functions takes an int and returns an int. An ML function can be defined to apply each of these functions to a number. The construction function applies a list of functions to a value.

Construction is based on a functional form found in FP, an early functional programming language developed by John Backus. It illustrates the possibility of passing functions as arguments. Since functions are first-class objects in ML, they may be stored in any sort of structure. It is possible to imagine an application for a stack of functions or even a tree of functions.

A function is called higher-order if it takes a function as a parameter or returns a function as its result. Higher-order functions are sometimes called functional forms since they allow the construction of new functions from already defined functions.

Continuation Passing Style (or CPS) is a way of writing functional programs where control is made explicit. In other words, the continuation represents the remaining work to be done. This style of writing code is interesting because the style is used in the SML compiler. To understand cps it’s best to look at an example. Let’s consider the len function for computing the length of a list.

To transform this to cps form we represent the rest of the computation explicitly as a parameter called k. In this way, whenever we need the continuation of the calculation, we can just write the identifier k. Here’s the cps form of len and an example of calling it.

Notice that the recursive call to cpslen is the last thing that is done. This function is tail recursive. However, tail recursion elimination cannot be applied because the function returns a function and recursively calls itself with a function as a parameter. CPS is still important because it can be optimized by a compiler. In addition, since control flow is explicit (passed around as k), function calls can be implemented with jumps and many of the jumps can be eliminated if the code is organized in the right way.

Eliminating calls and jumps is important since calls have the effect of interrupting pipelines in RISC processors. Since functional languages make lots of calls, one of the criticisms of functional languages is that they were inefficient. With the optimization of CPS functions, functional languages get closer to being as efficient as imperative languages. In addition, as cache sizes and processor speeds increase the performance difference becomes less and less of an issue.

SML contains a TextIO structure as part of the basis library. The signature of the functions in the TextIO structure is given in Appendix B. It is possible to read and write strings to streams using this library of functions. The usual standard input, standard output, and standard error streams are predefined. Here is an example of reading a string from the keyboard. Explode is used on the string to show the vector type is really the string type. It also shows how to print something to a stream.

Since streams can be directed to files, the screen, or across the network, there really isn’t much more to input and output in SML. Of course if you are opening your own stream it should be closed when you are done with it. Program termination will also close any open streams.

There are some TextIO functions that may or may not return a value. In these cases an option is returned. An option is a value that is either NONE or SOME value. An option is SML’s way of dealing with functions that may or may not succeed. Functions must always return a value or end with an exception. To prevent the exception handling mechanism from being used for input operations that may or may not succeed, this idea of an option was created. Options fit nicely into the strong typing that SML provides. The input1 function of the TextIO structure reads exactly one character from the input and returns an option as a result. The reason it returns an option and not the character directly is because the stream might not be ready for reading. The valOf function can be used to get the value of an option that is not NONE.

Standard ML is not a pure functional language. It is possible to write programs with side effects, such as reading from and writing to streams. To write imperative programs the language should support sequential execution, variables, and possibly loops. All three of these features are available in SML. The following sections show you how to use each of these features.

An exception occurs in SML when a condition occurs that requires special handling. If no special handling is defined for the condition the program terminates. As with most modern languages, SML has facilities for handling these exceptions and for raising user-defined exceptions. Consider the maxIntList function you wrote in practice problem 5.13. You probably had to figure out what to do if an empty list was passed to the function. One way to handle this is to raise an exception.

ML provides two language constructs that enable programmers to define new datatypes and hide their implementation details. The first of these language constructs we’ll look at is the signature. The other construct is the structure.

Perhaps Standard ML’s strongest point is the formally proven soundness of its type inference system. ML’s type inference system is guaranteed to prevent any run-time type errors from occurring in a program. This turns out to prevent many run-time errors from occurring in your programs. Projects like the Fox Project have shown that ML can be used to produce highly reliable large software systems.

The origins of type inference include Haskell Curry and Robert Feys who in 1958 devised a type inference algorithm for the simply typed lambda calculus. In 1969 Roger Hindley worked on extending this type inference algorithm. In 1978 Robin Milner independently from Hindley devised a similar type inference system proving its soundness. In 1985 Luis Damas proved Milner’s algorithm was complete and extended it to support polymorphic references. This algorithm is called the Hindley-Milner type inference algorithm or the Milner-Damas algorithm. The type inference system is based on a very powerful concept called unification.

Unification is the process of using type inference rules to bind type variables to values. The type inference rules look like this.

IfThen

This rule says that for an if-then expression to be correctly typed, the type of the first expression must be a bool and the types of the second and third expression must be unifiable. If those preconditions hold, then the type of the if-then expression is given by the type of either of the second two expressions (since they are the same). Unification happens when is written twice in the rule above. The is the presence of type information that is used when determining the types of the three expressions and is called the type environment.

Here are two examples that suggest how the type inference mechanism works. In this example we determine the type of the following function.

The function f takes one parameter, a pair.

From the nature of the argument patterns, we conclude that the three unknown types must be lists.

The function imposes no constraints on the domain lists, but the codomain list must be a list of pairs because of the cons operation (x, y) ::. We know x:’p and y:’s. Therefore ‘t=’p *’s.

where ‘p and ‘s are any ML types. In this example the type of the function g is inferred.

The function g takes two parameters, one at a time.

The second parameter, x, must serve as an argument to null, hd, and tl; it must be a list.

The first parameter, h, must be a function since it is applied to hd x, and its domain type must agree with the type of elements in the list. In addition, h must produce a boolean result because of its use in the conditional expression.

The result of the function must be a list since the base case returns nil. The result list is constructed by the code (hd x) ::g h (tl x), which adds items of type ‘s to the resulting list.

Therefore, the type of g must be:

Chapter 8 explores type inference in much more detail. A type checker for Standard ML is developed using Prolog, a programming language ideally suited to problems involving unification.

The datatype definition in Fig. 5.12 provided an abstract syntax tree definition for a calculator language with one memory location. A related prefix calculator expression language is relatively easy to define and from that we can build an interpreter of prefix calculator expressions. Prefix expressions are comprised of an operator first followed by an expression or expressions. The prefix calculator expression language is defined by this LL(1) grammar.

where

The only non-terminal in this grammar is E. The S is the store operator which stores the expression that follows it in the memory location. The R is the recall operator. The tilde (i.e. ^~) is the unary negation operator. To implement an interpreter for this language we must first parse the expression and build an abstract syntax tree. Then the abstract syntax tree can be evaluated. The entire process can be encapsulated in a run function.

The run function that provides the overall design of the prefix calculator interpreter is provided in Fig. 5.24.

A number of things should be explained about this code. Line 8 flushes standard output. Without it the prompt does not print before the program starts waiting for input. Line 9 gets a line of input from the user. It is returned as a string option so on line 10 the valOf function is applied to get the string or raise an Option exception if NONE had been returned.

Line 10 calls the tokens function. All the tokens must be separated by spaces or tabs for the program to read the tokens correct. Here is an example of running this code.

Line 12 calls the evaluator function eval to interpret the AST. The eval function returns the result of evaluating the tree. Line 17 prints the result to the screen.

There are two handled exceptions. If the eofException is thrown then the expression did not parse correctly. If the Option exception is thrown there was a bad token in the input. Note that only integers are allowed for numbers in this implementation. This was decided by the AST definition in Fig. 5.12.

This chapter introduced functional programming. For many this is a new way of thinking about programming. Recursion is the main pattern used in computing when writing in a functional programming style. Higher-order functions are an important part of functional programming. Certain patterns appear often in functional programs and these patterns have been implemented as some common higher-order functions like map, filter, foldr, and others.

An important thing to learn from this chapter is that functional programming is more declarative and less prescriptive than programming in an imperative language like C++ or Java. Standard ML is a good functional programming language but other languages like C++, Java, and Python support functional programming as well.

Standard ML has a strong type checker that has been proven sound and complete. That means that while more time is spent removing type errors from programs, much less time is spent debugging Standard ML programs. Experiments like the Fox Project at Carnegie Mellon have shown this is true for large software systems written in Standard ML as well.

Much more can be learned about Standard ML and the next chapter not only looks at some Standard ML tools for language implementation, but it also describes the implementation of a compiler that translates Standard ML to JCoCo assembly language.

Jeffrey Ullman’s book on functional programming in Standard ML is a very good introduction and reference for Standard ML. It is more thorough than the topics provided in this text and contains many topics not covered here including discussion of arrays, functors, and sharings along with a few of the Basis structures. The topics presented here and in the next chapter give you a good introduction to the ideas and concepts associated with functional programming. Ullman’s book and on-line tutorials and manual pages are another great resource for learning functional programming.

In the exercises below you are encouraged to write other functions that may help you in your solutions. You might have better luck with some of the harder ones if you solve a simpler problem first that can be used in the solution to the harder problem.

You may wish to put your solutions to these problems in a file and then

in SML. This will make writing the solutions easier. You can try the solutions out by placing tests right within the same file. You should always comment any code you write. Comments in SML are preceded with a (* and terminated with a *).

These are solutions to the practice problems. You should only consult these answers after you have tried each of them for yourself first. Practice problems are meant to help reinforce the material you have just read so make use of them.