This problem requires Lecture 30 and book section 4.4.
Exercise 4.16, p.160 - (45 minutes)
Consider the following examples:
1. proc (f,g,p,x) if (p(f x)) then (g 1 x) else add1((f x))
2. proc (x,p,f) if (p x) then add1(x) else (f p x)
3. proc (x,p,f,g) if (p add1(x)) then add1((f x)) else (g f x)
4. let x = 3 f = proc (x) add1(x) in (f x)
First, insert ? in front of each formal parameter. Then, solve the resultant type equation. Treat add1 as if it were a procedure of type
(int -> int)
and + as if it were a procedure of type (int * int -> int).
The book and the problem describe inference in terms of setting up "type equations" and then solving these equations, but these are just the type comparisons made at each step during the type-checking algorithm--we don't really set up systems of equations and then solve them, instead we just repeatedly traverse the AST until all of the type information is filled in. Just write down in order each type comparison that would take place.
The first one has been done for you. You would be wise to follow this model.
Instructions on submitting homework is here
Last updated at 9:23 am on Monday, January 12, 2004.