\input tugproc.sty      

\preprint % Comment this line out for final version following meeting

% \let\Now=\null % Uncovering this will remove time stamps on preprints

\def\BaSiX{B\kern-.18em\lower.45ex\hbox{A}\kern-.15em
S\kern-.1em\lower.45ex\hbox{I}\kern-.1em X}
\def\basic{{\smc Basic}}
\def\ps{{\smc PostScript}}
\Title \BaSiX\ \Dash\ An Interpreter Written in \TeX\endTitle
% \shortTitle {\sl Proceedings\/} 
%       Guidelines\endshortTitle  % for running head

\Author Andrew Marc Greene\endAuthor
\address MIT Project Athena, E40-342, 77 Massachusetts Avenue,
Cambridge, MA 02139
\endaddress
\netaddress 617-253-7788.\ Internet:\ amgreene@mit.edu
\endnetaddress

\Abstract
An interpreter for the \basic\ language is developed entirely in \TeX.
The interpreter presents techniques of scanning and parsing that are
useful in many contexts where data which do not contain formatting
directives are to be formatted by \TeX.  \TeX's expansion rules are
exploited to provide a macro that reads in the rest of the input file
as arguments and which never stops expanding.
\endAbstract

\article

\head Introduction \endhead

It is an accepted tenet of the \TeX\ faith that \TeX\ is
Turing-equivalent and that we can write any program in \TeX.  It is
also widely held that \TeX\ is ``the most idiosyncratic language
known to us.''\footnote*{Ward and Halstead -- cite this}
This project is an attempt to provide a simple
programming front end to \TeX.

{\smc Basic} was selected because it is a widely used
interpreted language.  It also features an infix syntax not found in
Lisp or \ps.  This makes it a more difficult but more
general problem than either of these others.

The speed of the \BaSiX\ interprester is not impressive.  It is not
meant to be.  The purpose of this interpreter is not to serve as the
{\smc Basic} implementation of choice.  Its purpose is to display
useful paradigms of input parsing and advanced \TeX\ programming.

\head Interaction with \TeX\endhead

\subhead Associative Arrays \endhead

Using |\csname| it is possible to implement associative arrays in
\TeX.  Associative arrays are arrays whose index is not necessarily a
number.  As an example, if |\student| has the name of a student, we
might look up the student's grade with 
\verbatim
\csname grade.\student\endcsname
\endverbatim
which would be |\grade.Greene| in my case.  (In the case of
|\csname|, all characters up to the |\endcsname| are used in the
command sequence regardless of their category code.)

\BaSiX\ makes extensive use of these arrays.  Commands are begun with
|C|; functions with |F|; variables with |V|; program lines with |/|;
and the linked list of lines with |L|.  This makes it easy for the
interpreter to look up the value of any of these things, given the
name as perceived by the user.

One benefit of |\csname|\dots|\endcsname| is that if the resultant
command sequence is undefined, \TeX\ replaces it with |\relax|.  This
allows us to check, using |\ifx|, whether the user has specified a
non-existant identifier.  This trick is used in exercise 7.7 in \TB.
We use it in \BaSiX\ to check for syntax errors and uninitialized
variables.

\subhead Token Streams \endhead

The \BaSiX\ interpreter was designed to be run interactively.  It is
called by typing |tex basix|; the file ends waiting for the first line of
\basic\ to be entered at \TeX's |*| prompt.  This also allows other files
to |\input basix| and immediately follow it with \basic\ code.

We cannot have the scanner read an entire line at once, since if the
last line of |basix.tex| were a macro that reads a line as a
parameter, we'd get a ``|File ended while scanning use of \getline|''
error.  Instead, we use a method which at first blush seems more
convoluted but which is actually simpler.

We note that \TeX\ does not make any distinction between the tokens
that make up our interpreter and the tokens that form the \basic\
code.  The \BaSiX\ interpreter is carefully constructed so that each
macro ends by calling another macro (which may read parameters).
Thus, expansion is never completed, but the interpreter can continue
to absorb individual characters that follow it.  These characters
affect the direction of the expansion; it is this behaviour that
allows us to implement a \basic\ interpreter in \TeX.

\subhead Category codes \endhead

