Computer Science & Engineering 505 -- Final -- Answer Key
December 14, 1992 


1. (30 points)  Briefly define the following words or phrases:

 (a) COMMON block

A COMMON block is a block of storage that can be shared among several
subroutines (and the main program) in FORTRAN.  [This is all you need for a
correct answer.]  If a subroutine (or the main program) includes a COMMON
declaration, those variables will be allocated in an area of memory shared
by other subroutines that have a COMMON declaration.  COMMON blocks can
also be named; each named block has a separate area in memory.

 (b) fully bracketed syntax

In a language with fully bracketed syntax, each compound statement includes
a matching "end" that delimits the scope of included statements.  For
example:
  if a=3 then
    ...
    ...
    end if;

Ada uses fully bracketed syntax.  Algol-60 doesn't; in Algol-60 the
programmer must add a begin-end pair after the "if" statement if more than
one statement follows it.


 (c) raise an exception

To raise an exception means to signal that some exceptional event (such as
an arithmetic error, bounds check, or the like) has occurred.  The
exception must then be *handled* by an exception handler.


 (d) propagate an exception

To propagate an exception means to raise the exception again in a handler;
some other handler would then need to be invoked.

 (e) metaclass

In Smalltalk-80, every object is an instance of some class; the object's
class defines the messages that the object can understand.  To allow
classes to define individual methods, and as a place to hang shared
constants and the like, every class is an instance of a separate metaclass.
CLOS has a similar mechanism.


 (f) rendezvous

In Ada, a rendezvous is the normal interprocess communication mechanism.  A
task T1 task invokes another task T2, using one of T2's entry points.  T1
blocks while T2 is executing the code in its ACCEPT statements (i.e. while
the tasks are rendezvousing).  Thereafter the two tasks can proceed
asynchronously. 


 (g) thunk

A thunk is an anonymous function, used to implement call-by-name
expressions.  Whenever the value of the parameter is needed, the thunk is
evaluated. 


 (h) static link

A static link is a pointer from a stack frame to the stack frame for the
lexically enclosing procedure or block.  It is used in implementing lexical
scoping.


 (i) dynamic link

A dynamic link is a pointer from a stack frame to the stack frame of the
calling procedure or other program unit.  It will become the current stack
frame when the currently executing unit exits.


 (j) super (in Smalltalk-80)

"super" is a pseudovariable in Smalltalk-80.  It is like "self" (the object
that is running the current method), except that when you send a message to
super, the method lookup starts in the superclass of the class that holds
the method being executed.


2. (5 points)
What is the difference between single dispatching and multiple dispatching
in object-oriented languages?  What are the advantages and disadvantages of
each technique?

In a single dispatch language, only the receiver of the message is used to
determine which method is invoked.  In a multiple dispatch language,
potentially all of the arguments to the message are used.  Advantages of
single dispatching are that it is simpler, more clearly object-oriented,
and also lends itself better to distributed systems.  Advantages of
multiple dispatch are that it allows programs to be better structured when
more than one argument is important in deciding which method to run.


3. (10 points) What is the difference between overloading, (universal)
polymorphism, and generics?


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.


4. (30 points) Suppose that the following Miranda script has been filed in.

    my_map2 f [] [] = []
    my_map2 f (a:as) (b:bs) = f a b : my_map2 f as bs
    rev f x y = f y x
    alligator x y = 3+y

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
::, then give the type, instead of the value.

 (a)   alligator (1/0) (6/2)

6.0


 (b)   alligator (6/2) (1/0)

program error: attempt to divide by zero


 (c)   alligator ::

*->num->num


 (d)   my_map2 alligator [1..] [10..]

