## Monash University

### CSE3322, Programming Languages and Implementation.

#### Exam duration: 3 hours writing time.

This paper is for students studying at Clayton and Malaysia.

During an exam, you must not have in your possession, a book, notes, paper, calculator, pencil case, mobile phone or other material/item which has not been authorised for the exam or specifically permitted as noted below. Any material or item on your desk, chair or person will be deemed to be in your possession. You are reminded that possession of unauthorised materials in an exam is a discipline offence under Monash Statute 4.1.

1. There are no `authorised materials'.
2. Closed book.
3. No calculators.
4. The total marks are 90.
5. Attempt all questions.
6. Write answers to all questions on the exam paper itself.
7. Answers required to give explanation will receive zero marks if they do not give explanation.
8. An appendix (eg.sml) gives some standard definitions in SML.
Candidates must complete this section
STUDENT ID:
DESK NUMBER:

Officeuseonly: /90

### Question 1

Definitions of datatype Tree, and functions height, append, map, zip and other common functions can be found in the appendix (eg.sml).

Each of the following pieces of SML code is inefficient in terms of time and/or space. For each one, write an efficient piece of SML code that computes the same result. For each answer explain why your solution is more efficient.

[6-marks]
(i) height t > 0

[2-marks]
(ii) append(append L1 L2) L3

[2-marks]
(iii) map (op +) (zip L1 L2)

[2-marks]

### Question 2

Consider the following SML definition of function tf:

```  fun tf g EmptyTree     = EmptyTree
| tf g (Fork(L,e,R)) = g (tf g L) e (tf g R)
```

The definition of datatype Tree can be found in the appendix (eg.sml).

[6-marks]
(i) What type does the SML compiler infer for function tf?

[2-marks]
(ii) Detail how the SML compiler infers the type of function tf.

[2-marks]
(iii) Use tf to define a function, mirror : 'et Tree -> 'et Tree, that performs the mirror-image operation on Trees.
e.g. mirror(
 d / \ b e / \ / \ a c f g
)  ---->
 d / \ e b / \ / \ g f c a

[2-marks]

### Question 3

Consider the following SML definition of function isBST.

```(* ?is a given tree a binary search tree?... *)
fun isBST EmptyTree = true
| isBST (Fork(L,e,R)) =
let fun check _ EmptyTree = true
| check p (t as Fork(_,e,_)) = p e andalso isBST t
in check (fn e' => e' < e) L andalso
check (fn e' => e' > e) R
end;
```
The definition of datatype Tree can be found in the appendix (eg.sml).
We would like isBST to be able to act on data-structures of types  int Tree, real Tree, string Tree, etc., but it cannot.

[6-marks]
(i)What type does function isBST actually have in SML?

[2-marks]
(ii) What is the feature that SML lacks (but Haskell has) which would allow isBST to act on data-structures of types  int Tree, real Tree, string Tree, etc.?

[2-marks]
(iii) What is the standard work-around for this lack in SML, and how would isBST be changed by using the work-around?

[2-marks]

### Question 4

[7-marks]
(i) Define the scope rules of SML.

[1-marks]
(ii) Consider the following skeleton SML program with five functions (a, b, c, d, e) and six expressions (e1, e2, e3, e4, e5, e6).
```let fun a() =
let fun b() = ...e1...;
fun c() = ...e2...
in ...e3...
end;
fun d() =
let fun e() = ...e4...
in ...e5...
end
in ...e6...
end
```

For each expression indicate which functions are in scope for the expression, that is which functions the expression can call and which it cannot call, by putting a tick (can call) or a cross (cannot call) in each box of the following table.

abcde
e1
e2
e3
e4
e5
e6

[6-marks]

### Question 5

Consider the following program in a hypothetical language which resembles SML but which may use a different binding mechanism to SML.

```let
val a = 22;

fun f() =
let val a = 33
in g()
end

and g() = 100 + a

in (f(), g())
end;
```

[7-marks]
(i) What would be the result of the program if the language used static-binding? Give reasons.

[2-marks]
(ii) What would be the result of the program if the language used dynamic-binding? Give reasons.

[2-marks]
(iii) Does SML use static-binding or dynamic-binding?

[1-marks]
(iv) State a possible advantage of static-binding over dynamic-binding.

[1-marks]
(v) State a possible advantage of dynamic-binding over static-binding.

[1-marks]

### Question 6

[7-marks]
(i) What is parametric-polymorphism (also known as polymorphism) as a programming language concept?

[1-marks]

[1-marks]
(iii) Does the language C have ad-hoc polymorphism? If so give an example.

[1-marks]
(iv) Does SML have ad-hoc polymorphism? If so give an example.

[1-marks]
Consider the following function definitions in SML.
```       fun length [] = 0 | length (_::t) = 1+length t;
fun max (x::xs)=
let fun mx m [] = m
| mx m (x::xs) = mx (if x > m then x else m) xs
in mx x xs
end;
val plus = (op +);
```
(v) What kinds of polymorphism, if any, does length have in SML?

[1-marks]
(vi) What kinds of polymorphism, if any, does max have in SML?

[1-marks]
(vii) What kinds of polymorphism, if any, does plus have in SML?

[1-marks]

### Question 7

[7-marks]
(i) What is the purpose of a Structure in SML?

[1-marks]
(ii) What is the purpose of a Signature in SML?

[1-marks]
(iii) What is the purpose of a Functor in SML?

[1-marks]
Consider the following SML example.
```signature Traversable = sig                 (* lect.ML7 *)
type elementType;
type ds;
type state;
val initialise : ds -> state;             (* state 0 *)
val next       : state -> elementType option;
val advance    : state -> state
val toList     : ds -> elementType list
end;

