CSE 505 - Sample Solution - Final Exam - Autumn 1993


1a.  type error in expression (i.e. compile time error)
1b.  [num]->[tree num]
1c.  [*]->tree [*]->[*]
1d.  tree [*]->[*]
1e.  40


2.  In Algol-60, arguments are passed by name or by value.  The default is
call-by-name.  Semantically, call-by-name is defined as making a copy of
the actual argument and substituting it for each occurence of the formal
parameter (changing variable names if needed to prevent clashes).  In a
typical implementation, the argument is passed by defining a thunk -- an
anonymous function that is called each time the argument's value is needed.
Call-by-name thus results in evaluting the argument on each use.  If it is
never used, it is never evaluated.  If the actual argument is a variable or
array element, it is also possible to assign into the formal parameter,
which results in assigning into the corresponding actual.  Call-by-value
involves evaluating the argument before entering the procedure or function,
and copying its value into the formal parameter.  It is not copied back.
Call-by-value always evaluates the argument exactly once.

In Miranda, semantically arguments are passed using lazy evaluation.  If
the argument is never used, it is never evaluated.  If it is used once, the
expression is evaluated, and the result saved.  This saved result is then
used if the value is needed subsequently.  Semantically, lazy evaluation
for a functional language is equivalent to call-by-name; it's just more
efficient.  Since this is a functional language, there is no notion of
assigning to variables, and hence assigning into a formal parameter and
copying the value back is not meaningful.

Prolog uses unification (two-way pattern matching) for argument passing.
In Prolog, actual and formal arguments may be atoms, logic variables, or
terms.  Corresponding actuals and formals are unified.  If both the actual
and the formal are atoms, they must be equal.  If one is a variable and the
other not a variable, the non-variable is substituted everywhere for the
variable.  If they are both variables, any subsequent unifications to one
variable or the other will affect both.  Otherwise they must be structures.
In this case, the functors must match, and the corresponding components are
unified recursively.

CLP(R) is an instance of the Constraint Logic Programming scheme for real
numbers.  In CLP(R), the corresponding actual and formal parameters are
constrained to be equal.  If these are of type real number, then this
corresponds to adding an equality constraint to CLP(R)'s solver; if they
are elements of the Herbrand Universe, then these equality constraints
amount to the same thing as unifying the actual and formal parameters (as
in Prolog).  (As an aside, pure Prolog is an instance of the CLP scheme,
where the domain is just the Herbrand Universe.)

Strand is a commited-choice logic programming language.  Strand uses a
restricted version of Prolog's matching, in which unification is replaced
by one-way pattern matching.  An atom in the goal can match an atom or
variable in the rule, but not vice versa.  If there is an attempt to match
a variable in a goal with an atom in a rule, then that process reduction
blocks until the variable is instantiated.


3.  In Miranda, there can be multiple definitions of a function.  The
correct definition is chosen by pattern matching, where the patterns are
built up using constructors.  These include tuples, lists, and user-defined
alebraic types.  In addition, one can write patterns of the form (p+k),
where k is a natural number; this matches integers greater than or equal to
k.  For example, the following definitions of map use pattern matching,
selecting the first or second definition depending on whether the second
argument is an empty list or a non-empty list:
  map f [] = []
  map f (a:x) = f a : map f x
This definition of factorial uses the (p+k) form of pattern matching:
  factorial 0     = 1
  factorial (k+1) = (k+1) * factorial k
The different possibilities are tried, top to bottom.  The first one that
matches is selected.

In CLP(R), there can be multiple versions of a rule.  A given goal
p(X1,...Xn) matches rules whose heads are of the form p(Y1,...Yn).  If Xi
unifies with Yi, or if they can be constrained to be equal, then that rule
can be selected.  CLP(R) chooses the first rule that matches to try.  The
subgoals and constraints are then attempted.  If there is a failure,
the next rule that matches is selected instead.  Backtracking is depth-first.

Strand is similar to CLP(R), in that there can be multiple versions of a
rule.  One-way pattern matching is used; if the match succeeds, the rule
can be used.  In addition to matching the head of the rule with the goal,
the rule may have guards, selected from a fixed set of predicates.  These
guards must all be satisfied for the rule to be selected.  As described in
the answer to question 2, sometimes the process (representing a goal) will
suspend if not enough information is known to select one.  If several rules
match, the language implementation can choose any one of them.


4.  CLP(R) returns the answer maybe when there are still constraints on the
variables in the answer, and when CLP(R)'s solver cannot determine whether
or not they are satisfiable.  (These will be non-linear constraints; it can
always determine whether linear constraints are satisfiable.  For example,
CLP(R) will return a maybe answer to the goal
   X*X=2.


5.  Both inner and super address the problem of combining information from
a method defined in one class and a method of the same name in a subclass.
(In Beta, these would be called a pattern used as a procedure or function
attribute, and a subpattern, respectively; but for simplicity, I'll just
call these methods and classes here.)  In Beta, a method in a superclass
can include the keyword "inner".  The superclass method gets control first,
then inserts the code from its subclass at the point of the inner.  This
subclass code can in turn have an inner, which causes its subclass's code
to be inserted, and so forth.  Thus, the method at the top of the
inheritance hierarchy gets control first.  In Smalltalk, the method in the
class of the receiver of the method is executed, or if none is present, the
method found by searching starting at the bottom of the hierarchy.  This
method can send a message to super, meaning that the lookup is to start in
the superclass of the class in which the current method is found.  Thus, in
Smalltalk the method at the bottom of the hierarchy gets control first.


6.  In Strand, one can represent an object as a process that consumes a
stream of messages.  The stream is represented as a list of messages,
produced by some other processes.  If P1 and P2 shared the same list, then
they would each be trying to bind a given variable in the list to two
different messages.  Instead, it is necessary to give each of P1 and P2
their own lists, and merge them.  


7.  a, c


8a.  N=4

8b.  N=3, X=[]
     N=4, X=[_1]
     N=5, X=[_1,_2]
     N=6, X=[_1,_2,_3]
     etc for an infinite number of answers

8c.  L=[], N=0
     L=[_1], N=1
     L=[_1,_2], N=2
     L=[_1,_2,_3], N=3
     after producing this answer, if another answer is requested CLP(R)
        goes into an infinite search, not returning any more answers

8d.  L=[], N=0
     L=[_1], N=1
     L=[_1,_2], N=2
     L=[_1,_2,_3], N=3
 
In this case, CLP(R) just says no if an additional answer is requested.

8e.  L=[_1,_2,_3]


9.  In Strand, goals represent processes.  A rule describes how a process
can be terminated, reduced to another process, or replaced by multiple new
processes.  For example, the rule
   foo(3).
asserts that any process matching foo(3) can be terminated.

The rule

append([X|Xs],Ys,Zs) :- 
   append(Xs,Ys,Zzzzs),
    Zs := [X|Zzzzs].

asserts that the append process can be replaced by the new append process
on the tail of the first list.

The quicksort rule below:

quicksort([X|Xs],Sorted) :-
  partition(X,Xs,Smalls,Bigs),
  quicksort(Smalls,SortedSmalls),
  quicksort(Bigs,SortedBigs),
  append(SortedSmalls,[X|SortedBigs],Sorted).

asserts that a process matching the rule head can be replaced by 4
subprocesses, which communicate by shared logic variables.


10a.  false (the multi-methods are selected based on the concrete types,
      not the abstract types)
10b.  true
10d.  true
10d.  true
10e.  true