Lectures onType Theory
ch:contextual-modal-tt: ch:contextual-modal-tt
appendix sectionsolutions

ch:contextual-modal-tt: ch:contextual-modal-tt

Exercise 63.1.

The modal lookup and the one-component substitution give u::A[x:A]ΔΔ;z:Az/x:x:AΔ;z:Aclo(u,z/x):AMeta. Applying Ctx-I yields Δ;y:Abox(z:A.clo(u,z/x)):[z:AA]. For the altered body, Ctx-I asks for Δ;z:Ay:A. Variable lookup fails because its ordinary context contains only z:A; the ambient declaration y:A is not a premise of the rule.

Exercise 63.2.

Substitution first reaches the neutral head and produces a canonical lambda: [λ(z:A).z/f]AAf=λ(z:A).z. The application clause would therefore create (λ(z:A).z)y. It does not return that noncanonical redex; it immediately continues with the lambda body at the domain approximation: [λ(z:A).z/f]AA(fy)=[y/z]Az=y. The term body need not be smaller than the original application, but the outer index has decreased strictly from AA to its proper subexpression A.

Exercise 63.3.

The normal component M/x forbids erasing x’s approximation, while the atomic component R//y permits either retaining or erasing y’s. The complete list is therefore (x:A,y:B)and(x:A,y:). There are no other choices. Erasing x’s type would lose the termination index needed if substituting its normal component creates a redex. The atomic component for y cannot create a head redex, so keeping B is safe but not required.

Exercise 63.4.

At the simply typed layer, let I=λ(x:A).x and take letbox(box(.I),u.clo(u,)). It has type AA and its box redex contracts to I. If the letbox occurs in function position, a commuting conversion must first expose that principal redex.

At the canonical layer, assume a closed constant c:A and a meta-variable u::(v::A[]A)[]. The atomic term mapp(clo(u,),^.c) synthesizes (A). Hereditarily substitute ^.mlam(v.clo(v,)) for (u). Substitution into the atomic head returns a meta-abstraction, so the contextual-application clause creates a meta-level beta-redex. It immediately substitutes ^.c for (v) in clo(v,), returning (c) at the strictly smaller domain approximation. Thus the first calculus normalizes an independently defined reduction relation, while the second contracts a newly created redex inside its typing computation. The examples do not transfer strong normalization between the calculi.

Practical route.

The Beluga scope experiment of exercise 63.5 is developed in appendix F. Its portable Kappa run, pinned Beluga source locator, and unavailable-toolchain boundary are recorded in appendix E.

Search the book

Type to search the local edition.