datatype 't sbTree = leaf of 't   (* strict binary tree *)
| fork of 't * ('t sbTree) * ('t sbTree)

functor Trav_sbTree( type et ) :Traversable = struct
type elementType = et;
type ds = et sbTree;
type state = et sbTree list;
fun initialise t = [t];
fun next []                 = NONE
| next ((fork(e,l,r))::_) = SOME e
| next ((leaf e)     ::_) = SOME e ;
fun advance ((fork(e,l,r))::s') = s' @ [l, r]
| advance (((leaf e))   ::s') = s' ;
fun toList v =            (* sbTree to list *)
let fun scan s =
case next s of NONE   => []
| SOME x => x :: (scan(advance s))
in scan(initialise v)
end
end;

structure tv_sbTree = Trav_sbTree( type et = int );
tv_sbTree.toList (fork(1, (fork(2,leaf 3,leaf 4)), (leaf 5)))
(* computes it = [1,2,5,3,4] *)
```

(iv) The example above makes strict binary trees Traversable. Give SML code to make SML's standard lists Traversable.

[4-marks]

### Question 8

[9-marks]
(i) Is C block structured? Is SML block structured?

[1-marks]
Consider the following skeleton of a program in a hypothetical block-structured language.
```begin(*main*)
int mv;
mv := 12;

procedure a(procedure ap(int app))
begin(*a*)
int av;
av := 34;
ap(56);       (*a calls its parameter*)
...
end(*a*);

procedure b(int bp)
begin(*b*)
int bv;
bv := bp+1;

procedure c(int cp)
begin(*c*)
int cv;
cv := cp+2;
bv := mv+bv+cv   (* see part (iii) *)
end(*c*);

a(c);         (*b calls a, passing it c*)
...
end(*b*);

b(78);           (*main calls b*)
...
end(*main*)
```

(ii) Draw the stack when procedure c is running.
Show variables and all necessary

[4-marks]
(iii) Give the code generated by the compiler for expression mv+bv+cv in procedure c. Your answer must be consistent with the stack organization in your answer to the previous part. Detail any conventions that you adopt.

 The target machine has 16 integer/index registers, R0-R15, and instructions of the form load ,   --e.g., load R3, R5 load ,
--store the reg to memory ,   --e.g., add R3, R5 ,
--e.g., add R3, 36[R2] where   -> add | sub | mult |...
->       | []   -> R0 | R1 | ... | R15
[4-marks]

### Question 9

Consider the following regular grammar, with terminals a and b, non-terminals S and X, start symbol S, and productions
```S -> X
X -> a X
X -> a
X -> b X
X -> b
```
[8-marks]
(i) The above grammar recognizes a regular language. Give a regular expression for the language of this grammar.

[2-marks]
(ii) Add attributes and attribute computation rules and conditions to the grammar above so that it recognises non-empty strings with an equal numbers of a's and b's.
I.e., abaabb should be in the language of the new grammar but aaabb should not.
Indicate whether the attributes are inherited or synthesized.

[6-marks]

### Question 10

Consider the following grammar with terminals a, b and +, and non-terminals S, A and B where S is the start symbol, and productions
(P1) S -> A + B
(P2) S -> B
(P3) A -> a A
(P4) A ->
ε
(P5) B -> b B
(P6) B ->
ε
[12-marks]
(i) Compute FIRST(A), FIRST(B), and FIRST(S).

[2-marks]
(ii) Compute FOLLOW(A), FOLLOW(B), and FOLLOW(S).

[2-marks]
(iii) Consider the following LL(1) parsing table for a predictive table parser
a b + \$
S P1 P2 P1
A P3   P4
B   P5   P6
where Pi refers to the ith production in the above grammar.

Detail how the sentence a+b is parsed with a predictive table parser using this table. For each step of the process give the parser action, input, and stack state.

stackinputaction

you might not need all lines of the table.

[4-marks]
(iv) Is the parsing table given above the correct LL(1) predictive table for this grammar? If not, identify and correct any error(s) in the table.

[4-marks]

### Question 11

Consider the context-free grammar with terminals a, b and c, non-terminals S, X and Y where S is the start symbol, and productions
```S -> a X
X -> b X
X -> b Y
Y -> c
```

[15-marks]
(i) Give the canonical collection of LR(0) items for the above grammar, remembering to first augment it with a new start symbol S'.

[5-marks]
(ii) Compute the FOLLOW sets for all non-terminals and give the SLR parsing table (action and goto) for this grammar.

state action goto
abc\$SXY

you might not need all lines of the table.

[5-marks]
(iii) Detail how an SLR parser will parse the sentence abbc using the SLR table you constructed above.
stackinputaction

you might not need all lines of the table.
[5-marks]

#### --- Appendix follows [[eg.sml]] ---

[[directory (click)]]