== Type System ==
Augment interpreter.ml with the following data type
type typ = TBool | TInt
and exception
exception Type_error
and create the function: type_check : exp -> typ
let rec type_check (e : exp) = … insert code …
The function type_check takes in input an expression and returns the type of that expression according to the type system that we have seen in class, or the function raises the
OCaml exception Type_error when type checking fails.
Test type_check with the following inputs:
1) true is of type bool
(type_check True)
Output: TBool
2) false is of type bool
(type_check False)
Output: TBool
3) 0 is of type int
(type_check (Num 0))
4) iszero(0) is of type bool
(type_check (IsZero (Num 0)))
Output: TBool
5) iszero(1 + 1) is of type bool
(type_check (IsZero (Plus (Num 1, Num 1))))
Output: TBool
6) iszero((2 + -1) + 1) is of type bool
(type_check (IsZero (Plus (Plus (Num 2, Num (-1)), Num 1))))
Output: TBool
7) (-1 + 1) + (-1 + 1) is of type int
(type_check (Plus (Plus (Num (-1), Num 1), Plus (Num (-1), Num 1))))
Output: TInt
8) -1 + ((2 * 2) + 1) is of type int
(type_check (Plus (Num (-1), Plus (Mult (Num 2, Num 2), Num 1))))
Output: TInt
9) (((2 + -1) + 1) + -1) is of type int
(type_check (Plus (Plus (Plus (Num 2, Num (-1)), Num 1), Num (-1))))
Output: TInt
10) iszero(-1 + 1) + 1 is a Type_error
(type_check (Plus (IsZero (Plus (Num (-1), Num 1)), Num 1)))
11) iszero(if iszero(0) then true else 0) is a Type_error
(type_check (IsZero (If (IsZero (Num 0), True, Num 0))))
Output: Type_error
12) iszero(if iszero(5 * 0) then (if false then 0 else iszero(-1 + 0)) else 0) is a Type_error
(type_check
(IsZero (If
( IsZero (Mult (Num 5, Num 0))
, If (False, Num 0, IsZero (Plus (Num (-1), Num 0)))
, Num 0 ))))
Output: Type_error
13) if iszero(-1 + 1) then 2 else true is a Type_error
(type_check (If (IsZero (Plus (Num (-1), Num 1)), Num 2, True)))
Output: Type_error
14) if (if iszero((1 + -1) * 1) then false else true) then 1 * 2 else true is a Type_error
(type_check
(If
( If (IsZero (Mult (Plus (Num 1, Num (-1)), Num 1)), False, True)
, Mult (Num 1, Num 2)
, True )))
Output: Type_error
15) if (if iszero(0 * 0) then iszero(2) else 0) then 2 * (1 * 1) else ((((if iszero(0) then 1 else 0) + -1) + 1) + -1) + 1 is a Type_error
(type_check
(If
( If (IsZero (Mult (Num 0, Num 0)), IsZero (Num 2), Num 0)
, Mult (Num 2, Mult (Num 1, Num 1))
, Plus
( Plus
( Plus
( Plus (If (IsZero (Num 0), Num 1, Num 0), Num (-1))
, Num 1 )
, Num (-1) )
, Num 1 ) )))
Output: Type_error
16) if true then (if true then (if false then 0 else 1) * 1 else 5) else (4 * 1) + 1 is of type int
(type_check
(If
( True
, If (True, Mult (If (False, Num 0, Num 1), Num 1), Num 5)
, Plus (Mult (Num 4, Num 1), Num 1) )))
Output: TInt
17) if iszero(if iszero(-1 + 2) then 0 else 1) then (if true then (if false then (0 * 6) else 5) else 5 is of type int
(type_check
(If
( IsZero (If (IsZero (Plus (Num (-1), Num 2)), Num 0, Num 1))
, If
( True
, If (False, Mult (Num 0, Num 6), Plus (Num 0, Num 1))
, Num 5 )
, Num 5 )))
Output: TInt
18) if iszero(-1 + (1 + (-1 + 1))) then iszero(true) else 1 is a Type_error
(type_check
(If
( IsZero (Plus (Num (-1), Plus (Num 1, Plus (Num (-1), Num 1))))
, IsZero True
, Num 1 )))
Output: Type_error
19) 1 + (-1 + (if iszero(1 + (if true then 1 else 2)) then 1 + 2 else 2 * 2)) is of type int
(type_check
(Plus
( Num 1
, Plus
( Num (-1)
, If
( IsZero (Plus (Num 1, If (True, Num 1, Num 2)))
, Plus (Num 1, Num 2)
, Mult (Num 2, Num 2) ) ) )))
Output: TInt
20) -1 + (if iszero(5 + -4) then 123 * (5 + -4) else iszero(0)) is a Type_error
(type_check
(Plus
( Num (-1)
, If
( IsZero (Plus (Num 5, Num (-4)))
, Mult (Num 123, Plus (Num 5, Num (-4)))
, IsZero (Num 0) ) )))
Output: Type_error
IMPORTANT: TESTS ARE NUMBERED AND MUST BE PASSED SEQUENTIALLY TO OBTAIN THE SCORE BELOW.
Score:
Succeding tests 1-6 = 0.70
Succeding tests 7-13 = 0.71
Succeding tests 14-20 = 0.72