\documentclass[12pt]{report}

\usepackage{amsmath}

\newcommand{\assign}{\mathrel{:=}}

\begin{document}
\begin{center}
	{\bf Com Sci 221/321 --- Programming Languages}\\
	{\bf Final Exam, Autumn 1999}\\
	Wednesday, 8 December, 10:30 AM - 12:30 PM\\
        Ryerson 251\\
        5 problems on pages 2--6 plus 1 graduate problem on page 7
\end{center}

\begin{itemize}

\item You may use the textbook, my class materials, any other published
material, and notes of your own.

\item There are 5 problems for Com Sci 221 and 321. There is 1
additional problem for Com Sci 321 only. Each numbered problem is
weighted equally for grading purposes.

\item You may use whatever sort of paper you find convenient, but
please make your answers legible, and write your name on every sheet.

\end{itemize}

\newpage

\section*{Com Sci 222 and 322}

\subsection*{Problem 1: l- and r-values}

Consider the assignment
$$A[i]=A[A[i]]$$
Describe carefully the sequence of seven operations on l-values and
r-values involved in executing this assignment command. You don't need
to give calculations in detail, but you must mention every time
something is calculated from something else.

Give an example of initial values for $A$ and $i$ that cause $A[i]\neq
A[A[i]]$ immediately after executing the assignment. Explain what
happened \emph{briefly} in terms of l- and r-values (don't go through
all the steps again, just mention which l- and/or r-values caused the
inequality).

\pagebreak

\subsection*{Problem 2: reasoning with invariants}

Suppose that you are given an array $A$ of integers, indexed from $0$
to $n$ ($n\geq 2$), and you are guaranteed that the values in the
array increase from $A[0]$ up to some maximum value at a position
$A[t]$, then decrease from $A[t]$ to $A[n]$. That is, there exists a
$t$ with $0<t<n$, such that
%
\begin{alignat*}{3}
%
\text{for all }&i\text{ with } & 1\leq{}&i<t\text{, } &
  A[i]&<A[i+1]\text{, and} \\
\text{for all }&j\text{ with } & t\leq{}&j\leq n\text{, } &
  A[j]&>A[j+1]\text{.}
%
\end{alignat*}
%
(Pay close attention to the difference between strict $<$, $>$ and
nonstrict $\leq$, $\geq$.)

Write a simple while-loop program to find the value of $t$, by
manipulating the values of three variables, $\textit{left}$, $\textit{middle}$, and
$\textit{right}$, using the invariant
%
$$
\textit{left}\leq\textit{middle}\leq\textit{right}
\text{ and }A[\textit{left}]<A[\textit{middle}]>A[\textit{right}]
$$
%
It is essential to use the given invariant---there is a very different
program using a different invariant. Try to look at the fewest
elements of $A$ that you can.

How is the value of $t$ determined when your loop halts?

\pagebreak

\subsection*{Problem 3: simulating control structures with higher-order
functions in \emph{ML}}

Consider a \textbf{while} loop with a single \textbf{break} that exits
the loop:
\begin{quote}
\textbf{while} $C_1$ \textbf{do begin}\\
\hspace*{1em}$SL_1$\\
\hspace*{1em}\textbf{if} $C_2$ \textbf{then break}\\
\hspace*{1em}$SL_2$\\
\textbf{end}
\end{quote}
Define a function \textit{while\_break} in pure functional \emph{ML} to
capture the behavior of the control structure above. The function
needs $4$ arguments, corresponding to $C_1$, $C_2$, $SL_1$, $SL_2$,
and another, corresponding to the state.

\pagebreak

\subsection*{Problem 4: conditional vs.\ pattern-matching in
\emph{ML}}

Here is an attempt to define conditional in \emph{ML}, using
pattern-matching instead of a built-in conditional function.
%
$$
\begin{array}{cllllcl}
%
\textbf{fun} & \textit{cond} & \textbf{true}  & x & y & = & x\\
 |           & \textit{cond} & \textbf{false} & x & y & = & y\\
 ;
%
\end{array}
$$
%
Explain \emph{very} briefly (one sentence) why the definition of
$\textit{cond}$ above is not satisfactory.

What is the difference in results between the two following forms?
$$\textit{cond}\;c\;(x\;z)\;(y\;z)$$
and
$$\textit{cond}\;c\;x\;y\;z$$
What sorts of values for $x$, $y$, $z$ will make them the same,
vs.\ different?

\pagebreak

\subsection*{Problem 5: occurs check in \emph{Prolog} unification}

Give an example of a small pure logic program in \emph{Prolog} that
demonstrates the lack of an occurs check in \emph{Prolog}'s
unification procedure. Describe \emph{very} briefly (one sentence) the 
behavior of this program with vs.\ without the occurs check.

\pagebreak

\section*{Com Sci 321 only}

\subsection*{Problem G1: circularity in \emph{ML} type inference}

Suppose that we implement \emph{ML} without any occurs check in the
type inference mechanism, and that we accept a program as correct when 
we infer a ``circular'' type for it. For example,
%
$$
\textbf{fun }\textit{paradox x }=(\textit{x x});
$$
%
is a correct program in circular-typed \emph{ML}.

\begin{enumerate}
%
\item Invent a sensible way to denote the type of $\textit{paradox}$ in
circular-typed \emph{ML}.
%
\item What is the type of $(\textit{paradox paradox})$?
%
\item Let $a$ and $b$ be expressions in circular-typed \emph{ML}, where $a$
 has a function type, and $b$ has any type. $(a\text{ }(\textit{paradox
 paradox }b))$ is also an expression in circular-typed \emph{ML}. That
 is, $(\textit{paradox paradox})$ appears to be a universal type
 converter. In \emph{Pascal} and \emph{C}, the use of variant records
 constitutes a loophole in the type system, and destroys the security
 that objects are only used with their true types. Does the presence
 of $(\textit{paradox paradox})$ similarly destroy the security of type
 checking in circular-typed \emph{ML}? Explain very briefly (1--3
 sentences).
%
\end{enumerate}

\end{document}
