\documentstyle[zed,a4wide]{article}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%% @(#)astyped.sty  1.3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ASTYPED DOCUMENT-STYLE OPTION - released 88/06/30
%    for LaTeX version 2.09
% Based on Leslie Lamport's verbatim environment in latex.tex.

% Defines the `astyped' environment, which is like the `verbatim'
% environment except most of the special characters have their usual meanings.
% Space, ^K, and ^A are the only specials changed.

\def\astyped{\trivlist \item[]\if@minipage\else\vskip\parskip\fi
\leftskip\@totalleftmargin\rightskip\z@
\parindent\z@\parfillskip\@flushglue\parskip\z@
\@tempswafalse \def\par{\if@tempswa\hbox{}\fi\@tempswatrue\@@par}
\obeylines \tt \catcode``=13 \@noligs \let\do\@makeother \do\ \do\^^K\do\^^A
 \frenchspacing\@vobeyspaces}

\let\endastyped=\endtrivlist

% Used inside astyped environments for normal formatting of a line.
% I wish I could give space its normal catcode within \notastyped.
\def\notastyped#1{\mbox{\rm #1}}
%%% end of astyped.sty
\makeatother

\newenvironment{code}{\begin{quote}\small}{\end{quote}}
\def\signed#1#2{{\unskip\nobreak\hfil\penalty50
  \hskip2em\hbox{}\nobreak\hfil#1\quad#2
  \parfillskip=0pt \finalhyphendemerits=0 \par}}       % TeXBook, p106

