Monash University

Semester Two Examination Period, 2006

Faculty of Information Technology

CSE3322, Programming Languages and Implementation.

Exam duration: 3 hours writing time.

Reading time: 10 minutes.

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:
 

  

  

  
 
Office
use
only:
 1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
Total     /90

Page 1 of 22

(Extra space for working)

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]

(Extra space for working)

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. 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
stack linkage information.









[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 <reg>, <reg>
  --e.g., load R3, R5
load <reg>, <address>
  --load the reg from the
  --word at the address
  --e.g., load R3, 36[R2]

sto <reg>, <address>
  --store the reg to memory

<opcd> <reg>, <reg>
  --e.g., add R3, R5
<opcd> <reg>, <address>
  --e.g., add R3, 36[R2]

where
 <opcd> -> add | sub | mult |...

 <address> -> <offset>
      | <offset>[<reg>]

 <reg> -> R0 | R1 | ... | R15
[4-marks]

(Extra space for working)

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]

(Extra space for working)

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)]]