# refining mechanized metatheory: subtyping for lf

Post on 07-Feb-2016

27 views

Embed Size (px)

DESCRIPTION

Refining Mechanized Metatheory: Subtyping for LF. William Lovas (with Frank Pfenning). LF: a framework for defining logics. (Harper, Honsell, and Plotkin, 1987, 1993) Dependently-typed lambda calculus Encode deductive systems and metatheory, in a machine-checkable way - PowerPoint PPT PresentationTRANSCRIPT

Refining Mechanized Metatheory: Subtyping for LFWilliam Lovas(with Frank Pfenning)

LFMTP '07

LF: a framework for defining logics (Harper, Honsell, and Plotkin, 1987, 1993)Dependently-typed lambda calculusEncode deductive systems and metatheory, in a machine-checkable waye.g. a programming language and its type safety theorem

Guiding principle: judgements as types

LFMTP '07

Judgements as typesOn paper:Syntaxe ::= Judgement e : DeductionD :: e : Proof checking

In LF:Simple typeexp : type.Type familyof : exp tp type.Well-typed termM : of E TType checking

LFMTP '07

Inclusion as subtypingSome judgements have a natural notion of inclusionall values are expressionsall odd natural numbers are positive

More interesting types means more interesting judgements!

LFMTP '07

Example: natural numbersnat : type.z : nat.s : nat nat.

double : nat nat type. % plus rules

even : nat type. % plus some rulesodd : nat type. % plus some rules

dbl-even : X:nat. Y:nat. % plus casesdouble X Y even Y type.

LFMTP '07

Example: nats using refinementsnat : type.z : nat.s : nat nat.

double : nat nat type. % plus rules

even : nat type. % plus some rulesodd : nat type. % plus some rules

dbl-even : X:nat. Y:nat. % plus casesdouble X Y even Y type.nat : type. even nat. odd nat.z : even.s : even odd odd even.

double : nat even type. % plus rulesmetatheorem checking problem typechecking problem!

LFMTP '07

Example: nats using refinementsnat : type. even nat. odd nat.z : even.s : even odd odd even.

double : nat even type.

dbl-z : double z z.

dbl-s : X:nat. Y:even.double X Y double (s X) (s (s Y)).dbl-s : X:nat. Y:even.double X Y double (s X) (s (s Y)).

LFMTP '07

Example: the lambda calculusIntrinsic values encoding:exp : type.val : type.

lam : (val exp) val.app : exp exp exp.

$ : val exp.

lam (x. app ($ x) ($ x)) : valval exp.lam (x. app x x) : val

LFMTP '07

Technology

LFMTP '07

AdequacyDoes this really mean what I think it means?

Strategy: exhibit a compositional bijection between mathematical objects and canonical forms following judgements as types.canonical forms are -normal and -long.

LFMTP '07

Canonical forms methodRepresent only the canonical forms.-normal: syntactically-long: through typingHereditary substitutions contract redexesSimplifies metatheory, emphasizes adequacyConcurrent LF (Watkins, et al, 2003)

LFMTP '07

LF typingBidirectional typing

Synthesis: R Aelims: R ::= x | c | R NChecking: N Aintros: N ::= R | x. N

LFMTP '07

Checking

Key rule:base type, so atoms fully appliedthe only appeal to type equality N A

R P P = P R P

LFMTP '07

Checking with subtyping!

Easy to adapt!just change equality to subtypingsubtyping only at base type? N A

R P P P R P

LFMTP '07

IntersectionsKind of like pairs, but the terms dont change

N A1 N A2 N A1 A2

N

R A1 A2 R A1

R A1 A2 R A2

LFMTP '07

Metatheory

LFMTP '07

LF(R) as a logicEntailment should be reflexive:A Aand transitive:if A B and B C, then A C

LFMTP '07

LF(R) as a logicAssume x is a proof of A. Is x a proof of A?not necessarily! x : A1 A2 x A1 A2have to -expand: x : A1 A2 y. x y A1 A2

LFMTP '07

LF(R) as a logicAssume x is a proof of A. Can M A stand in for x?if substitution is hereditary? [M/x]A N not obviously defined

LFMTP '07

Important principlesSubstitution if , x:A N B and M A , then [M/x]A N [M/x]A B .Identity for all A, , x:A A(x) A .

Substitution morally a normalization proof

LFMTP '07

More about subtyping

LFMTP '07

Subtyping

Key rule:

