There was a problem when proofreading this page.
Steele and Sussman
57
The Art of the Interpreter

{LABELS} Pages 29, 59

This technique can be generalized to allow the definition of recursive local procedures. (Although the Y-operator discussed in {Note Y-operator} can be used to implement recursive local procedures, it is extremely painful to construct several mutually recursive procedures. Although mutually recursive procedures can be theoretically eliminated (by procedure integration), this process destroys the conceptual structure of the program.)

Consider writing a procedure to construct the reverse of a given list:

(DEFINE (REVERSE L)
        (REVERSE1 L '()))

(DEFINE (REVERSE1 OLD NEW)
        (COND ((NULL OLD) NEW)
              (T (REVERSE1 (CDR OLD) (CONS (CAR OLD) NEW)))))

The procedure REVERSE1 is irrelevant to the outside world; we would like to hide it inside REVERSE.

Let us invent a new construction to permit the definition of local procedure definitions with names:

(LABELS (((f{{sub|1}} v{{sub|11}} v{{sub|12}} ...) body{{sub|1}})
         ((f{{sub|2}} v{{sub|21}} v{{sub|22}} ...) body{{sub|2}})
         ...
         ((f{{sub|N}} v{{sub|N1}} v{{sub|N2}} ...) body{{sub|N}}))
       body)

means the value of body when evaluated in an environment where the specified procedure definitions are available. For example:

(DEFINE (REVERSE L)
        (LABELS (((REVERSE1 OLD NEW)
                  (COND ((NULL OLD) NEW)
                        (T (REVERSE1 (CDR OLD) (CONS (CAR OLD) NEW))))))
                (REVERSE1 L '())))

The same trick works for LABELS as for the top level: when LOOKUP1 has found a LABELS-defined function, it has the correct environment in hand for constructing a &PROCEDURE-object. We need only add a test in EVAL for the LABELS construct, and arrange for the appropriate &LABELED-objects to be constructed (see Figure N5).