This chapter provides formal descriptions of what has already been
described informally in previous chapters of this report.
This section provides a formal syntax for Scheme written in an extended
BNF.
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 more
concise: <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 following
sections describe how expressions and programs are formed from sequences
of tokens.
<Intertoken space> may occur on either side of any token, but not
within a token.
Tokens which require implicit termination (identifiers, numbers,
characters, and dot) may be terminated by any <delimiter>, but not
necessarily by anything else.
The following five characters are reserved for future extensions to the
language:
[ ] { } |
<token> --> <identifier> | <boolean> | <number>
| <character> | <string>
| ( | ) | #( | ' | ` | , | ,@ | .
<delimiter> --> <whitespace> | ( | ) | " | ;
<whitespace> --> <space or newline>
<comment> --> ; <all subsequent characters up to a
line break>
<atmosphere> --> <whitespace> | <comment>
<intertoken space> --> <atmosphere>*
|
<identifier> --> <initial> <subsequent>*
| <peculiar identifier>
<initial> --> <letter> | <special initial>
<letter> --> a | b | c | ... | z
<special initial> --> ! | $ | % | & | * | / | : | < | =
| > | ? | ^ | _ | ~
<subsequent> --> <initial> | <digit>
| <special subsequent>
<digit> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<special subsequent> --> + | - | .: | @
<peculiar identifier> --> + | - | ...
<syntactic keyword> --> <expression keyword>
| else | => | define
| unquote | unquote-splicing
<expression keyword> --> quote | lambda | if
| set! | begin | cond | and | or | case
| let | let* | letrec | do | delay
| quasiquote
<variable> => <any <identifier> that isn't
also a <syntactic keyword>>
<boolean> --> #t | #f
<character> --> #\ <any character>
| #\ <character name>
<character name> --> space | newline
<string> --> " <string element>* "
<string element> --> <any character other than " or \>
| \" | \\
|
<number> --> <num 2>| <num 8>
| <num 10>| <num 16>
|
The following rules for <num R>, <complex R>, <real
R>, <ureal R>, <uinteger R>, and <prefix R>
should be replicated for
R = 2, 8, 10,
and 16. There are no rules for <decimal 2>, <decimal
8>, and <decimal 16>, which means that numbers containing
decimal points or exponents must be in decimal radix.
<num R> --> <prefix R> <complex R>
<complex R> --> <real R> | <real R> @ <real R>
| <real R> + <ureal R> i | <real R> - <ureal R> i
| <real R> + i | <real R> - i
| + <ureal R> i | - <ureal R> i | + i | - i
<real R> --> <sign> <ureal R>
<ureal R> --> <uinteger R>
| <uinteger R> / <uinteger R>
| <decimal R>
<decimal 10> --> <uinteger 10> <suffix>
| . <digit 10>+ #* <suffix>
| <digit 10>+ . <digit 10>* #* <suffix>
| <digit 10>+ #+ . #* <suffix>
<uinteger R> --> <digit R>+ #*
<prefix R> --> <radix R> <exactness>
| <exactness> <radix R>
|
<suffix> --> <empty>
| <exponent marker> <sign> <digit 10>+
<exponent marker> --> e | s | f | d | l
<sign> --> <empty> | + | -
<exactness> --> <empty> | #i | #e
<radix 2> --> #b
<radix 8> --> #o
<radix 10> --> <empty> | #d
<radix 16> --> #x
<digit 2> --> 0 | 1
<digit 8> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
<digit 10> --> <digit>
<digit 16> --> <digit 10> | a | b | c | d | e | f
|
7.1.2 External representations
|
<Datum> is what the
read procedure (section
Input)
successfully parses. Note that any string that parses as an
<expression> will also parse as a <datum>.
<datum> --> <simple datum> | <compound datum>
<simple datum> --> <boolean> | <number>
| <character> | <string> | <symbol>
<symbol> --> <identifier>
<compound datum> --> <list> | <vector>
<list> --> (<datum>*) | (<datum>+ .: <datum>)
| <abbreviation>
<abbreviation> --> <abbrev prefix> <datum>
<abbrev prefix> --> ' | ` | , | ,@
<vector> --> #(<datum>*)
|
<expression> --> <variable>
| <literal>
| <procedure call>
| <lambda expression>
| <conditional>
| <assignment>
| <derived expression>
| <macro use>
| <macro block>
<literal> --> <quotation> | <self-evaluating>
<self-evaluating> --> <boolean> | <number>
| <character> | <string>
<quotation> --> '<datum> | (quote <datum>)
<procedure call> --> (<operator> <operand>*)
<operator> --> <expression>
<operand> --> <expression>
<lambda expression> --> (lambda <formals> <body>)
<formals> --> (<variable>*) | <variable>
| (<variable>+ .: <variable>)
<body> --> <definition>* <sequence>
<sequence> --> <command>* <expression>
<command> --> <expression>
<conditional> --> (if <test> <consequent> <alternate>)
<test> --> <expression>
<consequent> --> <expression>
<alternate> --> <expression> | <empty>
<assignment> --> (set! <variable> <expression>)
<derived expression> -->
(cond <cond clause>+)
| (cond <cond clause>* (else <sequence>))
| (case <expression>
<case clause>+)
| (case <expression>
<case clause>*
(else <sequence>))
| (and <test>*)
| (or <test>*)
| (let (<binding spec>*) <body>)
| (let <variable> (<binding spec>*) <body>)
| (let* (<binding spec>*) <body>)
| (letrec (<binding spec>*) <body>)
| (begin <sequence>)
| (do (<iteration spec>*)
(<test> <do result>)
<command>*)
| (delay <expression>)
| <quasiquotation>
<cond clause> --> (<test> <sequence>)
| (<test>)
| (<test> => <recipient>)
<recipient> --> <expression>
<case clause> --> ((<datum>*) <sequence>)
<binding spec> --> (<variable> <expression>)
<iteration spec> --> (<variable> <init> <step>)
| (<variable> <init>)
<init> --> <expression>
<step> --> <expression>
<do result> --> <sequence> | <empty>
<macro use> --> (<keyword> <datum>*)
<keyword> --> <identifier>
<macro block> -->
(let-syntax (<syntax spec>*) <body>)
| (letrec-syntax (<syntax spec>*) <body>)
<syntax spec> --> (<keyword> <transformer spec>)
|
The following grammar for quasiquote expressions is not context-free.
It is presented as a recipe for generating an infinite number of
production rules. Imagine a copy of the following rules for D = 1, 2,3, .... D keeps track of the nesting depth.
<quasiquotation> --> <quasiquotation 1>
<qq template 0> --> <expression>
<quasiquotation D> --> `<qq template D>
| (quasiquote <qq template D>)
<qq template D> --> <simple datum>
| <list qq template D>
| <vector qq template D>
| <unquotation D>
<list qq template D> --> (<qq template or splice D>*)
| (<qq template or splice D>+ .: <qq template D>)
| '<qq template D>
| <quasiquotation D+1>
<vector qq template D> --> #(<qq template or splice D>*)
<unquotation D> --> ,<qq template D-1>
| (unquote <qq template D-1>)
<qq template or splice D> --> <qq template D>
| <splicing unquotation D>
<splicing unquotation D> --> ,@<qq template D-1>
| (unquote-splicing <qq template D-1>)
|
In <quasiquotation>s, a <list qq template D> can sometimes
be confused with either an <unquotation D> or a <splicing
unquotation D>. The interpretation as an
<unquotation> or <splicing
unquotation D> takes precedence.
<transformer spec> -->
(syntax-rules (<identifier>*) <syntax rule>*)
<syntax rule> --> (<pattern> <template>)
<pattern> --> <pattern identifier>
| (<pattern>*)
| (<pattern>+ . <pattern>)
| (<pattern>* <pattern> <ellipsis>)
| #(<pattern>*)
| #(<pattern>* <pattern> <ellipsis>)
| <pattern datum>
<pattern datum> --> <string>
| <character>
| <boolean>
| <number>
<template> --> <pattern identifier>
| (<template element>*)
| (<template element>+ . <template>)
| #(<template element>*)
| <template datum>
<template element> --> <template>
| <template> <ellipsis>
<template datum> --> <pattern datum>
<pattern identifier> --> <any identifier except ...>
<ellipsis> --> <the identifier ...>
|
7.1.6 Programs and definitions
|
<program> --> <command or definition>*
<command or definition> --> <command>
| <definition>
| <syntax definition>
| (begin <command or definition>+)
<definition> --> (define <variable> <expression>)
| (define (<variable> <def formals>) <body>)
| (begin <definition>*)
<def formals> --> <variable>*
| <variable>* .: <variable>
<syntax definition> -->
(define-syntax <keyword> <transformer spec>)
|
This section provides a formal denotational semantics for the primitive
expressions of Scheme and selected built-in procedures. The concepts
and notation used here are described in
[Stoy77].
Note: The formal semantics section was written in LaTeX which
is incompatible with TeXinfo. See the Formal semantics section of
the original document from which this was derived.
7.3 Derived expression types
|
This section gives macro definitions for the derived expression types in
terms of the primitive expression types (literal, variable, call,
lambda,
if,
set!). See section
Control features for a possible
definition of
delay.
(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 following
letrec macro uses the symbol
<undefined>
in place of an expression which returns something that when stored in
a location makes it an error to try to obtain the value stored in the
location (no such expression is defined in Scheme).
A trick is used to generate the temporary names needed to avoid
specifying 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 for
begin does not make use of
the ability to write more than one expression in the body of a lambda
expression. In any case, note that these rules apply only if the body
of the
begin contains no definitions.
(define-syntax begin
(syntax-rules ()
((begin exp)
exp)
((begin exp1 exp2 ...)
(let ((x exp1))
(begin exp2 ...)))))
|
The following definition
of
do uses a trick to expand the variable clauses.
As with
letrec above, an auxiliary macro would also work.
The expression
(if #f #f) is used to obtain an unspecific
value.
(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)))
|