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
Candidates must complete this section
|
|
Page 1 of 22 |
Question 1Definitions 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 2Consider 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,
| [2-marks] |
Question 3Consider 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 |
[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
| [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 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
| [6-marks] |
Question 5Consider 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] |
(ii) What is ad-hoc polymorphism (also known as overloading)
as a programming language concept?
| [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.
| [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 stack linkage information. | [4-marks] | |
(iii) Give the code generated by the compiler for
expression mv+bv+cv in
| [4-marks] |
Question 9Consider the following regular grammar, with terminals a and b, non-terminals S and X, start symbol S, and productionsS -> 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 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 10Consider 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] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| [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 11Consider the context-free grammar with terminals a, bS -> 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.
| [5-marks] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(iii) Detail how an SLR parser will parse the sentence abbc
using the SLR table you constructed above.
| [5-marks] |