\documentclass[11pt]{article}
\usepackage{code}
\usepackage{proof}
%\usepackage{fullpage}

\textheight 9.25in
\textwidth 6.25in
\oddsidemargin 0in
\topmargin -0.5in

\begin{document}

\begin{titlepage}
\begin{flushright} 
\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 
 Final Exam \\[1ex]
\normalsize
 14 December 1999
\end{center}
\vspace{2in}
\noindent
The exam consists of 8 problems on 8 pages, totaling 200 points.  Read
each question carefully and use your time judiciously.

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

%----------------------------------------------------------------------%
\begin{enumerate}

% #1 parameter passing
\item Consider the following program: \marginpar{(20 pts)}
\begin{verbatim}

main() {
 int a,b,c;

  function Rosencrantz(int x, int y) {
    a = 4;
    b = x*y;
    return (x+y);
  }

  a = 1;
  b = 2;
  c = Rosencrantz(a,b);
}
\end{verbatim}

What is the final value of c under each of the following conditions:
\begin{enumerate}
\item x is passed by value and y is passed by reference\\[10ex]

\item x is passed by reference and y is passed by value\\[10ex]

\item both x and y are passed by value\\[10ex]

\item both x and y are passed by reference
\end{enumerate}
\newpage

% #2 Grammars
\item Consider the following three grammars: \marginpar{(20 pts)}

\begin{tabular}{l@{\hspace{6ex}}l}
Grammar 1 & Grammar 2 \\
\hline
\verb!E ::= E * F | F!  
   & \verb!E ::= E + F | E - G | F! \\
\verb!F ::= F + G | F - G | G!  
   & \verb!F ::= F * G | G! \\
\verb!G ::= N | Id | ( E )!  
   & \verb!G ::= N | Id | ( E )! \\[2ex]
\end{tabular}

\begin{tabular}{l}
 Grammar 3 \\
\hline
 \verb!E ::= E + F | E - F | E * F! \\
   \verb!F ::= N | Id! \\[2ex]
\end{tabular}


Given the following sentences (where "a", "b" and "c" can be generated
by \cd{Id}), 
indicate which of the above grammars can generate each sentence.


\begin{enumerate}
\item  \cd{(a - b * 2 + c)} \\[10ex]
\item  \cd{a * b + ( 2 - c )}\\[10ex]
\item  \cd{a + b * c - 2}\\[10ex]
\item  \cd{a * b - c}
\end{enumerate}

\newpage


% #3 Typings
\item  Give the most general types \marginpar{(20 pts)}
	for each of the following declarations:
\begin{enumerate}
\item \cd{fun Curry f x y = f(x,y);} \\[10ex]
\item \cd{fun unCurry f (x,y) = f x y;} \\[10ex]
\item \cd{fun swapArgs f x y = f y x;} \\[10ex]
\item 
\begin{code}
fun reversemap (f, nil) = nil
  | reversemap (f, x::xs) = xs@[f x];\end{code}
\end{enumerate}
\newpage

% #4 Scoping
\item Consider the following program: \marginpar{(20 pts)}
\begin{verbatim}
program main
{
  int x,y,z;

  procedure Othello(int m)
  {
     int z;
     z = m + x;
     y = (x + y + z) * 2;
     print(x,y,z,m);
  }

  procedure Iago(int n)
  {
     int y;
     y = z * 2;
     Othello(n * y);
     print(x,y,z,n);
  }


  x = 1;
  y = 2;
  z = 3;
  Iago(y);
  print(x,y,z);
}
\end{verbatim}


\begin{enumerate}
\item Write the output of the program under static scoping call-by-value 
	rules. \\[10ex]
\item Write the output under dynamic scoping call-by-value rules.
\end{enumerate}
\newpage

