Take home, no time limit, estimated/suggested time 6 hours, open book.
Set Tuesday Dec 11th, due Friday Dec 14th.
1. General questions about functional programming
(i) What is functional programming?
(ii) What is a function, in the context of functional programming?
(iii) Briefly outline any advantages and disadvantages of functional programming.
2. Monomorphic type inference :
(i) (Exercise 11.2 in Reade's book)
Use the monomorphic type inference rules (described in the slides, and also in Chapter 11 of Reade's book), to prove that:
(a) given([add:intxint->int]) fn x => add(x,x):int->int
(b) given([add:intxint->int]+[3:int]) let val f = fn x => add(x,x)
in f (f 3) end : int
(ii) Informally outline an type checking algorithm for the monomorphic case,
analogous to Algorithm W.
3. Polymorphic type inference :
(i) Definitions:
What is a type expression, what are type operators, and
what is a polymorphic type?
(ii) Unification:
What is unification, and how is it used to determine the
type of an expression in which a polymorphic function
is applied to a polymorphic argument?
(iii) Generic variables:
What are generic type variables, and how are they treated
in type checking?
(iv) Give a brief outline of how the type of the following expression
could be found
given([3:int]) let val x=3 in let val f = fn y => x in f x end end :int
Email me and Josh a URL with your answers.