Final: Sample Questions

This page includes questions by the instructor (John Boyland) that may appear on the final.

The material on the exam will mainly come from Chapters 15-24 of the textbook, and Chapters 1-5 of SBE, but you should be ready to answer questions from anywhere in the books. Consult the midterm study help. You should be ready to do any of the exercises from the book that do not require research. At least one of the exam questions will be an exercise from the book.

Conceptual Terms

You should be able to define and explain the following concepts:

• inheritance, interfaces, multiple inheritance, generic classes
• objects, classes, prototypes, encapsulation, polymorphism
• meta-class, shared instance variables
• throwing and catching exceptions in Java, checked vs. unchecked exceptions
• abrupt termination in Java, finally
• parameter correspondence: by position, by keyword, optional parameters
• parameter passing: by value, by result, by value-result (copy-in, copy-out), early and late lvalue determination, by reference, by macro expansion, by name.
• terms, atoms, predicates, facts and rules.
• lists in Prolog: append, member, reverse
• flexible (``invertible'') predicates vs. inflexible
• negation and failure
• unification, occurs check, resolution, solve, proof trees
• cost models for lists, function calls, tail calls
• numeric evaluation in Prolog, instantiation, optimizing searches
• natural semantics (``big-step'' semantics), operational semantics (``small-step'' semantics), errors in semantics
• substitution
• denotational and axiomatic semantics, loop invariants, specification errors

Programming

Squeak

The interface Dictionary has the following methods (among others):

  size
  at:
  at:put:
  do:

Prolog

• Write an invertible predicate mingle/3 such that the third argument list is an interleaving of the first two argument lists. For example:

  mingle([a,b,c],[d,e,f],[a,b,d,e,c,f])
  

• A clique is a subgraph of an undirected graph such that every node is connected to every other node in the clique. It is a known difficult problem to determine whether a clique of a particular size exists in a graph. Prolog permits an easy definition of a brute-force solution technique.

  1. Given a predicate connected/2 that is true of two nodes (Prolog terms---usually atoms) are connected, write a predicate clique/1 that is true for a list of nodes where each element is connected to all the others. You must not assume that connected is symmetric. (You should not assume that if someone writes connected(a,b) that they also write connected(b,a) even though b and a are indeed connected, since this is an undirected graph.) You will want to define one or two helper predicates; explain them.
  2. Use this predicate to write another predicate clique/2 that unifies the first parameter with a clique whose length is specified by the second parameter (or fails if there is no such clique).
  3. Write a predicate maxClique/2 that unifies the first parameter with a clique of the length of the second parameter, but if no such clique can be found (use not), try with the next smaller number, etc. In other words, the first parameter is unified with a clique of maximum length up to (and including) the second parameter. This predicate may require the second parameter to be fully instantiated.

Language Concepts in Practice

Parameter Passing

(Questions on what the result of a program is using various parameter passing modes.)

Abstract and default methods

In Homework #8, you wrote an abstract class AbstractIntSet that had among its methods, one named ``find'' and an abstract method ``iterator''

1. What does it mean to be an abstract class?
2. Why do we have abstract classes?
3. Why do abstract classes provide implementations (such as for find)?
4. TreeIntSet inherits from AbstractIntSet and overrides find? Why does it inherit? Why does it override?
5. LinkedIntSet inherits from AbstractIntSet but does not override find. Why not?
6. Suppose we wrote a new implement of the IntSet interface that uses a sorted array of elements that grows as needed (using either an array or a java.util.ArrayList).
   1. Should it inherit from AbstractIntSet? Why or why not?
   2. Should it override find? Why or why not?
   3. Should it override toString? Why or why not?
   4. Why can't we inherit the add method from some other class?

Resolution and Unification

The basic engine in Prolog consists of solve, resolution and unify. Give the algorithm for the first two.

Answer:

solve (goals) =
  if goals is empty then succeed()
  else 
    for each rule R
      solve(resolution(rename(R),goals))
    repeat on failure

resolution (head:conditions,first:rest)
  (unify (head,first))(conditions ++ rest)

optional:
succeed() =
  if user presses return then Done
  else if user presses ';' fail()

Suppose we have the following rules:

parent(sandy,chris).
parent(pat,aidan).
parent(pat,sandy).
grandparent(X,Z) :- parent(X,Y), parent(Y,Z)

solve([grandparent(A,B)])

Answer the following questions:

1. Why does solve succeed when given an empty list of goals? What is the intuition?
2. Why does solve rename the variables in the rule before passing it to resolution?
3. Why does solve not rename the variables in the goals before passing it to resolution?
4. Why does resolution only unify the head of the rule, not the whole thing?
5. What happens in resolution when unify fails?
6. Why do we apply the unifier to the rest of the rule and goal list?
7. Why do we remove the first goal if unification succeeds?
8. Why do we add the tail of the rule to the goal list?

More on Resolution and solving

1. Give the results of the following calls to unify:
   1. unify(flattenH(leaf(X1),L1,[X1|L1]),flattenH(T,[],[1,2,3]))
   2. unify(flattenH(branch(V2,W2),L2,N2),flattenH(T,[],[1,2,3]))
   3. unify(flattenH(leaf(X3),L3,[X3|L3]),flattenH(W2,[],M2))
2. Using the previous calls, give the results of the following calls to resolution:
   1. resolution([flattenH(leaf(X1),L1,[X1|L1])], [flattenH(T,[],[1,2,3])])

   2. resolution([flattenH(branch(V2,W2),L2,N2),
                  flattenH(W2,L2,M2),
                  flattenH(V2,M2,N2)],
                 [flattenH(T,[],[1,2,3])])
      

   3. resolution([flattenH(leaf(X3),L3,[X3|L3])],
                 [flattenH(W2,[],M2), flattenH(V2,M2,[1,2,3])])
      

3. Using the previous steps to give the whole proof tree trace up to the first success for the following call. Please trace every call to solve, resolution and unify, even ones that fail.

   solve([flattenH(T,[],[1,2,3])])

   Assume the program consists of only the following rules:

   flattenH(leaf(X),L,[X|L]).
   flattenH(branch(V,W),L,N) :- flattenH(W,L,M), flattenH(V,M,N).
   

4. After this first success, the proof tree goes on forever without any more success. (Try it in Prolog!) Why?

Semantics

• What is the distinction between smal-step and large-step semantics?
• There are two ways to handle variables: using an explicit environment (as done in the textbook) and using substitution (as in the homework). Explain how this affects the definition.
• Which one can more easily handle updateable parameters? Explain!
• Define a big-step semantics (using prolog or natural semantics notation) for a language with integer literals, addition, and local (immutable) variables with substitution.
• If one has function values and application, then ``let''; can be syntactic sugar in that \verb|let(X,E1,E2)| can be expressed using application. Explain how.
• For what kinds of language features does denotational semantics need fixed points? (In the homework, we avoided fixed points; why was our solution not acceptable as a real denotational semantics?)

Language History

Draw a family tree/diagram showing the major influences on Java; name the important “ancestors” of Java.