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

Scheme BNF

Here is a draft of my proposed BNF for the RRRS appendix.  I would like
people to check it for correctness and completeness, and make other
appropriate remarks.

It will of course be properly fonted and explained in the report, with
discussion of *, +, whitespace, ambiguities (there are lots), etc.  I'll
try to come up with some way to distinguish essential features from
non-essential ones.

I'm not enamored of the names of the nonterminals, and would be happy to
entertain alternatives.

A couple of minor problems in the explanations have been exposed by this
exercise, which I'll quietly fix.  For example, (DEFINE (FOO . X) ...)
isn't defined to work in the current report, although I'm sure it does
work in everyone's implementation.


- Does anyone object to defining (COND) and (CASE) to return unspecified
values?  I think this would be a good idea.

- Shouldn't backquote work on vectors?  If not, then what's the rationale
for making them work on lists and not vectors?

- What kinds of constants should be allowed in CASE clauses?  I don't
really care, but I can imagine two possible answers:

1. If EQV? is used for comparisons, then it doesn't make any sense to allow
strings, lists, or vectors.  So these should be disallowed by the syntax.
This makes the grammar a little more complicated, since one has to define
what it means for something to be a "casable constant" (I'll come up with a
better name than that).

  <case clause> ::= ((<casable>*) <sequence>)
  <casable> ::= <boolean> | <number> | <character> | <symbol>

2. Use EQUAL? for comparisons, and allow any <datum>.  This makes the
grammar simpler and makes previously undefined and possibly useful
syntaxes meaningful.  This is an extension to the language, which some
people might object to as being too liberal and/or not useful enough to
warrant a change.  (There's definitely no efficiency loss except in a
very stupid interpreter.)  If no one objects, I'll do this, but I won't
argue if anyone does object, but I won't listen to anyone who doesn't
supply a better word to use for the nonterminal than "casable".

  <case clause> ::= ((<datum>*) <sequence>)

- I definitely want like to flush the (<var>) syntax for iteration specs in
DO.  It is inconsistent for DO to have this alternate form and not LET,
and I don't like either.  Does anyone actually ever use it?

- I would also like to flush the (<var> <init>) syntax for DO iteration
specs.  Does anyone ever use this?  I always wrap the DO in a LET if I
need extra bindings.  No replies from people who don't use DO, please.

- Oh yeah, I forgot to mention in my previous message that I would like to
document DELAY and FORCE, as non-essential special form and procedure,
respectively.  I believe they're non-controversial, and desirable given
that they have a central role in S&ICP and are a little tricky to
describe and implement.


  <file> ::= <form>*     ;This is what LOAD presumably parses
  <form> ::= <expression> | <definition>
                  ;This is what a read-eval-print might parse

  <expression> ::= <constant> | <variable>
      | <procedure call>
      | <quotation>
      | (lambda <bound var list> <body>)
      | (if <test> <consequent> <alternate>)
      | (if <test> <consequent>)
      | (cond <cond clause>*)
      | (cond <cond clause>* (else <sequence>))
      | (and <expression>*)
      | (or <expression>*)
      | (case <case clause>*)
      | (case <case clause>* (else <sequence>))
      | (let (<binding spec>*) <body>)
      | (let <variable> (<binding spec>*) <body>)
      | (let* (<binding spec>*) <body>)
      | (letrec (<binding spec>*) <body>)
      | (rec <variable> <expression>)
      | (set! <variable> <expression>)
      | (begin <sequence>)
      | (sequence <sequence>)
      | (do (<iteration spec>*) (<end test> <sequence>+) <expression>*)
      | (delay <expression>)
      | <quasiquotation>

  <variable> ::= <identifier>

  <procedure call> ::= (<operator> <operand>*)
  <operator> ::= <expression>
  <operands> ::= <expression>*

  <quotation> ::= '<datum> | (quote <datum>)
  <body> ::= <definition>* <sequence>
  <sequence> ::= <expression>+

  <definition> ::= (define <variable> <expression>)
      | (define <call pattern> <body>)

  <call pattern> ::= (<pattern> <variable>*)
      | (<pattern> <variable>* . <variable>)

  <pattern> ::= <variable> | <call pattern>

  <bound var list> ::= <variable>
      | (<variable>*) | (<variable>+ . <variable>)

  <test> ::= <expression>
  <consequent> ::= <expression>
  <alternate> ::= <expression>

  <cond clause> ::= (<test> <sequence>) | (<test> => <expression>)

  <case clause> ::= ((<datum>*) <sequence>)

  <binding spec> ::= (<variable> <expression>)

  <iteration spec> ::= (<variable> <init> <step>)

  <quasiquotation> ::= <quasiquotation 0>

  <template 0> ::= <expression>

  Repeat the following for N = 1 to infinity:

    <quasiquotation N> ::=  `<template N+1> | (quasiquote <template N+1>)

    <template N> ::= <constant> | <symbol>
        | <list template N>
	| <vector template N>
	| <unquotation N>

    <seq template N> ::= <template N> | <splicing unquotation N>

    <list template N> ::= (<seq template N>*)
	| (<seq template N>+ . <template N>)
	| <quasiquotation N+1>

    <vector template N> ::= #(<seq template N>*)

    <unquotation N> ::= ,<template N-1> | (unquote <template N-1>)
    <splicing unquotation N> ::= ,@<template N-1>
        | (unquote-splicing <template N-1>)

  end repeat

The grammar for external representations of objects from here on down is
self-contained.  <datum> is what READ parses.  Note that any string
which is an <expression> must also be a <datum>.

  <datum> ::= <constant> | <symbol> | <list> | <vector>

  <constant> ::= <boolean> | <number> | <character> | <string>

  <symbol> ::= <identifier>

  <boolean> ::= #!true | #!false

  <string> ::= " <string element>* "
  <string element> ::= <any character other than " or \> | \" | \\

  <list> ::= ( <datum>* ) | ( <datum>+ . <datum> )
      | <abbreviation>

  <abbreviation> ::= <abbrev prefix> <datum>
  <abbrev prefix> ::= ' | ` | , | ,@

  <vector> ::= #( <datum>* )

  <identifier> ::= <initial> <subsequent>* | <peculiar identifier>
  <initial> ::= <letter> | <special initial>
  <letter> ::= A | B | C | ... | Z
  <special initial> ::= ! | $ | % | & | * | / | : | < | = | > | ? | ~ | _ | ^
  <subsequent> ::= <initial> | <digit> | <special subsequent>
  <digit> ::= 0 | 1 | ... | 9
  <special subsequent> ::= . | + | -
  <peculiar identifier> ::= + | - | 1+ | -1+

  <number> ::= ... the grammar for numbers ...