[plt-scheme] a few questions (was: Scheme questions?)

From: John David Stone (stone at math.grinnell.edu)
Date: Mon Dec 5 15:53:02 EST 2005

        Gregory Woodhouse writes:

 > >> Is LABELS a special form in some  version of scheme, or something
 > >> bound by an enclosing let? Something else?

        And Bill Wood replied:

 > > Just a historical note:  The LISP 1.5 Programmer's Manual, 2nd ed.,
 > > (MIT, 1965) uses the form (LABEL <name> <lambda-expression>) to bind a
 > > name to a lambda expression.  Also, the Common Lisp form (labels (
 > > <fun-binding> ... ) <expr> ... ) corresponds to the Scheme letrec
 > > form, with the restriction that a labels form introduces bindings for
 > > functions only, whereas a letrec form can introduce bindings to any
 > > values, including lambda expressions.

        And Matthias Felleisen added:

 > Someone should look up the first Scheme report.

        The first Scheme report (Sussman and Steele, 1975) uses the keyword
LABELS for the syntax that has more recently been called LETREC, with the
following example of mutual recursion:

 # (DEFINE COUNT
 #     (LAMBDA (L)
 #         (LABELS ((COUNTCAR
 #                   (LAMBDA (L)
 #                       (IF (ATOM L) 1
 #                           (+ (COUNTCAR (CAR L))
 #                              (COUNTCDR (CDR L))))))
 #                  (COUNTCDR
 #                   (LAMBDA (L)
 #                       (IF (ATOM L)
 #                           (IF (NULL L) 0 1)
 #                          (+ (COUNTCAR (CAR L))
 #                              (COUNTCDR (CDR L)))))))
 #            (COUNTCDR L)                 ;Note: COUNTCDR is defined here.

About this form, the authors say, ``We have decided not to use the
traditional LABEL primitive in this interpreter because it is difficult to
define several mutually recursive functions using only LABEL.  The
solution, which Hewitt [Smith and Hewitt] also uses, is to adopt an
ALGOLesque block syntax.''

        Sussman and Steele's bibliography entry for [Smith and Hewitt] is:

 #         Smith, Brian C., and Hewitt, Carl.  _A PLASMA Primer_ (draft).
 # MIT AI Lab (Cambridge, October 1975).

        The Revised Report on Scheme (Steele and Sussman, 1978) also uses
the keyword LABELS for this syntax, but it becomes LETREC in R2RS (Clinger
_et al._, 1985).  R2RS also introduces named LET-expressions, in this
tentative way:

 # Some implementations of Scheme permit a ``named let'' syntax in which
 #
 #              (LET name ((var1 form1) ...) expr1 expr2 ...)
 #
 # is equivalent to
 #
 #        ((REC name (LAMBDA (var1 ...) expr1 expr2 ...)) form1 ...)

Bibliography:

        Clinger, William, _et al._  _The Revised Revised Report on Scheme
or An UnCommon Lisp_.  MIT Artificial Intelligence Laboratory, AI Memo 848,
August, 1985.

        Steele, Guy Lewis, Jr., and Sussman, Gerald Jay.  _The Revised
Report on Scheme_.  Massachusetts Institute of Technnology Artificial
Intelligence Laboratory, AI Memo No. 452, January 1978.

        Sussman, Gerald Jay, and Steele, Guy Lewis, Jr.  _Scheme: An
Interpreter for Extended Lambda Calculus_.  Massachusetts Institute of
Technnology Artificial Intelligence Laboratory, AI Memo No. 349, December
1975.


Posted on the users mailing list.