FUNCTIONAL LANGUAGES

Functional languages were invented early in the history of computing. In 1958 John McCarthy at MIT
invented LISP. Functional languages represent computing as solving mathematical functions. A function takes
one or more arguments, and returns a value. For example, an equation for a parabola is:
f = 2x2 + 5 (4.4)
When one supplies a particular value for x, the function returns a particular result:
f (3) = 2(3)2 + 5 = 23 (4.5)
With a functional language, computing proceeds by passing input parameters to a function, which then
returns the result of the function. The return value(s) typically provides the input parameter(s) for another
function(s), and so any level of computational complexity can be programmed.
In any functional language, some basic functions are built in, and they’re called primitives. In LISP these
include the mathematical functions of addition, subtraction, multiplication and division, for example, as well as
the function car, which returns the first element in a list, and cdr, which returns all but the first element in
a list. (By the way, the function names car and cdr come from acronyms for two registers used by LISP on
the old IBM 704 computer.)
As our example functional language, we will use Scheme, a newer (1975) descendent of LISP, which has
particularly consistent syntax. An expression in Scheme is an atom or a list. An atom is a single number, character
string, name, or function. A list is a collection of expressions contained within parentheses. Note that the elements
of a list may be atoms or other lists.
Computing in Scheme means evaluating the Scheme expressions. In particular, to evaluate a list, Scheme
expects the first element of the list to be a function, and the following elements of the list to be arguments to
the function. Since the elements of the list may themselves be lists, evaluation proceeds recursively, by first
evaluating the lists at the lowest level, and then proceeding to final evaluation of the function at the top level.
To add two numbers in Scheme, one creates a list. The first element within parentheses is the function ‘+’,
and the following elements are the arguments to the function. When an expression is complete, the Scheme
interpreter evaluates the function and returns the result. This cycle is called the REPL—the Read, Evaluate,
Print, Loop. Here is the code to add 3 and 5 together:
(+ 3 5 )
8
If we wish to add more than two numbers, we simply include more parameters to the function. For example,
to add five numbers, we simply increase the number of arguments:
(+ 3 5 7 4 2 )
21
Expressions can be evaluated as arguments, too, so this Scheme expression divides the sum of 3 and 5 by
the difference between 7 and 5:
( / (+ 3 5 ) ( - 7 5) )
4
Another primitive function in LISP and Scheme is the function list, which takes a series of arguments
and makes a list:
( list 1 5 6 )
( 1 5 6 )
If we need the first element in a list, the function car will return that:
( car (list 1 5 6) )
1
The function cdr will return all but the first element of the list:
( cdr (list 1 5 6) )
( 5 6 )

A list can include many elements, only one element, or no elements:
( list 8 )
( 8 )
( list )
()
One can define a new function at any time using the “lambda notation.” This code creates a new
function called ‘sum’ which adds two numbers together, just like the built-in primitive ‘+’ does, but for only two
arguments:
(define sum
(lambda (n m)
( + n m)))
The name sum is associated with a function that expects two arguments. The function completes after
adding the arguments n and m together, and the result of evaluating the function is the sum of the two arguments.
Our function sum produces the same result as the built-in function ‘+’ when presented with two arguments, but
sum will not accept an arbitrary number of input parameters:
> (sum 4 3)
7
> (+ 4 3)
7
> (sum 4 3 2)
[Repl(25)] Error: incorrect number of arguments to
#<procedure>.
Type (debug) to enter the debugger.
Looping in a functional language is accomplished by recursion, that is, by having the function call itself
repetitively. Indeed, one of the reasons to study functional programming is to become comfortable using recursion.
Even programmers using the popular imperative programming languages can take advantage of recursion,
which can make some programming tasks more compact, self-documenting, and reliable.
For instance, suppose we need a function to compute the factorial of an integer. One way to write such code
in C or Java is this:
int factorial( int n ){
int fact = 1;
while( n > 1 ) {
fact = fact * n;
n--;
}
return fact;
}
This version of the factorial function starts with the number passed in, and then iteratively multiplies that
number by each smaller number until the function works its way down to 1.
A different way to write this function in C or Java, using recursion, is this way:
int factorial( int n ){
if( n <= 1 ) return 1;
return( n * factorial( n-1 ));
}
If the number passed in is greater than 1, the recursive function simply multiplies the number passed in by
the factorial of that number minus 1. The factorial function calls itself repeatedly until the number passed
in is 1, at which point it returns the value 1 to the last caller, which can then return to its caller, etc.
Some would say that the recursive function is more self-descriptive. It’s certainly shorter, and simpler to write.

