This is a take home final examination, please return a hard copy of your solution no later than 6:00 pm on 08/13/98.
Part I. Imperative Programming Languages (25 points)
A palindrome is a string that reads the same forward and backward.
For a language that provides a pointer type for programmer-constructed data objects and operations such as new and dispose that allocate and free storage for data objects, write a program segment that generates a dangling reference. If one or the other program segment cannot be written, explain why.
Contrast the Ada for loop and the Pascal for loop in respect to the treatment of the loop-control variable. Give one advantage and one disadvantage of the Ada approach.
Part II. Object-Oriented Languages (25 points)
Why do we need null virtual classes in C++? We could just refrain from allocating objects of this class and simply use subclasses of the superclass.
Why is it necessary for Smalltalk to have separate methods for classes and for class instances? Could we eliminate one of these mechanisms and still develop Smalltalk programs effectively?
A chessboard consists of an 8x8 grid of squares, each of which can be empty or can hold a piece. Each piece is colored white or black. Different pieces can move in different ways: for example, a rook can move along either the row or the column it is on, whereas a bishop can move along either of the two diagonals through the square it is on. Rooks and bishops cannot move through other pieces; they must stop on the square before a piece of the same color or on the same square as a piece of the opposite color (in which case the opposing piece is captured and removed from the board). Define a tagged type to represent a chess piece with a primitive operation which takes a chessboard and a position on the board as its parameters and returns a linked list of board positions that the piece can move to, then derive types from this to represent rooks and bishops. Write a program, which will read the positions of a set of rooks and bishops on a chessboard and generate a list of all legal moves for each piece.
Part III. Functional Programming Languages (25 points)
The equivalence of program and data representations in LISP makes it possible to write many subtle programs easily that would be much more difficult in other languages. Some of these have the status of classical LISP problems, of which the self-reproducing function problem is typical: Write a LISP function SRF whose value is its own definition. SRF has no inputs. If SRF is defined as:
(defun SRF ( ) body)
then the result of the call (SRF) is the list structure (defun SRF ( ) body). SRF must construct its result list piecemeal. It cannot access the property list of the atom SRF to obtain its definition list.
Consider the following ML program:
datatype digit = zero | one | two | three | four | five
| six | seven | eight | nine;
datatype number = sdigit of digit | node of number * number;
fun digitv(one) = 1 | digitv(two) = 2 | digitv(three) = 3
| digitv(four) = 4 | digitv(five) = 5 | digitv(six) = 6
| digitv(seven) = 7 | digitv(eight) = 8 | digitv(nine) = 9
| digitv(zero) = 0;
fun value(node(x,y)) = 10 * value(x) + value(y)
| value(sdigit(x)) = digitv(x);
b. Draw the data structure for each expression given in (a).
Part IV. Logic Programming Languages (25 points)
A. Prolog Rules (10 points)
Prolog rules can be viewed as logical predicates. The rule a: - b, c will cause a to succeed if b and c both succeed. So we can say a is true if the condition b Ù c is true.
(1) x :- p,q.
x :- r,s.
x :- r,s.
x :- r,!,s.
B. Airline Reservation Database (15 points)
The goal for Prolog was to give the specifications of a solution and allow the computer to derive the execution sequence for that solution, rather than specifying an algorithm for the solution of a problem, such as is the normal case with most languages we have studied in the course. For example, if you have an airline flight information of the form:
flight(flight_number, from_city, to_city, departure_time, arrival_time)
Then all flights from Los Angeles to Baltimore can be specified as either direct flights:
flight(flight_number, Los Angeles, Baltimore, departure_time, arrival_time)
Or as flights with an intermediate stop, specified as:
flight(flight1, Los Angeles, X, depart1, arrive1),
flight(flight2, X, Baltimore, depart2, arrive2),
depart2 >= arrive1 + 30
Indicating that you are specifying a city X, which has a flight arriving from Los Angeles, has a flight leaving for Baltimore, and the Baltimore-bound flight leaves at least 30 minutes after the Los Angeles flight arrives to allow time to change planes.
Implement a Prolog database to answer queries about airline reservations, such as given in the above. Include the following functions:
Part V. Concurrent Computations (extra credit, 15 points)
When semaphores are used to implement mutual exclusion, it is possible to associate a semaphore SR with each resource R. Each access to R can then be written as
What should the initial value of SR be?
Some computers provide an indivisible machine instruction test and set (TS) that can be used for synchronization purposes. Let X and Y be two boolean variables. The execution of the instruction TS(X, Y) copies the values of Y into X and sets Y to false. A set of concurrent processes that must execute some instructions in mutual exclusion can use a global boolean variable PERMIT, initialized to true, and a local boolean variable X in the following way:
repeat TS(X, PERMIT)
instructions to be executed in mutual exclusion;
PERMIT := true