Suggested Homework #5 (for Quiz #5 on 11/15/07)

Problem 1: Consider the module shown below. Write a signature STACK that turns it into an abstract datatype where the only things visible to the client are: EmptyStack, new, push, pop, empty, toString. Note that this will require you to infer the types of the functions implemented below. 
  module Stack : STACK = 
    struct
       type 'a stack = Empty | Push of ('a * 'a stack) 
       
       exception EmptyStack

       let new () = Empty

       let push s e = Push (e,s)

       let pop s = 
         match s with 
	   Empty -> raise EmptyStack
	 | Push(x,_) -> x
    
       let empty s = 
	 match s with
	   Empty -> true 
	 | _ -> false

       let rec toList s =
         match s with 
	   Empty -> []
	 | Push(top,bot) -> top :: (toList bot)

       let toString f s = String.concat (List.map f (toList s))
       
    end
Problem 2: Consider the following signatures: 
module type NE1 = 
  sig 
    type name =  string
    type expr 
    type namedExpr = name * expr
    val makeExpr : string * (int * int -> int)  -> (namedExpr * namedExpr) -> namedExpr
    val constExpr : int -> namedExpr
    val eval : namedExpr -> int
  end 

module type NE2 = 
  sig 
    type name   
    type expr 
    type namedExpr = name * expr
    val makeExpr : string * (int * int -> int)  -> (namedExpr * namedExpr) -> namedExpr
    val constExpr : int -> namedExpr
    val eval : namedExpr -> int
  end 

module type NE3 = 
  sig 
    type name 
    type expr 
    type namedExpr 
    val makeExpr : string * (int * int -> int)  -> (namedExpr * namedExpr) -> namedExpr
    val constExpr : int -> namedExpr
    val eval : namedExpr -> int
  end
(a) Write down three expressions that Ocaml would accept for a client using implementation (structure) S : NE1 but would reject if S : NE2 .
(b) Write down three expressions that Ocaml would accept for a structure S : NE2 but would reject if S : NE3 .
For both parts above, S refers to an implementation of the signature, just like Stack is an implementation of the signature STACK in Problem 1.
For example, in lecture we saw that Ocaml would accept: Rational.to_string (60,40) if Rational : RATIONAL_A but would reject if Rational : RATIONAL_B .