% #5 Inference Rules
\newcommand{\senv}{\mbox{\sf senv}}
\newcommand{\intty}{\mbox{\sf int}}
\newcommand{\boolty}{\mbox{\sf bool}}
\newcommand{\truee}{\mbox{\sf true}}
\newcommand{\falsee}{\mbox{\sf false}}
\item Consider the following inference rules for \marginpar{(20 pts)}
typing values (where $N$ is any integer):
\[ \infer{\senv\vdash N :\intty}{} ~~~~~~
   \infer{\senv\vdash \truee :\boolty}{} ~~~~~~ 
   \infer{\senv\vdash \falsee :\boolty}{}
\]
\[   \infer{\senv\vdash(v_1,v_2) : (\tau_1\times\tau_2)}
         {\senv\vdash v_1 :\tau_1 & \senv\vdash v_2 :\tau_2}
\]
Indicate whether each of the following is true or false.

\begin{enumerate}
\item There is an inductively defined set $S$ such that
       $(v,\tau)\in S$ if and only if $v:\tau$ is provable using
	only the rules above.\\[10ex]
\item The following definition is  equivalent to the rules above:
      \begin{quote}
	1. Every integer $N$ has type \intty.\\
        2. Boolean constants \truee\ and \falsee\ have type \boolty.\\
        3. If $v_1$ has type $\tau_1$ and $v_2$ has type $\tau_2$
	   then $(v_1,v_2)$ has type $(\tau_1\times\tau_2)$.
      \end{quote} \mbox{}\\[10ex]
\item The following grammar generates exactly the typeable values
      specified by the above rules:
 \[ V ~~{::=}~~ N  ~|~ \truee ~|~ \falsee ~|~ (V,V) \] \mbox{}\\[10ex]

\item The following grammar generates exactly the types which can
      occur in a provable judgment $v:\tau$ using the above rules:
 \[ T ~~{::=}~~ \intty ~|~ \boolty ~|~ \intty \times \intty ~|~ 
       \boolty \times \boolty ~|~ (T) \] \mbox{} \\[10ex]

\item The above inference rules are ambiguous.
\end{enumerate}
\newpage


% #6 Prolog
\item Recall the definition of \cd{permute} \marginpar{(20 pts)}
  in Prolog:
\begin{code}
insert(X,L,[X|L]).
insert(X,[Y|L],[Y|K]) :- insert(X,L,K).

permute([],[]).
permute([X|L], L2) :- permute(L,L1), insert(X,L1,L2).
\end{code}

Which of the following goals are provable using this set of clauses?
If the goal contains variables, give the solutions (instantiations)
that Prolog will provide {\em first}.
\begin{enumerate}
\item \cd{permute([1,2,3],[1,2,3])} \\[5ex]
\item \cd{insert([1],[2,3],[1,2,3])} \\[5ex]
\item \cd{permute(X,Y)} \\[5ex]
\item \cd{permute([1,2,3],Z)} \\[5ex]
\end{enumerate}

Assume we reverse the order of the clauses for \cd{insert} in our program:
\begin{code}
insert(X,[Y|L],[Y|K]) :- insert(X,L,K).
insert(X,L,[X|L]).
\end{code}
and give Prolog the following goal:
\begin{code}
?- permute([a,b],L).\end{code}
Give in order all solutions generated by Prolog (assuming we keep
asking for more solutions).

\newpage

%# 7 - Threads
\item Define a class {\tt Semaphore} \marginpar{(20 pts)}
with the following methods:
\begin{enumerate}
\item A constructor method with an integer parameter n, 
representing the initial value of the semaphore.
\item A method {\tt down()} which decrements the semaphore if it is positive, 
and suspends otherwise.
\item A method {\tt up()} which increments the semaphore.
\end{enumerate}
\newpage


% #7 - Static vs Dynamic
\item For each of the following properties/conditions, \marginpar{(20 pts)}
state ({\bf yes} or {\bf no}) 
whether it can always be detected {\it statically} (at compile time)
in a statically typed, statically scoped, multi-threaded,
higher-order programming
language which does not allow implicit type coercions, but does support
C++-style generic modules.

\begin{enumerate}
\item A function can be called with the wrong number of arguments.\\[10ex]
\item Deadlock cannot occur. \\[10ex]
\item An arithmetic exception (e.g., overflow, divide by zero) cannot occur.
	 \\[10ex]
\item Generic modules are always instantiated with appropriate types. \\[10ex]
\item An undeclared variable is referenced. \\[10ex]
\end{enumerate}


\end{enumerate}
\end{document}

