Here is an answer key for the final.  I've just inserted the answers into
the latex source file of the final, marked by ***

Happy holidays!
  Alan


  \documentstyle{article}

  \topmargin -0.5in
  \oddsidemargin  0 in
  \evensidemargin  0 in
  \textwidth   6.5 in
  \textheight 8.5 in
  \setlength{\parindent}{0.0in}
  \setlength{\parskip}{7pt plus 1pt}

  \begin{document}

  \begin{center}
  {\large \bf Computer Science \& Engineering 505 -- Final} \\
  December 13, 1991 \\
  Closed Book -- 110 minutes -- 10 points per question -- 90 points total\\
  \end{center}

  {\bf Name:} \hrulefill


  \begin{enumerate}

  \item Describe Ada's exception handling mechanism.  Be sure to include
  definitions of the terms ``exception'', ``raise'', ``handle'', and
  ``propagate''.

*** An exception is an unusual condition, either defined by the underlying
system (such as divide-by-zero), or by the user.  In Ada an exception is an
instance of the type EXCEPTION, and is essentially just an atomic symbol
(there are no parameters).  "Raising" an exception means to signal that the
exceptional event has occurred.  This might be done by the system (such as
divide-by-zero) or by the user (using the RAISE EXCECPTION_NAME statement).

The user can define "handlers" for one or more exceptions.  For example, a
handler for the exception named zork looks like this:
    exception
      when zork => 
         ... -- exception handler body goes here 

There is also a catch-all "when others" that must occur last in the list of
handlers, and which matches any exception.

When an exception is raised, the runtime system looks in the currently
executing context (procedure, task, or block) for a handler for the named
exception.  If none is found, the system looks in the calling context, and
so forth up the stack (thus exceptions follow a dynamic scoping rule).  If
a handler is found, the currently executing statement is abandonded, and
control jumps to the handler.  (This would involve popping the stack if the
handler is non-local.)  The code in the handler is executed, and then Ada
returns from the program unit that had the handler (not the place where the
exception was raised.)

There is in effect a "when others" handler outside of the whole program,
that catches any unhandled exceptions and halts the program with an error
message.  

An exception can be "propagated" by raising it again in a handler.  For
example, in the handler for zork above, we could RAISE ZORK again, which
would cause Ada to look in the calling context and on down for another
handler for ZORK.


  \item What is the difference between:
    \begin{enumerate}
    \item an overloaded function
    \item a generic function
    \item a polymorphic function 
    \end{enumerate}
  Give an example of a language that allows overloaded functions, a language
  a language that allows generic functions, and a language that allows
  polymorphic functions.

*** An overloaded function is one with two or more definitions (chunks of
code) for a function with a given name.  The language (either at compile
time or run time) chooses which definition to use based on the types of the
arguments, and perhaps the type of the result that is expected.  For
example, + in Algol and Pascal is overloaded -- depending on the types of
the arguments, either integer or floating point plus is selected.

A generic function is one with one or more type or value parameters.  It is
essentially a macro.  The parameters must be supplied at compile time, and
the compiler can expand the function body and compile different object code
for the different parameters.  It isn't possible to manipulate a generic
function (with unbound parameters) at runtime.

A polymorphic function is a function with a single definition, whose type
signature includes type variables.  For example, in a statically typed
language we might have a polymorphic "append" function that takes two lists
of some type * as arguments, where the type of the list element is a type
variable.  In contrast to generic functions, polymorphic functions are true
functions, that themselves are legitimate runtime values.

Fortran, Algol, Pascal, and Ada allow overloaded functions.  Ada allows
generic functions.  Miranda allows polymorphic functions.

(The situation is more complicated for object-oriented languages.  However,
I would accept Smalltalk as an example of a language that allows both
overloading and polymorphism.)


  \item Suppose {\tt not} has been defined in Prolog in the usual way, along
  with an additional clause for {\tt squid}:

    \begin{verbatim}
      not(X) :- call(X), !, fail.
      not(X).

      squid(A,A).
    \end{verbatim}

  What answers would Prolog produce for the following queries?  Why?
    \begin{enumerate}
    \item {\tt ?- not(squid(J,K)), J=3, K=5.}
