Programming Languages

G22_2110_001

Summer 98

 

Final Examination

08/06/98

 

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)

  1. Language Translation Issues (10 points)

A palindrome is a string that reads the same forward and backward.

  1. Show that the set of odd-length palindromes over the alphabet {a, b} is a context-free language.
  2. Show that the set of odd-length strings over the alphabet {a, b} that are not palindromes is context-free.
  3. Why does the set of odd-length palindromes require a non-deterministic pushdown automaton for recognition rather than a deterministic pushdown automaton?

  1. Data Types (10 points)
  2. 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.

  3. Language Statements (5 points)

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)

  1. Virtual Classes in C++ (5 points)
  2. 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.

  3. Smalltalk Methods (5 points)
  4. 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?

  5. Polymorphism and Dispatching in Ada 95 (15 points)

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)

  1. The Self-Reproducing Function (10 points)
  2. 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.

  3. ML Programming (15 points)

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);

    1. Trace the execution of each of the following. What value is printed for each?

value(sdigit(seven))

value(node(sdigit(nine), sdigit(three)))

value(node(sdigit(three),node(sdigit(one),sdigit(four))))

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. Under what conditions for p, q, r, and s are the following Prolog rules satisfied:

(1) x :- p,q.

x :- r,s.

    1. x :- p,!,q.
    2. x :- r,s.

    3. x :- p,q.

x :- r,!,s.

  1. Repeat question (a) if we add the rule x :- fail after the two given rules. What if we add this rule first in the database?

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:

  1. connecting(source, destination, intermediate), which determines if it is possible to go from source to destination by passing through intermediate on direct flights.
  2. arrival_time(source, departure_time, destination), which prints the arrival time at destination of a flight (or connecting flight) that departs from the source city on or after the departure_time.
  3. itinerary(source, destination, departure_time), prints the flight numbers and destination arrival times of all flights from source to destination that leave within 60 minutes of departure_time.

Part V. Concurrent Computations (extra credit, 15 points)

  1. Semaphores (5 points)
  2. 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

    P(SR);

    access R;

    V(SR)

    What should the initial value of SR be?

  3. Synchronization (10 points)

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)

until X;

instructions to be executed in mutual exclusion;

PERMIT := true

  1. In this case, processes do not suspend themselves; they are always executing (this is called busy waiting). Compare this solution to one based on semaphores in which P and V are implemented by the kernel.
  2. Describe how to implement P and V on semaphores by using the test-and-set primitive in a busy wait scheme.