Sketchy LISP

An Introduction to Functional Programming in Scheme

1.2 Functional Programming

The majority of popular languages, like C, C++, and Java, is based on the paradigm of imperative programming. Each program ultimately consists of statements that do something, where doing something includes actions like storing values in variables, repeating sections of code, or selecting code based on conditions. Imperative languages typically include some functional aspects, too. For example, the C expression 5+7 evaluates to 12, just like (+ 5 7) does in Scheme. You can even write simple functional programs in some imperative languages like C:

/* Factorial function in C */
int fact(int n) {
        return n==0? 1:
                n*fact(n-1);
}

This function computes the factorial of its argument and returns it. There are no assignments or explicit repetitions in the program. In functional Scheme, all programs are written in this way. Each program has a number of arguments and a result. The Scheme version of the above functions looks like this:

(define (fact n)
  (cond ((zero? n) 1)
    (#t (* n (fact (- n 1))))))

Define looks like a procedure, but is in fact part of the Scheme syntax. Because its application looks like the application of a procedure or function, it is also called a pseudo function. Pseudo functions and Scheme syntax will be discussed later in detail. For now, it is sufficient to know that define defines a new procedure. Its general form is:

(define (procedure-name variable1 ... variablen)
  body)

The definition consists of two parts: a head and a body. The head of a procedure consists of the name of the procedure and the names of its variables. The second part is the body of the procedure, which is an ordinary expression.

When the new procedure is applied using, say,

(fact 3)

the variable n gets the value of the argument 3. In LISP terminology, you would say that n is bound to 3. [Footnote: Actually, variables are bound to storage locations rather than values, but we will use a simplified model here.] In this context, the procedure body is evaluated.

The zero? procedure is a so-called predicate. In LISP speak, a predicate is a procedure returning a truth value. Zero? tests whether its argument is equal to zero.

In Scheme, a predicate is a procedure returning one of the truth values #t and #f. The names of most Scheme predicates end with a question mark, like these:

eq?  equal?  zero?  number?

The outermost construct in the body of fact is cond. The cond pseudo function plays a central role in Scheme, becaus it controls the flow of evaluation. It is a generalized form of the if pseudo function which will be introduced later. A cond expression consists of a series of clauses, which are tested in sequence. Above cond expression has two clauses:

((zero? n) 1)

and

(#t (* n (fact (- n 1))))

Each clause has a predicate and a conditional body:

(predicate body)

Both the predicate and the body are ordinary expressions. Cond starts by evaluating the predicate of its first clause. If the predicate evaluates to logical truth, the body of the same clause is evaluated and the result of the body is the result of the entire cond expression. The remaining clauses are ignored. If the predicate of the first clause reduces to logical falsity, though, cond proceeds with the next clause until it finds one whose predicate evaluates to truth.

It is a good idea to make the last clause of cond catch the remaining cases by specifying constant truth as its predicate. In Scheme, the notation #f represents falsity and all other values represent truth. However, it is good style to use the expression #t to represent logical truth. This is exactly what is done in the second clause of fact, so

(cond ((zero? n) 1)
  (#t (* n (fact (- n 1))))))

has the following meaning:

if (zero? n) then evaluate to 1
             else evaluate to (* n (fact (- n 1)))

Because cond is a functional construct, it returns a value: the value of the body of the first clause with a true predicate:

(cond (#f 0) (#t 1)) => 1

So what exactly happens when the above fact procedure is applied to a value, say, 3? Here is an answer:

(fact 3)
-> (cond ((zero? 3) 1) (#t (* 3 (fact (- 3 1)))))
-> (* 3 (fact (- 3 1)))
-> (* 3 (fact 2))
-> (* 3 (* 2 (fact 1)))
-> (* 3 (* 2 (* 1 (fact 0))))
-> (* 3 (* 2 (* 1 1)))
-> (* 3 (* 2 1))
-> (* 3 2)
=> 6

In this book, the single arrow -> denotes half a reduction. The formula a -> b means that a is partially reduced to b by reducing one or multiple sub-expressions of a to their normal forms. For instance, in

(* 2 (+ 3 4)) -> (* 2 7)

the sub-expression (+ 3 4) is reduced to its normal form, 7. The normal form then replaces the sub-expression from which it resulted, forming a new expression (which can be reduced further). Partial reduction is used to illustrate the process of reducing an expression when multiple steps are involved. At some point the reduction normally reaches a point where the expression cannot be reduced any further. Such an expression is said to be in its normal form. The => operator always has a normal form on its righthand side, while -> never has a normal form on its righthand side:

(* 2 (+ 3 4))
-> (* 2 7)
=> 14

The value of an expression is exactly equal to its normal form. Computing the value of a procedure application normally involves multiple steps.

When the body of fact is evaluated as shown above, each n in it is replaced with 3. Cond then evaluates (zero? 3) which tests whether 0=3. This is not the case, so the second clause is tested. Its predicate is #t, so its body is evaluated. This body contains another application of fact, but this time, the procedure is applied to (- 3 1) = 2. The same path is taken over and over again until n reaches zero. Finally, (zero? n) returns truth and so fact evaluates to 1. The resulting 1 replaces the application of fact in the expression

(* 3 (* 2 (* 1 (fact 0))))

As soon as (fact 0) has returned its value, the complete expression can be reduced to 6 by performing the multiplications represented by *.

The sample reduction of fact above shows one major advantage of functional languages over imperative languages. Programs can be executed on a sheet of paper by re-writing them according to a set of simple rules. This property makes it easy to verify characteristics of programs formally. Try this with a C program.