Question 1

(1) Name or describe an abstraction feature of a programming language.

(2) Name two (2) languages with statement syntax that is very similar to that of the C language.

(3) Name a language feature whose use can enhance the relia- bility of programs written in that language.

(4) Why is readability of a programming language important?

(5) What are the three extra constructions present in Extended BNF (EBNF) compared to BNF?

(6) List the tokens in the the following C statement:
x+=p->val+1;

(7) Write a single EBNF rule for the language defined by the following syntax graph.

(8) Describe in English language the sentences produced by the following grammar.

S → aSb | aXb
X → y | z

(9) Given the grammar

declist → decl declist | ∈
decl → type varlist ;
type → int | float | char
varlist → ident , varlist | ident
ident → a | b | x | y
Produce a leftmost derivation for the following sentence of the langage:
int x,y; char a;

(10)  How can a grammar be proven to be ambiguous?

(11) What form of grammar rule is required to produce right associativity in expressions?

(12) What derivation order does a LR parser employ in parsing a sentence of a language?

(13) What is the lifetime of
(a) a stack-dynamic variable
(b) an explicit dynamic variable

(14) What is a type error?

(15) What is meant by strong typing?

(16) What kind of programming error can arise when implicit variable declarations are permitted in a language?

(17) What is meant by the scope of an identifier?

(18) The "lost variable" problem when using heap dynamic vari- ables leads to a so-called "memory leak". Describe a situation that demonstrates this problem.

(19) Consider the array x: array [0..10, 20..30] of double

If a double occupies 8 bytes, and access is in row major order, what is the byte offset (the number of bytes from the beginning of the array, starting from zero) of the element x[7,25]?

(20) What is short circuit expression evaluation? Give an example of a C expression which can be evaluated in this way.

(21) What is the minimum number of loop iterations possible for a pre-tested loop?

(22) Ada and Modula-2 use explicit end of statement keywords and sequences of statements, like this:

if Stmt → if expr then stmtList else stmtList end

C and Pascal use blocks and no statement terminating keyword, like this (using Pascal syntax):

if Stmt → if expr then block else block block → stmt | begin stmtList end

Give one advantage for using each of these two approaches.

(23) What is the dynamic parent of a subprogram?

(24) Consider the following program, written in a C-like language.

int x;
void f(int a) {a = a+2; x = x+1;} void main() {
x = 1;
f(x); printf("x= d\n",x);
}

What value of x will be printed by the main program under each of the following conditions? Imagine that formal parameter a of function f is being passed:
i. by value
ii. by value-result
iii. by reference

(25) What parameter passing mode (in, in-out or out) do the following parameter passing mechanisms implement?
- call-by-value
- call-by-reference
- call-by-result
- call-by-value-result

(26) Why are the return address and parameters placed in a procedure's activation record before its local variables?

(27) Consider the following skeletal program, written in a lan- guage with static scope.

procedure  Main; procedure  A;

procedure  B;

procedure  C;

begin { C  }

end { C } begin { B } end { B }

procedure  D;

procedure  E;

begin { E }

end { E } begin { D } end { D }

begin { A  }

end { A } begin  {  Main  } end  {  Main  }

Imagine that the following procedure calls have taken place:

i. Draw the run time stack showing just activation record instances and static links at the time when C is executing. Do not show contents of each activation record instance, apart from the static link.

ii. List the names of procedures that can be called from procedure B.

(28) Give two ways in which overloaded subprograms of the same name must differ from each other in order to be valid definitions.

(29) What are the two key features of an Abstract Data Type?

(30) Give one advantage of using an abstract data type.

(31) What is an exception?

(32) What is the advantage of using language defined exception handler features to deal with exceptions rather than using standard techniques such as calling an error procedure?

(33) What are the two key features of an Object Oriented lan- guage, beyond those provided by an Abstract Data Type?

(34) Describe one significant design decision faced by designers of object oriented languages?

Question 2

In this question you are required to write a number of small Haskell functions. You may use any Standard Prelude function in writing these functions. If you need, you may write other functions in order to implement the functions specified below; if you do so, be sure to show their definitions.

One of the definitions use the Maybe data type. Recall that the Maybe type has definition:

data Maybe a = Nothing | Just a

(1) Write the function
cap :: String -> String.

The application cap str will replace the initial letter of each word in str with a capital letter. Assume that str contains words separated by one or more space characters (you do not need to consider other whitespace such as tabs and newlines). For example:
cap "zip" ⇒ "Zip"
cap " aaa bbb ccc" ⇒ " Aaa Bbb Ccc"
Hint: Use the toUpper function from the Char module to help in writing this function.

(2) Assume the definition:
data Tree x = Node x (Tree x) (Tree x) | Nil.
Write the function
lookT :: Ord a => a -> Tree (a,b) -> Maybe b that searches a binary tree of (key,value) pairs. The values are stored in sorted order:
for each node, the left subtree contains only nodes with keys less than the node's key, while the right subtree contains only nodes with keys greater than the node's key. lookT key tree searches tree and returns the value associated with key, if a matching key value is found. Otherwise it returns Nothing. The function should only search in sub-trees likely to contain key. For example:
lookT 1 (Node (1,"Fred") Nil Nil ⇒ Just "Fred"
lookT 1 (Node (2,"Mary") Nil Nil ⇒ Nothing
lookT 1 (Node (2,"Mary") (Node (1,"Fred") Nil Nil) Nil)
⇒ Just "Fred"

(3) Write the function
mrep :: [String] -> String -> String.
mrep xs str returns str, where successive occurrences of the '

character in str are replaced by successive elements in xs. The length of xs does not need to match the number of '

For example:

mrep ["aa","bb"] "xx $ yy $ zz" ⇒ "xx aa yy bb zz"
mrep ["aa"] "xx $ yy $ zz" ⇒ "xx aa yy $ zz"
mrep ["aa","bb"] "xx $ yy" ⇒ "xx aa yy"

Question 3

In this question you are required to write a number of Prolog relations. You may need to define other relations in order to answer the questions below.

(1) Define the relation maxList(L,N) such that N is the maxi- mum value that appears in the (non-empty) list L. For example:
?- maxList([1,10,5,7], X). ⇒ X = 10 .

(2) Assume the presence of a database of family relations: parent(X,Y) asserts that X is a parent of Y, and husband(H,W) asserts that H is the husband of W.

i. Write the relation spouse(X,Y) that is true whenever X is married to Y.

ii. Write the relation inlaw(X,Y) that is true whenever Y is a parent-in-law of X. (A person's parents-in-law are that person's spouse's parents.)

iii. Write the relation sibinlaw(X,Y) that is true when- ever Y is a brother-in-law or a sister-in-law of X. (A person's sisters-in-law are that person's spouse's sisters; similarly for brothers-in- law.)