[13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28, ...


 (e)   my_map2 ::

(*->**->***)->[*]->[**]->[***] 


 (f)   my_map2 alligator  ::

[*]->[num]->[num] 


 (g)   my_map2 (rev alligator)  ::

[num]->[*]->[num]


 (h)   (rev alligator) 10 20

13

 (i)   rev  ::

(*->**->***)->**->*->***


 (j)   rev my_map2::

[*]->(*->**->***)->[**]->[***]


5. (10 points)  Miranda uses lazy evaluation for parameter passing.  
Suppose that programmers could optionally annotate parameters as either
call-by-name or call-by-value instead.

 (a) Are there any functions for which changing the parameter to
  call-by-name would change the semantics of the function?  If so, give an
  example; if not, explain why not.  Are there any functions for which this
  change would have no effect?  Again, if so, give an example; if not,
  explain why not.  What would be the effect on 
  performance of replacing lazy evaluation with call-by-name for a given
  function?  

No, replacing lazy evaluation by call-by-name would not change the
semantics.  In lazy evaluation, the parameter is evaluated the first time
its value is needed; the value is then cached and returned if the paramter
is used again.  In call-by-name, the parameter is re-evaluated each time it
is used.  However, in a functional lanuage re-evaluating the same
expression will always give the same answer.  If evaluating the parameter
would give an error, the error would arise in either case.
If the parameter is used more than once, call-by-name would be less efficient.


 (b) Are there any functions for which changing the parameter to
  call-by-value would change the semantics of the function?  If so, give an
  example; if not, explain why not.  Are there any functions for which this
  change would have no effect?  Again, if so, give an example; if not,
  explain why not.

Yes.  If the function doesn't use the value of the parameter, and
evaluating that parameter would give an error or a non-terminating
computation, then call-by-value would give an error for evaluating the
function, whereas lazy evaluation would not.  For example, if 
  f x = 3
and we evaluate 
  f (1/0)
lazy evaluation would return 3, while call-by-value would give an error.

If the function always needs the value of the parameter, then it would be
safe to replace lazy evaluation by call-by value.  For example, in this
function:
  f x = x+2
it would be safe to make this replacement.


6.  (10 points) Here is the standard definition for append in Prolog:

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

Give all the answers that would be produced for the following goals
(backtracking as needed to produce more answers).  If there are an infinite
number of answers, give the first three or so.

 (a)   ?- append(A,B,[1,2,3]).

A = [], B = [1,2,3]
A = [1], B = [2,3]
A = [1,2], B = [3]
A = [1,2,3], B = []


 (b)   ?- append([1,2,3],B,C).

B = _88
C = [1,2,3|_88]

(Here _88 is an internal name for a variable.  An answer to this question
such as C = [1,2,3|B] would be ok too.)


 (c)   ?- append(A,[7,8,9],C).

A = [], C = [7,8,9]
A = [_89], C = [_89,7,8,9]
A = [_90,_91], C = [_90,_91,7,8,9]
A = [_92,_93,_94], C = [_92,_93,_94,7,8,9]
...
(there are an infinite number of answers)

7. (10 points)  Now suppose we include a cut in the definition:
   append_cut([],Ys,Ys) :- !.
   append_cut([X|Xs],Ys,[X|Zs]) :- append_cut(Xs,Ys,Zs).

Give all the answers that would be produced for similar goals:

 (a)   ?- append_cut(A,B,[1,2,3]).

A = [], B = [1,2,3]


 (b)   ?- append_cut([1,2,3],B,C).

B = _88
C = [1,2,3|_88]


 (c)   ?- append_cut(A,[7,8,9],C).

A = [], C = [7,8,9]


8. (5 points) What is a difference list?  Why is it useful?  Give several
difference list representations of the list [1,2,3], including the
most general possible one.

A difference list is a representation of a list as the difference of two
lists.  It is useful because we can use a variable as the second list
during a computation, and later unify it with some other list, so that two
lists can be appended in constant time, without needing to copy the first.
Here are several difference list representations of [1,2,3]:

[1,2,3]\[]
[1,2,3,8]\[8]
[1,2,3,10,12]\[10,12]

The most general is:
[1,2,3|	A]\[A]


9.  (10 points) 
Compare argument passing in standard Prolog, in Flat Concurrent
Prolog, and in Strand.  Give examples that illustrate differences.

In standard Prolog, arguments are passed using unification (two-way pattern
matching, including logical variables).  In Flat Concurrent Prolog,
arguments are also passed using unification; however variables in some
arguments may be annotated as read-only.  A read-only variable that is
currently uninstantiated may not be unified with a non-variable.  In
Strand, unification is replaced by one-way pattern matching.  In this case,
a variable in a goal may not be unified with a non-variable in the rule
head.


10. (5 points) Briefly compare the mechanism for process synchronization 
in Concurrent Prolog and in Strand.

In both Concurrent Prolog and Strand, there is a process reading of a logic
program in addition to a declarative one.  Each goal represents a process.
Processes communicate and are synchronized via shared logic variables.  In
Concurrent Prolog, this is controlled using read-only annotations on some
variables in goals.  If the system attempts to unify a term with a variable
annotated as read-only, the process attempting the unification will block
until the variable becomes instantiated.  In Strand, unfication is replaced
by one-way pattern matching.  If the system attempts to unify a variable in
a goal with a non-variable in a rule head, again the process attempting the
reduction will block until the variable is instantiated.  Another mechanism
for process synchronization, used in both Concurrent Prolog and Strand, is
that guards on a rule may test arguments.  If not enough information is
available to determine the truth or falsity of the guard, that rule for
reducing the process may not be used; if none of the rules are applicable,
that process reduction would block.

[Since the question said the answer should be brief, you don't need to be
as detailed as this.]