Question 1

(1) Name two historically significant programming languages that were developed before 1960.

(2) What category or paradigm of programming language has a structure dictated by the von Neumann computer architecture?

(3) What is one advantage and one disadvantage of using an interpreter compared with using a compiler?

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

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

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

S → aSbb | X

X → cX | c

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

(8) Write BNF grammar rules for a language that is comprised only of sentences described as follows:

A sequence of one or more occurrences of an a symbol, fol- lowed by either zero or more z symbols or just one x symbol, followed by a sequence of one or more b symbols.

(9) The following fragment of grammar describes the syntax of the exponentiation operator. What is the associativity of the operator as defined here?

factor → expr ** factor | expr

(10) What are the two major styles of parser? In each case, what derivation order do they attempt to construct for the sentence being parsed?

(11) Name a variable attribute which is bound at
(a) compile time
(b) link time
(c) run time

(12) Define what is meant by the lifetime of a variable.

(13) What is a type error?

(14) What is type coercion?

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

(16) Describe one of the common programming errors which can arise when using pointers.

(17) Consider the array x : array [0..10, 5..10] 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,6]?

(18) What is an overloaded operator?

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

(20) What advantage is gained by providing user-located loop control statements in a programming language?

(21) Using an example, explain how operand evaluation order can affect the result of expression evaluation when a functional side effect is present.

(22) What is the static parent of a subprogram?

(23) What is a formal parameter?

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

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) Consider the C function

int myFun(a: int; b: char){ x,y: float;
.....
}

Draw the layout of the activation record for this function. The ordering of elements is important - assume that the stack grows upwards.

(26) What is the advantage of separate compilation over indepen- dant compilation?

(27) A static chain links a set of activation record instances to- gether. How are these instances related?

(28) Why do the actual parameters appear in an activation record below (that is, they are pushed onto the stack before) the local vari- ables?

(29) 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.

(30) What are the two key features of 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) What key advantage of using an abstract data type is weak- ened when inheritance is employed?

(35) Under what conditions is a derived class a subtype of its parent?

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
replace :: Eq a => a -> a -> [a] -> [a].
The application replace a b list will replace all occurrences of a in list
with b. For example:
replace 'a' 'X' "abcabAcdaee" ⇒ "XbcXbAcdXee" replace 1 100 [2,3,1,1,5,6] ⇒ [2,3,100,100,5,6]

(2) Write the function
posn :: Eq a => a -> [a] -> Maybe Int.
posn looks for an item in a list. If found it returns Just n where n is its position (starting from zero). Otherwise it returns Nothing. For example:
posn 'c' "abcde" ⇒ Just 2
posn 'a' "abcde" ⇒ Just 0
posn 'f' "abcde" ⇒ Nothing

(3) Write the function
merge :: Ord a => [a] -> [a] -> [a].

merge takes two lists sorted in ascending order and merges them into one sorted list. Lists can be of unequal length and may be empty. For example:

merge [1,3,5] [2,4] ⇒ [1,2,3,4,5]
merge [1,10] [2,2,2] ⇒ [1,2,2,2,10]

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) Evaluate the following equalities and write down the values for the variables H and T.

i. ?- [the, cat, [cat, sat]] = [H | T].
ii. ?- [the, [cat, sat], down] = [_,H | T].

(2) Define the relation replace(A,B,L1,L2) such that the list L2 is the same as list L1, except that all occurrences of A in L1 are replaced by B. For example:

?- replace(a,b,[a,b,a,c],X). ⇒ X = [b, b, b, c] .

(3) Assume the presence of a database of parent relations. parent(X,Y) asserts that X is a parent of Y.

i. Write the relation cousin(X,Y) that is true when two persons are cousins.

ii. Write the relation stepsib(X,Y) that is true when two people share only one (but not both) parents.