Lectures onType Theory
Evaluation-strategy source and target calculi
appendix sectionrules

Evaluation-strategy source and target calculi

The source formulas and terms of chapter 37 are A,B::=ZAB,M,N::=xλx.MMN. Contexts are finite maps with exchange. Besides the ordinary variable, abstraction, and application rules, their structural rules are ΓM:BΓ,x:AM:BSWeakΓ,x:A,y:AM:BΓ,z:AM[x:=z,y:=z]:BSContr. The beta rule is unrestricted in name and has a value premise V::=xλx.M in val.

The lin target formulas and terms are A,B::=Z!AAB,L,M,N::=x!Mλx.MMN::=let !x=M in N. An assumption x:A is linear and !x:!A is exponential. Context juxtaposition below requires disjoint variable domains. Xx:Ax:ALIdΓ,x:AM:BΓ,!x:!AM:BLDer ΓM:BΓ,!x:!AM:BLWeakΓ,!x:!A,!y:!AM:BΓ,!z:!AM[x:=z,y:=z]:BLContr !ΓM:A!Γ!M:!ALBangIΓM:!AΔ,!x:!AN:BΓ,Δlet !x=M in N:BLBangE Γ,x:AM:BΓλx.M:ABLLamΓM:ABΔN:AΓ,ΔMN:BLApp. Here !Γ changes every x:A in Γ to !x:!A. Reduction is the compatible closure of (λx.M)NlinM[x:=N],let !x=!M in NlinN[x:=M],(let !x=L in M)Nlinlet !x=L in (MN),let !y=(let !x=L in M) in Nlinlet !x=L in (let !y=M in N).

The call-by-let source adds let x=M in N, its ordinary typing rule, and Let-I, Let-V, Let-C, and Let-A from definition 37.7. The call-by-need source adds Need-G. The affine target replaces L-Weak by ΓM:BΓ,x:AM:BAWeak for arbitrary A, retains exponential-only contraction, and adds Aff-Weak. No source or target in this sheet contains products, sums, recursion, effects, or a deterministic evaluation-context rule.

Search the book

Type to search the local edition.