\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 7\\ \vspace{1 ex} Due Friday, 10/22/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{10}{Let expressions}
    
    Suppose we extend the grammar for typed PCF (see lecture 19) to 
    include ``let'' expressions:
    \begin{verbatim}
	e::= let x: T = e in e end
    \end{verbatim}
    Thus we could write 
    \begin{verbatim}
	let x: Int = 17 in succ(succ x) end
    \end{verbatim}

    \begin{enumerate}
        \item Please write down the type-checking rule for the let 
	expression in the same form as Lecture 19.  That is, the 
	bottom line (below the long horizontal line) should read
	\begin{verbatim}
	    E |- let x:T = e1 in e2 end : U
	\end{verbatim}
	Write down the complete rule including all of the hypotheses 
	necessary to prove the typeing of the let expression.
	
	\item Please write down the evaluation rule for the new let 
	expression.  As in Lecture 19, the bottom line should read:
	\begin{verbatim}
	    (let x:T = e1 in e2 end, env) => v
	\end{verbatim}
	Again, write down the entire rule, including the hypotheses 
	that generate that conclusion.
     \end{enumerate}   

 

    \item \phead{20}{Scala Programming}
    
    Be sure to have a computer with Scala installed (all Macs in the
    Pomona CS lab have Scala installed with Eclipse).  If you use
    Scala with Eclipse (my recommendation) then go to
    \texttt{http://www.scala-ide.org/} andfollow the instructions on
    how to download and install the right
    version of Eclipse and how to download and install Scala from
    within Eclipse.  Then go to user documentation and then the 
    ``Tutorial Example'' for information on how to write a program in 
    Scala using Eclipse.  Do read and follow the directions 
    carefully.  If you omit steps then Eclipse will not be able to 
    find your \texttt{main} method.
    
    If you would rather, you can just edit your program using emacs 
    and run scalac to compile your code using scalac.  See the 
    on-line tutorial for further information on running programs and 
    to find more info on the language.
    
    \begin{enumerate}
	\item The scala library class \texttt{List}, in
	\texttt{scala.collection.immutable}, provides immutable lists.
	You can create a list of numbers just by writing
	\texttt{List(1,2,3,4)}.  Notice that ``new'' is not required
	(though normally it would be to create objects).  You can find
	more information about the class and its operations by going
	to the general library documentation at
	\texttt{http://www.scala-lang.org/api/current/index.html} and
	then selecting \texttt{scala.collection.immutable} from the
	packages on the left and then clicking on \texttt{List}
	beneath it.
	
	The element \texttt{Nil} is a built in object, while ``::'' 
	can be used to create a new list by adding a new first 
	element.  For example, \texttt{5::List(6,7,8,9)} results in a 
	new list containing the numbers from 5 to 9.
	
	Please write a function that takes a list as input and 
	reverses it.  Write a main method that tests it.
	
	\item Look up information about methods \texttt{map} and 
	\texttt{foreach}.  Both apply a function to all the arguments 
	of the list, but \texttt{map} takes the results and puts 
	them in a list.
	
	Use \texttt{foreach} to write a method
	\texttt{printall(lst:List[Int])} that prints out all of the
	elements in a list of integers.  Write a sample program that
	creates a list of integers and calls \texttt{printall} to
	print out all of its values.
	
	\item Do problem 4a from homework 4.  It asks for you to code 
	up a list comprehension operator.  You may use the map and 
	filter functions from the library class \texttt{List} from 
	package \texttt{scala.collection.immutable}.
	
	\item Write a binary search tree class over integers.  [Don't
	bother to write a parameterized class, just have it use
	integers.]  Write methods that will allow you to add new
	elements to the tree, compute the size of the tree, and to
	traverse the tree inorder, applying a function f to all
	elements of the tree and gathering the results in a list.
	That is the declaration of this method will look like:
	\begin{verbatim}
	    def inorder(f:int => int):List[Int] {...}
	\end{verbatim}
	
	If an in-order traversal of the tree would produce 
	$[a_{1},\ldots,a_{n}]$ then this method should provide 
	$[f(a_{1}),\ldots,f(a_{n})]$.  Write a program that tests 
	this on a few simple trees and some simple functions.
    \end{enumerate}
\end{enumerate}

\end{document}