*** no
when not(squid(J,K)) is called, J and K are still variables, so squid(J,K)
succeeds with J=K, not(squid(J,K)) fails, and the whole goal fails.

    \item {\tt ?- J=3, not(squid(J,K)), K=5.}
*** no
when not(squid(J,K)) is called, K is still a variable, so squid(J,K)
succeeds with K=3, not(squid(J,K)) fails, and the whole goal fails.


    \item {\tt ?- J=3, K=5, not(squid(J,K)).}
*** yes
when not(squid(J,K)) is called, J=3 and K=5, so squid(J,K) fails,
not(squid(J,K)) succeeds, and the whole goal succeeds.

    \end{enumerate}


  \item
  Suppose that the following Miranda script has been filed in.

  \begin{verbatim}
      myadd x y = x+y
      mymap f [] = []
      mymap f (a:x) = f a : mymap f x
      crocodile = myadd 5
      alligator x y = y
  \end{verbatim}


  What is the result of evaluating the following Miranda expressions?  (If
  there is a compile-time type error, or a run-time error, or a
  non-terminating computation, say so.)  If the expression is followed by
  {\tt ::}, then give the type, instead of the value.

  \begin{enumerate}
  \item {\tt alligator (1/0) (6/2)}
*** 3.0 
*** (answer of 3 is acceptable instead, of course)

  \item {\tt alligator (6/2) (1/0)}
*** program error: attempt to divide by zero

  \item {\tt myadd ::}
*** num->num->num

  \item {\tt crocodile ::}
*** num->num

  \item {\tt mymap (alligator 5) ::}
