\documentclass[11pt]{article}	%
\usepackage{proof}
\usepackage{code}
\textheight 9.25in
\textwidth 6.25in
\oddsidemargin 0in
\topmargin -0.5in
\renewcommand{\baselinestretch}{1.1}
\newcommand{\bnf}[1]{$\langle{}$#1$\rangle$}
\newcommand{\lexp}{\langle exp \rangle}
\newcommand{\makeline}{\mbox{$\left\{\hspace*{4in}\right\}$}}

\newcommand{\boolean}{\mbox{\sf bool}}
\newcommand{\intg}{\mbox{\sf integer}}
\newcommand{\listtype}{\mbox{\sf list}}
\newcommand{\type}{\langle\mbox{\it type}\rangle}
\newcommand{\swhile}{\mbox{\sf while}}
\newcommand{\senddo}{\mbox{\sf end do}}
\newcommand{\sdo}{\mbox{\sf do}}
\newcommand{\divline}{\cline{2-2}}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}


\begin{document}

\begin{titlepage}

\begin{flushright} %\bf
\begin{tabular}{l@{:}l@{\hspace*{2in}}}
 Name&\\
 SSN &
\end{tabular}
\end{flushright}

\vspace*{1in}
\begin{center}
\Large \sl
 CSE 428\\[1ex]
 Fall 1999\\[1in]
\large 
 Midterm \#2 \\[1ex]
\normalsize
 17 November 1999
\end{center}
\vspace{2in}

\noindent
The exam consists of 5 problems on 7 pages, totaling 100 points.  Read
each question carefully and use your time judiciously.

\begin{center} 
{\it Write your name/number on every page.  }
\end{center}
\end{titlepage}

%\vspace*{1.5in}
\begin{enumerate}

%%% #1 Types %%%
\item Give the {\em most general} types for each of  \marginpar{(20 pts)}
	the following function declarations.

\bigskip

\begin{enumerate}
  \item \cd{fun flip(f,x,y) = f(y,x);} \\[12ex]
  \item \cd{fun flop(f,g,z) = f(g(z),z);} \\[12ex]
  \item \begin{code}
fun reduce(f,a,nil) = a
   |reduce(f,a, (x::xs)) = f(x,reduce(f,a,xs));\end{code}	 \\[12ex]
  \item \begin{code}
fun altnfold(f,g,0,x) = x + 0.0
   |altnfold(f,g,n,x) = f(g(altnfold(f,g,n-1,x)));\end{code}


\end{enumerate}

\newpage
%----------------------------------------------------------------------%

%%% #2 Values %%%
\item Consider the following function definitions:  \marginpar{(20 pts)}
\begin{code}
fun map(f,nil) = nil
   |map(f,x::xs) = f(x) :: map(f,xs);

fun filter(p,nil) = nil
   |filter(p,x::xs) = if p(x) then x::filter(p,xs) else filter(p,xs);

fun nfold (f,0) x = x
   |nfold (f,n) x = f(nfold(f,n-1) x);

fun even n = (n mod 2 = 0);
fun inc n = n+1;
\end{code}
Give the value produced by each of the expressions below.

\begin{enumerate}
  \item \marginpar{(5 pts)}
\begin{code}
map(inc, [2,4,6]);\end{code} 
\\[12ex]

  \item \marginpar{(5 pts)}
\begin{code}
nfold(inc,5) 4;\end{code} \\[12ex]

  \item \marginpar{(5 pts)}
\begin{code}
filter(even, map(inc, [1,2,3,4]));\end{code} \\[12ex]

  \item \marginpar{(5 pts)}
\begin{code}
map(nfold(inc,2), [1,2,3,4]);\end{code} 

\end{enumerate}

\newpage
%----------------------------------------------------------------------%
%%% #3 Higher-order Functions as data %%%
\item Consider the following representation of  \marginpar{(20 pts)}
   sets of integers as functions.  A set $S$ (of integers) is represented
   by a function $f$ of type \cd{int -> bool} such that
   \[ f(n)=\mbox{\it true} ~~\mbox{iff}~~ n\in S \]
   Each of the following definitions defines either a set or a function
   on sets.  For each definition, give a {\bf brief} description of
   what it does (in terms of sets).
   \begin{enumerate}
   \item \cd{fun A x = false;} \\[12ex]
   \item \cd{fun B (f,g) = fn x => f(x) orelse g(x);} \\[12ex]
   \item \cd{fun C (f,g) = fn x => f(x) andalso g(x);} \\[12ex]
   \item \cd{fun D (x,f) = fn y => (x=y) orelse f(y);} \\[12ex]
   \item \cd{fun E (f,g) = fn y => f(y) andalso (not (g(y)));}
   \end{enumerate}




