[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Message a011267 LONG message - part 1

Received: from csnet-relay.arpa by CSNET-SH.ARPA id a028166; 18 Mar 85 13:26 EST
Date:     Mon, 18 Mar 85 10:55:42 EST
From:     CSNET-RELAY Memo Service (MMDF) <mmdf@CSNET-RELAY.ARPA>
Subject:  Failed mail  (msg.a011267)
Sender:   mmdf@CSNET-RELAY.ARPA
To:       Postmaster@CSNET-RELAY.ARPA

    Your message could not be delivered to
'scheme@mit-mc.ARPA (host: mit-mc.arpa) (queue: smtp)' for the following
reason:  ' Message is too large to mail; use FTP.'

    Your message follows:

Received: from indiana by csnet-relay.csnet id a011267; 18 Mar 85 9:36 EST
Date: Mon, 18 Mar 85 01:24:29 est
From: willc@Indiana (Will Clinger)
Received: by iuvax.UUCP; id AA06606; Mon, 18 Mar 85 01:24:29 est
To: scheme@mit-mc
Subject: DRAFT of Revised Revised Report (LONG message)

Here is the DRAFT of the final report on the Brandeis workshop.
It is missing all its appendices, and a couple of sections that
deal with the lexical syntax of numbers need more work.  Please
read it and tell me what you think.  We'd like to have your
comments by 1 April so we can send it to press.

The font information has been stripped for posting to
scheme@mit-mc. Some ambiguities probably result, but please don't
get upset about them.

If you have anything more to say about Chris Hanson's work on
strings, please say it soon.  We'd like to include Chris's work
in this report.
				-- Will Clinger

                        Table of Contents

Part I: Introduction to Scheme 

    I.0   Brief history of Scheme                                
    I.1   Syntax of Scheme                                       
    I.2   Semantics of Scheme                                    

Part II: A catalog of Scheme 

   II.0   Notational conventions                                 
   II.1   Special forms                                          
   II.2   Booleans                                               
   II.3   Equivalence predicates                                 
   II.4   Pairs and lists                                        
   II.5   Symbols                                                
   II.6   Numbers (part 1)                                       
   II.7   Numbers (part 2)                                       
   II.8   Strings                                                
   II.9   Vectors                                                
   II.10  The object table                                        
   II.11  Procedures                                             
   II.12  Ports                                                  
   II.13  Input                                                  
   II.14  Output                                                 


Index (not yet ready)                                            


This report is primarily the work of a group of people who met 
at Brandeis University for two days in October 1984.  The 
participants at that workshop were Hal Abelson (MIT), Norman 
Adams (Yale), David Bartley (Texas Instruments), Gary Brooks, 
(Texas Instruments, Indiana University), William Clinger 
(Indiana University), Dan Friedman (Indiana University), Robert 
Halstead (MIT), Chris Hanson (MIT), Chris Haynes (Indiana 
University), Eugene Kohlbecker (Indiana University), Don Oxley 
(Texas Instruments), Jonathan Rees (MIT), Bill Rozas (MIT), 
Gerald Sussman (MIT), and Mitchell Wand (Indiana University, 
Brandeis).  Kent Pitman (MIT) made valuable contributions to the 
agenda for the workshop but was unable to attend the sessions.  

We would like also to thank the following people for their 
comments and criticisms in the months following the workshop: 
Kent Dybvig, Andy Freeman, Yekta Gursel, Paul Hudak, Chris 
Lindblad, Guy Steele Jr.  

We thank Dan Friedman and Chris Haynes for permission to use 
text from the Scheme 311 Version 4 reference manual.  We 
acknowledge the influence of manuals for MIT Scheme, T, Scheme 
84, and Common Lisp.  
Part I: Introduction to Scheme 

I.0 Brief history of Scheme 

Scheme is a programming language invented by Guy Lewis Steele Jr 
and Gerald Jay Sussman.  It is a statically scoped dialect of 
Lisp with an exceptionally clear and simple semantics.  

The first description of Scheme was written in 1975 [\ref].  A 
Revised Report [\ref] appeared in 1978, which described the 
evolution of the language as its MIT implementation was upgraded 
to support an innovative compiler [\ref].  Three distinct 
projects began in 1981 and 1982 to use variants of Scheme for 
courses at MIT, Yale, and Indiana University [\ref, ref, ref].  
An excellent introductory computer science textbook using Scheme 
was published in 1984 [\ref].  

As might be expected of a language used primarily for education 
and research, Scheme has always evolved rapidly.  This was no 
problem when Scheme was used only within MIT, but as Scheme 
became more widespread local subdialects began to diverge until 
students and researchers occasionally found it difficult to 
understand code written at other sites.  Fifteen representatives 
of the major implementations of Scheme therefore met in October 
1984 to work toward a better and more widely accepted standard 
for Scheme.  This paper reports their unanimous recommendations 
augmented by committee work in the areas of input/output and 

Scheme shares with Common Lisp [\ref] the goal of a core 
language common to several implementations.  Scheme differs from 
Common Lisp in that the purpose of the common language has as 
much to do with porting ideas as with porting code.  It is 
appropriate therefore that Scheme is much smaller, is less 
pervasively specified, and will evolve faster than Common Lisp.  

I.1 Syntax 

Formal definitions of the lexical and context-free syntaxes of 
Scheme will be added as appendices.  


Most identifiers allowed by other programming languages are also 
acceptable to Scheme.  The precise rules for forming identifiers 
vary among implementations of Scheme, but in all implementations 
a sequence of characters that contains no special characters and 
begins with a character that cannot begin a number is an 
identifier.  There may be other identifiers as well, and in 
particular the following are identifiers: 

			   + - 1+ -1+

It is guaranteed that the following characters cannot begin a 
number, so identifiers other than the four listed above should 
begin with one of: 

       a b c d e f g h i j k l m n o p q r s t u v w x y z
       A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
		     ! $ % & * / : < = > ? ~

Subsequent characters of the identifier should be drawn from: 

       a b c d e f g h i j k l m n o p q r s t u v w x y z
       A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
		       0 1 2 3 4 5 6 7 8 9
		  ! $ % & * / : < = > ? ^ _ . ~

The case in which the letters of an identifier are typed is 
immaterial.  For example, Foo is the same identifier as FOO.  

The following characters are special, and should never be used 
in an identifier: 

                      ) ( ] [ } { " ; blank

Scheme deliberately does not specify whether the following 
characters can be used in identifiers: 

			  # ' ` , @ \ |

Rationale: Some implementations might want to use backwhack ( \) 
and vertical bar ( | ) as in Common Lisp.  As for the others 
there are two schools of thought.  One school argues that 
disallowing special characters in identifiers allows the 
computer to catch more typing errors.  The other school agrees 
only for special characters that come in pairs, because errors 
that involve only the unpaired special characters are easy to 


For a description of the notations used for numbers, see section 
II.7.  A concise summary of the notations used to write numbers 
will be added to this section, and a formal description will be 
part of the appendix on lexical syntax.  


A semicolon indicates the start of a comment.  The comment 
continues to the end of the line on which the semicolon appears.  
Comments are invisible to Scheme, but the end of the line is 
visible as whitespace.  This prevents a comment from appearing 
in the middle of an identifier or number.  Comments may appear 
inside a string that extends over more than one line, but it is 
probably a bad idea to write such strings because their contents 
are implementation-dependent.  

Other notations 

Left and right parentheses are used for grouping and to notate 
lists as described in section II.4.  Left and right square 
brackets and curly braces are not used in Scheme right now but 
are reserved for unspecified future uses.  

The quote (') and backquote (`) characters are used to indicate 
constant or almost-constant data as described in section II.1.  
The comma is used together with the backquote, and the atsign 
(@) is used together with the comma.  

The doublequote character is used to notate strings as described 
in section II.8.  

The sharp sign (octathorp) is used for a variety of purposes 
depending on the character that follows it.  A sharp sign 
followed by a left parenthesis signals the beginning of a 
vector, as described in section II.9.  A sharp sign followed by 
an exclamation point is used to notate one of the special values 
#!true, #!false, and #!null.  A sharp sign followed by a 
backslash is used to notate characters as described in section 
II.8.  A sharp sign followed by any of a number of letters is 
used to notate numbers as described in section II.7.  

Context free grammar for Scheme 

The following grammar is ambiguous because a <special form> 
looks like a <procedure call>.  Some implementations resolve the 
ambiguity by reserving the identifiers that serve as keywords of 
special forms, while other implementations allow the keyword 
meaning of an identifier to be shadowed by lexical bindings.  

    <expression>  ::=  <constant>
                    |  <identifier>
                    |  <special form>
                    |  <procedure call>

    <constant>  ::=  <numeral>  |  #!true  |  #!false  |  #!null
                  |  (quote <datum>)  |  '<datum>

    <special form>  ::=  (<keyword> ...)

    <procedure call>  ::=  (<expression> <arguments>)

    <arguments>  ::=  <empty>  |  <expression> <arguments>

<datum> stands for any written representation of a Scheme 
object, as described in the sections that follow.  <identifier> 
and <numeral> have already been described informally.  <special 
form> stands for one of the special forms whose syntax is 
described in section II.1.  For uniformity the other kinds of 
expressions are also described in that section as though they 
were special forms.  
I.2 Semantics 

The formal semantics of Scheme will be the subject of an 
appendix to be added.  The detailed informal semantics of Scheme 
is the subject of Part II.  This section gives a quick review of 
Scheme's major characteristics.  

Scheme is a statically scoped programming language, meaning that 
each use of an identifier is associated with a lexically 
apparent binding of that identifier.  In this respect Scheme is 
like Algol 60, Pascal, and C but unlike dynamically scoped 
languages such as APL and traditional Lisp.  

Scheme has latent as opposed to manifest types, which means that 
types are associated with values (also called objects) rather 
than with variables.  (Some authors refer to languages with 
latent types as weakly typed or dynamically typed languages.) 
Other languages with latent types are APL, Snobol, and other 
dialects of Lisp.  Languages with manifest types (sometimes 
referred to as strongly typed or statically typed languages) 
include Algol 60, Pascal, and C.  

All objects created in the course of a Scheme computation, 
including all procedures and variables, have unlimited extent.  
This means in effect that no Scheme object is ever destroyed.  
The reason that implementations of Scheme do not (usually!) run 
out of storage is that they are permitted to reclaim the storage 
occupied by an object if they can prove mathematically that the 
object cannot possibly matter to any future computation.  Scheme 
is a practical programming language only because there exist 
fairly efficient "garbage collection" algorithms for performing 
these proofs.  Other languages in which most objects have 
unlimited extent include APL and Common Lisp.  

Scheme procedures are objects in their own right.  Procedures 
can be created dynamically, stored in data structures, returned 
as results of procedures, and so on.  Other languages with these 
properties include Common Lisp, ML, and KRC.  

Arguments to Scheme procedures are always passed by value, which 
means that the actual argument expressions are evaluated before 
the procedure actually gains control, whether the procedure 
needs the result of the evaluation or not.  ML, C, and APL are 
three good examples of other languages that always pass 
arguments by value.  KRC is a good example of a language that 
passes arguments by name, so that an argument expression is 
evaluated only if its value is needed by the procedure.  
Part II: A catalog of Scheme 

II.0 Notational conventions 

This part of the report is a catalog of the special forms and 
procedures that make up Scheme.  The special forms are described 
in section II.1, and the procedures are described in the 
following sections.  Each section is organized into entries, 
with one entry (usually) for each special form or procedure.  
Each entry begins with a header line that includes the name of 
the special form or procedure in bold face type within a 
template for the special form or a call to the procedure.  The 
names of the arguments to a procedure are italicized, as are the 
syntactic components of a special form.  A notation such as 

                            expr ...

indicates zero or more occurrences of expr, and so 

                         expr1 expr2 ...

indicates at least one expr.  

At the right of the header line one of the following categories 
will appear: 

                special form
                essential special form
                essential constant
                essential variable
                essential procedure

A special form is a syntactic class of expressions, usually 
identified by a keyword.  A constant is something that is 
lexically recognizable as a constant.  A variable is an 
identifier that is bound to a location in which values (also 
called objects) can be stored.  Those variables that initially 
hold procedure values are identified as procedures.  

Implementations are free to omit features of Scheme or to add 
extensions, provided the extensions are not in conflict with the 
language reported here.  It is guaranteed, however, that every 
implementation of Scheme will support the essential special 
forms, constants, variables, and procedures.  

Any Scheme value can be used as a boolean expression for the 
purposes of a conditional test.  As explained in section II.2, 
most values count as true, but a few -- notably #!false -- count 
as false.  This manual uses the word "true" to refer to any 
Scheme value that counts as true in a conditional expression, 
and the word "false" to refer to any Scheme value that counts as 
II.1.  Special forms 

Identifiers have two uses within Scheme programs.  When an 
identifier appears within a quoted constant (see quote), it is 
being used as data as described in the section on symbols.  
Otherwise it is being used as a name.  There are two kinds of 
things that an identifier can name in Scheme: special forms and 
variables.  A special form is a syntactic class of expressions, 
and an identifier that names a special form is called the 
keyword of that special form.  A variable, on the other hand, is 
a location where a value can be stored.  An identifier that 
names a variable is said to be bound to that location.  The set 
of all such bindings in effect at some point in a program is 
known as the environment in effect at that point.  

Certain special forms are used to allocate storage for new 
variables and to bind identifiers to those new variables.  The 
most fundamental of these binding constructs is the lambda 
special form, because all other binding constructs can be 
explained in terms of lambda expressions.  The other binding 
constructs are the let, let*, letrec, internal definition (see 
define), rec, define!, defrec!, and do special forms.  

Like Algol or Pascal, and unlike most other dialects of Lisp 
except for Common Lisp, Scheme is a statically scoped language 
with block structure.  To each place where an identifier is 
bound in a program there corresponds a region of the program 
within which the binding is effective.  The region varies 
according to the binding construct that establishes the binding; 
if the binding is established by a lambda expression, for 
example, then the region is the entire lambda expression.  Every 
use of an identifier in a variable reference or assignment 
refers to the binding of the identifier that set up the 
innermost of the regions containing the use.  If there is no 
binding of the identifier whose region contains the use, then 
the use refers to the binding for the identifier that was in 
effect when Scheme started up, if any; if there is no binding 
for the identifier, it is said to be unbound.  

variable                                   essential special form

An expression consisting of an identifier that is not the 
keyword of a special form is a variable reference.  The value 
obtained for the variable reference is the value stored in the 
location to which variable is bound.  An error is signalled if 
variable is unbound.  

(procedure arg1 ...)                       essential special form

A list of expressions whose first element is not the keyword of 
a special form indicates a procedure call.  The procedure and 
argument expressions are evaluated and the procedure is passed 
the values of the argument expressions.  In constrast to other 
dialects of Lisp the order of evaluation is not specified, and 
the procedure expression and the argument expressions are always 
evaluated in exactly the same way.  

                (+ 3 4)                 -->  7
                ((if #!false + *) 3 4)  -->  12

(quote constant)                           essential special form 
'constant                                  essential special form

Evaluates to constant.  This notation is used to include literal 
constants in Scheme code.  

                (quote a)               -->  a
                (quote #(a b c))        -->  #(a b c)
                (quote (+ 1 2))         -->  (+ 1 2)

(quote constant) may be abbreviated as 'constant.  The two 
notations are equivalent in all respects.  

                'a                      -->  a
                '#(a b c)               -->  #(a b c)
                '(+ 1 2)                -->  (+ 1 2)
                '(quote a)              -->  (quote a)
                ''a                     -->  (quote a)

Numbers, strings, and the constants #!true, #!false, and #!null 
need not be quoted.  

                '"abc"                  -->  "abc"
                "abc"                   -->  "abc"
                '145932                 -->  145932
                145932                  -->  145932
                '#!true                 -->  #!true
                #!true                  -->  #!true

(lambda (var1 ...) expr)                   essential special form

Each var must be an identifier.  The lambda expression evaluates 
to a procedure with formal argument list (var1 ...) and 
procedure body expr.  The environment in effect when the lambda 
expression was evaluated is remembered as part of the procedure.  
When the procedure is later called with some actual arguments, 
the environment in which the lambda expression was evaluated 
will be extended by binding the identifiers in the formal 
argument list to fresh locations, the corresponding actual 
argument values will be stored in those locations, and expr will 
then be evaluated in the extended environment.  The result of 
expr will be returned as the result of the procedure call.  

        (lambda (x) (+ x x))            -->  #<PROCEDURE>
        ((lambda (x) (+ x x)) 4)        -->  8
        (define reverse-subtract
          (lambda (x y) (- y x)))       -->  reverse-subtract
        (reverse-subtract 7 10)         -->  3
        (define foo
          (let ((x 4))
            (lambda (y) (+ x y))))      -->  foo
        (foo 6)                         -->  10

(lambda (var1 ...) expr1 expr2 ...)        essential special form

Equivalent to (lambda (var1 ...) (begin expr1 expr2 ...)).  

(lambda var expr1 expr2 ...)               essential special form

Returns a procedure that when later called with some arguments 
will bind var to a fresh location, convert the sequence of 
actual arguments into a list, and store that list in the binding 
of var.  

        ((lambda x x) 3 4 5 6)          -->  (3 4 5 6)

One last variation on the formal argument list provides for a 
so-called rest argument.  If a space/dot/space sequence precedes 
the last argument in the formal argument list, then the value 
stored in the binding of the last formal argument will be a list 
of the actual arguments left over after all the other actual 
arguments have been matched up against the formal arguments.  

        ((lambda (x y . z) z) 3 4 5 6)  -->  (5 6)

(if condition consequent alternative)      essential special form
(if condition consequent)                  essential special form

First evaluates condition.  If it yields a true value (see 
section II.2), then consequent is evaluated and its value is 
returned.  Otherwise alternative is evaluated and its value is 
returned.  If no alternative is specified, then the if 
expression is evaluated only for its effect, and the result of 
the expression is unspecified.  

        (if (>? 3 2) 'yes 'no)          -->  yes
        (if (>? 2 3) 'yes 'no)          -->  no
        (if (>? 3 2) (- 3 2) (+ 3 2))   -->  1

(cond clause1 clause2 ...)                 essential special form

Each clause must be a list of one or more expressions.  The 
first expression in each clause is a boolean expression that 
serves as the guard for the clause.  The guards are evaluated in 
order until one of them evaluates to a true value (see section 
II.2).  When a guard evaluates true, then the remaining 
expressions in its clause are evaluated in order, and the result 
of the last expression in the selected clause is returned as the 
result of the entire expression.  If the selected clause 
contains only the guard, then the value of the guard is returned 
as the result.  If all tests evaluate to false values, then the 
result of the conditional expression is unspecified.  

        (cond ((>? 3 2) 'greater)
              ((<? 3 2) 'less))         --> greater

The special keyword else may be used as a guard to obtain the 
effect of an otherwise clause.  

        (cond ((>? 3 3) 'greater)
              ((<? 3 3) 'less)
              (else 'equal))            -->  equal

The above forms for the clauses are essential.  Some 
implementations support yet another form of clause such that 

        (cond (form1 => form2) ...)

is equivalent to 

        (let ((form1_result form1)
              (thunk2 (lambda () form2))
              (thunk3 (lambda () (cond ...))))
          (if form1_result
              ((thunk2) form1_result)

(case expr clause1 clause2 ...)                      special form

Each clause is a list whose first element is a selector followed 
by one or more expressions.  Each selector should be a list of 
values.  The selectors are not evaluated.  Instead expr is 
evaluated and its result is compared against successive 
selectors using the memv procedure until a match is found.  Then 
the expressions in the selected clause are evaluated from left 
to right and the result of the last expression in the clause is 
returned as the result of the case expression.  If no selector 
matches then the result of the case expression is unspecified.  

        (case (* 2 3)
          ((2 3 5 7) 'prime)
          ((1 4 6 8 9) 'composite))     -->  composite
        (case (car '(c d))
          ((a) 'a)
          ((b) 'b))                     -->  unspecified

The special keyword else may be used as a selector to obtain the 
effect of an otherwise clause.  

        (case (car '(c d))
          ((a e i o u) 'vowel)
          ((y) 'y)
          (else 'consonant))            -->  consonant

(and expr1 ...)                                      special form

Evaluates the exprs from left to right, returning false as soon 
as one evaluates to a false value (see section II.2).  Any 
remaining expressions are not evaluated.  If all the expressions 
evaluate to true values, the value of the last expression is 

        (and (=? 2 2) (>? 2 1))         -->  #!true
        (and (=? 2 2) (<? 2 1))         -->  #!false
        (and 1 2 'c '(f g))             -->  (f g)

(or expr1 ...)                                       special form

Evaluates the exprs from left to right, returning the value of 
the first expr that evaluates to a true value (see section 
II.2).  Any remaining expressions are not evaluated.  If all 
expressions evaluate to false values, false is returned.  

        (or (=? 2 2) (>? 2 1))          -->  #!true
        (or (=? 2 2) (<? 2 1))          -->  #!true
        (or #!false #!false #!false)    -->  #!false
        (or (memq 'b '(a b c)) (/ 3 0)) -->  (b c)

(let ((var1 form1) ...) expr1 expr2 ...)   essential special form

Evaluates the forms in the current environment (in some 
unspecified order), binds the vars to fresh locations holding 
the results, and then evaluates the exprs in the extended 
environment, returning the value of the last one.  Each binding 
of a var has expr1 expr2 ...  as its region.  

        (let ((x 2)
              (y 3))
          (* x y))                      -->  6

        (let ((x 2)
              (y 3))
          (let ((foo (lambda (z)
                       (+ x y z)))
                (x 7))
            (foo 4)))                   -->  9

let and letrec give Scheme a block structure.  The difference 
between let and letrec is that in a let the forms are not within 
the regions of the vars being bound.  See letrec.  

Some implementations of Scheme permit a "named let" syntax in 

    (let name ((var1 form1) ...) expr1 expr2 ...)

is equivalent to 

    ((rec name (lambda (id1 ...) expr1 expr2 ...))
     form1 ...)

(let* ((var1 form1) ...) expr1 expr2 ...)            special form

Similar to let, but the bindings are performed sequentially from 
left to right and the region of a binding indicated by (var 
form) is that part of the let* expression to the right of the 
binding.  Thus the second binding is done in an environment in 
which the first binding is visible, and so on.  

(letrec ((var1 form1) ...) expr1 expr2 ...)essential special form

Binds the vars to fresh locations holding undefined values, 
evaluates the forms in the resulting environment (in some 
unspecified order), assigns to each var the result of the 
corresponding form, evaluates the exprs sequentially in the 
resulting environment, and returns the value of the last expr.  
Each binding of a var has the entire letrec expression as its 
region, making it possible to define mutually recursive 
procedures.  See let.  

        (letrec ((x 2)
                 (y 3))
          (letrec ((foo (lambda (z)
                          (+ x y z)))
                   (x 7))
            (foo 4)))                   -->  14

        (letrec  ((even? (lambda (n)
                           (if (zero? n)
                               (odd? (-1+ n)))))
                  (odd? (lambda (n)
                          (if (zero? n)
                              (even? (-1+ n))))))
          (even? 88))
                                        -->  #!true

One restriction on letrec is very important: it must be possible 
to evaluate each form without referring to the value of a var.  
If this restriction is violated, then the effect is undefined, 
and an error may be signalled during evaluation of the forms.  
The restriction is necessary because Scheme uses call by value 
rather than call by name.  In the most common uses of letrec, 
all the forms are lambda expressions and the restriction is 
satisfied automatically.  

(rec var expr)                                       special form

Equivalent to (letrec ((var expr)) var).  rec is useful for 
defining self-recursive procedures.  

(named-lambda (name var1 ...) expr ...)              special form

Equivalent to 

        (rec name (lambda (var1 ...) expr ...))

Rationale: Some implementatations may find it easier to provide 
good debugging information when named-lambda is used instead of 

(define var expr)                          essential special form

When typed at top level (so that it is not nested within any 
other expression), this form has essentially the same effect as 
(set! var expr) if var is bound.  If var is not bound, however, 
then the define form will bind var before performing the 
assignment, whereas it would be an error to perform a set! on an 
unbound identifier.  The value returned by a define form is not 

    (define add3 (lambda (x) (+ x 3)))  -->  unspecified
    (add3 3)                            -->  6
    (define first car)                  -->  unspecified
    (first '(1 2))                      -->  1

The semantics just described is essential.  Some implementations 
also allow define expressions to appear at the beginning of the 
body of a lambda, named-lambda, let, let*, or letrec expression.  
Such expressions are known as internal definitions as opposed to 
the top level definitions described above.  The variable defined 
by an internal definition is local to the body of the lambda, 
named-lambda, let, let*, or letrec expression.  That is, var is 
bound rather than assigned, and the region set up by the binding 
is the entire body of the lambda, named-lambda, let, let*, or 
letrec expression.  For example, 

        (let ((x 5))
          (define foo
            (lambda (y)
              (bar x y)))
          (define bar
            (lambda (a b)
              (+ (* a b) a)))
          (foo (+ x 3)))                -->  45

Internal definitions can always be converted into an equivalent 
letrec expression.  For example, the let expression in the above 
example is equivalent to 

            (let ((x 5))
              (letrec ((foo (lambda (y)
                              (bar x y)))
                       (bar (lambda (a b)
                              (+ (* a b) a))))
                (foo (+ x 3))))

(define (var0 var1 ...) expr1 expr2 ...)             special form
(define (form var1 ...) expr1 expr2 ...)             special form

The first form, where var0 is an identifier, is equivalent to 

  (define var0 (rec var0 (lambda (var1 ...) expr1 expr2 ...))).

The second form, where form is a list, is sometimes convenient 
for defining a procedure that returns another procedure as its 
result.  It is equivalent to 

  (define form (lambda (var1 ...) expr1 expr2 ...)).

(define! var expr)                                   special form

If var is bound, then the define! form is equivalent to the 
corresponding set!.  If var is unbound, however, define! binds 
var in the global environment before performing the assignment.  

Rationale: This makes sense only for implementations with a 
distinguished global environment.  

(defrec! var expr)                                   special form

Equivalent to (define! var (rec var expr)).  

(set! var expr)                            essential special form

Stores the value of expr in the location to which var is bound.  
expr is evaluated but var is not.  The result of the set! 
expression is unspecified.  

                (set! x 4)              -->  unspecified
                (1+ x)                  -->  5

Rationale: set! expressions are Scheme's assignment statements.  
Assignment statements are seldom used in good Scheme code.  
Their major uses are to initialize variables accessed 
interactively and to construct objects with local state.  

(begin expr1 expr2 ...)                    essential special form

Evaluates the exprs sequentially from left to right and returns 
the value of the last expr.  Used to sequence side effects such 
as input and output.  

        (begin (set! x 5)
               (1+ x))                  -->  6
        (begin (display "4 plus 1 equals ")
               (display (1+ 4)))
                        4 plus 1 equals 5

A number of special forms such as lambda and letrec implicitly 
treat their bodies as begin expressions.  

(sequence expr1 expr2 ...)                           special form

sequence is synonymous with begin.  

Rationale: sequence was used in the Abelson and Sussman text, 
but it should not be used in new code.  

(do ((var1 init1 step1) ...)                         special form
    (test expr1 ...)
    stmt1 ...)

The do special form is an extremely general albeit complex 
iteration macro.  Each var must be an identifier and each init 
and step must be expressions.  The init expressions are 
evaluated (in some unspecified order), the vars are bound to 
fresh locations, the results of the init expressions are stored 
in the bindings of the vars, and then the iteration phase 

Each iteration begins by evaluating test; if the result is false 
(see section II.2), then the stmts are evaluated in order for 
effect, the steps are evaluated (in some unspecified order), the 
results of the step expressions are stored in the bindings of 
the vars, and the next iteration begins.  

If test evaluates true, then the exprs are evaluated from left 
to right and the value of the last expr is returned as the value 
of the do expression.  If no exprs are present, then the value 
of the do expression is unspecified.  

The region set up by the binding of a var consists of the entire 
do expression except for the inits.  

A step may be omitted, in which case the corresponding var is 
not updated.  When the step is omitted the init may be omitted 
as well, in which case the initial value is not specified.  

    (do ((vec (make-vector 5))
         (i 0 (1+ i)))
        ((=? i 5) vec)
        (vector-set! vec i i))          -->  #(0 1 2 3 4)

    (let ((x '(1 3 5 7 9)))
      (do ((x x (cdr x))
           (sum 0 (+ sum (car x))))
          ((null? x) sum)))             -->  25

The do special form is essentially the same as the do macro in 
Common Lisp.  The main difference is that in Scheme the 
identifier return is not bound; programmers that want to bind 
return as in Common Lisp must do so explicitly (see 

`pattern                                       macro special form

The backquote special form is useful for constructing a list 
structure when most but not all of the desired structure is 
known in advance.  If no commas appear within the pattern, the 
result of evaluating `pattern is equivalent (in the sense of 
equal?) to the result of evaluating 'pattern.  If a comma 
appears within the pattern, however, the expression following 
the comma is evaluated and its result is inserted into the 
structure instead of the comma and the expression.  If a comma 
appears followed immediately by an at-sign (@), then the 
following expression must evaluate to a list; the opening and 
closing parentheses of the list are then "stripped away" and the 
elements of the list are inserted in place of the 
comma/at-sign/expression sequence.  

  `(a ,(+ 1 2) ,@(mapcar 1+ '(4 5 6)) b)  -->  (a 3 5 6 7 b)
  `(((foo ,(- 10 3)) ,@(cdr '(c)) cons))  -->  (((foo 7) cons))

Scheme does not have any standard facility for defining new 
special forms.  

Rationale: The ability to define new special forms creates 
numerous problems.  All current implementations of Scheme have 
macro facilities that solve those problems to one degree or 
another, but the solutions are quite different and it isn't 
clear at this time which solution is best, or indeed whether any 
of the solutions are truly adequate.  Rather than standardize, 
we are encouraging implementations to continue to experiment 
with different solutions.  

The main problems with traditional macros are: They must be 
defined to the system before any code using them is loaded; this 
is a common source of obscure bugs.  They are usually global; 
macros can be made to follow lexical scope rules as in Common 
Lisp's macrolet, but many people find the resulting scope rules 
confusing.  Unless they are written very carefully, macros are 
vulnerable to inadvertant capture of free variables; to get 
around this, for example, macros may have to generate code in 
which procedure values appear as quoted constants.  There is a 
similar problem with keywords if the keywords of special forms 
are not reserved.  If keywords are reserved, then either macros 
introduce new reserved words, invalidating old code, or else 
special forms defined by the programmer do not have the same 
status as special forms defined by the system.  
II.2.  Booleans 

The standard boolean objects for truth and falsity are written 
as #!true and #!false.  What really matters, though, are the 
objects that the Scheme conditional expressions (if, cond, and, 
or, do) will treat as though they were true or false.  The 
phrase "a true value" (or sometimes just "true") means any 
object treated as true by the conditional expressions, and the 
phrase "a false value" (or "false") means any object treated as 
false by the conditional expressions.  

Of all the standard Scheme values, only #!false and the empty 
list count as false in conditional expressions.  #!true, pairs 
(and therefore lists), symbols, numbers, strings, vectors, and 
procedures all count as true.  

The empty list counts as false for historical reasons only, and 
programs should not rely on this because future versions of 
Scheme will probably do away with this nonsense.  

Programmers accustomed to other dialects of Lisp should beware 
that Scheme has already done away with the nonsense that 
identifies the empty list with the symbol nil.  

#!false                                        essential constant

#!false is the boolean value for falsity.  The #!false object is 
self-evaluating.  That is, it does not need to be quoted in 

                        '#!false        -->  #!false
                        #!false         -->  #!false

#!true                                         essential constant

#!true is the boolean value for truth.  The #!true object is 
self-evaluating, and does not need to be quoted in programs.  

(not obj)                                     essential procedure

Returns #!true if obj is false and returns #!false otherwise.  

nil                                                      variable
t                                                        variable

As a crutch for programmers accustomed to other dialects of 
Lisp, some implementations provide variables nil and t whose 
initial values are #!false and #!true respectively.  These 
variables should not be used in new code.  
II.3.  Equivalence predicates 

A predicate is a procedure that always returns #!true or 
#!false.  Of the equivalence predicates described in this 
section, eq? is the most discriminating while equal? is the most 
liberal.  eqv? is very slightly less discriminating than eq?.  

(eq? obj1 obj2)                               essential procedure

Returns #!true if obj1 is identical in all respects to obj2, 
otherwise returns #!false.  If there is any way at all that a