This chapter provides formal descriptions of what has already beendescribed informally in previous chapters of this report.
This section provides a formal syntax for Scheme written in an extendedBNF.
All spaces in the grammar are for legibility. Case is insignificant;for example,#x1A and#X1a are equivalent. <empty>stands for the empty string.
The following extensions to BNF are used to make the description moreconcise: <thing>* means zero or more occurrences of<thing>; and <thing>+ means at least one<thing>.
This section describes how individual tokens (identifiers,numbers, etc.) are formed from sequences of characters. The followingsections describe how expressions and programs are formed from sequencesof tokens.
<Intertoken space> may occur on either side of any token, but notwithin a token.
Tokens which require implicit termination (identifiers, numbers,characters, and dot) may be terminated by any <delimiter>, but notnecessarily by anything else.
The following five characters are reserved for future extensions to thelanguage:[]{}|
The following rules for <numR>, <complexR>, <realR>, <urealR>, <uintegerR>, and <prefixR>should be replicated forR = 2, 8, 10,and 16. There are no rules for <decimal 2>, <decimal8>, and <decimal 16>, which means that numbers containingdecimal points or exponents must be in decimal radix.
<Datum> is what theread procedure (section 6.6.2)successfully parses. Note that any string that parses as an<expression> will also parse as a <datum>.
The following grammar for quasiquote expressions is not context-free.It is presented as a recipe for generating an infinite number ofproduction rules. Imagine a copy of the following rules forD = 1, 2,3,....D keeps track of the nesting depth.
In <quasiquotation>s, a <list qq templateD> can sometimesbe confused with either an <unquotationD> or a <splicingunquotationD>. The interpretation as an<unquotation> or <splicingunquotationD> takes precedence.
This section provides a formal denotational semantics for the primitiveexpressions of Scheme and selected built-in procedures. The conceptsand notation used here are described in [29]; the notation issummarized below:
The reason that expression continuations take sequences of values insteadof single values is to simplify the formal treatment of procedure callsand multiple return values.
The boolean flag associated with pairs, vectors, and strings will be truefor mutable objects and false for immutable objects.
The order of evaluation within a call is unspecified. We mimic thathere by applying arbitrary permutationspermute andunpermute, which must be inverses, to the arguments in a call beforeand after they are evaluated. This is not quite right since it suggests,incorrectly, that the order of evaluation is constant throughout a program (forany given number of arguments), but it is a closer approximation to the intendedsemantics than a left-to-right evaluation would be.
The storage allocatornew is implementation-dependent, but it mustobey the following axiom: ifnew
L, then (new |L)
2 =false.
The definition of
is omitted because an accurate definition of would complicate the semantics without being very interesting.
If P is a program in which all variables are defined before beingreferenced or assigned, then the meaning of P is
where I* is the sequence of variables defined in P, P'is the sequence of expressions obtained by replacing every definitionin P by an assignment, <undefined> is an expression that evaluatestoundefined, and
is the semantic function that assigns meaning to expressions.
Definition of deliberately omitted.
Here and elsewhere, any expressed value other thanundefined maybe used in place ofunspecified.
This section gives macro definitions for the derived expression types interms of the primitive expression types (literal, variable, call,lambda,if,set!). See section 6.4 for a possibledefinition ofdelay.
(define-syntax cond
(syntax-rules (else =>)
((cond (else result1 result2 ...))
(begin result1 result2 ...))
((cond (test => result))
(let ((temp test))
(if temp (result temp))))
((cond (test => result) clause1 clause2 ...)
(let ((temp test))
(if temp
(result temp)
(cond clause1 clause2 ...))))
((cond (test)) test)
((cond (test) clause1 clause2 ...)
(let ((temp test))
(if temp
temp
(cond clause1 clause2 ...))))
((cond (test result1 result2 ...))
(if test (begin result1 result2 ...)))
((cond (test result1 result2 ...)
clause1 clause2 ...)
(if test
(begin result1 result2 ...)
(cond clause1 clause2 ...)))))
(define-syntax case
(syntax-rules (else)
((case (key ...)
clauses ...)
(let ((atom-key (key ...)))
(case atom-key clauses ...)))
((case key
(else result1 result2 ...))
(begin result1 result2 ...))
((case key
((atoms ...) result1 result2 ...))
(if (memv key '(atoms ...))
(begin result1 result2 ...)))
((case key
((atoms ...) result1 result2 ...)
clause clauses ...)
(if (memv key '(atoms ...))
(begin result1 result2 ...)
(case key clause clauses ...)))))
(define-syntax and
(syntax-rules ()
((and) #t)
((and test) test)
((and test1 test2 ...)
(if test1 (and test2 ...) #f))))
(define-syntax or
(syntax-rules ()
((or) #f)
((or test) test)
((or test1 test2 ...)
(let ((x test1))
(if x x (or test2 ...))))))
(define-syntax let
(syntax-rules ()
((let ((name val) ...) body1 body2 ...)
((lambda (name ...) body1 body2 ...)
val ...))
((let tag ((name val) ...) body1 body2 ...)
((letrec ((tag (lambda (name ...)
body1 body2 ...)))
tag)
val ...))))
(define-syntax let*
(syntax-rules ()
((let* () body1 body2 ...)
(let () body1 body2 ...))
((let* ((name1 val1) (name2 val2) ...)
body1 body2 ...)
(let ((name1 val1))
(let* ((name2 val2) ...)
body1 body2 ...)))))
The followingletrec macro uses the symbol<undefined>in place of an expression which returns something that when stored ina location makes it an error to try to obtain the value stored in thelocation (no such expression is defined in Scheme).A trick is used to generate the temporary names needed to avoidspecifying the order in which the values are evaluated.This could also be accomplished by using an auxiliary macro.
(define-syntax letrec
(syntax-rules ()
((letrec ((var1 init1) ...) body ...)
(letrec "generate_temp_names"
(var1 ...)
()
((var1 init1) ...)
body ...))
((letrec "generate_temp_names"
()
(temp1 ...)
((var1 init1) ...)
body ...)
(let ((var1 <undefined>) ...)
(let ((temp1 init1) ...)
(set! var1 temp1)
...
body ...)))
((letrec "generate_temp_names"
(x y ...)
(temp ...)
((var1 init1) ...)
body ...)
(letrec "generate_temp_names"
(y ...)
(newtemp temp ...)
((var1 init1) ...)
body ...))))
(define-syntax begin
(syntax-rules ()
((begin exp ...)
((lambda () exp ...)))))
The following alternative expansion forbegin does not make use ofthe ability to write more than one expression in the body of a lambdaexpression. In any case, note that these rules apply only if the bodyof thebegin contains no definitions.
(define-syntax begin
(syntax-rules ()
((begin exp)
exp)
((begin exp1 exp2 ...)
(let ((x exp1))
(begin exp2 ...)))))
The following definitionofdo uses a trick to expand the variable clauses.As withletrec above, an auxiliary macro would also work.The expression(if #f #f) is used to obtain an unspecificvalue.
(define-syntax do
(syntax-rules ()
((do ((var init step ...) ...)
(test expr ...)
command ...)
(letrec
((loop
(lambda (var ...)
(if test
(begin
(if #f #f)
expr ...)
(begin
command
...
(loop (do "step" var step ...)
...))))))
(loop init ...)))
((do "step" x)
x)
((do "step" x y)
y)))