\documentclass{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 9\\ \vspace{1 ex} Due Thursday, 11/17/2011
\end{center}

\vspace{2 ex} 

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

Several questions on this homework involve ML programs.  However, they
behave identically to equivalent Haskell programs.  If you have any
problem understanding them, please let me know.  There are also some
Ada programs, where Ada is a procedural language designed about 1980,
but again the syntax should be pretty understandable.

\vspace{2 ex}


\begin{enumerate}
    
    \item \phead{20}{Modularity of Concrete Data Types}
    
    In lecture 19 we discussed an environment-based interpreter for
    PCF. It is available on-line from the course web page by following
    the link to ``Programs from lecture''.  In this problem, I would
    like you to modify that program in order to determine how easy it
    is to add new features.

    \begin{enumerate}
	\item Please add a new function \texttt{prettyprint} that
	takes a PCF term and returns a string containing a nice readable
	version of the term.
	
	\textbf{Note: The data type \texttt{Term} is given in the PCF parser,
	available from the same programs page.  Feel free to copy and 
	paste the definition into \texttt{PCFEnvinterp.hs} and drop the 
	\texttt{import} line.  Alternatively, turn in the \texttt{ParsePCF.hs} 
	file as well (enhanced as needed in part b), but don't forget to add
	\texttt{AST\_SUM} (see part b) to the export list of that 
	module.}

	The string should contain parentheses to indicate precedence.  For
	example, the term
    \begin{verbatim}
       AST_IF(AST_BOOL True,AST_NUM 5, AST_APP(AST_SUCC, AST_NUM 2)) 
    \end{verbatim}
	should be pretty-printed as
    \begin{verbatim}
       if true then 5 else (succ 2)
    \end{verbatim}
	whereas 
    \begin{verbatim}
       AST_APP(AST_IF(AST_BOOL true,AST_PRED, AST_SUCC), AST_NUM 2)
    \end{verbatim}
	should be pretty-printed as
    \begin{verbatim}
       (if true then pred else succ) 2
    \end{verbatim}

	\item Please add a new term to PCF representing sums of 
	integers.  I.e., add a new clause to the definition of term
	of the form \texttt{AST\_SUM (Term, Term)} so that 
	\texttt{AST\_SUM(a,b)} represents \texttt{a + b}.
	
	Modify the previous program that contains both the 
	\texttt{newinterp} function to evaluate terms and 
	\texttt{prettyprint} to accommodate the new term.
	
	\item I am not asking you to modify the PCF parser code that is 
	available on-line.  However, please describe at a high level what 
	would have to be done to modify that code.
	
	\emph{Note:  If you wish, you need only turn in the code from the 
	last part of this question plus the description of the 
	modifications to the parser from the previous part.  The answers 
	to the first two parts need not be turned in separately.}
    \end{enumerate}
    
        \item \phead{15}{Subtyping and Visibility}
    
    Please do problem 12.6 from Mitchell, page 375.    
    
    \item \phead{10}{Subtyping and Specifications}
    
    Please do problem 12.9 from Mitchell, page 377.
    
    \item \phead{25}{``Growing a Language'' Reading}
    
    Please read the short paper entitled ``Growing a Language'' from
    the auxiliary reading page.  The author, Guy Steele, is one of the
    designers of Java, and this was his keynote talk at the major
    American conference on object-oriented languages (OOPSLA) in
    1998.

    This paper includes a discussion of why some items were originally
    left out of Java when they designed the language, but likely
    should have been included.  It also gives some insight into
    programming language design in general.  The following questions
    will guide you through the paper:

    \begin{enumerate}
    \item What is wrong with designing/using a small language like
    Lisp?

    \item What is wrong with designing/using a huge language (C++)?

    \item What was Steele's goal in designing Java?

    \item Why does Steele feel that overloaded operators are
    important.  Contrast this with his conviction (expressed
    elsewhere) that overloaded methods might have been left out
    without much harm.

    \item Discuss why generics might have been left out originally,
    but why he now feels they are important.
    \end{enumerate}

    Write a separate paragraph discussing each of these items.  A few
    sentences on each part is sufficient.

    We will spend some time discussing these points after the
    homeworks are turned in.
    
        \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.


\end{enumerate}

\end{document}