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 `(go tag)` 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 `(go tag)` 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