Final: Sample Questions (v0.9)

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

The material on the exam will come from Chapters 15-24 of the textbook. 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
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
environments, closures, substitution
lazy evaluation, unit (AKA ()), list comprehensions, infinite structures
type classes, instances, constrained polymorphism
IO monads: actions, performing, ``bind'' (AKA >>=)

Programming

Java

The interface Dictionary has the following methods:

  int size();
  boolean isEmpty();
  Enumeration keys();
  Object get(Object key);
  Object put(Object key,Object value); // returns previous value (or null)

and the Enumeration interface has:

    boolean hasMoreElements();
    Object nextElement();

Implement a class LinkedDictionary which implements this interface correctly using a linked list of key-value pairs. This may seem inefficient, but it is a well-known solution called an ``association list'' and is practical when the lists stay short.

Prolog

Suppose we represent a maze by a collection of facts such as:

door(a,b).
door(b,c).
door(c,d).
door(d,e).
door(d,a).

Assume you can go either direction through a door.

Write a predicate connected(X) that is true for any room X that has a door.
Write a predicate path(X,Y,L) that is true of a list L if it represents a legal path from room X to room Y. (The fact that you can go either direction through a door makes this different from the lecture in week 11.) It is not required for path(X,Y,L) to unify L with all such paths if L is unbound. As in lecture, it may get caught making bigger and bigger paths going around cycles.
Write a predicate path(X,Y,N,L) that unifies L with all paths of length =<N. It may assume that X,Y,N are all instantiated when the call is made, but cannot assume L is bound to anything.
Write another routine shortest_path(X,Y,L) that unifies L with any shortest path from X to Y. There may be many such paths, or none at all. You may assume that any such path will have length =< the number of ``connected'' rooms; this can be proved easily in graph theory.

Haskell

Write ``merge sort'' in Haskell. (Don't count the length of the list to divide it in two---just assign alternate elements to the two sublists that will be recursively sorted.) What constraint will its type have?

Suppose I write the following function to find the minimum element of a list:

minlist l = head (mergesort l)

If we wrote the function in this way in ML (using ML syntax), it would be (asymptotically) inefficient. Why? Is it inefficient in Haskell? Why or why not?

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''

What does it mean to be an abstract class?
Why do we have abstract classes?
Why do abstract classes provide implementations (such as for find)?
TreeIntSet inherits from AbstractIntSet and overrides find? Why does it inherit? Why does it override?
LinkedIntSet inherits from AbstractIntSet but does not override find. Why not?
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)

Show what happens when we run:

solve([grandparent(A,B)])

Answer the following questions:

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

Lazy Evaluation

(Questions such as the ``Lazy Evaluation'' section of Homework #13

IO without side-efffects

ML is a functional function like Haskell and has functions such as

print : string -> unit
(;) : unit -> 'a -> 'a

so one can write:

fun inc n = (print "In inc"; n+1)

(Notice the use of ``;'' as an infix operator.) Suppose that Haskell provided such functions as predefined:

printString :: String -> ()

(;) :: () -> a -> a
(;) () y = y

and then one could write:

inc n = (printString "In inc"; n+1)

which is the same as:

inc n = (;)(printString "In inc")(n+1)

Why wouldn't this work in Haskell? (Hint: it's something to do with laziness.) Explain!

In a lazy language such as Haskell, one can give the type of an interactive program as

program :: [Char] -> [Char]

where the program takes the entire list of input and returns the entire output. Although one can write a function such as this in ML, it couldn't be interactive in ML; it wouldn't be able to prompt for input and generate output that depends on the input. Why not? (Hint: it's something to do with call-by-value.) Explain!

The Haskell I/O system is defined using ``monads'' or actions of type IO T where T is any type. In addition there are two functions that operate on these monads:

return :: a -> IO a
(<<=) :: IO a -> (a -> IO b) -> IO b

Answer the following questions:

Why is this more powerful than accepting a list of charactrs and returning a list of characters? (Hint: think about opening files.)
What is the meaning of an element of such type?
What is the return operation good for? Give an example.
Why doesn't <<= have the much simpler type:
```
(<<=) :: IO a -> IO b -> IO b
```
Why doesn't it have the simpler type?
```
(<<=) :: IO a -> (a -> b) -> IO b
```
If we have a function f of type Int -> Int, we know it cannot engage in any I/O or side-effects. How is that, since it could have a let body such as:
```
f n = let
        a1 = printStr "hello"
      in
        ...
```
(Recall that printStr has type String -> IO ().)