#!/bin/sh
echo 'Start of kamin, part 01 of 06:'
echo 'x - chap1.tex'
sed 's/^X//' > chap1.tex << '/'
X\chapter{The Basic Interpreter}
X
XThe structure of our basic interpreter\footnote{It should be noted that our
Xbasic interpreter is not an interpreter for Basic.}
Xdiffers somewhat from that described
Xby Kamin.  Our interpreter is structured around a small main program which
Xmanipulates three distinct types of data structures.  The main program is
Xshown in Figure~\ref{main}, and will be discussed in more detail in the
Xnext section.  
XEach of the three main data structures is represented by a C++ class, such
Xis subclassed in various ways by the different interpreters.
XThe three varieties of data structures are the following:
X\begin{itemize}
X\item
X{\bf Readers}.  
XInstances of this class prompt the user for input values,
Xand break the input into a structure of unevaluated components.
XA single instance of either the class {\sf Reader} or a subclass
Xis created during the initialization
Xprocess for each interpreter.  The base reader class is subclassed in those
Xinterpreters which introduce new syntactic elements (such as quoted lists
Xin Lisp or vectors in APL).
X\item
X{\bf Environments}.
XAn Environment is a data structure used to maintain a collection of
Xsymbol-value pairs, such as the global run-time environment or the values
Xof arguments passed to a function.  Values can be added to an environment,
Xand the existing binding of a symbol to a value can be changed to a new
Xvalue.
X\item
X{\bf Expressions}.
XExpressions represent the heart of the system, and the differences between
Xthe various interpreters is largely found in the various different types of
Xexpressions they manipulate.  Expressions know how to ``evaluate
Xthemselves'' where the meaning of that expression is determined by each
Xtype of expression.  In addition expressions also know how to print their
Xvalue, and that, too, differs for each type of expression.
X\end{itemize}
X
XIn subsequent sections we will explore in more detail each of these data
Xstructures.
X
X\section{The Main Program}
X
XFigure~\ref{main} shows the main program,\footnote{I have omitted the
X``include'' directives and certain global declarations from this figure.
XThe complete code can be found elsewhere (where?).}
Xwhich defines the top level
Xcontrol for the interpreters.  The same main program is used for each of
Xthe interpreters.  Indeed, the vast majority of code remains constant
Xthroughout the interpreters.
X
X\begin{figure}
X\begin{cprog}
Xmain() {
X	Expr entered;	// expression as entered by users
X
X	// common initialization
X	emptyList = new ListNode(0, 0);
X	globalEnvironment = new Environment(emptyList, emptyList, 0);
X	valueOps = new Environment(emptyList, emptyList, 0);
X	commands = new Environment(emptyList, emptyList, valueOps);
X
X	// language-specific initialization
X	initialize();
X
X	// the read-eval-print loop
X	while (1) {
X		entered = reader->promptAndRead();
X
X		// see if expression is quit
X		Symbol * sym = entered()->isSymbol();
X		if (sym && (*sym == "quit"))
X			break;
X
X		// nothing else, must just be an expression
X		entered.evalAndPrint(commands, globalEnvironment);
X		}
X}
X\end{cprog}
X\caption{The Read-Eval-Print Loop for the interpreters}\label{main}
X\end{figure}
X
XThe structure of the main program is very simple.
XTo begin, a certain amount of initialization is necessary.  There are four
Xglobal variables found in all the interpreters.  The variable
X{\sf emptyList} contains a list with no elements.  (We will return to a
Xdiscussion of lists in Section~\ref{listsec}).
XThe three environments {\sf globalEnvironment}, {\sf valueOps} and {\sf
Xcommands} represent the top-level context for the interpreters.
XThe {\sf globalEnvironment} contains those symbols that are accessible at
Xthe top level.  The {\sf valueOps} are those operations that can be
Xperformed at any level, but which are not symbols themselves that can be
Xmanipulated by the user.  Finally {\sf commands} are those functions that
Xcan be invoked only at the top level of execution.  That is, commands
Xcannot be executed within function definitions.
X
XFollowing the common initialization the function {\sf initialize} is called
Xto provide interpreter-specific initialization.  This chiefly consists of
Xadding values to the three environments.  This function is changed 
Xin each of the various interpreters.
X
XThe heart of the system is a single loop, which executes until the user
Xtypes the directive {\sf quit}.\footnote{The reader data structure will
Xtrap end-of-input signals, and if detected acts as if the user had typed
Xthe {\sf quit} directive.}  The reader (which must be defined as part of the
Xinterpreter-specific initialization) requests a value from the user.
XAfter testing for the the {\sf quit} directive, the entered expression is
Xevaluated.  We will defer an explaination of the {\sf evalAndPrint} method 
Xuntil Section~\ref{exprsec}, merely noting here that 
Xit evaluates the expression the user has entered and prints the result.
XThe read-eval-print cycle then continues.
X
X\section{Readers}
X
XReaders are implemented by instances of class {\sf Reader}, shown in
XFigure~\ref{readerclass}.  The only public function performed by this class
Xis provided by the method {\sf promptAndRead}, which prints the interpreter
Xprompt, waits for input from the user, and then parses the input into a
Xlegal, but unevaluated, expression (usually a symbol, integer or 
Xlist-expression).  These actions are implemented by a variety of utility
Xroutines, which are declared as {\sf protected} so that they may be
Xmade available to later subclasses.
X
X\begin{figure}
X\begin{cprog}
Xclass Reader {
Xpublic:
X	Expression * promptAndRead();
X
Xprotected:
X	char buffer[1000];	// the input buffer
X	char * p;		// current location in buffer
X
X	// general functions
X	void printPrimaryPrompt();
X	void printSecondaryPrompt();
X	void fillInputBuffer();
X	int  isSeparator(int);
X	void skipSpaces();
X	void skipNewlines();
X
X	// functions that can be overridden
X	virtual Expression * readExpression();
X
X	// specific types of expressions
X	int readInteger();
X	Symbol * readSymbol();
X	ListNode * readList();
X};
X\end{cprog}
X\caption{Class Description of the reader class}\label{readerclass}
X\end{figure}
X
X\begin{figure}
X\begin{cprog}
XExpression * Reader::promptAndRead()
X{
X	// loop until the user types something
X	do {
X		printPrimaryPrompt();
X		fillInputBuffer();
X		} while (! *p);
X
X	// now that we have something, break it apart
X	Expression * val = readExpression();
X
X	// make sure we are at and of line
X	skipSpaces();
X	if (*p) {
X		error("unexpected characters at end of line:", p);
X		}
X
X	// return the expression
X	return val;
X}
X\end{cprog}
X\caption{The Method {\sf promptandRead} from class {\sf Reader}}\label{promptAndRead}
X\end{figure}
X
XThe code that implements this data structure is relatively
Xstraight-forward, and most of it will not be presented here.
XThe main method is the
Xsingle public-accessible routine {\sf promptAndRead}, which is shown in
XFigure~\ref{promptAndRead}.  
XThis method loops until the user enters an expression.  The method
X{\sf fillInputBuffer} places the instance pointer {\sf p} at the first 
Xnon-space character (also stripping out comments).   Thus lines containing 
Xonly spaces,
Xnewlines, or comments are handled quickly here, and cause no further
Xaction.  Also, as have noted previously, an end-of-input indication is
Xcaught by the method {\sf fillInputBuffer}, which then places the 
X{\sf quit} command in the input buffer.
XThe method {\sf readExpression} (Figure~\ref{readExpression}) is the parser 
Xused to break the input into
Xan unevaluated expression.  This method is declared {\sf virtual}, and thus
Xcan be redefined in subclasses.  The base method recognizes only integers,
Xsymbols, and lists.   The routine to read a list recursively calls the
Xmethod to read an expression.
X
X\begin{figure}
X\begin{cprog}
XExpression * Reader::readExpression()
X{
X	// see if it's an integer
X	if (isdigit(*p))
X		return new IntegerExpression(readInteger());
X
X	// might be a signed integer
X	if ((*p == '-') && isdigit(*(p+1))) {
X		p++;
X		return new IntegerExpression(- readInteger());
X		}
X
X	// or it might be a list
X	if (*p == '(') {
X		p++;
X		return readList();
X		}
X	
X	// otherwise it must be a symbol
X	return readSymbol();
X}
X
XListNode * Reader::readList()
X{
X	// skipNewlines will issue secondary prompt
X	// until a valid character is typed
X	skipNewlines();
X
X	// if end of list, return empty list
X	if (*p == ')') {
X		p++;
X		return emptyList;
X		}
X
X	// now we have a non-empty character
X	Expression * val = readExpression();
X	return new ListNode(val, readList());
X}
X\end{cprog}
X\caption{The method {\sf readExpression} and {\sf readList}}\label{readExpression}
X\end{figure}
X
X\section{Environments}
X
XAs we have noted already, the {\sf Environment} data structure is used to
Xmaintain symbol-value pairings.  In addition to the global environments
Xdefined during initialization, environments are created for argument lists
Xpassed to functions, and in various other contexts by some of the later
Xinterpreters.  Environments can be linked together, so that if a symbol is
Xnot found in one environment another can be automatically searched.
XThis facilitates lexical scoping, for example.
X
XFor reasons having to do with memory management, the {\sf Environment} data
Xstructure, shown in Figure~\ref{environment}, is declared as a subclass of
Xthe class {\sf Expression}.  Unlike other expressions, however,
Xenvironments are never directly manipulated by the user.
XAlso for memory management reasons, there is a class {\sf Env} declared
Xwhich can maintain a pointer to an environment.   The two methods defined
Xin class {\sf Env} set and return this value.   Anytime a pointer is to be
Xmaintained for any period of time, such as the link field in an
Xenvironment, it is held in a variable declared as {\sf Env} rather than as
Xa pointer directly.
XFinally the overridden virtual methods {\sf isEnvironment} and {\sf free} 
Xin class {\sf Environment} are also
Xrelated to memory management, and we will defer a discussion of these until
Xthe next section.
X
X\begin{figure}
X\begin{cprog}
Xclass Environment : public Expression {
Xprivate:
X	List theNames;
X	List theValues;
X	Env theLink;
X
Xpublic:
X	Environment(ListNode *, ListNode *, Environment *);
X
X	// overridden methods
X	virtual Environment * isEnvironment();
X	virtual void free();
X
X	// new methods
X	Expression * lookup(Symbol *);
X	void add(Symbol *, Expression *);
X	void set(Symbol *, Expression *);
X};
X
Xclass Env : public Expr {
Xpublic:
X	operator Environment * ();
X	void operator = (Environment * r);
X};
X\end{cprog}
X\caption{The {\sf Environment} data structure}\label{environment}
X\end{figure}
X
XThe three methods used to manipulate environments are {\sf lookup}, {\sf
Xadd} and {\sf set}.   The first attempts to find the value of the symbol
Xgiven as argument, returning a null pointer if no value exists.
XThe method {\sf add} adds a new symbol-value pair to the front of the current
Xenvironment.  The method {\sf set} is used to redefine an existing value.
XIf the symbol is not found in the current environment and there is a valid
Xlink to another environment the linked environment is searched.  If the
Xlink field is null (that is, there is no next environment), the symbol and
Xvalued are {\sf add}ed to the current environment.
X
XEnvironments are implemented using the List data structure, a form of 
XExpression we will describe in more detail in Section~\ref{listsec}.
XTwo parallel lists contain the symbol keys and their associated values.
XFor the moment it is only necessary to characterize lists by four
Xoperations.   A list is composed of list nodes (elements of class {\sf
XListNode}).  Each node contains an expression (the head) and, recursively,
Xanother list.  The special value {\sf emptyList}, which we have already
Xencountered, terminates every list.
XThe operation {\sf head} returns the first element of a list node.  
XWhen provided with an argument, the operation {\sf head} can be used to
Xmodify this first element.
XThe operation {\sf tail} returns the remainder of the list.
XFinally the operation {\sf isNil} returns true if and only if the list is
Xthe empty list.
X
X\begin{figure}
X\begin{cprog}
XExpression * Environment::lookup(Symbol * sym)
X{
X	ListNode * nameit = theNames;
X	ListNode * valueit = theValues;
X
X	while (! nameit->isNil()) {
X		if (*sym == nameit->head())
X			return valueit->head();
X		nameit = nameit->tail();
X		valueit = valueit->tail();
X		}
X
X	// otherwise see if we can find it on somebody elses list
X	Environment * link = theLink;
X	if (link) return link->lookup(sym);
X
X	// not found, return nil value
X	return 0;
X}
X\end{cprog}
X\caption{The method {\sf lookup} in class {\sf Environment}}\label{lookup}
X\end{figure}
X
XFigure~\ref{lookup} shows the method {\sf lookup}, which is defined in
Xterms of these four operations.  The while loop cycles over the list of
Xkeys until the end (empty list) is reached.  Each key is tested against the
Xargument key, using the equality test provided by the class {\sf Symbol}.
XOnce a match is found the associated value is returned.
X
XIf the entire list of names is searched with no match found,
Xif there is a link to another environment the lookup message is passed to
Xthat environment.  If there is no link, a null value is returned.
X
XThe routine to add a new value to an environment (Figure~\ref{add}) merely 
Xattaches a new name and value to the beginning of the respective lists.  
XNote by attaching to be beginning of a list this will hide any existing 
Xbinding of the name, although such a situation will not often occur.  
XThe method {\sf set} searches for an existing binding, replacing it if
Xfound, and only adding the new element to the final environment if no 
Xbinding can be located.
X
X\begin{figure}
X\begin{cprog}
Xvoid Environment::add(Symbol * s, Expression * v)
X{
X	theNames = new ListNode(s, (ListNode *) theNames);
X	theValues = new ListNode(v, (ListNode *) theValues);
X}
X
Xvoid Environment::set(Symbol * sym, Expression * value)
X{
X	ListNode * nameit = theNames;
X	ListNode * valueit = theValues;
X
X	while (! nameit->isNil()) {
X		if (*sym == nameit->head()) {
X			valueit->head(value);
X			return;
X			}
X		nameit = nameit->tail();
X		valueit = valueit->tail();
X		}
X
X	// see if we can find it on somebody elses list
X	Environment * link = theLink;
X	if (link) {
X		link->set(sym, value);
X		return;
X		}
X
X	// not found and we're the end of the line, just add
X	add(sym, value);
X}
X\end{cprog}
X\caption{Methods used to Insert into an environment}\label{add}
X\end{figure}
X
X\section{Expressions}\label{exprsec}
X
XThe class {\sf Expression} is a root for a class hierarchy that contains 
Xthe majority of classes defined in these interpreters.  Figure~\ref{classpic} 
Xshows a portion of this class hierarchy.  We have already seen that
Xenvironments are a form of expression, as are integers, symbols, lists and
Xfunctions. 
X
X\setlength{\unitlength}{5mm}
X\begin{figure}
X\begin{picture}(16,10)(-4,-3)
X\put(-3.5,0){\sf Expression}
X\put(0,0.2){\line(1,0){1}}
X\put(1,0){\sf Function}
X\put(0,0.2){\line(1,1){1}}
X\put(1,1){\sf List}
X\put(0,0.2){\line(1,2){1}}
X\put(1,2){\sf Symbol}
X\put(0,0.2){\line(1,3){1}}
X\put(1,3){\sf Integer}
X\put(0,0.2){\line(1,-2){1}}
X\put(1,-2){\sf Environment}
X\put(4,0.2){\line(1,0){1}}
X\put(5,0){\sf BinaryFunction}
X\put(4,0.2){\line(1,1){1}}
X\put(5,1){\sf UnaryFunction}
X\put(4,0.2){\line(1,2){1}}
X\put(5,2){\sf BeginStatement}
X\put(4,0.2){\line(1,3){1}}
X\put(5,3){\sf SetStatement}
X\put(4,0.2){\line(1,4){1}}
X\put(5,4){\sf WhileStatement}
X\put(4,0.2){\line(1,5){1}}
X\put(5,5){\sf IfStatement}
X\put(4,0.2){\line(1,6){1}}
X\put(5,6){\sf DefineStatement}
X\put(4,0.2){\line(1,-1){1}}
X\put(5,-1){\sf UserFunction}
X\put(9.5,0.2){\line(1,0){1}}
X\put(10.5,0){\sf IntegerBinaryFunction}
X\end{picture}
X\caption{The {\sf Expression} class Hierarchy in Chapter 1}\label{classpic}
X\end{figure}
X
X\subsection{The Abstract Class}
X
XThe major purposes of the abstract class {\sf Expression} 
X(Figure~\ref{expression}) are to perform memory management functions, to
Xpermit conversions from one type to another in a safe manner, and to define
Xprotocol for evaluation and printing of expression values.  The latter is
Xeasist to dismiss.  The virtual methods {\sf eval} and {\sf print} provide
Xfor evaluation and printing of values.  The {\sf eval} method takes as
Xargument a target expression to which the evaluated expression will be
Xassigned, as well as two environments.  The first environment contains the
Xlist of legal value-ops for the expression, while the second is the more
Xgeneral environment in which the expression is to be evaluated.
XThe default method for {\sf eval} merely assigns the current expression to
Xthe target.  This suffices for objects, such as integers, which yield
Xthemselves no matter how many times they are evaluated.
XThe default method {\sf print}, on the other hand, prints an error message.
XThus this method should always be overridden in subclasses.
X
X\begin{figure}
X\begin{cprog}
Xclass Expression {
Xprivate:
X	friend class Expr;
X	int referenceCount;
Xpublic:
X	Expression();
X
X	virtual void free();
X
X	// basic object protocol
X	virtual void eval(Expr &, Environment *, Environment *);
X	virtual void print();
X
X	// conversion tests
X	virtual Expression * touch();
X	virtual IntegerExpression * isInteger();
X	virtual Symbol * isSymbol();
X	virtual Function * isFunction();
X	virtual ListNode * isList();
X	virtual Environment * isEnvironment();
X	virtual APLValue * isAPLValue();
X	virtual Method * isMethod();
X};
X\end{cprog}
X\caption{The Class {\sf Expression}}\label{expression}
X\end{figure}
X
X\subsubsection{Memory Management}
X
XFor long running programs it is imperative that memory associated with
Xunused expressions be recovered by the underlying operating system.
XThis is accomplished in these interpreters through the mechanism of
Xreference counts.  Every expression contains a reference count field,
Xwhich is initially set to zero by the constructor in class {\sf Expression}.
XThe integer value maintained in this field represents the number of
Xpointers that reference the object.  When this count becomes zero, no
Xpointers refer to the object and the memory associated with it can be
Xrecovered.
X
XThe maintenance of reference counts if peformed by the class 
X{\sf Expr} (Figure~\ref{expr}).
XAs with the class {\sf Env} we have already encountered, the class {\sf Expr}
Xis a holder class, which maintains an expression pointer.
XA value can be inserted into an {\sf Expr} either through construction or
Xthe assignment operator.  A value can be retrieved either though the
Xprotected method {\sf val} or, as a notational convenience, through the 
Xparenthesis
Xoperator.  The method {\sf evalAndPrint}, as have noted already, merely 
Xpasses the {\sf eval} message on to the underlying expression and
Xprints the resulting value.
X
X\begin{figure}
X\begin{cprog}
Xclass Expr {
Xprivate:
X	Expression * value;
X
Xprotected:
X	Expression * val()
X		{ return value; }
X
Xpublic:
X	Expr(Expression * = 0);
X
X	Expression * operator ()()
X		{ return val(); }
X
X	void operator = (Expression *);
X
X	void evalAndPrint(Environment *, Environment *);
X};
X\end{cprog}
X\caption{The class {\sf Expr}}\label{expr}
X\end{figure}
X
XFigure~\ref{assign} gives the implementation of the constructor and
Xassignment operator for class {\sf Expr}.  The constructor takes an
Xoptional pointer to an expression, which may be a null expression (the
Xdefault).  If the expression is
Xnon-null, the reference count for the expression is incremented.
XSimilarly, the assignment operator first increments the reference count of
Xthe new expression.  Then it decrements the reference count of the existing
Xexpression (if non-null), and if the reference count reaches zero,
Xthe memory is released, using the system function {\sf delete}.
XImmediately prior to destruction, the virtual method {\sf free} is invoked.
XClasses can override this method to provide any necessary class-specific 
Xmaintenance.  For example, the class {\sf Environment} (Figure~\ref{environment})
Xassigns null values to the structures {\sf theNames}, {\sf theValues} and
X{\sf theLink}, thereby possibly triggering the release of their storage as
Xwell.
X
X\begin{figure}
X\begin{cprog}
XExpr::Expr(Expression * val)
X{
X	value = val;
X	if (val) value->referenceCount++;
X}
X
Xvoid Expr::operator = (Expression * newvalue)
X{
X	// increment right hand side of assignment
X	if (newvalue) {
X		newvalue->referenceCount++;
X		}
X
X	// decrement left hand side of assignment 
X	if (value) {
X		value->referenceCount--;
X		if (value->referenceCount = 0) {
X			value->free();
X			delete value;
X			}
X		}
X
X	// then do the assignment
X	value = newvalue;
X}
X\end{cprog}
X\label{Assignment and Initialization of Expressions}\label{assign}
X\end{figure}
X
X\subsubsection{Type Conversion}
X
XA common difficulty in a statically typed language such as C++ is the {\em
Xcontainer problem}.  Elements placed into a general purpose data structure, such
Xas a list, must have a known type.  Generally this is accomplished by
Xdeclaring such elements as a general type, such as {\sf Expression}.  But
Xin reality such elements are usually instances of a more specific subclass,
Xsuch as an integer or a symbol.  When we remove these values from the list,
Xwe would like to be able to recover the original type.
X
XThere are actually two steps in the solution of this problem.
XThe first step is testing the type of an object, to see if it is of a
Xcertain form.   The second step is to legally assign the object to 
Xa variable declared as the more specific class.  In these interpreters
Xthe mechanism of virtual methods is used to combine these two functions.
XIn the abstract class {\sf Expression} a number of virtual functions are
Xdefined, such as {\sf isInteger} and {\sf isEnvironment}.   These are
Xdeclared as returning a pointer type.   The default behavior, as provided
Xby class {\sf Expression}, is to return a null pointer.  In an appropriate
Xclass, however, this method is overridden so as to return the current element.
XThat is, the class associated with integers overrides {\sf isInteger}, the
Xclass associated with symbols overrides {\sf isSymbol}, and so on.
XFigure~\ref{isEnvironment} shows the two definitions of {\sf
XisEnvironment}, the first from class {\sf Expression} and the second from
Xclass {\sf Environment}.  
XBy testing whether the result of this method is non-null or not, one can
Xnot only test the type of an object but one can assign the value to
Xa specific class pointer without compromising type safety.
XAn example bit of code is provided in Figure~\ref{isEnvironment} that
Xillustrates the use of these functions.
X
X\begin{figure}
X\begin{cprog}
XEnvironment * Expression::isEnvironment() 
X{ 
X	return 0; 
X}
X
XEnvironment * Environment::isEnvironment()
X{	
X	return this; 
X}
X
XExpression * a = new Symbol("test");
XExpression * b = new Environment(emptyList, emptyList, 0);
X
XEnvironment * c = a->isEnvironment();	// will yield null
XEnvironment * d = b->isEnvironment();	// will yield the environment
X
Xif (c) 
X	printf("c is an environment");	// won't happen
Xif (d)
X	printf("d is an environment");	// will happen
X\end{cprog}
X\caption{Type safe object test and conversion}\label{isEnvironment}
X\end{figure}
X
XThe method {\sf touch} presents a slightly different situation.
XIt is defined in the abstract class to merely return the object to which
Xthe message is sent.  That is, it is a null-operation.  In
XChapter~\ref{sasl}, when we introduce delayed evaluation, we will define a
Xtype of expression which is not evaluated until it is needed.   This
Xexpression will override the touch method to force evaluation at that point.
X
X\subsection{Integers}
X
XInternally within the interpreters integers are represented by the class
X{\sf IntegerExpression} (Figure~\ref{integerexpr}).  The actual integer
Xvalue is maintained as a private value set as part of the construction
Xprocess.  This value can be accessed via the method {\sf val}.
XThe only overridden methods are the {\sf print} method, which prints the
Xinteger value, and the {\sf isInteger} method, which yields the current
Xobject.
X
X\begin{figure}
X\begin{cprog}
Xclass IntegerExpression : public Expression {
Xprivate:
X	int value;
Xpublic:
X	IntegerExpression(int v) 
X		{ value = v; }
X
X	virtual void print();
X	virtual IntegerExpression * isInteger();
X
X	int val()
X		{ return value; }
X};
X\end{cprog}
X\caption{The class {\sf IntegerExpression}}\label{integerexpr}
X\end{figure}
X
X\subsection{Symbols}
X
XSymbols are used to represent uninterpreted character strings, for example
Xidentifier names.  Instances of class {\sf Symbol} (Figure~\ref{symbol})
Xmaintain the text of their value in a private instance variable.  This
Xcharacter pointer can be recovered via the method {\sf chars}.
XStorage for this text is allocated as part of the construction process,
Xand deleted by the virtual method {\sf free}.  The equality testing
Xoperators return true if the current symbol matches the text of the
Xargument.
X
X\begin{figure}
X\begin{cprog}
Xclass Symbol : public Expression {
Xprivate:
X	char * text;
X
Xpublic:
X	Symbol(char *);
X
X	virtual void free();
X	virtual void eval(Expr &, Environment *, Environment *);
X	virtual void print();
X	virtual Symbol * isSymbol();
X
X	int operator == (Expression *);
X	int operator == (char *);
X	char * chars() { return text; }
X};
X
Xvoid Symbol::eval(Expr & target, Environment * valueops, Environment * rho)
X{
X	Expression * result = rho->lookup(this);
X	if (result)
X		result = result->touch();
X	else
X		result = error("evaluation of unknown symbol: ", text);
X	target = result;
X}
X\end{cprog}
X\caption{The class {\sf Symbol}}\label{symbol}
X\end{figure}
X
XFigure~\ref{symbol} also shows the implementation of the method {\sf eval}
Xin the class {\sf Symbol}.  When a symbol is evaluated it is used as a key
Xto index the current environment.  If found the (possibly touched)
Xassociated value is assigned to the target.  If it is not found an error 
Xmessage is generated.   The routine {\sf error} always yields a null 
Xexpression.
X
X\subsection{Lists}\label{listsec}
X
XWe have already encountered the behavior of the List data structure
X(Figure~\ref{list}) in the discussion of environments.
XAs with expressions and environments, lists are represented by a pair of
Xclasses.  The first, class {\sf ListNode}, maintains the actual list data.
XThe second, class {\sf List}, is merely a pointer to a list node, and
Xexists only to provide memory management operations.
X
XOnly one feature of the latter class deserves comment; rather than
Xoverloading the parenthesis operator the class {\sf List} defines a
Xconversion operator which permits instances of class {\sf List} to be
Xconverted without comment to {\sf ListNodes}.  Thus in most cases a {\sf
XList} can be used where a {\sf ListNode} is expected, and the conversion
Xwill be implicitly defined.  We have seen this already, without having
Xnoted the fact, in
Xseveral places where the variable {\sf emptyList} (an instance of class
X{\sf List}) was used in situations where an instance of class {\sf
XListNode} was required.
X
X\begin{figure}
X\begin{cprog}
Xclass ListNode : public Expression {
Xprotected:
X	Expr h;		// the head field
X	Expr t;		// the tail field
X
Xpublic:
X	ListNode(Expression *, Expression *);
X
X	// overridden methods
X	virtual void free();
X	virtual void eval(Expr &, Environment *, Environment *);
X	virtual void print();
X	virtual ListNode * isList();
X
X	// list specific methods
X	int isNil();
X	int length();
X	Expression * at(int);
X	virtual Expression * head();
X	void head(Expression * x);
X	ListNode * tail();
X};
X
X
Xclass List : public Expr {
Xpublic:
X	operator ListNode *();
X	void operator = (ListNode * r);
X};
X\end{cprog}
X\caption{The classes {\sf List} and {\sf ListNode}}\label{list}
X\end{figure}
X
XThe actual list data is maintained in the instance variables {\sf h} and
X{\sf t}, which we have already noted can be retrieved (and, in the case of
Xthe h, set) by the methods {\sf head} and {\sf tail}.  The method {\sf
Xlength} returns the length of a list, and the method {\sf at} permits a
Xlist to be indexed as an array, starting with zero for the head position.
X
XThe majority of methods, such as {\sf length}, {\sf at}, {\sf print},
Xare simple recursive routines, and will not be discussed.  Only one method
Xis sufficiently complex to deserve comment, and this is the procedure used to
Xevaluate a list.  A list is interpreted as a function call, and thus 
Xthe evaluation of a list involves finding the indicated function and
Xinvoking it, passing as arguments the remainder of the list.  These actions
Xare performed by the method {\sf eval} shown in Figure~\ref{listeval}.
XAn empty list always evaluates to itself.  Otherwise the first argument to
Xthe list is examined.  If it is a symbol, a test is performed to see if it
Xis one of the value-ops.  If it is not found on the value-op list the first
Xelement is evaluated, whether or not it is a symbol.  Generally this will
Xyield a function value.  If so, the method {\sf apply}, which we will
Xdiscuss in the next section, is used to invoke the function.
XIf the first argument did not evaluate to a function an error is indicated.
X
X\begin{figure}
X\begin{cprog}
Xvoid ListNode::eval(Expr & target, Environment * valueops, Environment * rho)
X{
X
X	// an empty list evaluates to nil
X	if (isNil()) {
X		target = this;
X		return;
X		}
X
X	// if first argument is a symbol, see if it is a valueop
X	Expression * firstarg = head();
X	Expression * fun = 0;
X	Symbol * name = firstarg->isSymbol();
X	if (name) 
X		fun = valueops->lookup(name);
X
X	// otherwise evaluate it in the given environment
X	if (! fun)  {
X		firstarg->eval(target, valueops, rho);
X		fun = target();
X		}
X
X	// now see if it is a function
X	Function * theFun = 0;
X	if (fun) theFun = fun->isFunction();
X	if (theFun) { 
X		theFun->apply(target, tail(), rho);
X		}
X	else {
X		target = error("evaluation of unknown function");
X		return;
X		}
X}
X\end{cprog}
X\caption{The method {\sf eval} from class {\sf List}}\label{listeval}
X\end{figure}
X
X\section{Functions}
X
XIf expressions are the heart of the interpreter, then functions are the 
Xmuscles that keep the heart working.  All behavior, statements, valueops,
Xas well as user-defined functions, are implemented as subclasses of 
Xclass {\sf Function} (Figure~\ref{function}).
XAs we noted in the last section, when a function (written as a list
Xexpression) is evaluated the method {\sf apply} in invoked.
XThis method takes as argument the target for the evaluation and a list of
Xunevaluated arguments.  The default behavior in class {\sf Function} is to
Xevaluate the arguments, using the simple recursive routine {\sf evalArgs},
Xthen invoke the method {\sf applyWithArgs}.
X
X\begin{figure}
X\begin{cprog}
Xclass Function : public Expression {
Xpublic:
X	virtual Function * isFunction();
X
X	virtual min.log
X	
X	void apply(Expr &, ListNode *, Environment *);
X	virtual void applyWithArgs(Expr &, ListNode *, Environment *);
X	virtual void print();
X
X	// isClosure is recognized only by functions
X	virtual int isClosure();
X};
X
Xstatic ListNode * evalArgs(ListNode * args, Environment * rho)
X{
X	if (args->isNil())
X		return args;
X	Expr newhead;
X	Expression * first = args->head();
X	first->eval(newhead, valueOps, rho);
X	return new ListNode(newhead(), evalArgs(args->tail(), rho));
X	newhead = 0;
X}
X
Xvoid Function::apply(Expr & target, ListNode * args, Environment * rho)
X{
X	List newargs = evalArgs(args, rho);
X	applyWithArgs(target, newargs, rho);
X	newargs = 0;
X}
X\end{cprog}
X\caption{The class {\sf Function} and the method {\sf apply}}\label{function}
X\end{figure}
X
XBoth the methods {\sf apply} and {\sf applyWithArgs} are declared as
Xvirtual, and can thus be overridden in subclasses.  Those function that do
Xnot evaluate their arguments, such as the functions implementing the
Xcontrol structures of Chapter 1, override the {\sf apply} method.
XFunction that do evaluate their arguments, such as the majority of
Xvalue-Ops, override the {\sf applyWithArgs} method.
X
XTwo subclasses of {\sf Function} deserve mention.  The class 
X{\sf UnaryFunction} overrides {\sf apply} to test that only one argument 
Xhas been provided.  Similarly the class {\sf BinaryFunction} tests for
Xexactly two arguments.  
XThe remaining major subclass of {\sf Function} is the class {\sf
XUserFunction}.  We will defer a discussion of this until we examine
Xthe implementation of the {\sf define} statement.
X
X\section{The Basic Evaluator}
X
XWe are now in a position to finally describe the characteristics that are
Xunique to the basic evaluator of chapter one.  This interpreter recognizes
Xone command (the {\sf define} statement), several built-in statements
X({\sf if, while, set}, and {\sf begin}), and a number of value-ops.
XAll are implemented internally as functions.  What syntactic category a
Xsymbol is associated with is
Xdetermined by what environment it is placed on, and not by the
Xstructure of the function.
X
X\subsection{The define statement}
X
XThe define statement is implemented as the single instance of the class
X{\sf DefineStatement} (Figure~\ref{define}), entered with the key
X``define'' in the {\sf commands} environment.  The class overrides the
Xvirtual method {\sf apply}, since it must access its arguments before they
Xare evaluated.  It tests that the arguments are exactly three in number,
Xand that the first is a symbol and the second a list.
XIf no errors are detected, an instance of the class {\sf UserFunction} is
Xcreated and and set in the current (always global) environment.
X
X\begin{figure}
X\begin{cprog}
Xclass DefineStatement : public Function {
Xpublic:
X	virtual void apply(Expr &, ListNode *, Environment *);
X};
X
Xvoid DefineStatement::apply(Expr & target, ListNode * args, Environment * rho)
X{
X	if (args->length() != 3) {
X		target = error("define requires three arguments");
X		return;
X		}
X
X	Symbol * name = args->at(0)->isSymbol();
X	if (! name) {
X		target = error("define missing name");
X		return;
X		}
X
X	ListNode * argNames = args->at(1)->isList();
X	if (! argNames) {
X		target = error("define missing arg names list");
X		return;
X		}
X
X	rho->set(name, new UserFunction(argNames, args->at(2), rho));
X
X	// yield as value the name of the function
X	target = name;
X};
X\end{cprog}
X\caption{Implementation of the {\sf define} statement}\label{define}
X\end{figure}
X
XThe class {\sf UserFunction} created by the define statement is similarly a
Xsubclass of class {\sf Function} (Figure~\ref{userfunction}).
XUser functions maintain in instance variables the list of argument names, 
Xthe body of the
Xfunction, and the lexical context in which they are to execute.
XThese values are set by the constructor when the function is defined,
Xand freed by the virtual method {\sf free} when no longer needed.
X
X\begin{figure}
X\begin{cprog}
Xclass UserFunction : public Function {
Xprotected:
X	List argNames;
X	Expr body;
X	Env context;
Xpublic:
X	UserFunction(ListNode *, Expression *, Environment *);
X	virtual void free();
X	virtual void applyWithArgs(Expr &, ListNode *, Environment *);
X	virtual int isClosure();
X};
X
Xvoid UserFunction::applyWithArgs(Expr& target, ListNode* args, Environment* rho)
X{
X	// number of args should match definition
X	ListNode *an = argNames;
X	if (an->length() != args->length()) {
X		error("argument length mismatch");
X		return;
X		}
X
X	// make new environment
X	Env newrho; 
X	newrho = new Environment(an, args, context);
X
X	// evaluate body in new environment
X	Expression * bod = body();
X	if (bod)
X		bod->eval(target, valueOps, newrho);
X	else
X		target = 0;
X
X	newrho = 0;	// force memory recovery
X}
X\end{cprog}
X\caption{The class {\sf UserFunction} and method of application}\label{userfunction}
X\end{figure}
X
XUser functions always work with evaluated arguments, and thus they override
Xthe method {\sf applyWithArgs}.   The implementation of this method is
Xalso shown in Figure~\ref{userfunction}.  This method checks that the
Xnumber of arguments supplied matches the number in the function definition,
Xthen creates a new environment to match the arguments and their values.
XThe expression which represents the body of the function is then evaluated.
XBy passing the new context as argument to the evaluation, symbolic
Xreferences to the arguments will be matched with the appropriate values.
X
X\subsection{Built-In Statements}
X
XThe built-in statements {\sf if, while, set} and {\sf begin} are each
Xdefined by functions entered in the {\sf valueOps} environment.
XWith the exception of {\sf begin}, these must capture their arguments
Xbefore they are evaluated and thus, like {\sf define}, they override the
Xmethod {\sf apply}.
X
X\subsubsection{The If statement}
X
XThe If statement (Figure~\ref{ifstatement}) first insures it has three
Xarguments.  It then evaluates the first argument.  Using the auxiliary
Xfunction {\sf isTrue} (which will vary over the different interpreters as
Xour definition of ``true'' changes) the truth or falsity of the first
Xexpression is determined.  Depending upon the outcome, either the second or
Xthird argument is evaluated to determine the result.
XIn the Chapter 1 interpreter the value 0 is false, and all other values
X(integer or not) are considered to be true.
X
X\begin{figure}
X\begin{cprog}
Xclass IfStatement : public Function {
Xpublic:
X	virtual void apply(Expr &, ListNode *, Environment *);
X};
X
Xvoid IfStatement::apply(Expr & target, ListNode * args, Environment * rho)
X{
X	if (args->length() != 3) {
X		target = error("if statement requires three arguments");
X		return;
X		}
X
X	Expr cond;
X	args->at(0)->eval(cond, valueOps, rho);
X	if (isTrue(cond()))
X		args->at(1)->eval(target, valueOps, rho);
X	else
X		args->at(2)->eval(target, valueOps, rho);
X	cond = 0;
X}
X
Xint isTrue(Expression * cond)
X{
X	IntegerExpression *ival = cond->isInteger();
X	if (ival && ival->val() == 0)
X		return 0;
X	return 1;
X}
X\end{cprog}
X\caption{The implementation of the If statement}\label{ifstatement}
X\end{figure}
X
X\subsubsection{The while statement}
X
XThe function that implements the while statement is shown in
XFigure~\ref{whilestmt}.  Although the while statement requires two
Xarguments, it nevertheless cannot usefully be made a subclass of class {\sf
XBinaryFunction}, since it must access its arguments before they are evaluated.
XThe implementation of the while statements loops until the first argument
Xevaluates to a true condition, using the same test for true method used by
Xthe if statement.  The results returned by evaluating the body of the while
Xstatement are ignored, as the body is executed just for side effects.
X
X\begin{figure}
X\begin{cprog}
Xvoid WhileStatement::apply(Expr & target, ListNode * args, Environment * rho)
X{	Expr stmt;
X
X	if (args->length() != 2) {
X		target = error("while statement requires two arguments");
X		return;
X		}
X
X	// grab the two pieces of the statement
X	Expression * condexp = args->at(0);
X	Expression * stexp = args->at(1);
X
X	// then start the execution loop
X	condexp->eval(target, valueOps, rho);
X	while (isTrue(target())) {
X		// evaluate body
X		stexp->eval(stmt, valueOps, rho);
X		// but ignore it (and force memory reclamation)
X		stmt = 0;
X		// then reevaluate condition
X		condexp->eval(target, valueOps, rho);
X		}
X}
X\end{cprog}
X\caption{The implementation of the While statement}\label{whilestmt}
X\end{figure}
X
X\subsubsection{The set statement}
X
XThe implementation of the set statement is shown in
XFigure~\ref{setstatement}.  The function insures the first argument is a
Xsymbol, evaluates the second argument, then sets the binding of the symbol
Xto value in the current environment.
X
X\begin{figure}
X\begin{cprog}
Xvoid SetStatement::apply(Expr & target, ListNode * args, Environment * rho)
X{
X	if (args->length() != 2) {
X		target = error("set statement requires two arguments");
X		return;
X		}
X
X	// get the two parts
X	Symbol * sym = args->at(0)->isSymbol();
X	if (! sym) {
X		target = error("set commands requires symbol for first arg");
X		return;
X		}
X
X	// set target to value of second argument
X	args->at(1)->eval(target, valueOps, rho);
X
X	// set it in the environment
X	rho->set(sym, target());
X}
X\end{cprog}
X\caption{The implementation of the set statement}\label{setstatement}
X\end{figure}
X
X\subsubsection{The begin statement}
X
XUnlike the other statements, the begin statement does what to evaluate each
Xof its arguments.  Thus it overrides the method {\sf applyWithArgs},
Xinstead of the method {\sf apply}.  It merely assigns to the target
Xvariable the value of the last expression (Figure~\ref{beginstatement}).
X
X\begin{figure}
X\begin{cprog}
Xvoid BeginStatement::applyWithArgs(Expr& target, ListNode* args, Environment* rho)
X{
X	int len = args->length();
X
X	// yield as result the end of the list
X	if (len < 1) 
X		target = error("begin needs at least one statement");
X	else
X		target = args->at(len - 1);
X}
X\end{cprog}
X\caption{The implementation of the begin statement}\label{beginstatement}
X\end{figure}
X
X\subsection{The value-Ops}
X
XThe Value-ops are functions placed in the {\sf valueop} global environment.
XThey can be divided into two categories; there are those that take two
Xinteger arguments and produce an integer result ($+$, $-$, $*$, $/$, $=$,
X$<$ and $>$) and those that take a single argument ({\sf print}).  
X
XThe implementation of the integer binary functions is simplified by the
Xintroduction of an intermediate class {\sf IntegerBinaryFunction}, a
Xsubclass of {\sf BinaryFunction} (Figure~\ref{plusfun}).  
XThe private state for each instance of this class holds a pointer to a
Xfunction that takes two integer values and generates an integer result.
XThe {\sf applyWithArgs} method in this class
Xdecodes the two integer arguments, then invokes the stored function to
Xproduce the new integer value.  To implement each of the seven binary
Xinteger functions (the relational functions generate 0 and 1 values for
Xtrue and false, remember) it is only necessary define an appropriate
Xfunction and pass it as argument to the constructor during initialization of
Xthe interpreter.  This can be seen in Figure~\ref{chap1init}.
X
XThe print function is implemented by a subclass of {\sf UnaryFunction}
Xthat merely invokes the method {\sf print} on the argument.  All
Xexpressions will respond to this method.
X
X\begin{figure}
X\begin{cprog}
Xclass IntegerBinaryFunction : public BinaryFunction {
Xprivate:
X	int (*fun)(int, int);
Xpublic:
X	IntegerBinaryFunction(int (*afun)(int, int));
X	virtual void applyWithArgs(Expr &, ListNode *, Environment *);
X	virtual int value(int, int);
X};
X
Xvoid IntegerBinaryFunction::applyWithArgs(Expr& target, ListNode  args, 
X		Environment* rho)
X{
X	Expression * left = args->at(0);
X	Expression * right = args->at(1);
X	if ((! left->isInteger()) || (! right->isInteger())) {
X		target = error("arithmetic function with nonint args");
X		return;
X		}
X	
X	target =  new IntegerExpression(
X		fun(left->isInteger()->val(), right->isInteger()->val()));
X}
X
Xint PlusFunction(int a, int b) { return a + b; }
Xint MinusFunction(int a, int b) { return a - b; }
Xint TimesFunction(int a, int b) { return a * b; }
Xint DivideFunction(int a, int b)
X{
X	if (b != 0)
X		return a / b;
X	error("division by zero");
X	return 0;
X}
Xint IntEqualFunction(int a, int b) { return a == b; }
Xint LessThanFunction(int a, int b) { return a < b; }
Xint GreaterThanFunction(int a, int b) { return a > b; }
X\end{cprog}
X\caption{Implementation of the Arithmetic Functions}\label{plusfun}
X\end{figure}
X
X\section{Initializing the Run-Time Environment}
X
XFigure~\ref{chap1init} shows the initialization routine for the
Xinterpreters of chapter one.  In chapter one there are no global variables
Xdefined at the start of execution.  There is one command, the statement
X{\sf define}, and a number of value-ops.
X
X\begin{figure}
X\begin{cprog}
Xinitialize()
X{
X	// create the reader/parser
X	reader = new Reader;
X
X	// initialize the commands environment
X	Environment * cmds = commands;
X	cmds->add(new Symbol("define"), new DefineStatement);
X
X	// initialize the value-ops environment
X	Environment * vo = valueOps;
X	vo->add(new Symbol("if"), new IfStatement);
X	vo->add(new Symbol("while"), new WhileStatement);
X	vo->add(new Symbol("set"), new SetStatement);
X	vo->add(new Symbol("begin"), new BeginStatement);
X	vo->add(new Symbol("+"), new IntegerBinaryFunction(PlusFunction));
X	vo->add(new Symbol("-"), new IntegerBinaryFunction(MinusFunction));
X	vo->add(new Symbol("*"), new IntegerBinaryFunction(TimesFunction));
X	vo->add(new Symbol("/"), new IntegerBinaryFunction(DivideFunction));
X	vo->add(new Symbol("="), new IntegerBinaryFunction(IntEqualFunction));
X	vo->add(new Symbol("<"), new IntegerBinaryFunction(LessThanFunction));
X	vo->add(new Symbol(">"), new IntegerBinaryFunction(GreaterThanFunction));
X	vo->add(new Symbol("print"), new PrintFunction);
X}
X\end{cprog}
X\caption{Initialization of the Basic Evaluator}\label{chap1init}
X\end{figure}
/
echo 'x - list.cc'
sed 's/^X//' > list.cc << '/'
X# include <std.h>
X# include "list.h"
X# include "function.h"
X# include "environment.h"
X
XListNode::ListNode(Expression * car, Expression * cdr)
X{
X	h = car;
X	t = cdr;
X}
X
Xvoid ListNode::free()
X{
X	h = 0;
X	t = 0;
X}
X
Xint ListNode::isNil()
X{
X	// we are nil if we have no value and no rest of list
X	return h() == 0 && t() == 0;
X}
X
Xint ListNode::length()
X{
X	if (isNil())
X		return 0;
X	ListNode * cd = tail();
X	if (cd)
X		return 1 + cd->length();
X	return 0;
X}
X
XExpression * ListNode::at(int index)
X{
X	if (index <= 0)
X		return head();
X	ListNode * cd = tail();
X	if (cd)
X		return cd->at(index - 1);
X	return error("impossible case", "index to list at: illegal");
X}
X
XListNode * ListNode::tail()
X{
X	if (!t()) {
Xerror("impossible case", "tail on empty list??");
Xexit(1);
X}
X	ListNode * x = t()->isList();
X	if (!x) error("impossible case", "tail can't find list");
X	return x;
X}
X
Xvoid ListNode::eval(Expr & target, Environment * valueops, Environment * rho)
X{
X
X	// an empty list evaluates to nil
X	if (isNil()) {
X		target = this;
X		return;
X		}
X
X	// if first argument is a symbol, see if it is a command
X	Expression * firstarg = head();
X	Expression * fun = 0;
X	Symbol * name = firstarg->isSymbol();
X	if (name) 
X		fun = valueops->lookup(name);
X
X	// otherwise evaluate it in the given environment
X	if (! fun)  {
X		firstarg->eval(target, valueops, rho);
X		fun = target();
X		}
X
X	// now see if it is a function
X	Function * theFun = 0;
X	if (fun)
X		theFun = fun->isFunction();
X	if (theFun) { 
X		theFun->apply(target, tail(), rho);
X		}
X	else {
X		target = error("evaluation of unknown function");
X		// print();	// print out what we know
X		return;
X		}
X}
X
Xvoid ListNode::print()
X{
X	printf("(");
X	if (! isNil()) {
X		// not a nil list, print elements
X		h()->print();
X		Expression *cd = t();
X		while (cd) {
X			ListNode *cdl = cd->isList();
X			if (! cdl) {
X				printf(" "); cd->print();
X				break;
X				}
X			if (cdl->isNil())
X				break;
X			printf(" "); cdl->head()->print();
X			cd = cdl->tail();	
X			}
X		}
X	printf(")");
X}
X
XListNode * ListNode::isList()
X{	return this; }
X
/
echo 'Part 01 of kamin complete.'
exit