\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}}

\begin{document}

\begin{center}
    \Large Homework 3\\ \vspace{1 ex} Due Friday, 2/11/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}{Translation into Lambda Calculus}
    
    Please do problem 4.6 from Mitchell, page 84.
    
    \item \phead{20}{Lazy Evaluation and Parallelism}
    
    Please do problem 4.11 from Mitchell, page 87. 

    The function g should be defined as follows (there may be a typo 
    in the book, depending on the printing): 
    \begin{verbatim}
        fun g(x, y) = if x = 0 
                      then 1 
                      else if x + y = 0 
                           then 2 
                           else 3
    \end{verbatim}

    \item \phead{5}{Algol 60 Procedure Types}
    
    Please do problem 5.1 from Mitchell, page 122.
    
    
    \item \phead{10}{Haskell types}
    
    Explain the Haskell type for each of teh following declarations:
    \begin{enumerate}
        \item a(x,y) = x+2*y
        \item b(x,y) = x+y/2.0
        \item c(f) = \textbackslash y $\rightarrow$ f y
        \item d(f,x) = f(f(x))
        \item e(x,y,b) = if b(y) then x else y
    \end{enumerate}
    Because you can simply type these expressions into ghci (with a
    \texttt{let} in front if you type them directly or as is if you
    load them from a file) to determine their type, be sure to write a
    short explanation to show that you understand why the function has
    the type you give.
    
    \item \phead{50}{Haskell Programming}
    
For this problem, use the ghci interpreter on the Unix machines in the
computer lab.  To run the program in the file ``example.hs'', type
\begin{verbatim}
-> ghci
Prelude> :l example.hs
Prelude> :set +t       -- gives more info when you type an expression
\end{verbatim}
at the command line.  

The Haskell compiler will process the program in the file and then wait for
the user to type an expression.  For example, if ``example.hs''
contains
\begin{verbatim}

-- double an integer 
double x = x + x;

-- return the length of a list *)
listLength [] = 0
listLength (l:ls) = 1 + listLength ls

\end{verbatim}
You can test the program by typing the following:
\begin{verbatim}
*Main> double 10
20
it :: Integer
*Main> listLength (1:[2,3,4])
4
it :: Integer
\end{verbatim}

Start early on this part so you can see the TA or me if you have
problems understanding the language.  Looking at the examples in the
on-line tutorials and text and in your notes will help a great deal in
understanding how to use Haskell. Use pattern matching where possible.

Comments in Haskell appear from -- to the end of the line.

\begin{enumerate}

\item {\bf Basic Functions}

Define a function {\tt sumSquares} that, given a nonnegative integer
n, returns the sum of the squares of the numbers from 1 to n:
\begin{verbatim}
- sumSquares 4;
30
- sumSquares 5;
55
\end{verbatim}


Define a function {\tt listDup} that takes a pair of an element, e, of any type, and
   a non-negative number, n, and returns a list with n copies of e:
