CSPP 51091-1
Winter 2007

Midterm Exam 1
Feb 6, 2007
One hour, open book

1. [12] Determine whether the following are valid identifier or
constant tokens, and if so, what kind are they?

(a) 34e5     [valid real constant -- no decimal point needed when e occurs!]
(b) d4_x3'   [valid alphanumeric identifier]
(c) 45367    [valid integer literal (constant)]
(d) ''x3     [valid (equality) type variable]
(e) ++/$     [valid symbolic identifier]
(f) -13      [invalid - two tokens (- 13)]
(g) '_2      [invalid - ' must be followed by letter]
(h) "erg     [invalid - unclosed string constant]
(i) %x%	     [invalid - three tokens (% x %)]
(j) 'fred    [valid type variable]
(k) "Bob_$35"  [valid string constant]
(l) []       [invalid - two tokens ([ ])]


2. [14] Determine whether the following expressions type check, and if
so, give their types (as though they were entered in the interactive
top-level loop, with the standard initial environment).

(a) 1+2         : int
(b) x+3         : unbound variable x - not well typed
(c) (12,"abc")  : int * string
(d) [12,"abc"]  : not typed - list elements must have same type]
(e) if 2 < 3.5 then [] else [true]  : not typed - comparing int and real
(f) #"(" <= chr(13) : bool
(g) case [13] of nil => 35 | x => hd(x) + 3 : int


3. [14] Define a function f : string -> int such that f(s) opens a
file named s (in the current directory), and returns the integer value
designated by the first digit character found in that file. For
example, if the file starts with

.x$$3(((%45drss ...

f should return the value 3 : int.

------------------
(* question somewhat underdefined. What is it to do if the file ends
 * before the first digit is found?  I'll raise Fail *)

fun digit c = c >= #"0" andalso c <= #"9"
(* = Char.isDigit *)

fun f(s: string) =
    let val instrm = TextIO.openIn s
        fun scan () = 
	    (case TextIO.input1 instrm
	       of NONE => raise Fail "no digits found"
	        | SOME c => if digit c then (ord(c) - ord(#"0")) else scan())
     in scan()
    end
-----------------

4. [15] Suppose that a datatype of binary trees is defined by:

  datatype 'a tree = EMPTY
                   | NODE of 'a * tree * tree

Define an analogue of the map function for lists,

  maptree : ('a -> 'b) -> 'a tree -> 'b tree

such that (maptree f t) produces a new tree by applying
f to the first component of each node of t.

-----------------
fun maptree f EMPTY = EMPTY
  | maptree f (NODE(v,left,right)) =
      NONE(f v, maptree f left, maptree f right)
-----------------

5. [10] Give the type of the following function:

fun f ([x,y],z) = (x,y,z)
  | f (w,(u,v)) = (u,3,(v, hd w))

f : int list * (int * int) -> int * int * (int * int)


6. [15] Define a function

   search : (int -> bool) * int list -> int

such that (search f m) returns the first integer x in m such
that (f x) is true, or 0 if no such integer is found. Search
should use the exception

   exception Found of int

in the case where the search is successful. [Hint: search will
have to both raise and handle the Found exception.]

------------------
exception Found of int

fun search (p, l) =
    let fun search1 nil = 0
          | search1 (x::xs) = 
	      if p x then raise (Found x) else search1 xs
     in search1 l
        handle Found x => x
    end
------------------

7. [20] Give the type of the following function, and explain how
it was derived.

fun f x y =
    let fun g u = (x, u)
        fun h v = map g (y::v)
     in h []
    end

Does h have a polymorphic type in the scope of its definition
(i.e. in the body of the let expression)?

Let x have type 'x, y have type 'y.

Let u have type 'u.

  g has type 'u -> ('x * 'u)
  'u is local, but 'x is associated with an outer scope (binding of x)
  so g gets the polymorphic type

  g:  (All 'u). 'u -> ('x * 'u)

Let v have type 'v.

  Because of the subexpression y::v, 'v = 'y list, and y::v : 'y list.
  We instantiate the type of g to 'y -> 'x * 'y.  ('u |-> 'y)
  map g (y::v) then has type ('x * 'y) list.
  so h : 'y list -> ('x * 'y) list.
  Both 'x and 'y are bound in an outer scope, so type of h cannot be
  generalized (i.e. it is not polymorphic).

In h [], initially []: 'w list, and 'w list = 'y list (argument type
of h), hence 'w = 'y, yielding []: 'y list 
Then h [] : ('x * 'y) list, which is the type of the whole body of f.

So f : 'x -> 'y -> ('x * 'y) list.
'x and 'y are bound locally, so they can be generalized, giving

   f : (All 'x, 'y). 'x -> 'y -> ('x * 'y) list