\documentclass[12pt]{report}

\usepackage{amsmath}

\newcommand{\assign}{\mathrel{:=}}
\newcommand{\progindent}{\hspace*{3em}}
\newcommand{\exprbox}{\mathord{\underline{\phantom{\Sigma +\Sigma}}}}
\newcommand{\opbox}{\mathop{\underline{\phantom{++}}}}
\newcommand{\eopmark}{\mathord{\textit{eop}}}
\newcommand{\eolmark}{\mathord{\textit{eol}}}
\newcommand{\chartype}{\mathord{\textbf{kbd\_char}}}
\newcommand{\logicaltexttype}{((\chartype^*)^*)^*}
\newcommand{\reprtexttype}{(\chartype+\{\eolmark,\eopmark\})^*}
\newcommand{\ttexta}{\mathord{\textbf{textl}}}
\newcommand{\ttextb}{\mathord{\textbf{textr}}}

\newcommand{\pagewarning}{%
\vfil
\begin{center}
\emph{continued on next page}
\end{center}
\vfil
}

\begin{document}
\begin{center}
        \textbf{Com Sci 221 --- Programming Languages}\\
        \textbf{Final Exam, Autumn 2000}\\
        Monday, 4 December, 1:30 PM - 3:30 PM\\
        Ryerson Annex 276\\
        4 problems on pages 2--7
\end{center}

\begin{itemize}

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

\item 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}

\pagebreak

\section*{Problem 1: Datatypes}

