\documentclass{article}
\usepackage{fullpage}
\usepackage{mathpartir}

\parindent 0pt
\parskip 1.5ex

\begin{document}

\centerline{\textbf{\Large Graduate Programming Languages, Assignment 5}}
\centerline{\textbf{\Large Due: To Be Determined }}

\medskip

%Last updated: Summer 2011

\medskip

Ensure you understand the course policies for assignments.

\medskip

\texttt{hw5code.tar}, available on the course website, contains several
Caml files you need.

\medskip

For problems 1 and 2, do \emph{not} use mutable references, mutexes,
condition variables, fork-join, etc.  All you need is thread-creation
and the Concurrent ML primitives provided in the \texttt{Event}
module.  Remember to compile \texttt{cml.ml} via \texttt{ocamlc
  -vmthread -o hw5cml threads.cma cml.ml} or similar.  Also note Caml
terminates when the main thread terminates, so it is sometimes
convenient when testing to block the main thread (e.g., by calling
\texttt{Thread.yield} in an infinite loop).

\begin{enumerate}
  
\item (Concurrent ML) Implement the first commented-out interface in
  \texttt{cml.mli}.  Define type \texttt{barrier} and functions
  \texttt{new\_barrier} and \texttt{wait}.  If a barrier is created by
  \texttt{new\_barrier $i$} and a thread makes one of the first $i-1$
  calls to \texttt{wait} with that barrier, then the thread should
  block until the $i^{th}$ call, at which point all $i$ threads should
  proceed.  A thread that calls \texttt{wait} with a barrier after there
  have been $i$ calls with that barrier should block forever.
  
  \emph{How to do it:} \texttt{new\_barrier} should return a channel
  that a newly created thread receives on.  \texttt{wait} should send
  on this channel another channel and then receive on the channel it
  sends.  (It does not matter what is sent on this channel;
  \texttt{()} is a fine choice.) The newly created thread should
  ``remember'' how many waiters there are and what channels to send on
  after the last arrives.  The thread can then terminate.  You do
  not need \texttt{choose} or \texttt{wrap}.
  
\bigskip
\item (Concurrent ML) Implement the second commented-out interface in
  \texttt{cml.mli}.  This interface is for shared/exclusive locks
  (better known as readers/writer locks).  Function \verb|new_selock|
  creates a new lock.  Functions \verb|shared_do| and
  \verb|exclusive_do| take a lock and a thunk and run the thunk.  An
  implementation is correct if for each lock $lk$:
  \begin{itemize}
  \item If there are any thunks that have not completed, then at least one
    of these thunks gets to run.
  \item While a thunk passed to \verb|exclusive_do| $lk$ runs, no other
  thunk passed to \verb|exclusive_do| $lk$ or \verb|shared_do| $lk$
  runs.
  \item If there are no uncompleted exclusive thunks, then the
  uncompleted shared thunks get to run in parallel.
  \end{itemize}

  \begin{enumerate}
  \item A correct solution to this problem has been given to you, but
    it is much longer and more complicated than necessary.  In it, the
    ``server'' maintains explicit lists of waiting thunks.
    Reimplement the interface without these lists.  Instead just use a
    simpler protocol that relies on the fact that CML allows multiple
    threads to block on the same channel, effectively forming an
    implicit queue.  Hint: You still need \texttt{choose} and
    \texttt{wrap}, but you need fewer code cases and fewer total
    messages.
  
  \item Suppose a call to \verb|shared_do| $lk$ blocks before a call
    to \verb|exclusive_do| $lk$.  For the two implementations of the
    interface (the one given to you and your simpler one), describe
    the states under which we are \emph{sure} the call to
    \verb|shared_do| $lk$ will unblock before the call to
    \verb|exclusive_do| $lk$.  Explain your answer, which can be
    different for the two implementations.  Note \texttt{choose} is
    nondeterministic.
  \end{enumerate}

