The fragment of LISP we have learned so far is purely functional. We program by defining mathematical functions. Programming this way has the benefit of referential transparency, which means that an experession has the same value and the same behavior, no matter where it is located, and how many times it is invoked. For example, the following function always returns 4 when an input 2 is supplied:
(defun double (x) (* 2 x))Such programs are easy to develop and debug. The only effect of calling a function is the returned value. Functions become a lot harder to understand and debug when we allow them to produce side effects, that is, affecting subsequent computation in ways other than returning a value. This style of programming, in which side effect is not only permissible but is also the primary means by which we program, is called imperative programming. This is not something new, but is in fact the very kind of programming habits that you have acquired since you learned your first programming language (e.g. C/C++, Pascal, Java). Because of this, we intentionally leave the topic of imperative programming to the end of this series of tutorials. We do so since you already know so much about imperative programming, and since, in my taste, teaching it before teaching functional programming would only reinforce some of the bad habits programmers usually have, and thereby luring you to write C code with LISP, which, of course, make it harder to finish your assignment on time.
Imperative programming is made possible by the notion of program state. The behavior of an expression depends on the exact state a program is in. In turn, the state of a program is defined by, guess what, variables.
Suppose we want to create a global counter to keep track of the times some computational events occur. Common LISP allows us to define global variables as follows.
USER(7): (defparameter *counter* 0 "Counter to keep track of ....") *COUNTER* USER(8): (setf *counter* (1+ *counter*)) 1 USER(9): *counter* 1 USER(10): (setf *counter* (1+ *counter*)) 2 USER(11): *counter* 200We use the defparameter special form to define a global variable *counter*, with zero as its initial value. We also decorate the declaration by a documentation string. We then use the setf special form to assign new values to the variable. The setf special form returns the new value of the variable. Lastly, evaluating the variable gives its current value. Notice that *counter* is evaluated to two different values at different point of time. This is something you will never see if you work with purely functional programs.
Suppose we actually want this counter to reset to zero when it reaches a user defined threshold. We would encapsulate this service into the following definitions:
(defparameter *counter* 0
"Counter to keep track of ....")
(defparameter *threshold* 4
"Counter will be reset to zero when its value reaches this threshold.")
(defun counter-inc ()
"Increment global counter by one."
(if (>= (1+ *counter*) *threshold*)
(setf *counter* 0)
(setf *counter* (1+ *counter*))))
(defun counter-value ()
"Return current value of global counter."
*counter*)
(defun counter-threshold ()
"Return current threshold of global counter."
*threshold*)
USER(24): (counter-value) 0 USER(25): (counter-inc) 1 USER(26): (counter-inc) 2 USER(27): (counter-inc) 3 USER(28): (counter-threshold) 4 USER(29): (counter-inc) 0
The function counter-inc can also be defined as follows:
(defun counter-inc ()
"Increment global counter by one."
(if (>= (1+ *counter*) *threshold*)
(setf *counter* 0)
(incf *counter*)))
With the possibility of state alteration, we also need a new kind of programming construct --- sequencing. This allows us to perform multiple state-alterating operations, one after another. For example, we might want to introduce another function to our global counter abstraction: a function to modify the value of *threshold* on the fly:
(defun counter-set-threshold (th)
"Set counter threshold to TH."
(setf *threshold* th)
(if (>= *counter* *threshold*)
(setf *counter* 0))
*threshold*)
The function sets the global value of *threshold* to a new value,
and then checks if the current counter value has exceeded the new threshold.
If the check succeeds, then the counter is reset to zero. Lastly, the
function evaluates and returns the last expression, which is simply the
new value of *threshold*. Notice that
in this example the body of a function is no longer one expression, but
a sequence of expressions. They are evaluated in order, and the value
of the last expression is returned as a value of the sequence.
The effect is demonstrated as in the following trace:
USER(2): (counter-value) 0 USER(3): (counter-inc) 1 USER(4): (counter-inc) 2 USER(5): (counter-inc) 3 USER(6): (counter-inc) 0 USER(7): (counter-inc) 1 USER(8): (counter-inc) 2 USER(9): (counter-set-threshold 2) 0 USER(10): (counter-value) 0
In fact, forms like let, let*, when and unless all admit sequences as their bodies. The cond form allows sequencing in the body of each alternative. The exception is if, due to its syntax. However, you can always get around by introducing a let form in the alternatives or by using other conditional forms.
Before we move on, notice that we can rewrite the counter-inc function as follows:
(defun counter-inc ()
"Increment global counter by one."
(if (>= (1+ *counter*) *threshold*)
(setf *counter* 0)
(incf *counter*)))
The (incf x) form is simply a shorthand for (setf x (+ x 1)).
In general, the following are useful shorthands when developing imperative
programs:
| Shorthand | Meaning |
|---|---|
| (incf x delta) | (setf x (+ x delta)) |
| (incf x) | (incf x 1) |
| (decf x delta) | (setf x (- x delta)) |
| (decf x) | (decf x 1) |
| (push e x) | (setf x (cons e x)) |
| (pop x) | (let ((e (first x))) (setf x (rest x)) e) |
The above method for defining an abstraction is not good enough. For one, the global variables are not encapsulated. There is nothing to forbid a careless user to change the value of *counter* in ways violating the invariants of the counter abstraction. To enforce this, we make use of local variables and closures.
As one would expect, the names introduced by a let form turns out not to be a name binding to some immutable values. The names refer to local variables. Such variables follow typical lexical scoping rules, so that LISP always looks up the innermost variable definition when a variable name is to be evaluated.
What is more interesting is that, due to the ability to return functions as values, the local variable has a life span longer than the expression defining it. Consider the following example:
USER(20): (setf inc (let ((counter 0))
#'(lambda ()
(incf counter))))
#
USER(21): (funcall inc)
1
USER(22): (funcall inc)
2
USER(23): (funcall inc)
3
We assign a value to the global variable inc. That value
is obtained by first
defining local variable counter using let,
and then within the lexical scope of the local variable,
a lambda expression is evaluated,
thereby creating an annonymous function, which is returned as a value
to be assigned to inc. The most interesting part
is in the body of that lambda expression --- it increments
the value of the local variable counter! When the lambda
expression is returned, the local variable persists, and is accessible
only through the annonymous function.
The thing to remember from this example is that, in other kinds of languages like Pascal and C/C++ the lexical scope of a local variable somehow coincide with its life span. After executation passes beyond the boundary of a lexical scope, all the local variables defined within it cease to exist. This is not true in languages supporting higher-order functions, in particular, expressions that return functions as values. However, that is not to say that lexical scoping does not hold in such languages. In the contrary, lexical scoping is enforced strictly, and therefore the only place from which you can alter the value of counter is, as every true believer of lexical scoping would agree, within the lexical scope of the variable --- the lambda expression. As a result, the counter state is effectively encapsulated. The only way to modify it is by going through the annonymous function stored in inc. The technical term to refer to this thing that is stored in inc, this thing that at the same time captures both the definition of a function and the variables referenced within the function body is called a function closure.
What if we want to define multiple interface functions for the encapsulated counter? Simple, just return all of them:
USER(34): (setf list-of-funcs (let ((counter 0))
(list #'(lambda ()
(incf counter))
#'(lambda ()
(setf counter 0)))))
(#
#)
USER(35): (setf inc (first list-of-funcs))
#
USER(36): (setf reset (second list-of-funcs))
#
USER(37): (funcall inc)
1
USER(38): (funcall inc)
2
USER(39): (funcall inc)
3
USER(40): (funcall reset)
0
USER(41): (funcall inc)
1
Having only one instance of this encapsulated counter abstraction is not good enough. Imagine cases when we need multiple instances of such counters, each having its own state. Well, the answer is simple, we just evaluate the function-returning let form everytime we need a new instance of counter. Since, a new local variable will be created everytime we evaluate the let form, the function closure that is returned each time will be associated with a different incarnation of the local variable counter. To automate this process, of course we define a constructor for such closures:
(defun make-counter ()
"Create a new instance of a counter object."
(let ((counter 0))
(list #'(lambda ()
(incf counter))
#'(lambda ()
(setf counter 0)))))
Notice how this allows us to maintain independently encapsulated states:
USER(44): (setf c1 (make-counter)) (## ) USER(44): (setf c2 (make-counter)) (# # ) USER(45): (funcall (first c1)) 1 USER(46): (funcall (first c1)) 2 USER(47): (funcall (second c1)) 0 USER(48): (funcall (first c2)) 1 USER(49): (funcall (first c2)) 2 USER(50): (funcall (first c2)) 3 USER(51): (funcall (first c1)) 1 USER(52): (funcall (first c1)) 2 USER(53): (funcall (second c2)) 0 USER(54): (funcall (first c1)) 3
To make invoking counter interface functions easier, we can define the following shorthands:
(defun counter-increment (counter) "Increment counter." (funcall (first counter))) (defun counter-reset (counter) "Reset counter." (funcall (second counter)))And now we have an all-rounded counter abstraction.
USER(56): (counter-increment c1) 4 USER(57): (counter-reset c1) 0
The moral of this store is that, function closures are encapsulated states. They are a poor-man's version of objects, which, after all, are nothing but encapsulated states. (Yes, I am aware that Common LISP has a Common LISP Object System (CLOS), and there is no point of using closures in this manner if all we want is simply object orientation. But No, I want you to understand what higher-order functions buy you, and how they serve as a building block for other advanced programming language constructs. Lastly, I don't want you to spend time struggling to learn yet another object system.)
To round off this tutorial, we discuss something that you know so much about --- iterations. We start with something very simple:
USER(1): (dotimes (i 10) (print i)) 0 1 2 3 4 5 6 7 8 9 NILThe (dotimes (i n) body) form executes body N times. In addition, it defines a local variable i, which receives an integer value ranging from 0 to n-1. The body of the form could be a sequence of expressions. The form returns NIL. The (print x) form prints the LISP object x to the console.
A similar construct is defined for iterating through a list:
USER(2): (dolist (i '(a b c d e)) (print i)) A B C D E NIL
The most general looping construct is the do form:
(defun fibonacci (n)
"Compute the N'th Fibonacci number."
(do ((f1 0 f2)
(f2 1 (+ f1 f2))
(i 0 (1+ i)))
((= i n) f2)
; empty body
))
The first list following the do keyword is a list of
local variables and their initializations and update forms.
Each member of this list has the format (var
init-form update-form).
Within this loop are defined three local variables f1,
f2 and i. The three initialization forms
0, 1 and 0 are evaluated first, and then assigned to the
three locals simultaneously. In each subsequent iteration,
the three update forms f2, (+ f1 f2) and
(1+ i) will be evaluated first, and then the values
are assigned to the three local variables simultaneously.
The second list following the do keyword
(i.e. ((= i n) f2)) has the general format of
(exit-condition return-form).
The exit condition (= i n) is checked after
the initialization is done, or after the update is performed
in subsequent iterations. If the test succeeds, then the
return form is evaluated, and its value is returned. Otherwise,
the body of the do form, which in this case is empty,
will be executed with the updated value of the local variables.
Indefinite looping can be achieved using the (loop body) form. One may exit from such loop using the return-from form:
(defun fib (n)
"Compute the N'th Fibonacci number."
(let ((f1 0)
(f2 1)
(i 0))
(loop
(if (= i n)
(return-from fib f2))
; empty body
(psetf f1 f2
f2 (+ f1 f2)
i (1+ i)))))
The fib function has the same meaning as the fibonacci
function coded in terms of do. The psetf is a
variation of setf that implements "parallel" assignment.