CS40032 Assignment 3-  Typed λ-Calculus  Solved     

Description

Instructions: Please solve the questions using pen and paper and scan the images. Every image should contain your roll number and name.

1. Derive the type of each lambda expression. Show all derivation steps.

[3 * 5 = 15]

• Given E₀ ∪ y : bool :

y := true

• Given type constants func1 : A → B and func2 : (C → B) :

λ(x : A).(func1 x);λ(q : C).(func2 q)

• Given | be a constant of type Bool → Bool → Bool and type of true is Bool λ(ω : Bool → π). λ(x : Bool). (ω (x | true))
• Given + is type constant with the type S →

λ(f : S → C). λ(x : S). f(+x)

• Given E₀ = {x : Ref Bool, y : Bool} and the constants succ : Int → Int, true : Bool, 4 : Int :

succ 4; x := true

2. Derive the type of each of the following expression. Any assumptions are welcome. [5 * 2 = 10]
   • Given the type of φ is Float → Integer

(λ(p : Float → Integer). λ(f : Float → Float). λ(y : Float). p (f (f y))) φ

• Given φ be the constant with the type Bool → Bool → Bool and true with the type Bool λ(func1 : Bool → Char). λ(τ : Bool). func1 (τ φ true)

1