Common Lisp the Language, 2nd Edition

Next: Structure Traversal and Up: Iteration Previous: Mapping

7.8.5. The ``Program Feature’’

Lisp implementations since Lisp 1.5 have had what was originally called ``the program feature,’’ as if it were impossible to write programs without it! The prog construct allows one to write in an Algol-like or Fortran-like statement-oriented style, using go statements that can refer to tags in the body of the prog. Modern Lisp programming style tends to use prog rather infrequently. The various iteration constructs, such as do, have bodies with the characteristics of a prog. (However, the ability to use go statements within iteration constructs is very seldom called upon in practice.)

Three distinct operations are performed by prog: it binds local variables, it permits use of the return statement, and it permits use of the go statement. In Common Lisp, these three operations have been separated into three distinct constructs: let, block, and tagbody. These three constructs may be used independently as building blocks for other types of constructs.

[Special Form]
tagbody {tag | statement}*

The part of a tagbody after the variable list is called the body. An item in the body may be a symbol or an integer, in which case it is called a tag, or an item in the body may be a list, in which case it is called a statement.

Each element of the body is processed from left to right. A tag is ignored; a statement is evaluated, and its results are discarded. If the end of the body is reached, the tagbody returns nil.

If (gotag) is evaluated, control jumps to the part of the body labelled with the tag.

Compatibility note: The ``computed go’’ feature of MacLisp is not supported. The syntax of a computed go is idiosyncratic, and the feature is not supported by Lisp Machine Lisp, NIL (New Implementation of Lisp), or Interlisp. The computed go has been infrequently used in MacLisp anyway and is easily simulated with no loss of efficiency by using a case statement each of whose clauses performs a (non-computed) go.

The scope of the tags established by a tagbody is lexical, and the extent is dynamic. Once a tagbody construct has been exited, it is no longer legal to go to a tag in its body. It is permissible for a go to jump to a tagbody that is not the innermost tagbody construct containing that go; the tags established by a tagbody will only shadow other tags of like name.

The lexical scoping of the go targets named by tags is fully general and has consequences that may be surprising to users and implementors of other Lisp systems. For example, the go in the following example actually does work in Common Lisp as one might expect:

(tagbody 
   (catch 'stuff 
      (mapcar #'(lambda (x) (if (numberp x) 
                                (hairyfun x) 
                                (go lose))) 
              items)) 
   (return) 
 lose 
   (error "I lost big!"))

Depending on the situation, a go in Common Lisp does not necessarily correspond to a simple machine ``jump’’ instruction. A go can break up catchers if necessary to get to the target. It is possible for a ``closure’’ created by function for a lambda-expression to refer to a go target as long as the tag is lexically apparent. See chapter 3 for an elaborate example of this.

