\documentclass[twoside]{article}
\usepackage{graphics}
\usepackage{fancyheadings}

\newcommand{\coursenumber}{131}
\newcommand{\coursetitle}{Principles of Programming Languages}

\topmargin  18pt        % 27pt
\headheight 12pt        % 12pt
\headsep    35pt        % 45pt
\textheight 8.0in
\textwidth  6.2in

\oddsidemargin   22pt      % Left margin on odd-numbered pages.
\evensidemargin  22pt      % Left margin on even-numbered pages.
\marginparwidth  72pt       % Width of marginal notes.
\marginparsep    11pt      % Horizontal space between outer margin and 
                           % marginal note

\pagestyle{fancy}
\lhead{CSCI \coursenumber}
\chead{}
\rhead{\semester}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\setlength{\headrulewidth}{0pt}
\setlength{\footrulewidth}{0pt}

\newcommand{\semester}[0]{
     \ifnum\month>7{Fall}\fi
     \ifnum\month<8{Spring}\fi\  \number\year
}

\newcommand{\points}[1]{(#1 points)}
\newcommand{\phead}[2]{\points {#1} \textbf{#2}}

\def\rightarrowfill{\mathsurround=0pt  \mathord- \mkern-6mu
  \cleaders\hbox{$\mkern-2mu \mathord- \mkern-2mu$}\hfill
  \mkern-6mu \mathord-\!\!\!\!\longrightarrow}
\newcommand{\step}[1]{~~\stackrel{\texttt{\scriptsize #1}}{\rightarrowfill}~~}


\begin{document}

\begin{center}
    \Large Homework 11\\ \vspace{1 ex} Due Wednesday, 12/1/10
\end{center}

\vspace{2 ex} 

Please turn in your homework solutions online at  
\texttt{http://www.dci.pomona.edu/tools-bin/cs131upload.php}
before the beginning of class on the due date. 

\vspace{2 ex}


\begin{enumerate}
    
    \item \phead{15}{Smalltalk Reading}

    Read ``Design Principles Behind Smalltalk'' by Dan Ingalls 
    (available on the ``links'' page).

    Think about the Principles set forth.  Which are new?  Which have
    we seen before?  What principles are remniscent of Lisp?  What is
    the scope of the language (ie, what is included in its
    definition)?  A few sentences on each item is sufficient---
    clarity is more important than length of answer.


    \item \phead{15}{C++ }

    From ``An Overview of C++,'' by Bjarne Stroustrup, SIGPLAN
    Notices, 1986-10:

    "Section 6.  What is Missing?

    C++ was designed under severe constraints of compatibility,
    internal consistency, and efficiency: no feature was included that
    \begin{enumerate}
    \item would cause a serious incompatibility with C at the source
    or linker levels.  \item would cause run-time or space overheads
    for a program that did not use it.  \item would increase run-time
    or space requirements for a C program.  \item would significantly
    increase the compile time compared with C. \item could only be
    implemented by making requirements of the programming environment
    (linker, loader, etc.)  that could not be simply and efficiently
    implemented in a traditional C programming environment.
    \end{enumerate}

    Features that might have been provided but weren't because of
    these criteria include garbage collection, parameterized classes,
    exceptions, multiple inheritance, support for concurrency, and
    integration of the language with a programming environment.  Not
    all of these possible extensions would actually be appropriate for
    C++, and unless great constraint is exercised when selecting and
    designing features for a language, a large, unwieldy, and
    inefficient mess will result.  The severe constraints on the
    design of C++ have probably been beneficial and will continue to
    guide the evolution of C++."

    Contrast the design goals to those of Smalltalk?  What is
    different?  What is the same?  What is the intended use of C++,
    and how does that influence the design?
    
    \item \phead{10}{Subtyping and Binary Methods}
    
    Please do problem 11.8 from Mitchell, page 334.    
    
    \item \phead{15}{�Like Current� in Eiffel}
    
    Please do problem 12.8 from Mitchell, page 376.    
    
    \item \phead{15}{Expression Objects}

    We now look at an object-oriented way of representing arithmetic
    expressions given by the grammar
    \[
    \begin{array}{lll}
    e & ::= & \mathit{num} \;|\; e + e \\
    \end{array}
    \]
    We begin with an ``abstract class'' called \texttt{SimpleExpr}.  While
    this class has no instances, it lists the operations common to all
    instances of this class or subclasses.  In this case, it is just a
    single method to return the value of the expression.
    \begin{verbatim}
    abstract class SimpleExpr {
        int eval();
    }
    \end{verbatim}
    Since the grammar gives two cases, we have two subclasses of {\tt
    SimpleExpr}, one for numbers and one for sums.
    \begin{verbatim}
    public class Number extends SimpleExpr {
        private int n;
        public Number(int n) { this.n = n; }
        public int eval() { return n; }
    }

    public class Sum extends SimpleExpr {
        private SimplExpr left, right;
        public Number(SimpleExpr left, SimpleExpr right) { 
            this.left = left; 
            this.right = right;
        }
        public int eval() { return left.eval() + right.eval(); }
    }
    \end{verbatim}

    \begin{enumerate}
      \item  \emph{Product Class}

        Extend this class hierarchy by writing a \texttt{Times} class to
        represent product expressions of the form
      \[
      \begin{array}{lll}
        e & ::= & \ldots \;|\; e * e
      \end{array}
      \]

      \item  \emph{Method Calls}

      Suppose we construct a compound expression by
    \begin{verbatim}
    SimpleExpr a = new Number(3);
    SimpleExpr b = new Number(5);
    SimpleExpr c = new Number(7);
    SimpleExpr d = new Sum(a,b);
    SimpleExpr e = new Times(d,c);
    \end{verbatim}
        and send the message \texttt{eval} to \texttt{e}.  Explain the sequence
        of calls that are used to compute the value of this expression:
        \texttt{e.eval()}.  What value is returned?

      \item  \emph{Comparison to ``Type Case'' constructs}

    Let's compare this programming technique to the expression
    representation used in Haskell, in which we declared a data type
    and defined functions on that type by pattern matching.  The
    following \texttt{eval} and \texttt{toString} functions illustrate
    one form of a ``type case'' operation, in which the program
    inspects the actual tag (or type) of a value being manipulated and
    executes different code for the different cases:
    \begin{verbatim}
   data HaskellExp = Number Integer | Sum (HaskellExp, HaskellExp)

   eval:: HaskellExp -> Integer
   eval (Number(x)) = x
   eval (Sum(e1,e2)) = eval(e1) + eval(e2)

   toString:: HaskellExp -> String
   toString(Number(x)) = show x
   toString(Sum(e1,e2)) = toString(e1) ++ " + " ++ toString(e2)   
    \end{verbatim}      
    This idiom also comes up in class hierarchies or collections of
    structures where the programmer has included a \emph{Tag} field in
    each definition that encodes the actual type of an object.  

    \begin{enumerate}

        \item Discuss, from the point of view of someone maintaining
        and modifying code, the differences between adding the
        \texttt{Times} class to the object-oriented version and adding a
        \texttt{Times} constructor to the \texttt{HaskellExpr} data type.  In
        particular, what do you need to add/change in each of the
        programs.  Generalize your observation to programs containing
        several operations over the arithmetic expressions, and not
        just \texttt{eval} and \texttt{toString}.
      
        \item Discuss the differences between adding a new operation,
        such as \texttt{prettyPrint} (\texttt{toString} is pretty
        lame, not introducing any parenthesization), to each way of
        representing expressions.  Assume you have already added the
        product representation so that there is more than one class
        with nontrivial \texttt{eval} methods.
    \end{enumerate}


    \end{enumerate}
    
    \item \phead{25}{Visitor Design Pattern}

    The extension and maintenance of an object hierarchy can be
    greatly simplified (or greatly complicated) by design decisions
    made early in the life of the hierarchy.  This question builds on
    the previous question in exploring design possibilities for an
    object hierarchy representing arithmetic expressions.

    The designers of the hierarchy have already decided to structure it as
    shown below, with a base class \texttt{Expr} and derived classes {\tt
    Number, Sum, Times}, and so on.  They are now contemplating how to
    implement various operations on Expressions, such as printing the
    expression in parenthesized form or evaluating the expression.  They
    are asking you, a freshly-minted language expert, to help.

    The obvious way of implementing such operations is by adding a method to
    each class for each operation. The Expression hierarchy would then look like:
    {\small \begin{center}
    \begin{verbatim}
        public interface Expr {
            public String toString();
            public int eval();
        }

        public class Number implements Expr {
            private int n;

            public Number(int n) { this.n = n; }
            public String toString() { ... }
            public int eval() { ... }
        }

        public class Sum implements Expr {
            private Expr left, right;

            public Sum(Expr left, Expr right) {
                this.left = left;
                this.right = right;
            }
            public String toString() { ... }
            public int eval() { ... }
        }
    \end{verbatim}
    \end{center}
    }

    Suppose there are $n$ subclasses of \texttt{Expr} altogether, each
    similar to \texttt{Number} and \texttt{Sum} shown here.  How many
    classes would have to be added or changed to add each of the following
    things?
    \begin{enumerate}
    \item 
    A new class to represent product expressions.

    \item 
    A new operation to graphically draw the expression parse tree.
    \end{enumerate}


    Another way of implementing expression classes and operations uses
    a pattern called the Visitor Design Pattern.  In this pattern,
    each \emph{operation} is represented by a \texttt{Visitor} class.
    Each Visitor class has a \texttt{visit\emph{Class}} method for
    each expression class \emph{Class} in the hierarchy.  Each
    expression class \emph{Class} is set up to call the
    \texttt{visit\emph{Class}} method to perform the operation for
    that particular class.  In particular, each class in the
    expression hierarchy has an \texttt{accept} method which accepts a
    \texttt{Visitor} as an argument and ``allows the Visitor to visit
    the class and perform its operation."  The expression class does
    not need to know what operation the visitor is performing.

    If you write a Visitor class \texttt{ToString} to construct a string
    representation of an expression tree, it would be used as follows:
    {\small \begin{center}
    \begin{verbatim}
        Expr expTree = ...some code that builds the expression tree...;
        ToString printer = new ToString();
        String stringRep = expTree.accept(printer);
        System.out.println(stringRep);
    \end{verbatim}
    \end{center}
    } 
    
    The first line defines an expression, the second defines an instance
    of your \texttt{ToString} class, and the third passes your visitor object
    to the \texttt{accept} method of the expression object.
    
    An \texttt{Eval} visitor might work similarly, but evaluating an 
    expression rather than converting it to a string.

    The expression class hierarchy using the Visitor Design Pattern has
    the following form, with an \texttt{accept} method in each class and
    possibly other methods.  Since different kinds of visitors return
    different types of values, the accept method is parameterized by the
    type that the visitor computes for each expression tree:
    {\small \begin{center}
    \begin{verbatim}
    public interface Expression {
            <T> T accept(Visitor<T> v);
    }

    public class Number implements Expression {
            private int n;

            public Number(int n) {
                    this.n = n;
            }

            // Do visitor operation to number being represented
            public <T> T accept(Visitor<T> v) {
                    return v.visitNumber(this.n);
            }
    }


    public class Sum implements Expression {
            private Expression left, right;

            public Sum(Expression left, Expression right) {
                    this.left = left;
                    this.right = right;
            }

            // Do visitor operation on left and right and then do
            public <T> T accept(Visitor<T> v) {
                    T leftVal = left.accept(v);
                    T rightVal = right.accept(v);
                    return v.visitSum(leftVal, rightVal);
            }

    \end{verbatim}
    \end{center}
    }

    The associated \texttt{Visitor} abstract class, naming the methods
    that must be included in each visitor, and some example classes
    implementing it, have this form: {\small \begin{center}
    \begin{verbatim}
    public interface Visitor<T> {
            T visitNumber(int n);

            T visitSum(T left, T right);
    }
    \end{verbatim}
    
    Notice that there is a \texttt{visit}\emph{Class} method for each 
    class that the visitor must handle.  (Traditionally, these are 
    all just named \texttt{visit} without the class name, relying on 
    static overloading.  Needless to say, I find this more confusing 
    than helpful!)
    \begin{verbatim}
    // A Visitor class to evaluate expressions, returning an Integer
    public class Eval implements Visitor<Integer> {
            public Integer visitNumber(int n) {
                // evaluating an integer is easy
                return new Integer(n);
            }

            public Integer visitSum(Integer left, Integer right) {
                // evaluate sum by adding values of given left and right sides
                return new Integer(left.intValue() + right.intValue());
            }
    }


    // A Visitor class to convert an expression ot a String
    public class ToString implements Visitor<String> {
            public String visitNumber(int n) {
                // convert the integer to a string
                return "" + n;
            }

            public String visitSum(String left, String right) {
                // Given the String representations of left and right
                // create the String representations of the sum
                return "(" + left + " + " + right + ")";
            }
    }
    \end{verbatim}
    \end{center}
    }

    Here is an example of using the visitor to evaluate and print the
    value of an expression.
    {\small
    \begin{center}
    \begin{verbatim}
    public class ExpressionVisitor {
            public static void main(String s[]) {
                    Expression e = new Sum(new Number(3), new Number(2));
                    Eval eval = new Eval();
                    int n = e.accept(eval);
                    System.out.print(e.accept(new ToString()) + " = " + n);
            }
    }
    \end{verbatim}
    \end{center}}
    
    In the above, once the expression is created, it ``accepts'' an 
    evalution visitor whose job is to evaluate the expression.  In 
    the ``println'' statement a \texttt{ToString} visitor is 
    accepted, resulting in a string representation of the expression.

    \begin{enumerate}
    \setcounter{enumii}{2}
    \item 
    Starting with the call to \texttt{e.accept(eval)}, what is the
    sequence of method calls that will occur while evaluating the
    expression tree \texttt{e}?  (Do not record calls to constructors
    and \texttt{intValue}-- just consider the \texttt{visit} and
    \texttt{accept} methods).
    \end{enumerate}

    Suppose there are $n$ subclasses of \texttt{Expression}, and $m$
    subclasses of \texttt{Visitor}.  How many classes would have to be
    added and how many would have to be changed to add each of the
    following things using the Visitor Design Pattern?

    \begin{enumerate}
    \setcounter{enumii}{3}
    \item 
    A new class to represent product expressions.

    \item 
    A new operation to graphically draw the expression parse tree.

    \end{enumerate}

    The designers want your advice.
    \begin{enumerate}
    \setcounter{enumii}{5}
    \item 
    Under what circumstances would you recommend using the standard design?

    \item 
    Under what circumstances would you recommend using the Visitor Design Pattern?

    \end{enumerate}

    
\end{enumerate}

\end{document}