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. The syntax for the entire language, including features which are not essential, is given here.
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.
<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> which 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> --> <real> | <real> + <ureal> i
| <real> - <ureal> i | <real> @ <real>
<real> --> <sign> <ureal>
<ureal> --> <ureal 2> | <ureal 8> | <ureal 10> | <ureal 16>
The following rules for <ureal R>, <uinteger R>, and <prefix R> should be replicated for R = 2, 8, 10, and 16:
<ureal R> --> <prefix R> <uinteger R> <suffix>
| <prefix R> <uinteger R> / <uinteger R> <suffix>
| <prefix R> . <digit R>+ #* <suffix>
| <prefix R> <digit R>+ . <digit R>* #* <suffix>
| <prefix R> <digit R>+ #* . #* <suffix>
<prefix R> --> <radix R> <exactness> <precision>
| <radix R> <precision> <exactness>
| <exactness> <radix R> <precision>
| <exactness> <precision> <radix R>
| <precision> <radix R> <exactness>
| <precision> <exactness> <radix R>
<uinteger R> --> <digit R>+ #*
<sign> --> <empty> | + | -
<suffix> --> <empty> | e <sign> <digit>+
<exactness> --> <empty> | #i | #e
<precision> --> <empty> | #s | #l
<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> | a | b | c | d | e | f
<Datum> is what the read procedure (section see section 6.10.2 Input)
successfully parses. Note that any string which 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>
<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> <sequence>)
<command>*)
| (delay <expression>)
| <quasiquotation>
<cond clause> --> (<test> <sequence>)
| (else <sequence>)
| (<test>)
| (<test> => <recipient>)
<recipient> --> <expression>
<case clause> --> ((<datum>*) <sequence>)
| (else <sequence>)
<binding spec> --> (<variable> <expression>)
<iteration spec> --> (<variable> <init> <step>)
| (<variable> <init>)
<init> --> <expression>
<step> --> <expression>
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>
<template 0> --> <expression>
<quasiquotation D> --> `<template D>
| (quasiquote <template D>)
<template D> --> <simple datum>
| <list template D>
| <vector template D>
| <unquotation D>
<list template D> --> (<template or splice D>*)
| (<template or splice D>+ . <template D>)
| '<quasiquotation D>
| <quasiquotation D+1>
<vector template D> --> #(<template or splice D>*)
<unquotation D> --> ,<template D-1>
| (unquote <template D-1>)
<template or splice D> --> <template D>
| <splicing unquotation D>
<splicing unquotation D> --> ,@<template D-1>
| (unquote-splicing <template D-1>)
In <quasiquotation>s, a <list template D> can sometimes be confused with an <unquotation D> or <splicing unquotation D>. The interpretation as an <unquotation> or <splicing unquotation D> takes precedence.
<program> --> <command or definition>*
<command or definition> --> <command> | <definition>
<definition> --> (define <variable> <expression>)
| (define (<variable> <def formals>) <body>)
<def formals> --> <variable>*
| <variable>* . <variable>
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: http://swissnet.ai.mit.edu/~jaffer/r3rs-formal.pdf
This section gives rewrite rules for the derived expression types. By
the application of these rules, any expression can be reduced to a
semantically equivalent expression in which only the primitive
expression types (literal, variable, call, lambda, if,
set!) occur.
(cond (<test> <sequence>)
<clause2> ...)
== (if <test>
(begin <sequence>)
(cond <clause2> ...))
(cond (<test>)
<clause2> ...)
== (or <test> (cond <clause2> ...))
(cond (<test> => <recipient>)
<clause2> ...)
== (let ((test-result <test>)
(thunk2 (lambda () <recipient>))
(thunk3 (lambda () (cond <clause2> ...))))
(if test-result
((thunk2) test-result)
(thunk3)))
(cond (else <sequence>))
== (begin <sequence>)
(cond)
== <some expression returning an unspecified value>
(case <key>
((d1 ...) <sequence>)
...)
== (let ((key <key>)
(thunk1 (lambda () <sequence>))
...)
(cond ((<memv> key '(d1 ...)) (thunk1))
...))
(case <key>
((d1 ...) <sequence>)
...
(else f1 f2 ...))
== (let ((key <key>)
(thunk1 (lambda () <sequence>))
...
(elsethunk (lambda () ...)))
(cond ((<memv> key '(d1 ...)) (thunk1))
...
(else (elsethunk))))
where <memv> is an expression evaluating to the memv procedure.
(and) == #t
(and <test>) == <test>
(and <test1> <test2> ...)
== (let ((x <test1>)
(thunk (lambda () (and <test2> ...))))
(if x (thunk) x))
(or) == #f
(or <test>) == <test>
(or <test1> <test2> ...)
== (let ((x <test1>)
(thunk (lambda () (or <test2> ...))))
(if x x (thunk)))
(let ((<variable1> <init1>) ...)
<body>)
== ((lambda (<variable1> ...) <body>) <init1> ...)
(let* () <body>)
== ((lambda () <body>))
(let* ((<variable1> <init1>)
(<variable2> <init2>)
...)
<body>)
== (let ((<variable1> <init1>))
(let* ((<variable2> <init2>)
...)
<body>))
(letrec ((<variable1> <init1>)
...)
<body>)
== (let ((<variable1> <undefined>)
...)
(let ((<temp1> <init1>)
...)
(set! <variable1> <temp1>)
...)
<body>)
where <temp1>, <temp2>, ... are variables, distinct
from <variable1>, ..., which do not free occur in the
original <init> expressions, and <undefined> is an expression
which returns something which when stored in a location makes it an
error to try to obtain the value stored in the location. (No such
expression is defined, but one is assumed to exist for the purposes of this
rewrite rule.) The second let expression in the expansion is not
strictly necessary, but it serves to preserve the property that the
<init> expressions are evaluated in an arbitrary order.
(begin <sequence>) == ((lambda () <sequence>))
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
<sequence> contains no definitions.
(begin <expression>) == <expression>
(begin <command> <sequence>)
== ((lambda (ignore thunk) (thunk))
<command>
(lambda () (begin <sequence>)))
(do ((<variable1> <init1> <step1>)
...)
(<test> <sequence>)
<command1> ...)
== (letrec ((<loop>
(lambda (<variable1> ...)
(if <test>
(begin <sequence>)
(begin <command1>
...
(<loop> <step1> ...))))))
(<loop> <init1> ...))
where <loop> is any variable which is distinct from
<variable1>, ..., and which does not occur free in the do
expression.
(let <variable_0> ((<variable1> <init1>) ...)
<body>)
== ((letrec ((<variable_0> (lambda (<variable1> ...)
<body>)))
<variable_0>)
<init1> ...)
(delay <expression>)
== (<make-promise> (lambda () <expression>))
where <make-promise> is an expression evaluating to some procedure
which behaves appropriately with respect to the force procedure;
see section 6.9 Control features.