There are some holes in this specification (and that of go) that leave some room for interpretation. For example, there is no explicit prohibition against the same tag appearing more than once in the same tagbody body. Every implementation I know of will complain in the compiler, if not in the interpreter, if there is a go to such a duplicated tag; but some implementors take the position that duplicate tags are permitted provided there is no go to such a tag. (``If a tree falls in the forest, and there is no one there to hear it, then no one needs to yell `Timber!’’’) Also, some implementations allow objects other than symbols, integers, and lists in the body and typically ignore them. Consequently, some programmers use redundant tags such as - for formatting purposes, and strings as comments:

(defun dining-philosopher (j) 
  (tagbody - 
   think   (unless (hungry) (go think)) 
           - 
           "Can't eat without chopsticks." 
           (snatch (chopstick j)) 
           (snatch (chopstick (mod (+ j 1) 5))) 
           - 
   eat     (when (hungry) 
             (mapc #'gobble-down 
                   '(twice-cooked-pork kung-pao-chi-ding 
                     wu-dip-har orange-flavor-beef 
                     two-side-yellow-noodles twinkies)) 
             (go eat)) 
           - 
           "Can't think with my neighbors' stomachs rumbling." 
           (relinquish (chopstick j)) 
           (relinquish (chopstick (mod (+ j 1) 5))) 
           - 
           (if (happy) (go think) 
               (become insurance-salesman))))

In certain implementations of Common Lisp they get away with it. Others abhor what they view as an abuse of unintended ambiguity in the language specification. For maximum portability, I advise users to steer clear of these issues. Similarly, it is best to avoid using nil as a tag, even though it is a symbol, because a few implementations treat nil as a list to be executed. To be extra careful, avoid calling from within a tagbody a macro whose expansion might not be a non-nil list; wrap such a call in (progn ...), or rewrite the macro to return (progn ...) if possible.

[Macro]

prog ({var | (var [init])}*) {declaration}* {tag | statement}* 
prog* ({var | (var [init])}*) {declaration}* {tag | statement}*

The prog construct is a synthesis of let, block, and tagbody, allowing bound variables and the use of return and go within a single construct. A typical prog construct looks like this:

(prog (var1 var2 (var3 init3) var4 (var5 init5)) 
      {declaration}*
      statement1 
 tag1 
      statement2 
      statement3 
      statement4 
 tag2 
      statement5 
      ... 
      )

The list after the keyword prog is a set of specifications for binding var1, var2, etc., which are temporary variables bound locally to the prog. This list is processed exactly as the list in a let statement: first all the init forms are evaluated from left to right (where nil is used for any omitted init form), and then the variables are all bound in parallel to the respective results. Any declaration appearing in the prog is used as if appearing at the top of the let body.

The body of the prog is executed as if it were a tagbody construct; the go statement may be used to transfer control to a tag.

A prog implicitly establishes a block named nil around the entire prog construct, so that return may be used at any time to exit from the prog construct.

Here is a fine example of what can be done with prog:

(defun king-of-confusion (w) 
  "Take a cons of two lists and make a list of conses. 
   Think of this function as being like a zipper." 
  (prog (x y z)     ;Initialize x, y, z to nil 
        (setq y (car w) z (cdr w)) 
   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 
        (cerror "Will self-pair extraneous items" 
                "Mismatch - gleep!   S" y) 
        (setq z y) 
        (go rejoin)))

which is accomplished somewhat more perspicuously by

(defun prince-of-clarity (w) 
  "Take a cons of two lists and make a list of conses. 
   Think of this function as being like a zipper." 
  (do ((y (car w) (cdr y)) 
       (z (cdr w) (cdr z)) 
       (x '() (cons (cons (car y) (car z)) x))) 
      ((null y) x) 
    (when (null z) 
      (cerror "Will self-pair extraneous items" 
              "Mismatch - gleep!   S" y) 
      (setq z y))))

The prog construct may be explained in terms of the simpler constructs block, let, and tagbody as follows:

(prog variable-list {declaration}* . body) 
   == (block nil (let variable-list {declaration}* (tagbody . body)))

The prog* special form is almost the same as prog. The only difference is that the binding and initialization of the temporary variables is done sequentially, so that the init form for each one can use the values of previous ones. Therefore prog* is to prog as let* is to let. For example,

(prog* ((y z) (x (car y))) 
       (return x))

returns the car of the value of z.

I haven’t seen prog used very much in the last several years. Apparently splitting it into functional constituents (let, block, tagbody) has been a success. Common Lisp programmers now tend to use whichever specific construct is appropriate.

[Special Form]
go tag

The (gotag) special form is used to do a ``go to’’ within a tagbody construct. The tag must be a symbol or an integer; the tag is not evaluated. go transfers control to the point in the body labelled by a tag eql to the one given. If there is no such tag in the body, the bodies of lexically containing tagbody constructs (if any) are examined as well. It is an error if there is no matching tag lexically visible to the point of the go.

The go form does not ever return a value.

As a matter of style, it is recommended that the user think twice before using a go. Most purposes of go can be accomplished with one of the iteration primitives, nested conditional forms, or return-from. If the use of go seems to be unavoidable, perhaps the control structure implemented by go should be packaged as a macro definition.

Next: Structure Traversal and Up: Iteration Previous: Mapping

AI.Repository@cs.cmu.edu