Code in F#.

This language has three types: I for integers, B for booleans, and IB for expressions (such as fail) that can be used both as integers and booleans. The function infer : expr -> typ is meant to infer the type of an expression. (i) Implement the function getCommonType : typ -> typ -> typ. This function is used to infer the type of an If. It is meant to check that the branches have compatible types, and to find the common type of the two branches if they are compatible. It should raise an F# exception (use failwith) if the two types are incompatible. You need to be careful with IB: the expression if 0 < x then 0 else fail should have type I, and the expression if 0 < x then fail else fail should have type IB. (ii) Implement the Try case of infer. This should check that the two subexpressions have com- patible types using getCommonType.

Here is the code that needs to be implemented:

let getCommonType (t1 : typ) (t2 : typ) : typ =

failwith "Not implemented"

let rec infer (e : expr) : typ =

match e with

| Var x -> I

| Let (x, erhs, ebody) ->

match infer erhs with

| I | IB -> infer ebody

| B -> failwith "variables must be integers"

| Num i -> I

| Plus (e1, e2) ->

match infer e1, infer e2 with

| I, I | I, IB | IB, I | IB, IB -> I

| _, _ -> failwith "wrong operand type"

| Times (e1, e2) ->

match infer e1, infer e2 with

| I, I | I, IB | IB, I | IB, IB -> I

| _, _ -> failwith "wrong operand type"

| True -> B

| False -> B

| LessThan (e1, e2) ->

match infer e1, infer e2 with

| I, I | I, IB | IB, I | IB, IB -> B

| _, _ -> failwith "wrong operand type"

| Or (e1, e2) ->

match infer e1, infer e2 with

| B, B | B, IB | IB, B | IB, IB -> B

| _, _ -> failwith "wrong operand type"

| And (e1, e2) ->

match infer e1, infer e2 with

| B, B | B, IB | IB, B | IB, IB -> B

| _, _ -> failwith "wrong operand type"

| If (econd, etrue, efalse) ->

match infer econd with

| B | IB -> getCommonType (infer etrue) (infer efalse)

| I -> failwith "if condition of type integer"

| Fail -> IB

| Try (etry, ecatch) ->

failwith "Not implemented"

| Choose [] -> IB

| Choose (e :: es) -> getCommonType (infer e) (infer (Choose es))