\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 Friday, 11/12/2010
\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. 

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{10}{Exceptions}
    Consider the following functions, written in ML: 
    \begin{verbatim}
        exception Excpt of int; 
        fun twice(f,x) = f(f(x)) handle Excpt(x) => x; 
        fun pred(x) = if x = 0 then raise Excpt(x) else x-1; 
        fun dumb(x) = raise Excpt(x); 
        fun smart(x) = (1 + pred(x)) handle Excpt(x) => 1; 
    \end{verbatim}
    What is the result of evaluating each of the following expressions? 
    \begin{enumerate}
        \item twice(pred,1); 
        
        \item twice(dumb,1); 

        \item twice(smart,0); 
    \end{enumerate}
    In each case, be sure to describe which exception gets raised and
    where.

   \item \phead{10}{Haskell Exceptions via monads}

    The function \texttt{stringToNum} defined below uses two auxiliary
    functions to convert a string of digits into a non-negative
    integer.
    \begin{verbatim}
   import Char

   charToNum c = ord c - ord '0'

   calcList ([],n) = n 
   calcList (fst:rest,n) = calcList(rest,10 * n + charToNum fst)

   stringToNum s = calcList(s, 0)    
    \end{verbatim}
    For instance, \texttt{stringToNum "3405"} returns the integer 3405. 

    Unfortunately, \texttt{calcList} returns a spurious result if the string
    contains any non-digits. For instance, \texttt{stringToNum "3a05"} returns
    7905, while \texttt{stringToNum " 405"} returns -15595. This occurs
    because
    \texttt{charToNum} will convert any character, not just digits. We can
    attempt to fix this by having \texttt{charToNum} raise an exception if it
    is applied to a non-digit.


    \begin{enumerate}

    \item Revise the definition of \texttt{charToNum} to raise an exception, 
    and then modify the function \texttt{stringToNum} so that it handles the
    exception, returning -1 if there is a non-digit in the string. 
    Here is the Haskell code to throw and catch exceptions (via the 
    Exn monad), as well as the code for charToNum and calcList.  The 
    only thing missing is the code for stringToNum.  (Note that I 
    changed the name of ``catch'' to ``catchIt'' to avoid a name 
    conflict with a different function in the standard prelude.)
    \begin{verbatim}
import Char

data Exn a = Oops String | Answer a     deriving (Show)

instance Monad Exn where 
         return a = Answer a -- recall that return :: a -> Exn a

         -- recall that (>>=) :: M a -> (a -> M b) -> M b 
         (Oops s) >>= f = Oops s 
         (Answer a) >>= f = f a

throw :: String -> Exn a 
throw = Oops

catchIt :: Exn a -> (String -> Exn a) -> Exn a 
catchIt (Oops l ) h = h l 
catchIt (Answer r) _ = Answer r

charToNum :: Char -> Exn Int
charToNum c = if (c < '0' || c > '9') then throw "non-digit"
                                      else return (ord c - ord '0')
calcList:: ([Char],Int) -> Exn Int
calcList ([],n) = return n 
calcList (fst:rest,n) = 
         do nextDigit <- charToNum fst
            calcList(rest,10 * n + nextDigit)

stringToNum :: [Char] -> Int
stringToNum s = ...
    \end{verbatim}

    Note that because calcList returns a value of type Exn Int, 
    stringToNum (which should be written with helping functions) will 
    need to catch the result of calcList and then extract the value 
    from the monad to get an Int answer.
    
    \item Implement  Haskell
    functions to provide the same behavior (including returning -1 if
    the string includes a non-digit) as in the first part, but without
    using exceptions. While you may change any function, try to preserve
    as much of the structure of the original program as possible.

    \item Which implementation do you prefer?  Why?

    \end{enumerate}

    \item \phead{15}{Exceptions and Recursion}
    
    Please do problem 8.4 from Mitchell, page 230.
    
    \item \phead{5}{Tail Recursion}
    
    Please define a tail recursive function \texttt{sumsquares(n)} that can
    compute the sum of the first n squares: $1^2 + 2^2 + \ldots +
    n^2$.
   
    \item \phead{10}{Tail Recursion and Exception Handling}
    
    Please do problem 8.5 from Mitchell, page 230.
\end{enumerate}

\end{document}