CSC448: Type Checking Revisited: Hindley-Milner Type Inference: Implementation II [120/133] Previous pageContentsNext page

We can also see the inferred types of subexpressions and the constraints as they are created:

(fun f i => (fun g xs => (if (is_zero i) then [] else ((head xs)::((f ((add i) -1)) (tail xs))))))

Inferred is_zero : (int -> boolean)
Inferred i : 'A0
Added constraint: 'A4 = int
Added constraint: 'A5 = boolean
Added constraint: 'A0 = 'A4
Inferred (is_zero i) : 'A5
Inferred [] : ('A6 list)
Inferred head : (('A7 list) -> 'A7)
Inferred xs : 'A2
Added constraint: ('A7 list) = 'A8
Added constraint: 'A7 = 'A9
Added constraint: 'A2 = 'A8
Inferred (head xs) : 'A9
Inferred f : ('A0 -> 'A1)
Inferred add : (int -> (int -> int))
Inferred i : 'A0
Added constraint: 'A10 = int
Added constraint: (int -> int) = 'A11
Added constraint: 'A0 = 'A10
Inferred (add i) : 'A11
Inferred -1 : int
Added constraint: 'A11 = ('A12 -> 'A13)
Added constraint: 'A12 = int
Inferred ((add i) -1) : 'A13
Added constraint: 'A0 = 'A14
Added constraint: 'A1 = 'A15
Added constraint: 'A13 = 'A14
Inferred (f ((add i) -1)) : 'A15
Inferred tail : (('A16 list) -> ('A16 list))
Inferred xs : 'A2
Added constraint: ('A16 list) = 'A17
Added constraint: ('A16 list) = 'A18
Added constraint: 'A2 = 'A17
Inferred (tail xs) : 'A18
Added constraint: 'A15 = ('A19 -> 'A20)
Added constraint: 'A18 = 'A19
Inferred ((f ((add i) -1)) (tail xs)) : 'A20
Added constraint: ('A9 list) = 'A20
Inferred ((head xs)::((f ((add i) -1)) (tail xs))) : 'A20
Added constraint: 'A5 = boolean
Added constraint: ('A6 list) = 'A20
Inferred (if (is_zero i) then [] else ((head xs)::((f ((add i) -1)) (tail xs)))) : ('A6 list)
Added constraint: ('A6 list) = 'A3
Inferred (fun g xs => (if (is_zero i) then [] else ((head xs)::((f ((add i) -1)) (tail xs))))) : ('A2 -> 'A3)
Added constraint: ('A2 -> 'A3) = 'A1
Inferred (fun f i => (fun g xs => (if (is_zero i) then [] else ((head xs)::((f ((add i) -1)) (tail xs)))))) : ('A0 -> 'A1)

Inferred type is: ('A0 -> 'A1)

Constraints:
('A2 -> 'A3) = 'A1
('A6 list) = 'A3
('A6 list) = 'A20
'A5 = boolean
('A9 list) = 'A20
'A18 = 'A19
'A15 = ('A19 -> 'A20)
'A2 = 'A17
('A16 list) = 'A18
('A16 list) = 'A17
'A13 = 'A14
'A1 = 'A15
'A0 = 'A14
'A12 = int
'A11 = ('A12 -> 'A13)
'A0 = 'A10
(int -> int) = 'A11
'A10 = int
'A2 = 'A8
'A7 = 'A9
('A7 list) = 'A8
'A0 = 'A4
'A5 = boolean
'A4 = int
        

Previous pageContentsNext page