\newpage
%----------------------------------------------------------------------%
%%% #4 SML Meta Programming %%%
\item  Consider the following datatype declaration \marginpar{(20 pts)}
	for a small subset of expressions using deBruijn notation:

\begin{code}
datatype deBruijn = dbIntConst of int
             | ## of int   (* constructor for deBruijn indices *)
             | dbOp of (deBruijn * Oper * deBruijn)
             | dbLet of (deBruijn * deBruijn);
\end{code}

Complete the definition below such that \cd{closed}  is a function
which when given a deBruijn expression returns \cd{true} if and only if
the expression contains {\em no free variables}.  I.e., every variable
occurrence must be within the scope of a declaration for that variable.
(Hint: use the
second parameter of \cd{f} to keep track of the current lexical ``depth''.)

\begin{code}
local
  fun f (dbIntConst(x),D) = 


     |f (## k, D) = 


     |f (dbOp(e1,_,e2),D) = 


     |f (dbLet(e1,e2),D) = 


in
  fun closed e = f(e, 0)
end;
\end{code}

\newpage

%----------------------------------------------------------------------%
%%% #5 Java & Concurrency %%%
\item    


Consider the problem of the shared bank account  \marginpar{(20 pts)}
 presented in  Lecture 31, where for simplicity we 
restrict deposits and withdrawals to be of 100 dollars at the time. 
{\em Assume that there can be an arbitrary number of threads sharing 
the same account.  Also, assume that each account holder can do
an arbitrary number of deposits and withdrawals, in any order.}

For each of the following solutions, say whether it is correct, namely 
whether it avoids interference (race hazards), deadlock, 
and prevents the balance from becoming negative. 
% For each solution which is incorrect, explain briefly the reasons why it is incorrect.

\begin{enumerate}
\item
\begin{verbatim}
   class Account {
       private double balance;

       public Account(double initialDeposit) {
           balance = initialDeposit;
       }

       public double getBalance() {
           return balance;
       }
      
       public void deposit() { 
           balance += 100;
           notify();
      }   

       public void withdraw() { 
           if ( balance < 100 ) wait();
           balance -= 100; 
      }     

   }

   class AccountHolder extends Thread {
       private Account acc;
           ...
       public void run() {
           ...
           acc.deposit();
           ...
           acc.withdraw();
           ...
      }
   }
\end{verbatim}

\vskip 1.5in

\item Like in (a), but with the methods in Account synchronized
\begin{verbatim}
   class Account {
       ...
       public synchronized double getBalance() { ... }
       ...
       public synchronized void deposit() { ... }
       ...
       public synchronized void withdraw() { ... }
   }
\end{verbatim}

\vskip 1.5in

\item Like in (b), but with the ``if'' replaced by a ``while'' in the method withdraw() 
\begin{verbatim}
   class Account {
       ...
        public synchronized void withdraw() { 
            while ( balance < 100 ) wait();
            balance -= 100; 
        }
   }
\end{verbatim}

\vskip 1.5in

\item Like in (c), but with the ``notify()'' replaced by a ``notifyAll()'' in the method deposit() 
\begin{verbatim}
   class Account {
       ...
       public void deposit() { 
           balance += 100;
           notifyAll();
       }     
       ...
   }
\end{verbatim}

\newpage

\item Like in (d), but with the test on balance done in the AccountHolder class rather than in the Account class
\begin{verbatim}
   class Account {
       ...
        public synchronized void withdraw() { 
            balance -= 100; 
       }     
       ...
   }

   class AccountHolder extends Thread {
       private Account acc;
           ...
       public void run() {
           ...
           acc.deposit();
           ...
           safeWithdraw(acc);
           ...
       }
       private synchronized void safeWithdraw(Account a) {
           while ( balance < 100 ) wait();
           a.withdraw();
   }   
\end{verbatim}

\vskip 2in

\end{enumerate}


%----------------------------------------------------------------------%
%----------------------------------------------------------------------%
%\item If your life was a game of {\em Jeopardy}, what   \marginpar{(0 pts)}
%	would the categories be?
%\item In the movie {\em Bride of Chucky}, what  \marginpar{(0 pts)}
%	was the name of Chucky's bride?

\end{enumerate}
\end{document}


 