\newpage  
\item (Implementing Class-Based OOP) You will complete the code in
  \texttt{oo.ml}, which demonstrates one way to implement
  simple object-oriented programming.  There are \emph{two} similar
  languages involved: the ``source'' language and the language that
  the interpreter expects.
  
  The ``source'' language is an ML expression of type
  \verb|((classname option) classdef list) * exp| i.e., a pair of (1)
  a list of class definitions where the \verb|super| field contains a
  \verb|classname option| and (2) a ``main'' expression.  The
  \verb|super| field is the immediate superclass if there is one.  You
  may \emph{assume} the following: class names are distinct, the
  superclass relation has no cycles, all superclasses are defined in
  the program, the methods in one class definition have distinct
  names, the fields in one class definition have names distinct from
  each other and from all fields in all superclasses.  A subclass
  extends its superclass by adding all its fields and any
  methods with names different from those in any superclass.  To
  override a method, a class definition just includes a method of the
  same name (see the challenge problems).  

  The language for our interpreter is an ML expression of type
  \verb|((classname list) classdef list) * exp|.  Unlike the source
  language:
  \begin{itemize}
  \item The \verb|super| field holds a list of all superclasses
  (transitively).  There may be none.
  \item The \verb|methods| field holds all the methods for a class,
  including those defined in superclasses.
  \item The \verb|fields| field holds all the fields for a class,
  including those defined in superclasses.
  \end{itemize}

\begin{enumerate}
\item The code given to you defines a \verb|boolclass| in the source
  language.  Define two subclasses \verb|trueclass| and
  \verb|falseclass|.  Each should override the \verb|ifThenElse|
  method, using the encoding of true returning the first of two
  objects and false the second.
  
\item Implement \verb|translate_classdefs| of type\\
  \verb|(classname option) classdef list -> (classname list) classdef list| 
  for translating a list of class definitions from the source language to
  the interpreter language.  The sample solution uses several helper
  functions and several functions in Caml's list library, and is
  30--35 lines.

\item Complete the interpreter \verb|interp| of type \\
 \verb|classname list classdef list -> (varname * valu) list -> valu -> exp -> valu|.
Three cases are done for you.  The other cases are described
informally below; there should be no surprises.  In general, you may
throw whatever sort of exception you like for bad programs, even
\texttt{List.Not\_found}.  The arguments to \verb|interp| are the
(translated) class definitions (needed for method calls), an
environment (needed for local variables), the value currently bound to
self, and the expression being evaluated.  Note \texttt{New} creates a
\texttt{valu} where the fields start uninitialized.
\begin{itemize}
\item Getting a field fails if the result of evaluating the
  subexpression does not have that field or that field is still
  uninitialized.  Otherwise, it returns the \texttt{valu} held in the
  field.
\item Setting a field fails if the result of evaluating the
  first subexpression does not have that field.  Otherwise, it does
  the appropriate mutation and returns the field's new contents.
\item A let-expression is interpreted very much like in ML\@.
\item A cast fails if the class of the result of evaluating the
  subexpression is neither the class specified nor a (transitive)
  subclass of it.  Otherwise, the result is the result of the
  subexpression.
\item A local variable is looked up in the environment.
\item A method call evaluates all the subexpressions and then looks up
  the method in the class of the receiver.  The lookup just uses the
  name of the method, returning the first method in the list with that
  name.  The result is the evaluation of the method body using the
  receiver for self and an environment containing bindings just for
  the method arguments.  It is an error to have the wrong number of
  arguments.
\end{itemize}

\item In a short English paragraph, explain why having casts in our
  language is of little use.  In particular, give \emph{two} standard
  uses of casts in languages like Java and C++, one of which affects
  type-checking and one of which affects method-call semantics.
  Explain how neither is relevant with our implementation.

\newpage
\item \textbf{(Challenge Problems)} 
\begin{itemize}
\item (Fairly easy) Change the interpreter to support
  ``arity overloading'' --- a method call should not fail due to
  having the wrong number of arguments if a superclass of the receiver
  defined a method with the same name and the correct number of arguments.
\item (Fairly easy) Change your interpreter to detect type mismatches
  on field-assignment or method-call and fail immediately.
\item (Much more challenging) Changing your translation but not your
  interpreter, implement static overloading.  Document ambiguities and
  how you deal with them.  (Small hints: \verb|Fail| causes
  ambiguities.  You will need a type-checker even though
  the language is not type-safe.)
\end{itemize}
\end{enumerate}

\end{enumerate}

\textbf{Turn in:} Written/typed answers to 2b and 3d, and
Caml code in files \texttt{oo.ml} and \texttt{cml.ml}

\end{document}