\newenvironment{grammar}{\begingroup\mymathcodes\begin{syntax}}%
   {\end{syntax}\endgroup\ignorespaces}
{\catcode`\:=\active \gdef:{\;}}  
\def\mymathcodes{\mathcode`+="072B
\mathcode`-="072D
\mathcode`*="072A
\mathcode`<="073C
\mathcode`>="073E
\mathcode`=="073D
\mathcode`!="0721
\mathcode`/="072F
\mathchardef\lp="0728
\mathchardef\rp="0729
\mathchardef\lb="075B
\mathchardef\rb="075D
\mathcode`[="405B
\mathcode`]="505D
\mathcode`|="326A
\def\is{\hbox{::=}}
\mathcode`\:="8000 % for extra space around nonterminals
\mathchardef\colon="073A}

\def\T#1{\hbox{\tt #1}}
\def\N#1{\hbox{\rm #1}}
\def\nt#1{\hbox{\it #1}}
\def\lb{\hbox{\it [}}
\def\rb{\hbox{\it ]}}
\def\Tee{{\bf T}}
\begin{document}
\begin{titlepage}
% a front or cover page for EG docs suitable for inclusion inside
% a titlepage environment in a LaTeX document
% for use with Plain TeX uncomment the \nopagenumbers and the \eject

\hoffset=0in
\hsize=6.25in
%\hoffset=.5in
%\hsize=5.25in
\vsize=10.25in
%---gives left and right margins of 1.5in
\font\small=cmssbx10 scaled \magstep2
\font\medium=cmssbx10 scaled \magstep3
\font\large=cmssbx10 scaled \magstep4
%\nopagenumbers
\hrule height 0pt
\parindent=0pt
%\parskip=0pt
\large
\rightline{EDOC???}
\vskip .5in
\large
EUROGAM PROJECT\par
\vskip 1.5in
\hrule height 2pt
\vskip 20pt
\large
NSF DATA ACQUISITION SYSTEM\par
\vskip .5in
\baselineskip 25pt
Prototyping a Sort Language\par
\vskip 20pt
\hrule height 2pt
\vskip 1in
\medium
Edition 1.0\par
\vskip 5pt
November 1990\par
\vfill
\medium
NSF Software Systems Group\par
\vskip 5pt
UK Science and Engineering Research Council\par
\vskip 5pt
Daresbury Laboratory\par
\vskip .5in
%\eject
\end{titlepage}
\title{Prototyping a Sorting Language}
\author{David Brightly}
\date{November 1990}
\maketitle
\section{Introduction}
This document shows, by way of an example,  how the \Tee\ system \cite{T} 
can be used to prototype a small language and its implementation.
\Tee\ is a Lisp dialect deriving from the Scheme \cite{Scheme} language.
The chosen example is the core part of a language designed for
processing nuclear structure event data.
The paper describes a grammar for the language together with a 
parser and evaluator written in \Tee.
The parser produces a parse tree for a program in the form of
an s-expression. 
The evaluator animates the execution of the program by walking over
the parse tree and recursively evaluating its sub-expressions.

\section{A grammar for a simple sorting language}
The grammar has been cast in a form suitable for recursive descent
parsing.
This is the grammar for expressions:
\begin{grammar}
  expr     & \is & :[\T{not}]:relexpr: \{ (\T{and} | \T{or} ): relexpr \} & \omit \\
  relexpr  & \is & :simpexpr: [ ( < | <= | == | != | >= | > ):simpexpr ] & \omit \\
          &  |  & :simpexpr:\T{in}:window & \omit \\
  simpexpr & \is & :[-] :term: \{ (+|-):term: \} & \omit \\
  term    & \is & :factor: \{ ( * | /) :factor: \} & \omit \\
  factor  & \is & :xfactor | id:!:indexpr       & \omit \\
  indexpr  & \is & :xfactor: \{ ! :xfactor \}     & \omit \\
  xfactor & \is & :id | \lp expr \rp            & \omit 
\end{grammar}%
Note that the logical operators have equal precedence, as do the relational
operators, and all binary operators associate to the left.
Array indexing is a little out of the ordinary, using the BCPL-inspired
\T{!} operator rather than the conventional brackets which are needed 
elsewhere.

Physicists like to talk about `windows' and `gates' so we have some syntax for
some data structures representing these:
\begin{grammar}
  window & \is & :\T{[}:gate:\{\T{,}:gate\}:\T{]} & \omit \\
  gate   & \is & : expr:\T{..}:expr                 & \omit 
\end{grammar}
This is the grammar for statements:
\begin{grammar}
  program & \is & :block: & \omit \\
  block   & \is & :\T{begin}:statement:\{\semicolon:statement\}:\T{end} & \omit \\
  statement&\is & :simplestatement | block & \omit \\
simplestatement&\is&:assignstatement|incstatement|filterstatement|expression & \omit \\
  assignstatement&\is&:\T{set}:id:=:expr & \omit \\
  incstatement&\is&:\T{inc}:expr:\T{of}:specref & \omit \\
  specref &\is&:id | id:!:indexpr  & \omit \\
  filterstatement&\is&:\T{filter}:expr & \omit
\end{grammar}
The semantics of these statement forms is explained below.
\section{Parsing a program}
The following recursive descent parsing routines were written directly
from the grammar above.
The tokens forming the source program to be parsed are symbols in 
the list \T{prog}.
We use the \Tee\ reader to do the tokenising (see the appendix).
Each call to \T{scan} puts the next token of the program into
the variable \T{sym} and decapitates \T{prog}.
%(define semicolon '\verb-\-;)
\begin{code}
\begin{astyped}
(define openparen '\verb-\-()
(define closeparen '\verb-\-))
(define openbracket '\verb-\-[)
(define closebracket '\verb-\-])
(define semicolon '\verb-\-;)
(define equals '\verb-\-=)
(define bang '\verb-\-!)
(define comma '\verb-\-,)
\end{astyped}

\begin{astyped}
(define (make-node s l r) (list s l r))
(define (make-unary-node s l) (list s l))
(define (make-leaf a) a)
(define (append-node l n) (append l (list n)))
\end{astyped}

\begin{astyped}
(define (scan) 
  (cond ((null? prog) (set sym eof))
        (else (set sym (car prog)) (set prog (cdr prog)))))
(define (lookahead) (if (null? prog) eof (car prog)))
(define (id? i) true)       \notastyped{; temporary measure}
\end{astyped}

\begin{astyped}
(define (parse-error s) (print s (standard-output)) (ret (false)))
\end{astyped}
\end{code}
The next definitions form a mutually recursive set of parsers for sub-expressions.
Each procedure returns an s-expression representing the parse tree for the
sub-expression recognised.
For example, the \nt{simpexpr} \T{a + b + c} is represented by the s-expression
\T{(+ (+ a b) c)}.
\begin{code}
\begin{astyped}
(define (expr) (logexpr))
\end{astyped}

\begin{astyped}
(define (logexpr) 
  (let ((l (cond ((eq? sym 'not) (scan) (make-unary-node 'not (relexpr)))
                 (else (relexpr)))))
    (labels (((relexpr* t)
              (cond ((eq? sym 'and) (scan) (relexpr* (make-node 'and t (relexpr))))
                    ((eq? sym 'or) (scan) (relexpr* (make-node 'or t (relexpr))))
                    (else t))))
            (relexpr* l))))
\end{astyped}

\begin{astyped}
(define (relexpr) 
  (let ((t (simpexpr)))
    (cond ((eq? sym '<) (scan) (make-node '< t (simpexpr)))
          ((eq? sym '<=) (scan) (make-node '<= t (simpexpr)))
          ((eq? sym '==) (scan) (make-node '== t (simpexpr)))
          ((eq? sym '!=) (scan) (make-node '!= t (simpexpr)))
          ((eq? sym '>=) (scan) (make-node '>= t (simpexpr)))
          ((eq? sym '>) (scan) (make-node '> t (simpexpr)))
          ((eq? sym 'in) (scan) (make-node 'in t (window)))
          (else t))))
\end{astyped}

\begin{astyped}
(define (simpexpr) 
  (let ((l (cond ((eq? sym '-) (scan) (make-unary-node '- (term)))
                 (else (term)))))
    (labels (((term* t)
              (cond ((eq? sym '+) (scan) (term* (make-node '+ t (term))))
                    ((eq? sym '-) (scan) (term* (make-node '- t (term))))
                    (else t))))
            (term* l))))
\end{astyped}

\begin{astyped}
(define (term) 
  (let ((l (factor)))
    (labels (((factor* t)
              (cond ((eq? sym '*) (scan) (factor* (make-node '* t (factor))))
                    ((eq? sym '/) (scan) (factor* (make-node '/ t (factor))))
                    (else t))))
            (factor* l))))
\end{astyped}

\begin{astyped}
(define (factor)
  (cond ((and (id? sym) (eq? (lookahead) bang))
         (let ((l (id))) (scan) (make-node 'index l (indexpr))))
        (else (xfactor))))
\end{astyped}

\begin{astyped}
(define (xfactor)
  (cond ((eq? sym openparen) 
         (scan)
         (block0 (expr) 
                 (cond ((eq? sym closeparen) (scan))
                       (else (parse-error "expecting ')'"))))) 
        (else (id))))
\end{astyped}

\begin{astyped}
(define (id)
  (block0 (make-leaf sym) (scan)))
\end{astyped}
\end{code}
A reference to an array element such as \T{A!2!3}, more conventionally
written as \T{A[2,3]} perhaps, is represented by the form 
\T{(INDEX A (2 3))}, i.e., an array name followed by a list of indexes.
\begin{code}
\begin{astyped}
(define (indexpr)
  (let ((l (xfactor)))
    (labels (((index* t)
              (cond ((eq? sym bang) (scan) (index* (append-node t (xfactor))))
                    (else t))))
            (index* (list l)))))
\end{astyped}
\end{code}
The language has a notation for one dimensional `windows',
such as \T{[100..200, 400..500, 800..900]} commonly required in processing
event data. 
These are represented as a list of 2-element lists (or `gates') such as
\T{(WINDOW (100 200) (400 500) (800 900))}.
\begin{code}
\begin{astyped}
(define (window)
  (cond ((eq? sym openbracket) (scan))
        (else (parse-error "expecting '['")))
  (let ((l (list 'window (gate))))
    (labels (((gate* t)
              (cond ((eq? sym comma) (scan) (gate* (append-node t (gate))))
                           (else t))))
            (block0 (gate* l) 
                    (cond ((eq? sym closebracket) (scan))
                          (else (parse-error "expecting ']'")))))))
\end{astyped}

\begin{astyped}
(define (gate)
  (let ((l (expr))) 
    (cond ((eq? sym '..) (scan) (list l (expr)))
          (else (parse-error "expecting '..'")))))
\end{astyped}
\end{code}
Multi-dimensional arrays of spectra provide a compact notation for expressing
complicated selection criteria. 
We use the indexing notation to refer to an element in an array of spectra.
\begin{code}
\begin{astyped}
(define (specref)
  (cond ((and (id? sym) (eq? (lookahead) bang))
         (let ((l (id))) (scan) (make-node 'index l (indexpr))))
        (else (id))))
\end{astyped}
\end{code}
We now come to parsing procedures for program language statements.
Statements are recognised by a distinguishing leading token and return
special s-expressions. 
For example, the assignment statement \T{set a = b + c} is 
represented by the s-expression \T{(SET A (+ B C))}.
\begin{code}
\begin{astyped}
(define (statement)
  (case sym
    ((begin) (blk))
    ((inc) (inc-statement))
    ((set) (assign-statement))
    ((filter) (filter-statement))
    (else (expr-statement))))
\end{astyped}

\begin{astyped}
(define (blk)
  (cond ((eq? sym 'begin) (scan))
        (else (parse-error "expecting 'begin'")))
  (let ((l (list 'block (statement))))
    (labels (((state* t)
              (cond ((eq? sym semicolon)
                     (scan) (state* (append-node t (statement))))
                    (else t))))
            (block0 (state* l) 
                    (cond ((eq? sym 'end) (scan))
                          (else (parse-error "expecting 'end'")))))))
\end{astyped}

\begin{astyped}
(define (inc-statement)
  (scan)
  (let ((l (list 'inc (expr))))
    (append-node l (cond ((eq? sym 'of) (scan) (specref))
                         (else (parse-error "expecting 'of'"))))))
\end{astyped}

\begin{astyped}
(define (assign-statement)
  (scan)
  (let ((l (list 'set (id))))
    (append-node l (cond ((eq? sym equals) (scan) (expr))
                         (else (parse-error "expecting '='"))))))
\end{astyped}

\begin{astyped}
(define (filter-statement)
  (scan)
  (list 'filter (expr)))
\end{astyped}

\begin{astyped}
(define (expr-statement)
  (list 'expr (expr)))
\end{astyped}
\end{code}
Finally, a program as a whole is just a \nt{block} so we can parse it
with
\begin{code}
\begin{astyped}
(define (parse-program) (scan) (blk))
\end{astyped}
\end{code}
which returns an s-expression representing the program.

\section{An example program}
Our language has no facilities for reading in an event to be sorted,
so we simulate this by an initial sub-block of assignments of arbitrary
values to simple variables that can be taken as event components.
\begin{quote}
\begin{verbatim}
begin
  begin
    set a = 17 ;
    set b = 3 * 4 ;
    set c = 10 ;
    set d = 15 ;
    set e = 7 ;
    set g = 11 ;
    set h = 13 
  end ;

  begin
    set h = 14 ;
    h < g ;
    inc h of s
  end ;
  
  begin
    filter b + 300 in [ 100 .. 200 , 300 .. 400 ] ;
    inc a + 255 of s ;
    begin
      a - b > 4 and d - c > 0 ;
      inc  a + b * c of t ! ( c * d  in [ 100 .. 200 , 300 .. 400 ] )
    end ;
    inc e * g + h of u ! ( b + c ) 
  end
end
\end{verbatim}
\end{quote}
\section{An example parse tree}
This is the list structure returned by \T{parse-program} applied to the above
example:
\begin{quote}
\begin{verbatim}
 (BLOCK (BLOCK (SET A 17)
               (SET B (* 3 4))
               (SET C 10)
               (SET D 15)
               (SET E 7)
               (SET G 11)
               (SET H 13))
        (BLOCK (SET H 14) (EXPR (< H G)) (INC H S))
        (BLOCK (FILTER (IN (+ B 300) (WINDOW (100 200) (300 400))))
               (INC (+ A 255) S)
               (BLOCK (EXPR (AND (> (- A B) 4) (> (- D C) 0)))
                      (INC (+ A (* B C))
                           (INDEX T ((IN (* C D) (WINDOW (100 200) (300 400)))))))
               (INC (+ (* E G) H) (INDEX U ((+ B C))))))
\end{verbatim}
\end{quote}


\section{Evaluating the parsed program}
In this section we will give some semantics for our little language by
describing an evaluator for the s-expression returned by \T{parse-program}.
First we need a means of recording the values held in program variables.
Rather than invent new names for the program variables we can keep them
separate from names used in the evaluator itself by using a \Tee\ concept
called a {\em locale\/}.
For example, if we need to record that program variable \T{A} has value
\T{23} we will bind the value 23 to the symbol \T{A} in the locale \T{symbols}.
\begin{code}
\begin{astyped}
(define symbols (make-empty-locale '*symbols*))
\end{astyped}
\end{code}
The heart of the evaluator is the procedure \T{eval-form} which takes an s-expression
and recursively applies itself where necessary to its sub-expressions.
When it reaches numeric or symbolic sub-expressions it either returns these
directly or looks up their current value in the \T{symbols} locale.
\begin{code}
\begin{astyped}
(define (first l) (car l))
(define (second l) (cadr l))
(define (third l) (caddr l))
\end{astyped}

\begin{astyped}
(define (eval-error s) (print s (standard-output)) (ret (false)))
\end{astyped}

\begin{astyped}
(define (eval-form f)
  (cond ((symbol? f) (*value symbols f))
        ((number? f) f)
        ((list? f) (eval-list f))
        (else (eval-error "not a recognised form"))))
\end{astyped}
\end{code}
Sub-expressions in the form of lists are evaluated by dispatching on the
symbol at their head:
\begin{code}
\begin{astyped}
(define (eval-list l)
  (case (car l)
    ((+) (add (eval-form (second l)) (eval-form (third l))))
    ((-) (if (eq? (length l) 3)
             (subtract (eval-form (second l)) (eval-form (third l)))
             (negate (eval-form (second l)))))
    ((*) (multiply (eval-form (second l)) (eval-form (third l))))
    ((/) (divide (eval-form (second l)) (eval-form (third l))))
    ((<) (if (less? (eval-form (second l)) (eval-form (third l))) 1 0))
    ((<=) (if (<= (eval-form (second l)) (eval-form (third l))) 1 0))
    ((==) (if (equal? (eval-form (second l)) (eval-form (third l))) 1 0))
    ((!=) (if (not-equal? (eval-form (second l)) (eval-form (third l))) 1 0))
    ((>=) (if (not-less? (eval-form (second l)) (eval-form (third l))) 1 0))
    ((>) (if (greater? (eval-form (second l)) (eval-form (third l))) 1 0))
    ((not) (if (zero? (eval-form (second l))) 1 0))
    ((and) (if (or (zero? (eval-form (second l)))
                   (zero? (eval-form (third l)))) 0 1))
    ((or) (if (and (zero? (eval-form (second l)))
                   (zero? (eval-form (third l)))) 0 1))
    ((block) (eval-block l))
    ((set) (eval-set l))
    ((filter) (eval-filter l))
    ((expr) (eval-expr l))
    ((inc) (eval-inc l))
    ((index) (eval-index l))
    ((in) (eval-in l))
    ((window) (eval-window l))
    (else (eval-error "not a known operator"))))
\end{astyped}
\end{code}
Note that the logical operators take non-zero to denote `true' and
zero to denote `false', and always return 1 or 0 respectively.
 
The following procedures evaluate statement level forms.
All statement level forms return a truth value which is used to determine
the semantics of a block of statements.

An assignment form evaluates its third element and binds this value to
the symbol given by its second element in the \T{symbols} locale, issuing
a trace report as it does so, and returns TRUE:
\begin{code}
\begin{astyped}
(define (eval-set f)
  (let ((var (second f))
        (val (eval-form (third f))))
    (*lset symbols var val)
    (format (standard-output) "setting \verb-~-A to \verb-~-A\verb-~-\verb-%-" var val)
    true))
\end{astyped}
\end{code}
An expression form evaluates its second element and returns TRUE if the
result is non-zero, else FALSE.
A filter form does the same.
\begin{code}
\begin{astyped}
(define (eval-expr f)
  (not-zero? (eval-form (second f))))
\end{astyped}

\begin{astyped}
(define (eval-filter f)
  (not-zero? (eval-form (second f))))
\end{astyped}
\end{code}
The simple language defined here has no explicit control constructs.
Instead, a program is seen as a nest of statement blocks which themselves
consist of a sequence of simple statements or further blocks.
A block is evaluated by evaluating the statements or blocks within it in order
until one of them returns FALSE.
Any remaining statements or blocks within the block are then skipped.
Blocks themselves always return TRUE.
\T{eval-block} issues a trace report when statements are skipped in this way.
\begin{code}
\begin{astyped}
(define (eval-block f)
  (labels 
   (((eval-block* l)
     (cond ((null? l) true)
           (else (cond ((eval-form (car l))  (eval-block* (cdr l)))
                       (else (format (standard-output)
                                     "abandoning block\verb-~-\verb-%-") true))))))
   (eval-block* (cdr f))))
\end{astyped}

\end{code}

Event sorting programs are evaluated for the side effect of incrementing
channels in spectra.
An increment form just reports that it is incrementing the channel
given by the expression in its second element in the spectrum denoted by
its third element.
This third element must be either a symbol or an array element reference.
\begin{code}
\begin{astyped}
(define (eval-inc f)
  (format (standard-output) "incrementing channel \verb-~-a of spectrum \verb-~-a\verb-~-\verb-%-"
          (eval-form (second f)) (eval-spec (third f)))
  true)
\end{astyped}

\begin{astyped}
(define (eval-spec f)
  (cond ((symbol? f) (format nil "\verb-~-a" f))
        (else (eval-index f))))
\end{astyped}

\begin{astyped}
(define (eval-index f)
  (if (not (list? f)) (eval-error "not an index expression"))  
  (if (neq? 'index (first f)) (eval-error "not an index form"))
  (format nil "\verb-~-a:\verb-~-a" (second f) (map eval-form (third f))))
\end{astyped}
\end{code}

Finally, we give the semantics of the \T{in} operator
which tests the value of an expression against a window and returns the
number of the first gate of the window through which the value passes.
A value `passes' a gate if it is no less than the gate's lower bound and
no greater than its upper bound.
\begin{code}
\begin{astyped}
(define (eval-in f)
  (window-test (eval-form (second f)) (third f)))
\end{astyped}

\begin{astyped}
(define (window-test e w)
  (labels (((window-test* v i l)
            (cond ((null? l) 0)
                  ((and (>= v (first (first l)))  (<= v (second (first l))))  i)
                  (else (window-test* v (add i 1) (cdr l))))))
    (window-test* e 1 (cdr w))))
\end{astyped}

\end{code}

\section{Conclusions}
I hope that this paper has shown that it is practical to build a prototype
of a problem-oriented language using \Tee.
The work described here (including preparation of the document itself) has taken
about a week of elapsed time, starting with no previous experience of
writing in a Lisp-like language, but with a passing acquaintance with \cite{Scheme}.
This effort should be contrasted with the likely development time for a similar
prototype in, say, C.
One advantage of the \Tee\ system is the ease with which a program can be developed
incrementally. 
Both parser and evaluator were developed ``bottom-up'', by building on top
of already checked-out lower-level procedures,
virtually all of which were keyed in one at a time
and checked out on small program fragments or s-expressions before moving on.

This rapidity of development means that you can afford to experiment with
language constructs. 
Instead of spending weeks and months developing a compiler and run-time system 
from an abstract specification which intended users of the system cannot understand,
you can sit down with users and demonstrate how their sorting 
requirements can (or cannot!) be expressed in the prototype language.
Any doubts about the semantics of the language can be cleared up by
watching the evaluator execute a sample program.
The benefit from this, of course, is that you have more confidence that
you have the right product when you finally come to build a production
implementation of the language.
And by then you already have a parser for the final form of the language and
only need to replace the evaluator with a suitable code generator.

The little sorting language described here is clearly only a starting point 
for such a language and the implementation of the parser and evaluator takes
lots of shortcuts which
could not be permitted in a piece of production software.
For example, the \T{scan} procedure returns unclassified tokens and the \nt{id\/}
parser, \T{id}, accepts any token as a valid identifier.
Directions which could be investigated include:
\begin{itemize}
\item syntax for declarations, especially for arrays of spectra and simple
variables, enabling run-time checking of array references;
\item proper treatment of integer and real types in expressions;
\item syntax for function application in expressions, and for user-declared
functions;
\item multi-dimensional spectra and windows (two at least);
\item extended control constructs such as \T{case};
\item language constructs for dealing with permutations---especially 
valuable for highly symmetric event data.
\end{itemize}

\section{Acknowledgements}
I'd like to thank my colleague Dave Love for installing the \Tee\ system
at DL and for demonstrating that higher order languages can usefully be put
to work in this environment.

\begin{thebibliography}{99}
\bibitem{T}{\sl The T Manual---Fifth Edition\/}, Rees, Adams and Meehan,
Computer Science Department, Yale University, 1988
\bibitem{Scheme}{\sl Structure and Interpretation of Computer Programs\/},
Abelson and Sussman, McGraw-Hill, 1985
\end{thebibliography}


\appendix
\section{Appendix---Running the example program}
Having loaded the parser and evaluator procedures we need to initialise 
the variable \T{prog} to a list of the tokens of our source program.
To save effort writing a scanner we will use the \Tee\ reader to 
lexically analyse the source
program and produce a list of tokens for the parser.
This makes the \T{scan} procedure trivial but we have to be careful
to escape certain \Tee\ reserved characters such as `\T{(}' and `\T{;}'
and to leave white space around individual tokens.
\begin{code}
\begin{astyped}
(set prog '(
begin
  begin
    set a = 17 \verb-\-\notastyped{;}
    set b = 3 * 4 \verb-\-\notastyped{;}
    set c = 10 \verb-\-\notastyped{;}
    set d = 15 \verb-\-\notastyped{;}
    set e = 7 \verb-\-\notastyped{;}
    set g = 11 \verb-\-\notastyped{;}
    set h = 13 
  end \verb-\-\notastyped{;}

  begin
    set h = 14 \verb-\-\notastyped{;}
    h < g \verb-\-\notastyped{;}
    inc h of s
  end \verb-\-\notastyped{;}
  
  begin
    filter b + 300 in \verb-\-[ 100 .. 200 \verb-\-, 300 .. 400 \verb-\-] \verb-\-\notastyped{;}
    inc a + 255 of s \verb-\-\notastyped{;}
    begin
      a - b > 4 and d - c > 0 \verb-\-\notastyped{;}
      inc  a + b * c of t ! \verb-\-( c * d  in \verb-\-[ 100 .. 200 \verb-\-, 300 .. 400 \verb-\-] \verb-\-)
    end \verb-\-\notastyped{;}
    inc e * g + h of u ! \verb-\-( b + c \verb-\-) 
  end
end
))
\end{astyped}
\end{code}
We can now compile and execute our program by invoking
\begin{code}
\begin{astyped}
(eval-block (parse-program))
\end{astyped}
\end{code}
The trace reports we get are as follows:
\begin{quote}
\begin{verbatim}
setting A to 17
setting B to 12
setting C to 10
setting D to 15
setting E to 7
setting G to 11
setting H to 13
setting H to 14
abandoning block
incrementing channel 272 of spectrum S
incrementing channel 137 of spectrum T:(1)
incrementing channel 91 of spectrum U:(22)
\end{verbatim}
\end{quote}
The ``abandoning block'' report arises because the expression statement
\verb+(h < g)+ returns FALSE.
\end{document}