Normally, \TeX\ distinguishes between sixteen categories of
characters.  To avoid unwanted side effects, the \BaSiX\ interpreter
reassigns category codes of all non-letters to category 12, ``other''.
One undocumented feature of \TeX\ is that it will never let you strand
yourself without an ``active'' character (which is normally the
backslash); if you try to reassign the category of your only active
character (with, {\it e.g.,} |\catcode`\\=12|), it will fail silently.
To allow us to use every typeable character in \BaSiX, we first make
|\catcode31=0|, which allows us to then reassign the catcode of the
backslash without stranding ourselves.  (Of course, the \BaSiX\
interpreter provides an escape back to \TeX\ which restores the normal
category codes.)

We also change the category code of |^^M|, the end-of-line character,
to ``active''.  This lets us detect end-of-line errors that may crop
up.

\subhead etc. \endhead

\head Semantics \endhead

\subhead Words \endhead

A {\sl word} is a collection of one or more characters that meet
requirements based on the first character.  These rules are:

\medskip
\halign{#\hfil&\ #\hfil&\ #\hfil\cr
First & Regular \cr
\noalign{\vskip-2pt}
Character & Expression & Meaning \cr
\noalign{\vskip2pt\hrule\vskip2pt}
% I'm not clear on how to get the brackets to show up - AMG
|[A-Z,a-z]| & |[A-Z,a-z][A-Z,a-z,0-9]*\$?| & Identifier \cr
|[0-9]| & |[0-9]+| & Integer literal \cr
|"| & |"[^"]*[",^^M]| & String literal \cr
Other & |.| & Symbol \cr}
\medskip

\noindent
An end-of-line at the end of a string literal is converted to a |"|.

Everything in \BaSiX\ is one of these four types.  Line numbers are
integer literals, and both variables and commands are identifiers.

The |\scan| macro is used in \BaSiX\ to read the next word.  It uses
|\futurelet| to look at the next token and determine whether it should
be part of the current word ({\it i.e.}, whether it matches the
regular expression of the current type).  If it should be, then it is
read in and appended; otherwise |\scan| returns, leaving this next
token in the input stream.  The word is returned in the macro |\word|.

The peculiar way |\scan| operates is problematic, however.  We can't
say 

\verbatim
\def\Cgoto{\scan\lineno=\word}
\endverbatim

\noindent
because |\scan| looks at the tokens which follow it, which in this
case are |\lineno=\word|.  We need some way to define the |goto|
command such that the |\scan| is at the end of the macro; this will
take the next tokens from the input stream.  We therefore have |\scan|
``return'' to its caller by breaking the caller up in two parts; the
first part ends with |\scan| and the second part contains the code
which should follow.  The second macro is stored in |\afterscan|, and
|\scan| ends with |\afterscan|.  As syntactic sugar, |\after| has been
defined as |\let\afterscan|.  This allows |\Cgoto| to be coded as

\verbatim
\def\Cgoto{\after\gotoPartTwo\scan}
\def\gotoPartTwo{\lineno=\word}
\endverbatim

\noindent
(Actually, the |goto| code is slightly more complicated than this; but
the scanner is the important point here.)  This trick is used
throughout the \BaSiX\ interpreter to read in the next tokens from the
user's input without interrupting the expansion of the \TeX\ macros
that comprise the interpreter.

\subhead Expressions \endhead

An {\sl expression} is a sequence of words that, roughly speaking,
alternates between {\sl values} and {\sl operators}.  A value is
either a literal, an identifier, or a parenthesized expression.  An
operator is one of less-than, more-than, equality, addition,
subtraction, multiplication, division, or reference.  (Reference is an
implicit operator that is inserted between a function identifier and
its parameters.)

Expressions are evaluated in a similar approach to the scanner.
A word is scanned using |\scan| and its type is determined.
``Left-hand'' values are stored for relatives, additives,
multiplicatives, and references.  Using \TeX's grouping operations the
evaluator is reentrant, permitting parenthesized expressions to be
recursively evaluated.  

In order to achieve a similar functionality to |\futurelet|, we exit
the evaluator by |\expandafter\aftereval\word|, where |\aftereval| is
analogous to |\afterscan|.  Since |\word| will have neither macros nor
tokens whose category code needs changing in it, this is as good as
|\futurelet|.

\head Structure of the Interpreter \endhead

The file |basix.tex| defines all the macros that are needed to run the
interpreter.  The last line of this file is |\endeval|, which is
usually called when the interpreter has finished evaluating a line.
In this case, it calls |\enduserline|, which, in turn, calls
|\parseline|.

The |\parseline| macro is part of the {\sl Program Parser} section of
the interpreter.  It starts off by calling |\scan| to get the first
word of the next line.  If |\word| is an integer literal, it is
treated as a line number and the rest of the input line is stored in
the appropriate variable without any interpretation.  If |\word| is
not an integer literal, it is treated as a command.

Each command is treated with an {\it ad hoc} routine near the bottom
of |basix.tex|.  However, most of them call on a set of utilities that
appear earlier in the file.

\subhead Character-string Calls \endhead

There is a simple library of macros that convert between ASCII codes
and character tokens, test for string equality, take subsections of
strings, and deal with concatenation.

\subhead Debugging Definitions \endhead

The macro |\diw| is a debugging-mode-only |\immediate\write16| (hence
the name |\diw|).  It is toggled by the user commands |debug| and
|nodebug|.

\subhead Expression Evaluation \endhead

The expression evaluator has a similar calling structure to the
scanner.  Calling routines are split in twain, with 

\verbatim
\def\foo{\after\fooPartTwo\expression}
\def\fooPartTwo{\etc}
\endverbatim

\noindent
being a prototype of the calling convention.  The evaluator will
|\scan| as many words as it can that make sense; in contrast to the
scanner, however, it evaluates their value instead of merely
accumulating them.  The method by which this happens is described
above.

\subhead Linked List \endhead

The \BaSiX\ interpreter maintains a linked list of line numbers.  The
macro 

% Fix how this is done.
\quad|\csname L|$\langle$current line number$\rangle$|\endcsname|

\noindent
contains the next line number.  These macros will follow the linked
list (for the |list| command); they also can insert a new line or
return the line number of the next line.

\subhead Program Parser \endhead

This section contains a number of critical routines.  |\evalline| is
the macro that does the dispatching based on the user's command.
|\mandatory| specifies what the next character must be (for example,
the character after the identifier in a |let| statement must be |=|).
|\parseline| has already been described.

\subhead Syntactic Scanner \endhead

This is the section containing |\scan| and its support macros, which
are described above.

\subhead Type Tests \endhead

These routines take an argument and determine whether it is an
identifier, a string variable, a string literal, an integer literal, a
macro, or a digit.  The normal way of calling these routines is

\verbatim
\expandafter\if\stringP\word
\endverbatim

\noindent
These predicates expand into either |tt| (true) or |tf| (false).
Syntactic sugar is provided in the form of |\itstrue| and |\itsfalse|.
|\ifstring\word| doesn't work because of the way \TeX\ matches |\if|
and |\fi| tokens -- only |\if|-style primitives are recognized.

\subhead User Utilities \endhead

This is the section of the interpreter in which most of the user
commands are defined.  Commands are preceded by |\C| ({\it e.g.},
|\Clist| is the macro called when the user types |list|).  Functions
are preceded by |\F|.

\head Generalization \endhead

The \BaSiX\ interpreter can easily be generalized to serve other
needs.  These other needs might be to interpret Lisp or \ps\ code
[Anyone want to write a \ps\ interpreter in \TeX?]; or to take source
code in a given language and pretty-print it.

The definition of a ``word'' can be changed by modifying the |\scan|
macro.  It selects a definition for |\scantest| based on the first
character; |\scantest| is what determines if a given token matches the
regexp (and it is allowed to redefine itself).  

The evaluation of expressions can be extended or changed by modifying
the |\math| code.  Floating-point (or even fixed-point) numbers could
be dealt with, although the period would need to pass the |\digitP|
test in some cases and not in others.

The method of dealing with newlines is easily removed for languages
such as \ps\ or Lisp for which all whitespace is the same.

\head Summary \endhead

Using a number of \TeX\ tricks, some more devious than others, a
\basic\ interpreter can be written in \TeX.  While \TeX\ macros will
often be less efficient than, for example, awk paired with \TeX,
solutions using only \TeX\ will be more portable.  A less general
macro package than \BaSiX\ could be written that uses these routines
as paradigms and that is very efficient at parsing a specific input
format.

\bye
