CS 3304 Solutions to Final Exam

3304
Solutions to Final Exam
August 9, 1997

[75] 1.

Consider carefully the following C program:

#include <stdio.h>                                      /* LINE 1 */
                                                        /* LINE 2 */
/* number of times strange called */                    /* LINE 3 */
static int called = 0;                                  /* LINE 4 */
                                                        /* LINE 5 */
int strange (int n) {                                   /* LINE 6 */
    static int called = 0;                              /* LINE 7 */
    int x;                                              /* LINE 8 */
                                                        /* LINE 9 */
    called++;                                           /* LINE 10 */
    x = n-2;                                            /* LINE 11 */
    if (x <= 1)                                         /* LINE 12 */
        return 1;                                       /* LINE 13 */
    else                                                /* LINE 14 */
        return x*strange(x-1);                          /* LINE 15 */
}                                                       /* LINE 16 */
                                                        /* LINE 17 */
void main () {                                          /* LINE 18 */
    int x;                                              /* LINE 19 */
                                                        /* LINE 20 */
    for (x=1;x<7;x++)                                   /* LINE 21 */
        printf("strange(%d)=%d\n",x,strange(x));        /* LINE 22 */
    printf("strange called %d times\n",called);         /* LINE 23 */
}                                                       /* LINE 24 */

Assume normal compile-link-execute processing of this program. Do the following for this program.
Fill in the table in Figure 1 with the requested binding times. Be as specific as possible. Use the line numbers in the program when appropriate.

Figure 1: Table of Binding Times

What is the output of this C program?

See binding times in Figure 1.

Here is the output:

strange(1)=1
strange(2)=1
strange(3)=1
strange(4)=2
strange(5)=3
strange(6)=4
strange called 0 times

[75] 2.

You are to add Dijkstra's guarded commands to C, Pascal, or ALGOL (your choice). You are to make the syntax compatible with the existing language and ``in the same style.'' Do the following:

Give your syntax for the selection and loop structures in BNF or EBNF. You may assume that the rules for standard nonterminals such as

and

are defined elsewhere.

Express the following sorting routine using the syntax you developed.
do q1 > q2 -> temp := q1; q1 := q2; q2 := temp; [] q2 > q3 -> temp := q2; q2 := q3; q3 := temp; [] q3 > q4 -> temp := q3; q3 := q4; q4 := temp; od

Give operational semantics for the code in item 2. Assume the existence of a nondeterministic goto
gotoany label1, label2, ..., labeln
that nondeterministically transfers control to one of the labels in the list.

Here is a solution for C.

We need to represent the if and do constructs of section 7.6 in C-like syntax. We add new keywords guardedif and guardeddo to distinguish these constructs from other C control structures. Here is the EBNF for these two constructs:

The punctuation in quotes (") must appear literally as given.

Here is the sorting routine using a guardeddo construct.

guardeddo {
  (q1 > q2) {
    temp = q1; q1 = q2; q2 = temp;
    }
  (q2 > q3) {
    temp = q2; q2 = q3; q3 = temp;
    }
  (q3 > q4) {
    temp = q3; q3 = q4; q4 = temp;
    }
}

An operational semantics for the above code is:

loop_top:
  if q1>q2 goto first_true
  if q2>q3 goto false_true
  if q3>q4 goto third_block
  goto loop_exit
first_true:
  if q2>q3 goto true_true
  if q3>q4 gotoany first_block third_block
  goto first_block
false_true:
  if q3>q4 gotoany second_block third_block
  goto second_block
true_true:
  if q3>q4 gotoany first_block second_block third_block
  goto first_block second_block
first_block:
  temp := q1
  q1 := q2
  q2 := temp
  goto loop_top
second_block:
  temp := q2
  q2 := q3
  q3 := temp
  goto loop_top
third_block:
  temp := q3
  q3 := q4
  q4 := temp
  goto loop_top
loop_exit:

[75] 3.

This problem is about Ada tasks and the possibility of deadlocks. Assume that each of the tasks in question is in an infinite loop in which it will periodically accept any of its entries. Do the following.

Define deadlock for a collection of two or more Ada tasks.
Here are the specifications for four Ada tasks:
task task1 is entry get; entry put; end task1; task task2 is entry new; entry old; end task2; task task3 is end task3; task task4 is entry win; entry lose; end task4;
Assume that task1 invokes only task2.new and task4.lose. Assume that task2 invokes no entries in the other tasks. Assume that task3 invokes only task1.get, task1.put, task2.old, and task4.win. Assume that task4 invokes only task2.new.
Can these tasks deadlock? Explain.
Here are the specifications for three Ada tasks:
task monday is entry january; entry february; end monday; task tuesday is entry june; entry july; end tuesday; task wednesday is entry october; entry november; end wednesday;
Assume that monday invokes only tuesday.june and tuesday.july. Assume that tuesday invokes only monday.january, wednesday.october, and wednesday.november. Assume that wednesday invokes only monday.february.
Can these tasks deadlock? Explain.

There are different definitions that will be acceptable here. One is that there is a cycle of two or more of the tasks where each task in the cycle simultaneously reaches the point of attempting to rendezvous with the next task in the cycle.
We can draw a ``rendezvous graph'' for this case, which will look like this:
As there are no directed cycles in this graph, there can be no deadlock.
Again, we can draw a ``rendezvous graph'' for this case, which will look like this:
As there are directed cycles in this graph, deadlock is possible. For example, it could happen that monday is waiting for a rendezvous with tuesday.june, while tuesday is waiting for a rendezvous with monday.january. This is clearly a deadlock.

[75] 4.

A Prolog binary tree is a binary tree such that every internal node has exactly two children and every node is labeled with a Prolog atom. Here is an example: tex2html_wrap418

Do the following:

Devise a representation for Prolog binary trees using Prolog lists. Represent the example tree in your representation.
Give the rules for a Prolog predicate prologtree(X) that is true when X is a Prolog binary tree. You may assume that there exists a predicate atom(Y) that is true when Y is a Prolog atom.
Show the steps that Prolog will go through to show that your representation of the example tree is a Prolog binary tree. Include instantiations and resolutions.

The representation for trees in Programming Assignment 2 can be adapted for this purpose. The tree consisting of a single node labeled with an atom, say, bob, is represented by that atom, in this case, bob. If X and Y are Prolog binary trees and Z is an atom, then the Prolog binary tree with root labeled Z, left child of the root X, and right child of the root Y is represented by the Prolog list [Z,X,Y].
The example tree is represented
```
[bob,julie,[alice,sue,bill]]
```

Here are the Prolog rules:

prologtree(X) :- atom(X).
prologtree([X,Y,Z]) :- atom(X), prologtree(Y), prologtree(Z).

The user enters the goal:
```
[bob,julie,[alice,sue,bill]]
```
The table in Figure 2 gives the successful steps that Prolog follows. The steps without instantiations are the resolution of atom terms (or goals), where no rule is involved. At the end of the table, the empty goal indicates success.

Figure 2: Prolog instantiations and resolutions

About this document ...

The command line arguments were:
latex2html -split 0 -t CS 3304 Solutions to Final Exam solvefinal.

The translation was initiated by cs3304sm class account on Sat Aug 9 13:16:56 EDT 1997

cs3304sm class account
Sat Aug 9 13:16:56 EDT 1997