To write a recursive function, one first defines the “grounding condition,” or “base case,” at which the
recursion terminates. In the example of factorial, both 1! and 0! return 1 by definition, and no further
computation is necessary. When the grounding condition occurs, the function should stop calling itself and
simply return the value 1.
The factorial for a larger number can be defined as the larger number times the factorial of the next smaller
integer. So the factorial function can be thought of as a process: multiply the number times the factorial of
the next smaller number. The process continues until the number being evaluated is 1. At that point, the function
returns 1, which provides the factor for computing 2!, which answer provides the factor for computing 3!, which
answer provides the factor for computing 4!, etc. The recursion “unwinds” providing the answer for the factorial
of the larger number.
In a functional language, all computation proceeds by means of evaluating functions. Assignment of values to
variables in order to maintain state is not permitted, so we cannot use a variable like ‘n’ to keep track of our progress
in a loop. Looping must be accomplished by recursion. Here is a Scheme function to compute the factorial:
(define factorial
(lambda (n)
(if (<= n 1) 1 (* n (factorial(- n 1)))
)))
Here we also see the conditional execution function if. The if function in Scheme is followed by three
expressions. The first is evaluated for its truth. If the first expression following if is true, the second expression
is evaluated and returned (in this case, if n <= 1, return 1). If the first expression is false, the third expression is
evaluated and returned (in this case, if n > 1, return the product of n and the factorial of n−1).
We can elaborate on our simple summation function and illustrate some more ideas. Here is a version of
sum that takes a list as an argument. This way, our sum function can compute the sum of any number of
integers:
(define listSum
(lambda (n)
(cond ((null? n) 0)
( (null? (cdr n)) (car n) )
(else (+ (car n) (listSum (cdr n))))
)))
The cond (condition) operator is like multiple if and else-if statements in C or Java. Following the
function cond is a list of condition/action pairs. Cond tests the first condition and, if it’s true, cond executes
the associated action. If the first condition is false, cond checks the second condition. If the second condition
is true, cond executes the action associated with the second condition. There can be any number of conditions,
and cond will execute only the action associated with the first true condition. At the end can be an else condition
that cond will execute if no other condition is true. The else condition is not required, however.
The listSum function tests to see whether the list it was passed is null. If so, the function returns 0.
If not, then it tests to see if the cdr of the list is null. That will be true if the list consists of a single element,
and in that case the function will simply return the value of the first and only element. Otherwise, the function
recursively adds the first element of the list to the sum of the elements in the back (cdr) of the list.
When we evaluate listSum, we get the correct result:
> (listSum (list 2 4 5))
11
We can go one step further and make a function that behaves like the ‘+’ function, which accepts any
number of addends. Notice that next to lambda, n appears without parentheses. Scheme will accept any
number of parameters; in this case, create a list of the parameters, and pass the list to the function giving the
list the name n.

(define sum
(lambda n
(cond ((null? n) 0)
( (null? (cdr n)) (car n) )
( else (+ (car n) (listSum (cdr n))))
)))
The code for sum is similar to listSum in its checking for the length of n (the set of parameters in the
case of sum), but if the number of parameters is two or greater, sum uses the listSum function to compute
the sum of elements 2 through n. That is because listSum expects a list as an argument, whereas sum expects
one or more separate arguments that get concatenated into a new list. If sum were to recursively call itself passing
(cdr n), the next call to sum would create ((cdr n)), a list of one element (the element is another list,
the cdr of the list of parameters), and the second line of cond would return a list instead of a number.
Our version of sum now behaves like ‘+’ and will accept any number of parameters and return the sum.
> (sum 2 4 5 6)
17
A more elegant solution accepts the list, builds a new expression by putting the ‘+’ in front of the list, and
passes the new list to the Scheme eval function directly. The eval function is the function that Scheme itself
uses to evaluate expressions.
(define sum
(lambda n
(cond ((null? n) 0)
( else (eval (cons '+ n)))
)))
This solution introduces two new elements of Scheme syntax. To understand this version, you need to know
that the single quote before the ‘+’ stops Scheme from evaluating the function ‘+’, and instead forces Scheme
to treat ‘+’ as a simple character atom. In addition, the function cons creates a new list by adding an element
to the front of a list, in this case adding the ‘+’ to the front of the list of numbers to be summed.
Functional programming has the desirable properties of simple syntax and semantics, and compact code.
Also, since a function may not change any of the parameters passed to it, and since assignment is not used
to change program state, “side effects” (any changes in variables that endure after execution of the code) are
eliminated, with resulting improvements in reliability.
Historically, functional programming has found advocates in the fields of artificial intelligence and expert
systems. The popular editor Emacs is written in LISP, too, as is the on-line fare search program employed by
Orbitz (http://www.paulgraham.com/icad.html).