Suggestions for the wtypei assignment

[Bryan Morse]

When doing type inference by hand, it's tempting to just reason your way through it in your head and then write that all down. Do NOT do this! In class we talked about very specific algorithms for generating constraints and then unifying them. Don't just generate your constraints by scanning through the code and writing them down as they come to you--try writing down for each expression the constraints that must be generated based only on that expression and not anything else. (Follow the algorithm and don't let your much-smarter-than-a-computer brain interject during this.) Don't worry if there are duplicates because those will come out in the wash later during unification.

Also keep in mind that the list operators are polymorphic. Don't assume that "empty" returns a list of numbers. It returns a list of some yet-to-be-determined type, so give this a type variable. I.e., when you see that expression #42 is the expression "empty" generate the constraint [[42]] = list([[empty943]]) where empty943 is some unique type variable to be figured out later. (Nothing magical about the name given it here--any unique identifier will do as long as you generate a new unique one for every time you see "empty".)

Combining this with the earlier suggestion, don't just impose a type here because you (the smart you, not the computer) knows how it's used later.

So, for the expression

(cons 1 empty)

and letting [[1]] be the type of this expression, [[2]] being the type of the first subexpression (1), and [[3]] being the type of the second subexpression (empty), here would be the constraints:

Generated by the "cons" expression:
[[1]] = list[[2]]
[[1]] = [[3]]

Generated by the "1":
[[2]] = number

Generated by the "empty":
[[3]] = list([[empty01]]

With the entire set now being
[[1]] = list[[2]]
[[1]] = [[3]]
[[2]] = number
[[3]] = list([[empty01]]

After unification (NOT before), you get that
[[1]] = list[[number]
[[2]] = number
[[3]] = list(number)
[[empty01]] = number

Notice that this last one comes only after the unification figures out that list[[empty01]] = [[3]] = [[1]] = list[[2]] = list(number). Again, do not just jump to that yourself but instead do it algorithmically.

---
Bryan S. Morse
BYU Computer Science
mo...@cs.byu.edu
http://morse.cs.byu.edu