\documentstyle[proof,code,11pt]{article}	%
\textheight 9.25in
\textwidth 6.25in
\oddsidemargin 0in
\topmargin -0.5in
\renewcommand{\baselinestretch}{1.1}
\newcommand{\ef}{\mbox{$\mbox{\tt e}_{\mbox{\tt f}}$}}
\newcommand{\eg}{\mbox{$\mbox{\tt e}_{\mbox{\tt g}}$}}
\newcommand{\tauone}{\mbox{$\tau_1$}}
\newcommand{\tautwo}{\mbox{$\tau_2$}}
\newcommand{\tauthree}{\mbox{$\tau_3$}}
\newcommand{\taufour}{\mbox{$\tau_4$}}
\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 \#1 \\[1ex]
\normalsize
 6 October 1999
\end{center}
\vspace{2in}

\noindent
The exam consists of 5 problems on 5 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 Grammars %%%
\item  Consider the following grammar: \marginpar{(20 pts)}
 \begin{eqnarray*}
	E & {::}= & E \mbox{``+''} F ~|~ E \mbox{``--''} F ~|~ F \\
	F & {::}= & F \mbox{``$\ast$''} F ~|~ G  \\
        G & {::}= & \mbox{``--''} G ~|~ H \\
	H & {::}= & N ~|~ Id ~|~ \mbox{``(''} E \mbox{``)''}\\
\end{eqnarray*}
in which $N$ and $Id$ are nonterminals which unambiguously generate
a non-empty sequence of digits and identifiers beginning with an
alphabetic character, respectively.

For each of the following sentences, state whether it can be generated by
the grammar, and if it can, whether it can be generated unambiguously.
\begin{enumerate}
 \item $x * (y - - 5)$\\[3ex]
 \item $+x * y$ \\[3ex]
 \item $x*y+z*v$ \\[3ex]
 \item $(x+z) * -u * (v)$ \\[3ex]
 \item $-(-(x+y))$ \\[3ex]
\end{enumerate}

\newpage
%----------------------------------------------------------------------%
%% #2 -  Typing Rules %%
\item 	Recall the typing of a single recursive function \marginpar{(20 pts)}
	declaration:
	{\tt
	\[ \infer{senv \vdash \mbox{let}~f(x:\tau_1):\tau_2=e_2 ~\mbox{in}~
	    e ~\mbox{end} ~:~ \tau}
	    {senv[f:\tau_1\ra\tau_2,\,x:\tau_1] \vdash e_2:\tau_2 &
	     senv[f:\tau_1\ra\tau_2] \vdash e:\tau } \]
	}
	Consider the extension of the language to support exactly 2 mutually
	recursive function declarations.  We might write such a declaration
	as:
\begin{code}
let f(x:\tauone):\tautwo = \ef
    g(y:\tauthree):\taufour = \eg
in e
end
\end{code}
where \cd{f} and \cd{g} can appear in \cd{e}, \cd{\ef} and \cd{\eg}.

Give a typing rule, similar to the one above, to type such expressions.


\newpage

%----------------------------------------------------------------------%
%% #3 - Type Checking %%
\item Using the typechecking rules	\marginpar{(20 pts)}
 given in class (and on assignments),
type each of the following expressions.
Assume sequences of declarations in one \cd{let} expression are
handled {\em sequentially}.
If the expression is not well-typed, then
write {\bf no type}; otherwise, give the type of the expression.

\begin{enumerate}
  \item 
\begin{code}
let f(x:int):int = x*2;
    g(x:int):bool = x>0;
    z = 5
in  g(f(z+2)) and g(f(3+f(z)))
endlet\end{code} \\[2ex]

  \item 
\begin{code}
let x = 23;
    y = x * x;
in  let z = x*y;
        y = x>y
    in y+z
    endlet
endlet\end{code} \\[2ex]

  \item 
\begin{code}
let sq(x:int):int = x*x;
    qd(y:int):int = sq(sq(y));
    z = true
in  (let z=qd(4) in sq(z) endlet) + sq(4)
endlet
endlet\end{code} \\[2ex]

  \item 
\begin{code}
let x = (let x = 5 in x>0 endlet)
in let x = (if x then 3 else 6)
   in let x = x*x
      in x>0
      endlet
   endlet
endlet\end{code}
\end{enumerate}

\newpage

%----------------------------------------------------------------------%
%Parameter Passing
\item  Consider the following program: \marginpar{(20 pts)}
\begin{code}
program main
  x,y : integer;

procedure petruchio(a : integer, b : integer)
begin
  y := 43;
  a := b;
  b := 7;
  write(a,b);
end petruchio;

begin main
  x := 1;
  y := 0;
  petruchio(x,y);
  write(x,y);
end main;
\end{code}

Assuming the language is statically scoped, give the output of
this program when the parameters are passed

  \begin{enumerate}
        \item call-by-value  \\[.5in]
        \item call-by-value-result  \\[.5in]
        \item call-by-reference  \\[.5in]
        \item call-by-need  \\[.5in]
  \end{enumerate}

\newpage

%%% #5 Static Links %%%
\item Which of the following language restrictions   \marginpar{(20 pts)}
{\bf allow} us to implement a language {\bf without} static links or displays?
(Write {\bf yes} for each item which does allow this, 
 write {\bf no} otherwise.)

\begin{enumerate}
    \item procedures can only reference their parameters and local 
	variables \\[2ex]
    \item dynamic typing \\[2ex]
    \item static scoping \\[2ex]
    \item only call-by-value parameter passing \\[2ex]
    \item no recursive functions \\[2ex]
    \item no nested procedure declarations \\[2ex]
    \item static typing \\[2ex]
    \item no overloading of procedure names \\[2ex]
    \item dynamic scoping \\[2ex]
    \item recursive procedures and functions must be tail-recursive.
\end{enumerate}


\end{enumerate}
\end{document}


 