Let $\chartype$ be a datatype containing the normal visible characters
(letters, numbers, punctuation) and space character on a typewriter
keyboard (the character type in most programming languages contains
additional stuff that I don't want to include). Suppose that you want
to represent typed text that is broken up into lines and pages.

Logically, such text has the type $\ttexta=\logicaltexttype$, that is
lists of pages, which are lists of lines, which are lists of keyboard
characters. In \emph{ML} notation, this is defined by
%
$$
\begin{array}{clcl}
%
\textbf{datatype} & \textit{textl} & = &
   \textit{kbd\_char list list list} \\
 & & ;
%
\end{array}
$$

A common implementation of typed text uses two special marks to
indicate the ends of each line ($\eolmark$) and the end of each page
($\eopmark$). The type of lists of characters with interspersed marks
is $\ttextb=\reprtexttype$. In \emph{ML} notation, this is
%
$$
\begin{array}{clcl}
%
\textbf{datatype} & \textit{textrelt} & = &
         \textit{letter} \textbf{ of } \textit{kbd\_char} \\
 & & | & \textit{eop} \\
 & & | & \textit{eol} \\
 & & ; \\
\textbf{datatype} & \textit{textr} & = & \textit{textrelt list} \\
 & & ;
%
\end{array}
$$

\pagewarning

\pagebreak

\begin{enumerate}
%
\item Encode the following members of $\logicaltexttype$ in
  \mbox{$\reprtexttype$}. Be careful: $\eolmark$ and $\eopmark$ mark the
  \emph{end} of each line and each page. You will get something different and
  wrong if you mark the breaks between lines and pages, or the
  beginnings.
%
  \begin{enumerate}
%
  \item $[\;\;]$ (empty text)
%
  \item $[\:[\;\;]\:]$ (text containing empty page)
%
  \item $[\:[\:[\;\;]\:]\:]$ (text containing one page containing
    empty line)
%
  \item $[\:[\;\;],\:[\:[\:\:]\:]\:]$ (text containing two pages, one
    empty, one containing empty line)
%
  \item $[\:[\:[a,b,c],\:[d,e,f]\:],\:[\:[g,h,i],\:[j,k,l]\:]\:]$ (two pages
    each containing two lines each containing three characters)
%
  \item $[\:[\:[a,b,c],\:[d,e,f]\:],\:[\:[g,h,i],\:[j,k,l],\:[\;\;]\:],\:[\;\;]\:]$
%
  \end{enumerate}
%
\item Give a brief but precise characterization of the members of
  \mbox{$\reprtexttype$} that are \emph{not} used to represent members
  of $\logicaltexttype$.
%
\end{enumerate}

\pagebreak

\section*{Problem 2: Loop invariant}

The solution to this problem is similar to the clever exponentiation
program that we developed in class, but slightly trickier. Be
\emph{very} careful with the arithmetic reasoning. It is all simple
elementary high-school algebra, but if you make a guess instead of
doing the calculation, you are \emph{very} likely to be wrong. All
values in this problem are integers.

Consider a rather peculiar function $f$ mapping two nonnegative
integer arguments to a nonnegative integer result, defined
recursively by
%
$$f(m,n)=\left\{\begin{array}{ll}
              1 & \mbox{if }m,n=0\\
              f(m-1,m*2)+1 & \mbox{if }m>0\mbox{ and }n=0\\
              f(m,n-1)*2+1 & \mbox{if }n>0
              \end{array}\right.
$$
%
Even though the recursive definition above is \emph{not} a tail
recursion, there is a simple iterative way to compute values of $f$
using a single \textbf{while} loop with initialization of some
variables before the \textbf{while} loop. Let $m_0$ and $n_0$ be given
nonnegative integer values. Use the invariant
%
$$f(m,n)*i+j=f(m_0,n_0)\mbox{ and }m\geq 0\mbox{ and }n\geq 0$$
%
to develop a simple iterative program (a small number of assignments
to initialize $m,n,i,j$, followed by a single \textbf{while} loop
containing a single \textbf{if-then-else} command) computing
$f(m_0,n_0)$. You are not required to prove that your program
satisfies the invariant. What very simple combination of $i$ and $j$
gives the value of $f(m_0,n_0)$ when your loop terminates?

Construct your answer by filling in the blanks on the next page. Some
of the assignments are redundant ones of the form $x\assign x$. I
ordered the assignments carefully so that you don't need any temporary
variables.

\pagewarning

\pagebreak

{\renewcommand{\arraystretch}{2.1}
%
\begin{tabular}{l}
$n\assign\exprbox$\\
$m\assign\exprbox$\\
$j\assign\exprbox$\\
$i\assign\exprbox$\\
\textbf{while} $m>0$ \textbf{or} $n>0$ \textbf{do}\\
\progindent \textbf{if} $n=0$ \textbf{then}\\
\progindent\progindent $n\assign\exprbox$\\
\progindent\progindent $m\assign\exprbox$\\
\progindent\progindent $j\assign\exprbox$\\
\progindent\progindent $i\assign\exprbox$\\
\progindent \textbf{else}\\
\progindent\progindent $n\assign\exprbox$\\
\progindent\progindent $m\assign\exprbox$\\
\progindent\progindent $j\assign\exprbox$\\
\progindent\progindent $i\assign\exprbox$\\
\progindent \textbf{fi}\\
\textbf{od}\\
\textbf{output} $i\opbox j$
\end{tabular}
%
}

\pagebreak

\enlargethispage*{10ex}

\section*{Problem 3: Higher-order programming}

Recall the recursive definition of the base-2 exponential function:
%
\begin{verbatim}
(define exp2
        (lambda (i)
            (if (< i 1)
                        1 
                        (* 2 (exp2 (- i 1)))
            )
        )
)
\end{verbatim}
I defined \texttt{exp2} as a \texttt{lambda} expression, instead of
using the more convenient form of \emph{Scheme}
definition---\texttt{(define (exp2 i) \dots)}---because it makes your
work below slightly easier.

In the spirit of defining control structures as higher-order
functions, here is the mother of all recursions for one-argument
functions:
%
\begin{verbatim}
(define (recurse rbody)
        (letrec ((rfunc
                  (lambda (i)
                      ((rbody rfunc) i)
                  )
                ))
                rfunc
        )
)
\end{verbatim}
%
When \texttt{rbody} is a higher-order function representing the
\emph{body} of a recursive definition, \texttt{(recurse rbody)} is the
function of one argument produced by the recursive definition.

Define a higher-order function \texttt{exp2rbody}, representing the
body of the recursive definition of \texttt{exp2}, so that the
alternate definition of base-2 exponentiation:
%
\begin{verbatim}
(define nexp2 (recurse exp2rbody))
\end{verbatim}
%
makes \texttt{nexp2} work just like \texttt{exp2}. The \emph{body} of
the recursive definition of \texttt{exp2} is the part starting with
\texttt{(lambda (i) \dots}, but you have to think about the form
\texttt{(rbody rfunc)} in the definition of \texttt{recurse} in order
to package it just right into \texttt{exp2rbody}. (Because
\texttt{recurse} deals with pure functions rather than program
fragments, the \emph{state} parameter that enters into many of the
exercises is not involved here.)

\pagebreak

\section*{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}
$$
%
\begin{enumerate}
%
\item What type does \emph{ML} infer for \textit{cond}?
%
\item 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?
\item Explain \emph{very} briefly (one sentence) why the definition of
$\textit{cond}$ above is not satisfactory.
%
\end{enumerate}

\end{document}
