Lisp provides a variety of structures for flow of control. Function application is the basic method for construction of programs. Operations are written as the application of a function to its arguments. Usually, Lisp programs are written as a large collection of small functions, each of which implements a simple operation. These functions operate by calling one another, and so larger operations are defined in terms of smaller ones.
A function may always call itself in Lisp. The calling of a function by itself is known as recursion ; it is analogous to mathematical induction.
The performing of an action repeatedly (usually with some changes between repetitions) is called iteration , and is provided as a basic control structure in most languages. The do statement of PL/I, the for statement of ALGOL/60, and so on are examples of iteration primitives. Lisp provides a general iteration facility called do , which is explained below.
A conditional construct is one which allows a program to make a decision, and do one thing or another based on some logical condition. Lisp provides and and or , which are simple conditionals, and cond , which is a more general conditional.
Non-local exits are similar to the leave , exit , and escape constructs in many modern languages. 'c French, Italian, ... They are similar to a return , but are more general. In Lisp, their scope is determined at run-time. They are implemented as the catch and *throw functions. Lisp Machine Lisp also provides a multiple-process or coroutine capability. This is explained in the section on stacks (this link).
Examples: (and x y) (and (setq temp (assq x y)) (rplacd temp z)) (and (not error-p) (princ "There was no error."))Note: (and) => t , which is the identity for this operation.
(cond (antecedent consequent consequent ...) (antecedent ) (antecedent consequent ...) ... )The idea is that each clause represents a case which is selected if its antecedent is satisfied and the antecedents of all preceding clauses were not satisfied. When a clause is selected, its consequent forms are evaluated. cond processes its clauses in order from left to right. First, the antecedent of the current clause is evaluated. If the result is nil , cond advances to the next clause. Otherwise, the cdr of the clause is treated as a list of forms, or consequents, which are evaluated in order from left to right. After evaluating the consequents, cond returns without inspecting any remaining clauses. The value of the cond special form is the value of the last consequent evaluated, or the value of the antecedent if there were no consequents in the clause. If cond runs out of clauses, that is, if every antecedent is nil , that is, if no case is selected, the value of the cond is nil .
Example: (cond ((zerop x) ;First clause: (+ y 3)) ; (zerop x) is the antecedent. ; (+ y 3) is the consequent. ((null y) ;A clause with 2 consequents: (setq y 4) ; this (cons x z)) ; and this. (z) ;A clause with no consequents: ; the antecedent is just z. (t ;An antecedent of t 105) ; is always satisfied. ) ;This is the end of the cond.
A typical example: (cond ((eq x 'foo) ...) ((eq x 'bar) ...) ((memq x '(baz quux mum)) ...) (t ...))The selectq macro can be used for such tests. Its form is as follows:
(selectq key-form (pattern consequent consequent ...) (pattern consequent consequent ...) (pattern consequent consequent ...) ...)Its first "argument" is a form, which is evaluated (only once) as the first thing selectq does. The resulting value is called the key . It is followed by any number of clauses . The car of each clause is compared with the key, and if it matches, the consequents of this clause are evaluated, and selectq returns the value of the last consequent. If there are no matches, selectq returns nil . Note that the patterns are not evaluated; if you want them to be evaluated use select rather than selectq . A pattern may be any of:
1) A symbol | If the key is eq to the symbol, it matches. | |
2) A number | If the key is eq to the number, it matches. Only small numbers (fixnums ) will work. | |
3) A list | If the key is eq to one of the elements of the list, then it matches. The elements of the list should be symbols or fixnums. | |
4) t or otherwise | ||
The symbols t and otherwise are special keywords which match anything. Either symbol may be used, it makes no difference. t is accepted for compatibility with Maclisp's caseq construct. |
Example: (selectq x ;This is the same as the cond example (foo ...) ; above. (bar ...) ((baz quux mum) ...) (otherwise ...))
Example: (select (frob x) (foo 1) ((bar baz) 2) (otherwise 3)) is equivalent to (let ((var (frob x))) (cond ((eq var foo) 1) ((or (eq var bar) (eq var baz)) 2) (t 3)))
(selector (frob x) equal (('(one . two)) (frob-one x)) (('(three . four)) (frob-three x)) (otherwise (frob-any x)))
Example: (princ (dispatch 0202 cat-type (0 "Siamese.") (1 "Persian.") (2 "Alley.") (3 (ferror nil "~S is not a known cat type." cat-type))))It is not necessary to include all possible values of the byte which will be dispatched on. [This function may get flushed.]
(prog (var1 var2 (var3 init3 ) var4 (var5 init5 )) tag1 statement1 statement2 tag2 statement2 . . . )var1, var2, ... are temporary variables. When the prog is entered, the values of these variables are saved. When the prog is finished, the saved values are restored. The initial value of a variable inside the prog depends on whether the variable had an associated init form or not; if it did, then the init form is evaluated and becomes the initial value of the corresponding variable. If there was no init form, the variable is initialized to nil .
Example: (prog ((a t) b (c 5) (d (car '(zz . pp)))) <body> )The initial value of a is t , that of b is nil , that of c is the fixnum 5, and that of d is the symbol zz . The binding and initialization of the variables is done in parallel ; that is, all the initial values are computed before any of the variables are changed. The part of a prog after the variable list is called the body . An item in the body may be a symbol or a number, in which case it is called a tag , or some other form (i.e. a list), in which case it is called a statement . After prog binds the temporary variables, it processes each form in its body sequentially. tags are skipped over. Statements are evaluated, and their returned values discarded. If the end of the body is reached, the prog returns nil . However, two special forms may be used in prog bodies to alter the flow of control. If (return x) is evaluated, prog stops processing its body, evaluates x , and returns the result. If (go tag) is evaluated, prog jumps to the part of the body labelled with the tag . tag is not evaluated. The "computed-go " (mis)feature of Maclisp is not supported. The compiler requires that go and return forms be lexically within the scope of the prog ; it is not possible for one function to return to a prog which is in progress in its caller. This restriction happens not to be enforced in the interpreter. Thus, a program which contains a go which is not contained within the body of a prog (or a do , see below) cannot be compiled. Since virtually all programs will be compiled at some time, the restriction should be adhered to. Sometimes code which is lexically within more than one prog (or do ) form wants to return from one of the outer prog s. However, the return function normally returns from the innermost prog . In order to make return ing from outer prog s more convenient, a prog may be given a name by which it may be referenced by a function called return-from , which is similar to return but allows a particular prog to be specified. If the first subform of a prog is a non-nil symbol (rather than a variable list), it is the name of the prog . See the description of the return-from special form, on LINK:(return-from-fun).
Example: (prog george (a b d) (prog (c b) ... (return-from george (cons b d)) ...))If the symbol t is used as the name of a prog , then it will be made "invisible" to return s; return s inside that prog will return to the next outermost level whose name is not t . (return-from t ...) will return from a prog named t . See also the do special form, which uses a body similar to prog . The do , *catch , and *throw special forms are included in Lisp Machine Lisp as an attempt to encourage goto-less programming style, which often leads to more readable, more easily maintained code. The programmer is recommended to use these functions instead of prog wherever reasonable.
Example: (prog (x y z) ;x, y, z are prog variables - temporaries. (setq y (car w) z (cdr w)) ;w is a free variable. loop (cond ((null y) (return x)) ((null z) (go err))) rejoin (setq x (cons (cons (car y) (car z)) x)) (setq y (cdr y) z (cdr z)) (go loop) err (break are-you-sure? t) (setq z y) (go rejoin))
(prog ((y z) (x y)) (return x))returns the value of z .
(do ((var init repeat )...) (end-test exit-form ...) body ...)The first item in the form is a list of zero or more index variable specifiers. Each index variable specifier is a list of the name of a variable var , an initial value init , which defaults to nil if it is omitted, and a repeat value repeat . If repeat is omitted, the var is not changed between repetitions. In index variable specifier can also be just the name of a variable. In this case, the variable has an initial value of nil , and is not changed between repetitions. All assignment to the index variables is done in parallel. At the beginning of the first iteration, all the init s are evaluated, then the var s are saved, then the var s are set to the values of the init s. To put it another way, the var s are lambda -bound to the values of the init s. Note that the init s are evaluated before the var s are bound, i.e. lexically outside of the do . At the beginning of each succeeding iteration those var s that have repeat s get setq 'ed to the values of their respective repeat s. Note that all the repeat s are evaluated before any of the var s is changed. The second element of the do -form is a list of an end-testing predicate end-test , and zero or more forms, called the exit-form s. At the beginning of each iteration, after processing of the repeat s, the end-test is evaluated. If the result is nil , execution proceeds with the body of the do . If the result is not nil , the exit-forms are evaluated from left to right and then do returns. The value of the do is the value of the last exit-form , or nil (not the value of the end-test as you might expect) if there were no exit-form s. Note that the second element of the do -form resembles a cond clause. If the second element of the form is nil , there is no end-test nor exit-form s, and the body of the do is executed only once. In this type of do it is an error to have repeat s. This type of do is a "prog with initial values." If the second element of the form is (nil) , the end-test is never true and there are no exit-form s. The body of the do is executed over and over. The infinite loop can be terminated by use of return or *throw . The remainder of the do -form constitutes a prog -body; that is, go 's and return forms are understood within the do body, as if it were a prog body. When the end of the body is reached, the next iteration of the do begins. If a return form is evaluated, do returns the indicated value and no more iterations occur. The older variety of do is:
(do var init repeat end-test body ...)The first time through the loop var gets the value of init ; the remaining times through the loop it gets the value of repeat , which is re-evaluated each time. Note that init is evaluated before the value of var is saved, i.e. lexically outside of the do . Each time around the loop, after var is set, end-test is evaluated. If it is non-nil , the do finishes and returns nil . If the end-test evaluated to nil , the body of the loop is executed. The body is like a prog body. go may be used. If return is used, its argument is the value of the do . If the end of the prog body is reached, another loop begins.
Examples of the older variety of do : (setq n (array-length foo-array)) (do i 0 (1+ i) (= i n) (aset 0 foo-array i)) ;zeroes out the array foo-array (do zz x (cdr zz) (or (null zz) (zerop (f (car zz))))) ; this applies f to each element of x ; continuously until f returns zero. ; Note that the do has no body. return forms are often useful to do simple searches: (do i 0 (1+ i) (= i n) ; Iterate over the length of foo-array. (and (= (aref foo-array i) 5) ; If we find an element which ;equals 5, (return i))) ; then return its index.
Examples of the new form of do : (do ((i 0 (1+ i)) ; This is just the same as the above example, (n (array-length foo-array))) ((= i n)) ; but written as a new-style do. (aset 0 foo-array i)) (do ((z list (cdr z)) ; z starts as list and is cdr'ed each time. (y other-list) ; y starts as other-list, and is unchanged by the do. (x)) ; x starts as nil and is not changed by the do. (nil) ; The end-test is nil, so this is an infinite loop. body ) (do ((x) (y) (z)) (nil) body ) is like (prog (x y z) body ) except that when it runs off the end of the body, do loops but prog returns nil. On the other hand, (do ((x) (y) (z)) nil body ) is identical to the prog above (it does not loop.)The construction
(do ((x e (cdr x)) (oldx x x)) ((null x)) body )exploits parallel assignment to index variables. On the first iteration, the value of oldx is whatever value x had before the do was entered. On succeeding iterations, oldx contains the value that x had on the previous iteration. In either form of do , the body may contain no forms at all. Very often an iterative algorithm can be most clearly expressed entirely in the repeats and exit-forms of a new-style do , and the body is empty.
(do ((x x (cdr x)) (y y (cdr y)) (z nil (cons (f x y) z))) ;exploits parallel ((or (null x) (null y)) ; assignment. (nreverse z)) ;typical use of nreverse. ) ;no do-body required. is like (maplist 'f x y).
Example: (dotimes (i (// m n) (frob i)) is equivalent to: (do ((i 0 (1+ i)) (count (// m n))) ((≥ i count)) (frob i)) except that the name count is not used.
Example: (dolist (item (frobs foo)) (mung item)) is equivalent to: (do ((lst (frobs foo) (cdr lst)) (item)) ((null lst)) (setq item (car lst)) (mung item)) except that the name lst is not used.
Example: (prog (x y z) (setq x some frob ) loop do something (and some predicate (go endtag)) do something more (and (minusp x) (go loop)) endtag (return z))
Example: (do ((x x (cdr x)) (n 0 (* n 2))) ((null x) n) (cond ((atom (car x)) (setq n (1+ n))) ((memq (caar x) '(sys boom bleah)) (return n))))return is, like go , a special form which does not return a value. return can also be used to return multiple values from a prog or do , by giving it multiple arguments. For example,
(defun assqn (x table) (do ((l table (cdr l)) (n 0 (1+ n))) ((null l) nil) (and (eq (caar l) x) (return (car l) n))))This function is like assq , but it returns an additional value which is the index in the table of the entry it found. See the special forms multiple-value (LINK:(multiple-value-fun)) and multiple-value-list (LINK:(multiple-value-list-fun)).
(defunp fctn (args) form1 form2 ... formn)expands into
(defun fctn (args) (prog nil form1 form2 ... (return formn)))
Example (*catch 'negative (mapcar (function (lambda (x) (cond ((minusp x) (*throw 'negative x)) (t (f x)) ))) y) )which returns a list of f of each element of y if they are all positive, otherwise the first negative member of y . Note: The Lisp Machine Lisp functions *catch and *throw are improved versions of the Maclisp functions catch and throw . The Maclisp ones are similar in purpose, but take their arguments in reversed order, do not evaluate the tag , and may be used in an older form in which no tag is supplied. Compatibility macros are supplied so that programs using the Maclisp functions will work.
(catch form tag ) ==> (*catch (quote tag ) form ) (throw form tag ) ==> (*throw (quote tag ) form )The forms of catch and throw without tags are not supported.
(progn (turn-on-water-faucet) (hairy-function 3 nil 'foo) (turn-off-water-faucet))The non-local exit facility of Lisp creates a situation in which the above code won't work, however: if hairy-function should do a *throw to a *catch which is outside of the progn form, then (turn-off-water-faucet) will never be evaluated (and the faucet will presumably be left running). In order to allow the above program to work, it can be rewritten using unwind-protect as follows:
(unwind-protect (progn (turn-on-water-faucet) (hairy-function 3 nil 'foo)) (turn-off-water-faucet))If hairy-function does a *throw which attempts to quit out of the evaluation of the unwind-protect , the (turn-off-water-faucet) form will be evaluated in between the time of the *throw and the time at which the *catch returns. If the progn returns normally, then the (turn-off-water-faucet) is evaluated, and the unwind-protect returns the result of the progn . One thing to note is that unwind-protect cannot return multiple values. The general form of unwind-protect looks like
(unwind-protect protected-form form1 form2 ...)protected-form is evaluated, and when it returns or when it attempts to quit out of the unwind-protect , the form s are evaluated.
(mapcar f x1 x2 ... xn )In this case f must be a function of n arguments. mapcar will proceed down the lists x1, x2, ..., xn in parallel. The first argument to f will come from x1 , the second from x2 , etc. The iteration stops as soon as any of the lists is exhausted. There are five other mapping functions besides mapcar . maplist is like mapcar except that the function is applied to the list and successive cdr's of that list rather than to successive elements of the list. map and mapc are like maplist and mapcar respectively, except that they don't return any useful value. These functions are used when the function is being called merely for its side-effects, rather than its returned values. mapcan and mapcon are like mapcar and maplist respectively, except that they combine the results of the function using nconc instead of list . That is,
(defun mapcon (f x y) (apply 'nconc (maplist f x y)))Of course, this definition is less general than the real one. Sometimes a do or a straightforward recursion is preferable to a map; however, the mapping functions should be used wherever they naturally apply because this increases the clarity of the code. Often f will be a lambda-expression, rather than a symbol; for example,
(mapcar (function (lambda (x) (cons x something))) some-list)The functional argument to a mapping function must be acceptable to apply - it cannot be a macro or the name of a special form. Of course, there is nothing wrong with using functions which have optional and rest parameters. Here is a table showing the relations between the six map functions.
applies function to | successive | successive | | sublists | elements | ---------------+--------------+---------------+ its own | | | second | map | mapc | argument | | | ---------------+--------------+---------------+ list of the | | | returns function | maplist | mapcar | results | | | ---------------+--------------+---------------+ nconc of the | | | function | mapcon | mapcan | results | | | ---------------+--------------+---------------+There are also functions (mapatoms and mapatoms-all ) for mapping over all symbols in certain packages. See the explanation of packages (LINK:(package)).