\begin{verbatim}
> listDup("moo", 4);
["moo","moo","moo","moo"]
it :: [[Char- listDup(1, 2);
[1,1]
it :: [Integer]
> listDup(listDup("cow", 2), 2)
[["cow","cow"],["cow","cow"]]
it :: [[[Char]]]
\end{verbatim}
Your function will have a type like {\tt (Num t) => (a, t) -> [a]}.  What
does this type mean?  Why is it the appropriate type for your function.


\item {\bf Zipping and Unzipping}

The function \texttt{zip} to compute the pairwise interleaving of two
lists of arbitrary length is predefined, but I'd like you to write it
from scratch anyway (calling it \texttt{zip'}.  You should use pattern
matching to define this function:

\begin{verbatim}
-> *Main> zip' [1,3,5,7] ["a","b","c","de"]
[(1,"a"),(3,"b"),(5,"c"),(7,"de")]
it :: [(Integer, [Char])]
\end{verbatim}

Note: If the lists don't have the same length, you may decide how
you would like the function to behave. If you don't specify any
behavior at all you will get a warning from the compiler that you have
not taken care of all possible patterns--- this is fine.

Write the inverse function, \texttt{unzip'}, which behaves as follows:
\begin{verbatim}
*Main> unzip' [(1,"a"),(3,"b"),(5,"c"),(7,"de")]
([1,3,5,7],["a","b","c","de"])
it :: ([Integer], [[Char]])
\end{verbatim} 
Again, \texttt{unzip} is built-in, but you will write your own 
\texttt{unzip'}.

Write \texttt{zip3'}, to zip three lists. 
\begin{verbatim}
*Main> zip3' [1,3,5,7] ["a","b","c","de"] [1,2,3,4]
[(1,"a",1),(3,"b",2),(5,"c",3),(7,"de",4)]
it :: [(Integer, [Char], Integer)]
\end{verbatim}
Once again, \texttt{zip3} is built-in, but you will write your own
\texttt{zip3'}.

Why can't you write a function
\texttt{zip\_any} that takes a list of any number of lists and zips them
into tuples? From the first part of this question it should be pretty
clear that for any fixed n, one can write a function \texttt{zipn}. The
difficulty here is to write a single function that works for all n!
I.e., can we write a single function \texttt{zip\_any} such that 
\texttt{zip\_any [list1,list2,...,listk]} returns a list of k-tuples no matter what k
is?

\item {\bf find}

Write a function find with type {\tt (Eq a) => (a, [a]) $\rightarrow$
Integer} that takes a pair of an element and a list and returns the
location of the first occurrence of the element in the list.  For
example:
\begin{verbatim}
*Main> find(3, [1, 2, 3, 4, 5])
2
*Main> find("cow", ["cow", "dog"])
0
*Main> find("rabbit", ["cow", "dog"])
-1
\end{verbatim}
First write a definition for find where the element is guaranteed to
 be in the list. Then, modify your definition so that it returns 
 \verb@-1@ if
 the element is not in the list.
 
 [When the system is asked for the type of my solution for find, it 
 gives me the even more general: \texttt{(Num a, Eq t) => (t, [t]) -> a}.]


\item {\bf Trees}

Here is the datatype definition for a binary tree storing integers at the leaves:
\begin{verbatim}
data IntTree = Leaf Integer | Interior (IntTree,IntTree) deriving Show
\end{verbatim}
Write a function \texttt{treeSum:IntTree $\rightarrow$ Integer} that adds up
the values in the leaves of a tree:
\begin{verbatim}
*Main> treeSum(Leaf 3)
3
*Main> treeSum(Interior (Leaf 2, Leaf 3))
5
*Main> treeSum(Interior(Leaf 2, Interior(Leaf 1, Leaf 1)))
4
\end{verbatim}


Write a function \texttt{height : IntTree $\rightarrow$ Integer} that
returns the height of a tree:
\begin{verbatim}
*Main> height(Leaf 3);
1
*Main> height(Interior(Leaf 2, Leaf 3));
2
*Main> height(Interior(Leaf 2, Interior(Leaf 1, Leaf 1)));
3
\end{verbatim}


Write a function \texttt{balanced: IntTree $\rightarrow$ Bool} that
returns true if a tree is balanced (i.e., both subtrees are balanced
and differ in height by at most one).  You may use your height
function above.
\begin{verbatim}
*Main> balanced(Leaf 3);
True
*Main> balanced(Interior(Leaf 2, Leaf 3));
True
*Main> balanced(Interior(Leaf 2, Interior(Leaf 3, Interior(Leaf 1, Leaf 1))));
False
\end{verbatim}

Is your implementation as efficient as possible?  What is wrong with
using the \texttt{height} function in the definition of
\texttt{balanced}?  How would you write \texttt{balanced} to be more
efficient?  (You need not write code, but describe how you would do
this.)

\item {\bf Stack Operations}


Certain programming languages (and HP calculators) evaluate
expressions using a stack.  As some of you may know,
PostScript is a programming language of this ilk for describing images
when sending them to a printer.  We are going to implement a simple
evaluator for such a language.  Computation is expressed as a sequence
of operations, which are drawn from the following data type:
\begin{center}
\begin{verbatim}
data OpCode = Push Float | Add | Mult | Sub | Div | Swap deriving Show
\end{verbatim}
\end{center}
The operations have the following effect on the operand stack.  (The
top of the stack is shown on the left.)
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
OpCode        & Initial Stack & Resulting Stack    \\
\hline\hline
\texttt{Push(r)}   & ...           & r ...           \\
\texttt{Add}       & a b ...       & (b + a) ...        \\
\texttt{Mult}      & a b ...       & (b * a) ...        \\
\texttt{Sub}       & a b ...       & (b - a) ...        \\
\texttt{Div}       & a b ...       & (b / a) ...        \\
\texttt{Swap}      & a b ...       & b a ...        \\
\hline
\end{tabular}
\end{center}
The stack may be represented using a list for this example, although
we could also define a stack data type for it.
\begin{center}
\begin{verbatim}
type Stack = [Float]
\end{verbatim}
\end{center}
Write a recursive evaluation function with the signature
\begin{center}
\begin{verbatim}
eval :: ([OpCode], Stack) -> Float
\end{verbatim}
\end{center}
It takes a list of operations and a stack.  The function should
perform each operation in order and return what is left in the top of
the stack when no operations are left.  For example,
\begin{center}
\begin{verbatim}
eval([Push 2.0, Push 1.0, Sub],[])
\end{verbatim}
\end{center}
returns 1.0.  The \texttt{eval} function will have the following basic form:
\begin{center}
\begin{verbatim}
eval ([],          a:rest)   = --
eval ((Push n):ops, rest)     = --
--
eval (_,            _)       = 0.0;
\end{verbatim}
\end{center}
You need to fill in the blanks and add cases for the other opcodes.

The last rule handles illegal cases by matching any operation list and
stack not handled by the cases you write.  These illegal cases include
ending with an empty stack, performing addition when fewer than two
elements are on the stack, and so on.  You may ignore divide-by-zero
errors for now (or look at exception handling in Ullman-- we will
cover that topic in a few weeks).


\end{enumerate}



\end{enumerate}

\end{document}