Lectures onType Theory
ch:dependent-records: ch:dependent-records
appendix sectionsolutions

ch:dependent-records: ch:dependent-records

Exercise 79.1.

For p:PointedLoopi, p.Carrier:Ui,p.point:p.Carrier,p.loop:Idp.Carrier(p.point,p.point). The point search passes the visible loop field and then stops: p.point(p|loop).point0. The carrier search passes loop and point before projection beta: p.Carrier(p|loop).Carrier((p|loop)|point).CarrierN. Each restriction names the actual rightmost field stripped by that passing step: first loop, then point. Every step shortens the searched signature.

Exercise 79.2.

For neutral q, lookup typing gives q.point:q.Carrier and q.loop:Idq.Carrier(q.point,q.point). Neither term is headed by a record constructor, so neither contracts. Construction gives q|loop,loop=q.loop:PointedLoopi. The displayed computation rules reduce only constructor-headed restriction or projection. They contain no eta rule, so the new constructor is not judgmentally equal to q.

Exercise 79.3.

For a last field r, the candidate source equation translates to qS=?(pr1(qS),pr2(qS)). Sigma eta validates this target equality. The comparison theorem preserves source equality but does not reflect every equality of arbitrary target terms. In particular, no source rule maps back from this Sigma-eta step, so the source record-eta equation remains underivable from the displayed rules.

Exercise 79.4.

Define f(q):=q|r:L. This is an explicit term former, not a subsumption rule. If width subsumption were added, the raw term q:L would itself also have type L. Those types are not judgmentally equal, so ordinary uniqueness of types would fail. Under the Sigma translation, fS is the first projection fS:ρ:LSAS(ρ)LS,fS(q):=pr1(q). The selected calculus contains f but no width judgment.

Exercise 79.5.

The Pollack signature appends fields in the order Carrier, point, loop, name. The CPT translation reverses the association: Carrier:Ui,x.point:x,y.loop:Idx(y,y),z.name:2,w.1. Selecting point in the source passes name and loop, then projects point. In the target, (Carrier=N,(point=0,(loop=refl,(name=tt,())))).point passes Carrier once and then uses dot beta at point. Selecting Carrier is immediate in the target but passes name, loop, and point in that order in the left-associated source. These are the two association conventions described by the correspondence proof.

Search the book

Type to search the local edition.