CSPP 51091-1
Winter 2007

Midterm Exam 1
Feb 27, 2007
One hour, open book, open notes

Section 1: Types

1. [10] Value restriction
Explain the "value restriction" in type checking, and give an example
showing why it is necessary. (Hint: ref.)

The value restriction is a rule that constrains when type variables
in the types of let-bound variables can be generalized to make those
types polymorphic. The restriction is necessary to prevent the
combination of polymorphism and refs (or arrays, or first-class
continuations) from causing holes or unsoundness in the type system.

The restriction only allows the definition type to be generalized if
it is a syntactic "value", meaning a term that involves no real
computation when it is evaluated. Constants, variables and function
expressionns (fn p => e) are examples of basic value expressions, but
compound expressions built from these by forming tuples or records, or
by application of datatype constructors like "::" are also classified
as value expressions.

A typical example illustrating the need for the value restriction is:

let val r = ref (fn x => x)
 in r := (fn x => x+1);
    !r true
end
 
Without the value restriction, the type of the expression defining
r will be generalized to give 

   r : All 'a . ('a -> 'a) ref

and then at the two uses of r in the body this polymorphic type can
be instantiated to 

   r : (int -> int) ref

and

   r : (bool -> bool) ref

respectively, and the let expression will type check. But this means
that an integer function can be passed through the ref and applied
to a boolean argument, a violation of the type system.


2. [18]Type checking

For the following terms and declarations, give their types or state
why the do not type check. Also, give the type of each let-bound
variable or local function.
[Hint: pay close attention to whether a let bound variable is assigned
a polymorphic type, and consider the application of the value
restriction where appropriate.]

(a) [4] fun k x y = x
----------------------------------------------------------------------
    k : All ('a,'b). 'a -> 'b -> 'a   (polymorphic)
----------------------------------------------------------------------

(b) [7]
    let val nn = nil :: nil
        val id = (fn x => x)
	val id2 = id id
     in (id2 3, id :: nn)
    end

----------------------------------------------------------------------
    nn : All 'a . 'a list list   (polymorphic because nil::nil is a
				  value expression)
    id : All 'a . 'a -> 'a       (polymorphic because a function expr
				  is a value expression)
    id2 : 'x -> 'x               (nonpolymorpic because id id is not a
                                  value)
    The let expression is not well typed because the
    expression id :: nn does not type check. id has a function type
    which cannot match the element type of nn, which is 'y list
    for some 'y.
----------------------------------------------------------------------

(c) [7]
    fun f x =
        let val u = ref(nil)
            fun g v = (v::(!u), 1::x)
	    fun h z w = (g z, w::x)
         in (g 3, h "a")
        end

----------------------------------------------------------------------
    x : int			 (constrained by 1::x in line 3)

    u : 'p list ref		 (nonpolymorphic because of value
			          restriction, initially typed with
				  a free type variable 'p)

    g : 'p -> 'p list * int list (non-polymorphic 'p shared with type
                                  of u)

    h : 'p -> int -> ('p list * int list) * int list

Now the application "g 3" in the body of the let forces 'p to be
instantiated to int, and this instantiation affects the types of 
g and h:

    g : int -> int list * int list

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

Then the application (h "a") causes a type error because the type
of the domain of h is int.

- fun f x =
        let val u = ref(nil)
            fun g v = (v::(!u), 1::x)
	    fun h z w = (g z, w::x)
         in (g 3, h "a")
        end
;
stdIn:5.13-5.25 Error: operator and operand don't agree [literal]
  operator domain: int
  operand:         string
  in expression:
    h "a"
----------------------------------------------------------------------


Section 2: Higher-order functions (e.g. map,fold,all,exists)

3. [5] Define the exists function on lists

   val exists : ('a -> bool) -> 'a list -> bool

in terms of a fold function (foldl or foldr).

----------------------------------------------------------------------
(a) fun exists f l = foldl (fn (x,b) => b orelse f(x)) false l

(b) fun exists f l = foldl (fn (x,b) => f(x) orelse b)) false l

These two versions have the same effect, but the first will only
evaluate f(x) for elements x in l until the first evaluates to true
(if any), while the second will evaluate f(x) for all elements
of the list l. They are both linear, but the first is more efficient.
----------------------------------------------------------------------


4. [7] Define exists directly, by a recursive traversal of the list
argument. Do this definition and the previous one from problem 3 have
the same behavior for all arguments?  Should they?

----------------------------------------------------------------------
fun exists f nil = false
  | exists f (x::xs) = f(x) orelse exists f xs

Like version (a) for Problem 3 above, this will evaluate f(x)
for successive elements x in l until the first one returns true,
but then it returns immediately, unlike 3(a), which contintues
to evaluate "true orelse f(x)" for the remaining elements.
----------------------------------------------------------------------

Section 3:  Readers

Readers are values of having the type reader defined by

   type ('a, 'b) reader = 'b -> ('a * 'b) option


5. [10] Define a reader

   listReader : ('a, 'a list) reader

that produces the successive elements of a list.

--------------------------------------------
fun listReader nil = NONE
  | listReader (x::xs) = SOME(x, xs)
--------------------------------------------

[Note: There is a small but important error in the type of
readerFoldl in Problem 6 below. It should have been:

   readerFoldl : ('a * 'b -> b) -> 'b -> ('a, 'c) reader -> 'c -> 'b

where 'c is the type of the source that the reader is initially
applied to.]

6. [15] Define the analogue of the foldl function for ('a, 'b) readers:

   readerFoldl : ('a * 'b -> b) -> 'b -> ('a, 'c) reader -> 'b

and combine this with the listReader function from (a) to define
a function that takes the sum of an integer list.

--------------------------------------------------------------------
fun readerFoldl f b r p =
    (case r p         (* apply reader to initial producer value *)
       of NONE => b   (* no values forthcoming *)
        | SOME(x, p') => readerFoldl f (f(x,b)) r p')

fun sumList l = readerFoldl (op +) 0 listReader l
--------------------------------------------------------------------


7. [10] Define a reader that will return the elements of given
fixed array A of length n in reverse order of their indexes
(i.e. sub(A,n-1), sub(A,n-2), ..., sub(A,0)). [Hint: the
"source" type 'b should be int.]
--------------------------------------------------------------------
Let A be the fixed array of length n. The reader will produce values
from this particular array. The initial producer should be the index
of the last element of the array, namely n-1.

fun areader k = if k < 0 then NONE else SOME(Array.sub(A,k),k-1)
--------------------------------------------------------------------


8. [10] Define a reader that uses an 'a stream as a producer
and produces the successive elements of the initial stream.
--------------------------------------------------------------------
fun streamReader Snil = NONE
  | streamReader (Scons(x,s)) = SOME(x, s())
--------------------------------------------------------------------


9. [15] Define a for loop function that applies an effectful 
operation to each element produced from a given source,
reader pair. (This is an analogue of List.app).

   for : ('b * ('a, 'b) reader) -> ('a -> unit) -> unit

Use this to print the elements of an integer list. (See
problem 5 above).
--------------------------------------------------------------------
fun for (source,reader) f =
    (case reader source
       of NONE => ()
        | SOME(x,source') => (f(x); for (source',reader) f))

fun printList l = 
    for (l,listReader) (fn n => (print(Int.toString n); print " "))
--------------------------------------------------------------------