Bidirectional: subtyping only at mode switchCanonical: mode switch only at base type N A

R P P P R P

LFMTP '07

Subtyping at higher types?What happened to the structural rules? E.g.,

Distributivity?

A2 A1 B1 B2A1 B1 A2 B2

(A B1) (A B2) A (B1 B2)

LFMTP '07

Subtyping at higher types!Intrinsic subtyping: if A B and N A , then N B .Equivalently: if A B then x:A A(x) B .Just like the Identity principle! also the Substitution principleUsual rules are all sound in this sense.

LFMTP '07

Subtyping at higher types!? and also complete!Theorem: if x:A A(x) B then A B .Also: if N A implies N B , then A B .

There are no new subtyping principles.

LFMTP '07

Future workTwo directions:Extend LFR with Twelf stufftype reconstructionunificationproof searchExtend LFR with CLF stuffmore type constructorssubtyping with linearity?

LFMTP '07

SummaryRefinement types are a useful addition to LF.Canonical forms method is up to the task.Concentrating only on canonical forms and bidirectional typing yields new insights into subtyping.

LFMTP '07

secret slides

LFMTP '07

Related workRefinement typesTim Freeman, Rowan Davies, Joshua DunfieldLogical frameworksRobert Harper, Furio Honsell, Gordon Plotkin Frank PfenningSubtyping and dependent typesDavid Aspinall, Adriana Compagnoni

LFMTP '07

LF syntaxTerms

TypesR ::= c | x | R NN ::= R | x. NP ::= a | P NA, B ::= P | x:A.Batomicnormalatomicnormalno redexes

LFMTP '07

Hereditary substitutionSubstitution must contract redexes Example:

Indexed by type subscript for termination

Sometimes undefined:[(x. d x x) / y] y z = d z z[M/x]A N[(x. x x) / y]A y y fails by induction on A

LFMTP '07

Synthesis R Ahereditary substitution

R x:A.B N A R N [N/x]A B

x:A x A

c:A c A

LFMTP '07

Checking N A

R P P = P R P

, x:A N B x.N x:A.B

LFMTP '07

Example: the lambda calculusexp : type.val exp.

lam : (exp exp) exp.app : exp exp exp.

value : exp type.lam : (val exp) val.

LFMTP '07

s a :: L

R P P P R P

LFMTP '07

SubtypingKey rule:

Bidirectional: subtyping only at mode switchCanonical: mode switch only at base typesubtyping only at base type!

LFMTP '07

, x:A M B eabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

R A

LFMTP '07

Evident judgement =~ Inhabited type familySome judgements mostly syntactic ones

Since under judgements as types, its natural to regard judgemental inclusion as subtyping, this suggests that adding subtyping to LF might be worthwhile.

NB: In the paper we take care to distinguish sorts, or refinements, from types. In the talk, Ill gloss over that distinction and say all we have are types.fact that double returns an even number is evident in its type.in other words, weve replaced a meta-theorem with a statically checkable property.

Lets see that a little more closelyThe key of course is that we declare Y to be even. If Y is even, then (s Y) is odd, and (s (s Y)) is again even.Simple as that!

Lets see another example.No special coercions or anything

Thats the why, what about the how?A very successful and modern view of LF is the canonical forms methodology.

Hereditary substitution might not always be defined. Some terms have no normal form.R stands for atomic terms, which are variables, constants, or eliminations of atomic termsN stands for normal terms. Note that atomic terms are included in the normal terms.Key rule: switch modes from checking to synthesis. All other places you might want to use type equality bubble up to this rule.and subtyping at base type is just declared, basically.Isnt it interesting, though, that we only need to define a subtyping judgement at base type?Ill come back to that in a minute.Standard straightforward canonical forms method: intros are checked, elims are synthesizing.Rules are now nondeterministic, but thats okay doesnt hurt anything.

So whats the downside?While canonical forms makes the metatheory simpler overall, it does introduce some unexpected gotchas.mighty 3-D less-than signKey rule: switch modes from checking to synthesis. All other places you might want to use type equality bubble up to this rule.Doesnt make sense to add rules theyd never get used!A B here is the *full* structural relation.Worth pausing: this is a *strong* theorem.Have we left out any rules? Well, no.. we havent!

So, where do we go from here?novel challenges presented by nondeterminism of subtyping and intersectionsnot clear how subtyping interacts with linearity, if at allThanks for listening. (Should I mention questions at all?)undefined only finitelyNo special coercions or anything!!! next slide is transition !!!