*** [*]->[*]

  \end{enumerate}

  \item Suppose the following {\sc Common Lisp} code has been filed in.
  (Recall that {\tt defvar} declares a special variable that is looked up
  using dynamic scope rules; otherwise variables are looked up using lexical
  scoping.)  

    \begin{verbatim}
      (setf fred1 '(a b c))
      (defvar fred2 '(d e f))

      (defun test1 (fred1)
	(aux1 '(x y z)))

      (defun aux1 (m)
	(append fred1 m))

      (defun test2 (fred2)
	(aux2 '(x y z)))

      (defun aux2 (m)
	(append fred2 m))
    \end{verbatim}

  What is the result of evaluating:
    \begin{enumerate}
    \item {\tt (test1 nil)}
*** (A B C X Y Z)

    \item {\tt (test2 nil)}
*** (X Y Z)

    \end{enumerate}


  \item Suppose the following Prolog program has been filed in:
    \begin{verbatim}
      oyster(A,B) :- starfish(A,B).
      oyster(A,B) :- starfish(B,B).
      starfish(M,M).
      starfish(X,3).
    \end{verbatim}

  What are all the answers would Prolog produce for the query \\
  \hspace*{1 cm} {\tt ?- oyster(5,Y).} \\
  Give them in exactly the order that Prolog would.

***
Y = 5 ;
Y = 3 ;
Y = _3023 ;  /* or some other indication that Y is an unbound variable */
Y = 3 ;
no


  \item What is a difference list in Prolog?  Why is it useful?  Compare the
  use of difference lists with using the {\sc Common Lisp}
  {\tt nconc} function.

*** A difference list is represented as the difference between two lists.
For example, if we define the operator \, the following lists all
these all represent the list [1,2,3]:
   [1,2,3]\[]
   [1,2,3,4,5]\[4,5]
   [1,2,3,4,5,6,7,8]\[4,5,6,7,8]
   [1,2,3|M]\M

We often use the last case (where the second list is a logic variable, and
the first list has that logic variable at its tail).  The importance of
difference lists is that the tailing logic variable can be unified with
another list, thus appending the two lists in constant time.  This is
related to the Lisp nonc function, which destructively appends two or more
lists by surgically altering the tail of one list to point to the head of
the next.  However, unlike nonc in Lisp, difference lists are still
declarative, and don't involve destructive assignment.  (Thus they could be
used in pure Prolog, while nonc could not be used in pure Lisp.)  For
example, the list [1,2,3|M]\M will always be the difference list
representation of [1,2,3] no matter what M is unified with.


  \item The CLP($\cal R$) implementation attempts to satisfy constraints, or
  determine that they are unsatisfiable, as soon as possible.  Suppose
  instead that all constraints were simply accumulated, and the system tried
  to solve them after the goal had been completely reduced.

    \begin{enumerate}
    \item What would be the effect on the CLP($\cal R$) semantics if this
	  change was made?  If there is no change, argue why this is the case.
	  If there is a change, give an example of a CLP($\cal R$) program
	  that behaves differently.
*** The semantics would change, since there may be an infinite search path.
If the constraints are satisfied as soon as possible, this path might not
be taken.  For example, the following program gives an answer of "yes" if
constraints are satisfied (or determined to be unsatisfiable) as soon as
possible, but doesn't terminate if they are saved until the goal is
completely reduced.

   squid(X,Y) :- X=Y+3, bottomless(X).
   squid(X,X).
   bottomless(X) :- bottomless(X+1).

?- squid(1,1).
   

    \item What would be the effect on efficiency?  Why?
*** Efficiency suffers dramatically, since trying to satisfy the
constraints early may prune search paths (whether infinite or not); also,
the system can often pass around a single value rather than a set of
constraints (which is more efficient).


    \item Suppose that CLP($\cal R$) used breadth-first search rather than
	  depth-first search.  Would the semantics change if the constraints
	  were solved after the goal had been completely reduced, rather than
	  as soon as possible?  Why or why not?
*** The semantics still changes.  If the constraints are unsatisfiable, but
all the search paths are infinite, the program may say no if the
constraints are processed as soon as possible; and if they are saved, it
wouldn't terminate.  For example, this program exhibits that behavior:
   squid(X,Y) :- X=Y+3, bottomless(X).
   bottomless(X) :- bottomless(X+1).

?- squid(1,1).

    \end{enumerate}


  \item True or false?

    \begin{enumerate}
    \item  In Smalltalk-80, {\tt while} loops are defined using the 
       {\tt whileTrue:} message, which is sent to a boolean.
*** False.  (The message is sent to a BlockContext -- if the message were
sent to a boolean, the truth or falsity of the test would not be updated
each loop iteration.)

    \item In Smalltalk-80, every object is an instance of some class.
       Classes are themselves objects, and each class is an instance of 
       a different metaclass.  Each metaclass is an instance of a different
       meta-metaclass, and so forth.  However, to stop the infinite regress,
       the system only stores 100 levels of meta-meta-meta \ldots metaclasses,
       and creates the remaining levels on demand.
*** False.  Although it's almost that bad.

    \item The name of the Lisp {\tt car} function stands for ``contents of 
       address register''.
*** True.

    \item Variable names in Prolog have scope only within the single fact,
      rule, or goal in which they occur---a variable {\tt X} in one rule is not
      the same as a variable {\tt X} in another.
*** True.

    \item Parameters in Algol-60 are passed either by value or by name.
*** True.

    \item Pure Lisp doesn't include the {\tt setq} function.
*** True.  (Setq corresponds to an assignment statement; pure Lisp is a
functional subset.)

    \item In Prolog the goal {\tt X = 2+3} would unify {\tt X} with the term
	  {\tt 2+3}.  In CLP($\cal R$) it would set up the constraint
	  {\tt X = 2+3}, which would be solved, yielding {\tt X = 5}.
*** True

    \item FORTRAN is not type safe, since (among other things) the {\tt
      EQUIVALENCE} statement allows one to alias an integer variable and a real
      variable. 
*** True

    \item A FORTRAN loop {\tt DO 100 I=1,N} will execute zero times if N=0.
*** False.  Loops in FORTRAN always execute at least once (an old
efficiency hack).

    \item Ada allows parameters to be passed using both positional and
       keyword notation; however, in a given call, the notations can't 
       be mixed.
*** False.


    \end{enumerate}

  \end{enumerate}

  \end{document}