\documentclass{article}

\usepackage{6001}


%\usepackage{oldlfont}

%\usepackage{fullpage}

\usepackage{amsmath}

\usepackage{amsthm}

\theoremstyle{definition}
\newtheorem{exercise}{Exercise}

\setcounter{secnumdepth}{0}

\newcommand{\tlisp}[1]{\relax\ifmmode\text{\texttt{#1}}\else\texttt{#1}\fi}

\newcommand{\type}[1]{\text{#1}}

%\newcommand{\cross}{\times}

\newcommand{\pairtyp}[2]{\mathrm{Pair}(\type{#1}, \type{#2})}
\newcommand{\listtyp}[1]{\mathrm{List}(\type{#1})}
\newcommand{\treetyp}[1]{\mathrm{Tree}(\type{#1})}

\newcommand{\vvenv}{\type{Vvenv}}

%\newcommand{\rulesto}{\Rightarrow}

\newcommand{\dsum}{\mid}


\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
%\setlength{\textwidth}{6.0in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}

\begin{document}

\title{Abstract Syntax for Arithmetic Expressions\\
6.001 Section Notes}

\author{Albert R. Meyer}

\date{30 March 2000}

\maketitle

In these notes we'll consider a very simple case of arithmentic
expressions.  There will be just four kinds of expressions: numbers,
variables, sums and products.  We can express this with a data-type
equation:
\[
    \type{Expr} \cong \type{Number-expr} \dsum \type{Variable} \dsum
    \type{Sum} \dsum \type{Product}
\]
where the special symbol ``$\cong$'' should be read as ``has the shape
of''.  The ``$\dsum$'' operation on types indicates that the four kinds of
\type{Expr}'s are separate cases---every expression is of exactly one of
the four kinds above, and there are procedures which, given an
expression, test for each case.  That is, there are procedures:
\[
    \tlisp{number-expr?},\ \tlisp{variable?},\ \tlisp{sum?},\
    \tlisp{product?}: \type{Expr} \to \type{Bool},
\]
and these satisfy the contract that for any given arithmetic expression,
exactly one of them returns the value \texttt{\#t}.

We'll consider sums first.  Abstractly, all that matters about a sum is
that it can be identified as a sum---the procedure \tlisp{sum?}  does
that---and that it has two summands.  So a data type can serve as
\type{Sum} if abstractly it ``has the shape of'' pairs of expressions:
\[
\type{Sum} \cong \pairtyp{Expr}{Expr}.
\]

``Having the shape of'' pairs means that there are constructors and
selectors for \type{Sum} of types
\begin{align*}
    \tlisp{make-sum}:{} & \type{Expr} , \type{Expr} \to \type{Expr} \\
      \tlisp{addend}:{} & \type{Sum} \to \type{Expr}
                && \text{(aka ``first-summand'')} \\
      \tlisp{augend}:{} & \type{Sum} \to \type{Expr}
                && \text{(aka ``second-summand'')}
\end{align*}
which satisfy the \emph{pairing contract}:
\begin{align*}
    \texttt{(addend (make-sum <e\_1> <e\_2>))}
            & \rulesto \texttt{<e\_1>}, \\
    \texttt{(augend (make-sum <e\_1> <e\_2> ))}
            & \rulesto \texttt{<e\_2>}.
\end{align*}

Products work exactly the same way:
\[
    \type{Product} \cong \pairtyp{Expr}{Expr}
\]
\begin{align*}
    \tlisp{make-product}: \type{Expr} , \type{Expr} \to \type{Expr}\\
      \tlisp{multiplier}: \type{Product} \to \type{Expr}
            && \text{(aka ``first-multiplicand'')} \\
    \tlisp{multiplicand}: \type{Product} \to \type{Expr} 
            && \text{(aka ``second-multiplicand'')}
\end{align*}

For simplicity, we won't introduce a \type{Number-expr} abstraction; we'll just
use Scheme numbers:
\[
     \type{Number-expr} = \type{Scheme-numbers},
\]
(Notice this time it is ``$=$'' not ``$\cong$''.)
\[
     \tlisp{(define number-expr?\ number)}
\]



Finally, we consider variables.  Certainly one important feature of a
variable is its name.  Names are intended for use in printing and as
identification tags.  Scheme \type{Symbol}'s have exactly the properties
we want for names, so we'll use them without further abstraction.  To get
the symbolic name of a variable, we require a selector:
\[
     \tlisp{variable-name}: \type{Variable} \to \type{Symbol}.
\]

Another important feature of a variable is its numerical value.  This
value is determined by an abstract structure called a
\emph{variable-values environment} whose type is designated
\vvenv.\footnote{The simple variable-value environments we use here are
sometimes called \emph{dictionaries} or (abstract) \emph{association
lists}.}.  (The point of variables is that their values may vary, which is
why values are not ``built into'' variables.)  A given expression may be
evaluated using different environments which may assign different values
to the same variable.  There is a selector for looking up the value an
environment assigns to a variable:
\[
    \tlisp{lookup}:
        (\type{Variable} , \vvenv) \to \type{Number}
\]

We'll examine the \type{Variable} and \vvenv\ abstractions in more
detail later.


\section{Evaluating expressions}

At this point, the procedure for finding the numerical value of an
expression should be easy to understand: the \tlisp{eval-arith} procedure
takes \emph{two} arguments, the expression whose numerical value is to be
calculated and a variable-value environment to assign the values of
variables; it returns the numerical value of the expression.
\[
    \tlisp{eval-arith}: (\type{Expression} , \vvenv) \to \type{Number}
\]

\newpage
\begin{verbatim}
(define (eval-arith expr env)
  (cond ((number-expr? expr) expr)
        ((sum? expr)
         (let ((rand1
                (eval-arith (addend expr) env))
               (rand2
                (eval-arith (augend expr) env)))
           (+ rand1 rand2)))
        ((product? expr)
         (let ((rand1
                (eval-arith (multiplier expr) env))
               (rand2
                (eval-arith (multiplicand expr) env)))
           (* rand1 rand2)))
        ((variable? expr)
         (lookup expr env))
        (else (error "Bad expression" expr))))
\end{verbatim}


\section{Derivatives}
A procedure for computing the derivative of a abstract expression was
described in lecture.  Here's what it looks like with abstract variables:

\begin{verbatim}
(define (deriv expr var)
  (cond ((number-expr? expr) 0)
        ((sum? expr)
         (make-sum
          (deriv (addend expr) var)
          (deriv (augend expr) var)))
        ((product? expr)
         (let ((plier (multiplier expr))
               (plicand (multiplicand expr)))
           (make-sum
            (make-product (deriv plier var) plicand)
            (make-product (deriv plicand var) plier))))
        ((variable? expr)
         (if (eq? (variable-name expr) (variable-name var)) 1 0))
        (else (error "Bad expression" expr))))
\end{verbatim}

\begin{exercise}   Simplification is another useful operation on
abstract expressions.  Complete the definition of the \texttt{simplify}
procedure below by defining an appropriate \texttt{simplify-prod}
procedure.
\begin{verbatim}
(define (simplify expr)
  (cond ((sum? expr) (simplify-sum expr))
        ((product? expr) (simplify-prod expr))
        (else expr)))
\end{verbatim}

\begin{verbatim}
(define (simplify-sum sum)
  (let ((ad (simplify (addend sum)))
        (au (simplify (augend sum))))
    (cond ((and (number? ad) (number? au))
           (+ ad au))
          ((and (number? ad) (zero? ad)) au)
          ((and (number? au) (zero? au)) ad)
          (else (make-sum ad au)))))

(define (simplify-prod prod)...)
\end{verbatim}
\end{exercise}


\section{Printing and Inputting Expressions}

So far we have considered \emph{computations} with abstract expressions,
but another important activity is \emph{printing} them.  The standard
Scheme/Lisp approach to printing expressions is an interesting contrast to
printing in other languages: we don't try to write our own printing
procedure.  Instead, we take advantage of Scheme's built-in printer and
the Scheme conventions for printing list structures.  Namely, in Scheme,
lists are conventionally displayed as parenthesized expressions which
resemble completely parenthesized mathematical expressions as well as
Scheme expressions.  This, of course, is no coincidence.

So our printing strategy for abstract expressions is to \emph{transform}
an abstract expression \emph{into a list structure}---more precisely a
\emph{tree} structure---whose printed representation looks like an
expression in the format we desire.

For example, suppose we want to exhibit expressions in ``infix''
format---where the operator appears in between the operands as in
\[
                              ((x + 3) * 7)
\]
The following procedure transforms an expression into a tree structure
which prints in infix format:
\[
    \tlisp{expr->infix-tree}: \type{Expr} \to
        \treetyp{Sch-Num $\dsum$ Symbol}
\]
\begin{verbatim}
(define (expr->infix-tree expr)
  (cond ((number-expr? expr) expr)
        ((variable? expr) (variable-name expr))
        ((sum? expr)
         (let ((addend-tree (expr->infix-tree (addend expr)))
               (augend-tree (expr->infix-tree (augend expr))))
           (list addend-tree '+ augend-tree)))
        ((product? expr)
         (let ((multiplier-tree (expr->infix-tree (multiplier expr)))
               (multiplicand-tree (expr->infix-tree (multiplicand expr))))
           (list multiplier-tree '* multiplicand-tree)))
        (else (error "Bad expression" expr))))
\end{verbatim}

To test this procedure, assume \texttt{varx}, \texttt{vary}, and \texttt{varz},
have been defined to be \type{Variables} with names \texttt{x}, \texttt{y}, \texttt{z}:
\begin{verbatim}
(define test-expr
  (make-product
   (make-sum 3 (make-product varz 9))
   (make-sum vary varz)))

>>  (expr->infix-tree test-expr)
;Value: ((3 + (x * 9)) * (y + z))
\end{verbatim}

To get prefix format, we merely reorder the arguments in the two
\tlisp{list} expressions within the \tlisp{expr->infix-tree}
procedure:
\begin{verbatim}
(define (expr->prefix-tree expr)
  (cond ((number-expr? expr) expr)
        ((variable? expr) (variable-name expr))
        ((sum? expr)
         (let ((addend-tree (expr->prefix-tree (addend expr)))
               (augend-tree (expr->prefix-tree (augend expr))))
           (list '+ addend-tree augend-tree))) ; REORDERED
        ((product? expr)
         (let ((multiplier-tree (expr->prefix-tree (multiplier expr)))
               (multiplicand-tree (expr->prefix-tree (multiplicand expr))))
           (list '* multiplier-tree multiplicand-tree))) ; REORDERED
        (else (error "Bad expression" expr))))

>> (expr->prefix-tree test-expr)
;Value 7: (* (+ 3 (* x 9)) (+ y z))
\end{verbatim}
In case you were wondering:
\[
    \treetyp{Anytype} \cong
        \type{Anytype}
            \dsum \listtyp{$\treetyp{Anytype}$}
\]
where
\[
    \listtyp{Anytype} \cong
        \type{Niltype} \dsum \pairtyp{Anytype}{$\listtyp{Anytype}$}
\]
and \type{Niltype} is some datatype with exactly one element.

Instead of constructing a tree, we could construct a string; this time we
have to generate our own parentheses:
\begin{verbatim}
(define (expr->infix-string expr)
  (cond ((number-expr? expr) (number->string expr))
        ((variable? expr) (symbol->string (variable-name expr)))
        ((sum? expr)
         (let ((addend-string (expr->infix-string (addend expr)))
               (augend-string (expr->infix-string (augend expr))))
           (string-append
            "(" addend-string " + " augend-string ")")))
        ((product? expr)
         (let ((multiplier-string (expr->infix-string (multiplier expr)))
               (multiplicand-string (expr->infix-string (multiplicand expr))))
           (string-append "(" multiplier-string " * " multiplicand-string ")")))
        (else (error "Bad expression" expr))))

>> (expr->infix-string test-expr)
;Value: "((3 + (x * 9)) * (y + z))"
\end{verbatim}
Note that all these printing procedures preserve the expression
abstraction.  The procedures print in the same desired format even if
the implementation of expressions changes.  Conversely, we can change
the printing format by selecting the desired printing procedure---not
by changing the expression implementation.

\begin{exercise}
Write an \tlisp{expr->prefix-tree} procedure.
\end{exercise}

\begin{exercise}
Modify \tlisp{expr->infix-string} so the outermost matching
parentheses are not included in the result.  Is this possible to do
with infix lists?\dots explain.
\end{exercise}

\begin{exercise}
So far, the only way to construct abstract expressions is by explicitly
using the expression constructors as in the \texttt{test-expr} example
above.  It would be more convenient for users of an abstract expression
system if they could use familiar input notation.  For example, we would
like an input procedure \texttt{infix-tree->expr} to turn an infix
notation expression into an abstract one.  Then, for example, instead of
\begin{verbatim}
(define test-expr
  (make-product
   (make-sum 3 (make-product varz 9))
   (make-sum vary varz)))
\end{verbatim}
we could allow a user to enter
\begin{verbatim}
(define test-expr (infix-tree->expr '((3 + (z * 9)) * (y + z))))
\end{verbatim}
Write such an \texttt{infix-tree->expr} procedure.
\end{exercise}

With the solution to the previous exercise we have a simple way to
translate from infix to prefix notation:

\begin{verbatim}
(expr->prefix-tree (infix-tree->expr '((3 + (z * 9)) * (y + z))))
>>(* (+ 3 (* z 9)) (+ y z))
\end{verbatim}


\section{Variables and variable-values environments}

\subsection{Contracts}
For our purposes, all that matters about a variable is its name and how to
find its value.  We know there are selectors \texttt{variable-name} and
\texttt{lookup} for finding names and values.

To contruct \vvenv, we specify that there be an ``initial'' environment,
and that there is a way to extend a given environment so it assigns a
specified value for a new variable:
\begin{align*}
    \tlisp{initial-env} : {} & \vvenv \\
    \tlisp{extended-env}: {}
        & (\type{Variable} , \type{Number-expr} ,
            \vvenv) \to \vvenv
\end{align*}
The contract for these procedures is that:
\begin{enumerate}

\item
$\texttt{(lookup <var> (extended-env <var> <val> <env>))}
 \rulesto \texttt{<val>}$, and

\item
if \texttt{<var\_1>} is not equal to \texttt{<var\_2>}, then the two
expressions
\[
    \texttt{(lookup <var\_1> (extended-env <var\_2>  <val> <env>))}
\]
and
\[
 \texttt{(lookup <var\_1> <env>)}
\]
return the same value.

\end{enumerate}

From these constructors, we can see that \vvenv\ acts like a list
of variable-value pairs:
\[
 \vvenv \cong \mathrm{List}(\pairtyp{Variable}{Number-expr})
\]

\subsection{Implementing variables and Variable-values Environments}

In many cases, the \emph{only} thing that matters about a variable is its
name, in which case a simple implementation of variables as Scheme symbols
works well:
\[
    \type{Variable} = \type{Symbol}.
\]
This allows a straightforward implemention of a variable-values
environment as an association list of variables and numbers:
\begin{verbatim}
(define (make-variable symb) symb)
(define (variable-name var) var)

(define initial-env '())

(define (extended-env name val env)
  (cons (list name val) env))

(define (lookup var env) (assq var env))
\end{verbatim}

For example, the environment in which variables \texttt{x}, \texttt{y},
\texttt{z} have respective values 6, 20, 20 would be a length three
association list:
\begin{verbatim}
(define varx 'x)
(define vary 'y)
(define varz 'z)

(define env-1
  (extended-env
    varx 6
    (extended-env
     vary 20
     (extended-env
       varz 20
       initial-env))))

>>env-1
;Value: ((x 6) (y 20) (z 20))
\end{verbatim}
and we could use this environment to evaluate our test expression above:
\begin{verbatim}
>> (eval-arith test-expr env-1)
;Value: 2280
\end{verbatim}

\begin{exercise}
Complete an implementation of these abstract arithmetic expressions.
\end{exercise}

\begin{exercise}
Implement variable-values environments as trees whose leaves are numbers, and a
variable consists of a name and a path to its value in the tree.  You may
assume that variables with the same path also have the same name, but if
you do assume this, illustrate how your implementation would fail the
\texttt{lookup} contract if the assumption was violated.
\end{exercise}


\section{Expressions as Records}
In this section we will examine an implementation of expressions as
\emph{records}.  Abstractly, a record has a tag and a set of distinctly
tagged values called the \emph{fields} of the record.
\begin{eqnarray*}
\type{Record} & \cong & \pairtyp{Tag}{$\mathrm{Set}(\type{Field})$}\\
\type{Field} & \cong & \pairtyp{Tag}{Anytype}
\end{eqnarray*}
For example, an arithmetic sum will be represented as a record with tag
\texttt{sum}.  The record will have a field tagged \texttt{addend}
containing the record representing the augend of the sum; there will be a
similar \texttt{augend} field.  We'll assume there is a procedure
\[
\texttt{field-content}: \type{Tag}, \type{Record} \to \type{Anytype}
\]
for looking up the contents of a field within a record.  Namely,
\[
\texttt{(field-content key record)}
\]
looks up and returns the value of the field in \texttt{record} whose tag is
\texttt{key}.

The benefit of this implementation is that it is easy to attach useful
data to expressions, and this can make some computations a lot easier.

For example, suppose a typical expression is going to be repeatedly
printed in infix notation.  We could apply our \texttt{expr->infix-string}
procedure above each time the expression was to be printed, but, knowing
that the resulting string will be needed repeatedly, it's sensible to
compute it once and simply look it up when it's needed instead of
constructing it again.  The question is where to save the string and how
to look it up?  With expressions implemented as records, there is a simple
answer to this question: store the string \emph{in the expression}.  More
precisely, store the string in an \texttt{infix-string} field of the
record representing the expression.  Now the \texttt{expr->infix-string}
procedure need only get the contents of this field:
\begin{verbatim}
(define (expr->infix-string expr)
  (field-content 'infix-string expr)).
\end{verbatim}  
The benefit here is that looking up the string in the record will
typically be much faster than constructing it.  For example, with records
and fields implemented as tagged lists, looking up the infix string takes a
\emph{constant} number of operations for any expression, while the number
of operations to construct an infix string is \emph{linear} in the size of
an expression.

To make this work, we have to modify the constructors of expression
records so they include an \texttt{infix-string} field in the records,
but that's easy:
\begin{verbatim}
(define (make-sum expr1 expr2)
 (attach-tag
   'sum
   (attach-tag
     'addend expr1)
   (attach-tag
     'augend expr2)
   (attach-tag
     'infix-string
     (string-append
       "(" (expr->infix-string expr1) "+" (expr->infix-tree expr2) ")"))))
\end{verbatim}

\begin{verbatim}
(define (make-variable symb)
  (attach-tag
   'variable
   (attach-tag 'variable-name symb)
   (attach-tag 'infix-string symb)))
\end{verbatim}

\begin{verbatim}
(define (make-number-expr num)
  (attach-tag
   'number-expr
   (attach-tag 'number num)
   (attach-tag 'infix-string (number->string num))))
\end{verbatim}

Notice that we have paid a price to have this efficient infix-string
by look up: the expression constructors now have to do the
extra work of constructing and storing an infix string.  This is a good
tradeoff if an expression will indeed be printed as an infix string more
than once, but is a complete waste in the case of an expression whose
infix string is \emph{never} needed.

This last problem can be overcome by initially omitting construction of an
\texttt{infix-string} field, and then adding the field the first time it
is needed.  With this idea, the constructors become simple again:

\begin{verbatim}
(define (make-sum expr1 expr2)
 (attach-tag
   'sum
   (attach-tag
     'addend expr1)
   (attach-tag
     'augend expr2)))
\end{verbatim}

\begin{verbatim}
(define (make-variable symb)
  (attach-tag
   'variable
   (attach-tag 'variable-name symb)))
\end{verbatim}

\begin{verbatim}
(define (make-number-expr num)
  (attach-tag
   'number-expr
   (attach-tag 'number num)))
\end{verbatim}
but the \texttt{expr->infix-string} procedure has to be modified to check
for an \texttt{infix-string} field and to create one if it's missing:

\begin{verbatim}
(define (expr->infix-string expr)
  (begin
   (or (has-field? 'infix-string expr)
       (add-field!
         expr
         'infix-string
         (cond                   
           ((variable? expr)
            (symbol->string
             (field-content 'variable-name expr)))
           ((number-expr? expr)
            (number->string
             (field-content 'number expr)))
           ((sum? expr)
            (string-append
             "(" (expr->infix-string expr1)
             "+" (expr->infix-string expr2) ")" ))
           ((product? expr)
            (string-append
            "(" (expr->infix-string expr1)
            "*" (expr->infix-string expr2) ")" ))
           (else (error "Bad expression" expr)))))
    (field-content 'infix-string expr)))
\end{verbatim}

\section{Partial Evaluation and An Analyzing Evaluator}
The techniques in the previous section for computing, saving, and looking
up infix strings apply more generally to any repeatedly reused results of
computation.  A typical situation is when an expression is going to be
evaluated repeatedly.  For example, within a numerical computation
package, such an expression might be a polynomial used for approximating
the cosine function.  The twist in this case is that while the polynomial
expression is likely to be repeatedly evaluated---it is \emph{not} likely
to be evaluated many times with the \emph{same values} for its variables,
that is, in the same environment.  But we can still find and save reusable
results in an expression evaluation by separating the evaluation process
into a part that depends only on the expression and not on the
environment.  This idea is known as \emph{partial evaluation}.

To partially evaluate an expression, we define a higher-order procedure
\texttt{analyze} which preprocesses an expression before any environment
is available.  The preprocessing yields a single procedure that will map
any environment into the value of the expression in that environment.
That is, \texttt{analyze} satisfies the contract:
\[
    \texttt{((analyze <expr>) <env>)} = \texttt{(eval-arith <expr> <env>)}
\]
For example, if \texttt{<expr1>} was a sum of expressions \texttt{<add1>}
and \texttt{<add2>}, we could define \texttt{(analyze <expr1>)} to be the
procedure \texttt{expr1-proc}:
\begin{verbatim}
(define expr1-proc
 (lambda (env)
   (+ (eval-arith <add1> env)
      (eval-arith <add2> env))))
\end{verbatim}
Now, whenever we want to evaluate \texttt{<expr1>} in some environment
\texttt{env}, we could simply evaluate \texttt{(expr1-proc env)}.  This
wins a little bit because it eliminates the need to parse \texttt{<expr1>}
into \texttt{<add1>} and \texttt{<add2>} at each evaluation.  The
top-level parsing gets done only once---when we do the analysis of
\texttt{<expr1>}.  It will not be repeated when \texttt{<expr>} is
evaluated in different environments by applying \texttt{expr1-proc}.

On the other hand, the recursive calls to \texttt{eval-arith} within the
body of \texttt{expr1-proc} will wind up parsing \texttt{add1} and
\texttt{add2} every time \texttt{expr1-proc} is applied, so the
\emph{only} parse that is not repeated is the top-level one.  The problem
is that we haven't saved the results of analyzing the subexpressions.  We
should have analyzed the subexpressions \texttt{<add1>} and
\texttt{<add2>} recursively and then saved the resulting
analyze-procedures for reuse.  A simple place to save these
analyze-procedures is \emph{within} the \texttt{expr1-proc} procedure
environment.  We do this by including the following \texttt{let} bindings
within the definition:
\begin{verbatim}
(define expr1-proc1
  (let ((add1-proc (analyze <add1>))
        (add2-proc (analyze <add2>)))
    (lambda (env)
      (+ (add1-proc env)
         (add2-proc env)))))
\end{verbatim}
Now the parsing of \texttt{<add1>} and \texttt{<add2>} will not be repeated
when \texttt{expr1-proc} is applied.

This approach leads to the following recursive definition of \texttt{analyze}:
\begin{verbatim}
(define (analyze expr)
  (cond
   ((number-expr? expr)
    (lambda (env) (field-content 'number expr))
        
    ((variable? expr)
     (lookup (field-content 'variable-name expr) env))
    ((sum? expr)
     (let ((addend-proc (analyze (addend expr)))
           (augend-proc (analyze (augend expr))))
       (lambda (env)
         (+ (augend-proc env)
            (addend-proc env)))))
    ((product? expr)
     (let ((multiplier-proc (analyze (multiplier expr)))
           (multiplicand-proc (analyze (multiplicand expr))))
       (lambda (env)
         (+ (multiplier-proc env)
            (multiplicand-proc env)))))
    (else (error "Bad expression" expr)))))

(define analyze1 (analyze <expr1>))
\end{verbatim}

Computing the value of \texttt{<expr1>} in an environment by applying
\texttt{analyze1} to the environment will be significantly more efficient
than applying \texttt{eval-arith}, because \emph{none} of the parsing of
\texttt{<expr1>} gets repeated when \texttt{analyze1} is applied.  So
\texttt{analyze1} is a useful procedure to save for reuse when
\texttt{<expr1>} needs to be evaluated in different environments---and the
more often \texttt{<expr1>} needs to be evaluated, the bigger the win.
Our record representation of expressions allows us to save
analyze-procedures within expression records in the same way we did for
infix strings.

Notice that now we could legitimately redefine the expression evaluation
procedure in terms of \texttt{analyze}:
\begin{verbatim}
(define (eval-arith exp env)
  ((analyze exp) env))
\end{verbatim}
However, with this definition there is no gain in efficiency---there is
even a slight loss---when evaluating arithmetic expressions.  That's
because the value of \texttt{(analyze exp)} is recomputed whenever
\texttt{eval-arith} is applied.  Since the construction of the
analyze-procedure requires a complete parsing of the \texttt{exp}
argument, this version of \texttt{eval-arith} is doing essentially the
same work as the original one, just in a different order.

But it's worth looking ahead a bit to observe that defining \texttt{eval}
in terms of \texttt{analyze} in this way will really pay off for
\emph{recursively defined procedures}.  The point is that the body of a
recursive procedure is an expression that will be evaluated in many
environments---a different one at each recursive call---during the course
of a single recursive evaluation.  In this case, partially evaluating the
procedure body at the start of evaluation eliminates having to reparse the
procedure body at each recursive call; this can speed up evaluation by a
large constant factor (as much as ten or twenty for the 6.001
meta-circular Scheme evaluator) compared to an evaluator styled after
\texttt{eval-arith}.


\begin{exercise}
Implement expressions as records which \emph{may} have an
\texttt{analyzed} field containing an analyzed-expression procedure.  Then
define \texttt{eval-arith} so it checks an expression record for an
\texttt{analyzed} field, and creates such a field if it's missing.
(Pattern your definition after the definition of
\texttt{expr->infix-string} in the previous section.)
\end{exercise}

\end{document}
