A Short Introduction to Logic Summer School on Proofs as Programs 2002 Eugene (Oregon) Stefano Berardi Università di Torino [email protected] http://www.di.unito.it/~stefano 1 The text of this short course on Logic, together with the text of the next short course on Realizability, may be found in the home page of the author http://www.di.unito.it/~stefano (look for the first line in the topic TEACHING) 2 Plan of the course • Lesson 1. Propositional Calculus. Syntax and Semantic. Proofs (Natural Deduction style). Completeness Result. • Lesson 2. Predicate Calculus. Syntax and Semantic. Proofs (Natural Deduction style). • Lesson 3. Gödel Completeness Theorem. Validity. Completeness. • Lesson 4. Strong Normalization. Intuitionistic Logic. Strong Normalization. Structure of Normal proofs. • Next Course: Realization Interpretation. 3 Reference Text • Logic and Structure. Dirk van Dalen. 1994, Springer-Verlag. Pages 215. 4 Using the Textbook • 1. 2. 3. • • • What we skipped: Model theory of Classical Logic (most of §3) Second Order Logic (§ 4) Model theory of Intuitionistic Logic (in §5) Roughly speaking: Lessons 1,2,3,4 correspond to sections §1, §2, §3 and 4, §5 and 6 of Van Dalen’s textbook. Roughly speaking (and on the long run): in these Course Notes, one slide corresponds to one page of Van Dalen’s book. 5 Lesson 1 Propositional Calculus Syntax Semantic Proofs Completeness 6 Plan of Lesson 1 • We will quickly go through Syntax and Semantic of Propositional Calculus again. • § 1.1 Syntax. The set of formulas of Propositional Calculus. • § 1.2 Semantic. Truth tables, valuations, and tautologies. • We will really start the course from here: • § 1.3 Proofs. We introduce Natural Deduction formalization of Propositional Calculus. • § 1.4 Completeness. We prove that logical rules prove exactly all “true” propositions. • Forthcoming Lesson: First Order Logic 7 § 1.1 Syntax • The symbol of the language. • Propositional symbols: p0, p1, p2, … • Connectives: (and), (or), (not), (implies), (is equivalent to), (false). • Parenthesis: (, ). 8 § 1.1 Syntax • 1. 2. 3. 4. The set PROP of propositions: the smallest closed under application of connectives: PROP pi PROP for all iN PROP ()PROP ,PROP (), ( ), (), () PROP 9 § 1.1 Syntax • • • • • • Examples: (p0) ((p0)) (p0 (p1 p2)) (p0 (p1 p2)) Correct expressions of Propositional Logic are full of unnecessary parenthesis. 10 § 1.1 Syntax • Abbreviations. Let c=, , . We write p0 c p1 c p2 c … • in the place of (p0 c (p1 c (p2 c …))) • Thus, we write p0 p1 p2, p0p1 p2, … • in the place of (p0 (p1 p2)), (p0 (p1 p2)) 11 § 1.1 Syntax • We omit parenthesis whenever we may restore them through operator precedence: • binds more strictly than , , and , bind more strictly than , . • Thus, we write: • p0 for ((p0)), • p0 p1 for ((p0 ) p1) • p0 p1 p2 for ((p0 p1) p2), … 12 § 1.1 Syntax • • Outermost symbol. The outermost symbol of , pi , , (), (), (), () are, respectively: , pi , , , , , 13 § 1.1 Syntax • 1. 2. 3. • • Immediate Subformulas : Of and pi are none Of is Of (), ( ), (), () are , is a subformula of iff there is some chain =0, …, n=, each formula being some immediate subformula of the next formula. Subformulas of =((p0 p1) p2) are: itself, (p0 p1), p0, p1, p2. 14 § 1.2 Semantic • • • • • Interpreting Propositional constant and connective. Each proposition pi may be either T (true) or F (false). is always F (false). , , , , are interpreted as unary or binary map (or Truth Tables), computing the truth of a statement , (), (), (), (), given to the truth of immediate subformulas , . 15 § 1.2 Semantic • Truth table of . =T =F =F =T 16 § 1.2 Semantic • Truth table of . =T =F =T = T = F = F = F = F 17 § 1.2 Semantic • Disjunction is taken not exclusive: if , then both , may be true. =T =F =T = T = T = F = T = F 18 § 1.2 Semantic • Implication is “material”: is true also for unrelated statements , : it only depends on the truth values of , . =T =F =T = T = T = F = F = T 19 § 1.2 Semantic • Equivalence is identity of truth values. =T =F =T =T =F =F =F =T 20 § 1.2 Semantic • Inductive definition. Fix any set I, any map v:NI, any bI, and for any unary (binary) connective c, some unary (binary) map Tc on I. • Then there is exactly one map h:PROPI, such that: • f(pi) = v(i) I for all iN, • f() = b I • f() = T(f()) I • f( c ) = Tc(f(), f()) I for all binary connectives c 21 § 1.2 Semantic • • 1. 2. • A Valuation is any map v:N{T,F}, assigning truth values to Propositional constants. Interpreting Propositional formulas. Any valuation v may be extended by an inductive definition to some map h:PROP{T,F}, by: mapping into b=False, using, as Tc, the truth table of connective c= , , , , . For all PROP, we denote h() by []v {T,F} 22 § 1.2 Semantic • • • • Let PROP. Tautologies. is a tautology iff for all valuations v we have []v =T. Contradictions. is a contradiction iff for all valuations v we have []v =F. Tautology conveys our intuitive idea of being “logically true”, or “true no matter what the Propositional constants are”. 23 § 1.2 Semantic • • • • • Some examples of tautologies Double Negation Law: . Excluded Middle: . An easy exercise: check that is a tautology, i.e., that []v = True for all valuations v:N{T,F}. 24 § 1.3 Proofs • • • • Formal Proofs. We introduce a notion of formal proof of a formula : Natural Deduction. A formal proof of is a tree whose root is labeled , and whose children are proofs of the assumptions 1, 2, 3, … of the rule r we used to conclude . 25 § 1.3 Proofs • • • • Natural Deduction: Rules. For each logical symbol c=, , , , and each formula with outermost connective c, we give: A set of Introduction rules for c, describing under which conditions is true; A set of Elimination rules for c, describing what we may infer from the truth of . Elimination rules for c are justified in term of the Introduction rules for c we chose. 26 § 1.3 Proofs • • • • Natural Deduction: the missing connectives. We treat , , as abbreviating (), ()(), We do not add specific rules for the connectives , . 27 § 1.3 Proofs • • • • Natural Deduction: notations for proofs. Let be any formula, and be any unordered (finite or infinite) list of formulas. We use the notation … abbreviated by |- , for: “there is a proof of whose assumptions are included in ”. 28 § 1.3 Proofs • • • Natural Deduction: crossing assumptions. we use the notation , \ … for: “we drop zero or more assumptions equal to from the proof of ”. 29 § 1.3 Proofs • • • Natural Deduction: assumptions of a proof 1 2 3 … r ------------------------------- are inductively defined as: all assumptions of proofs of 1, 2, 3, …, minus all assumptions we “crossed”. 30 § 1.3 Proofs • • • • Identity Principle: The simplest proof is: having 1 assumption, , and conclusion the same . We may express it by: |-, for all We call this proof “The Identity Principle” (from we derive ). 31 § 1.3 Proofs • • • Rules for Introduction rules: none ( is always false). Elimination rules: from the truth of (a contradiction) we derive everything: --- • If |- , then |-, for all 32 § 1.3 Proofs • • Rules for Introduction rules: ------- • If |- and |- then |- 33 § 1.3 Proofs • • Elimination rules: ------- ------ If |- , then |- and |- 34 § 1.3 Proofs • • • Rules for Introduction rules: ------- ------ If |- or |- , then |- 35 § 1.3 Proofs • Elimination rules: … … ------------------------------------- \ • • \ If |- and ,|- and , |-, then |- We may drop any number of assumptions equal to (to ) from the first (from the second) proof of 36 § 1.3 Proofs • Rules for Introduction rule: … ------- \ • • If , |- , then |- We may drop any number of assumptions equal to from the proof of . 37 § 1.3 Proofs • • Elimination rule: --------------- If |- and |-, then |- . 38 § 1.3 Proofs • The only axiom not associated to a connective, nor justified by some Introduction rule, is Double Negation: …. -- If , |- , then |- We may drop any number of assumptions equal to from the proof of . \ • • 39 § 1.3 Proofs • 1. 2. • • • Lemma (Weakening and Substitution). If |- and p, then p|-. If |- and , |-, then |- . Proof. Any proof with all free assumptions in has all free assumption in p. Replace, in the proof of with free assumptions all in ,, all free assumptions by a proof of with all free assumptions in . 40 § 1.4 Completeness • • • • Definition (Validity). |- is valid iff for all valuations v such that v(){True}, we have v()=True (iff for no valuation v we have v(){True}, v()=False). Validity conveys the idea “|- is true no matter what the Propositional constants are”. Definition (Consistency). is consistent iff (|) is false (if does not prove ). Definition (Completeness). is complete iff for all propositions , either |- or |- . 41 § 1.4 Completeness Correctness. If |- is true in Natural Deduction, then |- is valid. • Proof. Routine. By induction over the proof of |-, considering: 1. one case for each introduction and elimination rule, 2. one for the Identity rule, 3. one for Excluded middle. • 42 § 1.4 Completeness • Completeness Theorem. If |- is valid, then then |- is derivable in Natural Deduction. • • • Proof. We will pass through many Lemmas: Lemma 1 (Consistency). If |- is not derivable, then , is consistent. Lemma 2 (Consistent Extension). For all formulas , if is consistent, then either , or , is consistent. • 43 § 1.4 Completeness • • • Lemma 3 (Complete Consistent extension). Any consistent set may be extended to some consistent complete set ’. Lemma 4 (Valuation Lemma). For every complete consistent consistent set there is some valuation v such that v()={True}. Lemma 5 (2nd Valuation Lemma). For every consistent set there is some valuation v such that v(){True}. 44 § 1.4 Completeness • Lemma 1 (Consistency). If |- is not derivable, then , is consistent. • Proof. We will prove the contrapositive: if , |-, then |-. This statement follows by Double Negation. 45 § 1.4 Completeness • Lemma 2 (Consistent Extension). For for all formulas , if is consistent, then either , or , is consistent. • Proof. We will prove the contrapositive: if ,|- and ,|-, then |-. 1. From ,|- and -Intr. we deduce |-. 2. From |- (by 1 above), the hypothesis ,|-, and Substitution, we conclude |-. 46 § 1.4 Completeness • Lemma 3 (Complete Consistent extension). Any consistent set may be extended to some consistent complete set ’ (such that for all formulas , either ’|- or ’ |- ). • Proof. Fix any numbering of formulas 0, …, n, … . Let 0, …, n, … be the sequence of sets of formulas defined by: 0 = n+1 = n, n, if n, n is consistent n+1 = n, n if n, n is not consistent • • • 47 § 1.4 Completeness • • • Proof of Complete Consistent Extension . (Consistency) By the Consistent Extension lemma, if n is consistent then n+1 is. Since 0 = is consistent, then all n are consistent. Thus, = nn is consistent (a proof of with assumptions in would have all assumptions in some n). (Completeness) By construction, includes, for all formulas n, either n or n. By the Identity Principle, in the first case |-n, in the second one |-n . 48 § 1.4 Completeness • Lemma 4 (Valuation Lemma). For every complete consistent set there is some valuation v such that v()={True}. • • • • • Proof. Define v()=T iff |-. We have to prove: v() =F v( ) = T v()=T or v()=T v( ) = T v()=T and v()=T v( ) = T v()=F or v()=T 49 § 1.4 Completeness • v() = F because |- is false, by consistency of . 50 § 1.4 Completeness • • • v( ) = T v()=T or v()=T Left-to-Right. Assume for contradiction v()=F and v()=F. By Completeness of , |- and |- are true. By -Elim., we have ,|- and ,|-. From |- (by hyp.) and -Elimination we conclude |-, against the consistency of . Right-to-Left. If |- or |-, then |- by -Introduction. 51 § 1.4 Completeness • • • v( ) = T v()=T and v()=T Left-to-Right: by -Elimination. Right-to-Left: by -Introduction. 52 § 1.4 Completeness • • • 1. 2. v( ) = T v()=F or v()=T Left-to-Right: If v()=F, we are done. If v()=T, then |-, and by -E |-, v()=T. Right-to-Left. Assume either v()=F or v()=T, in order to prove v()=T. Case v()=F. By completeness of , we have |-. Then ,|- by -Elimination, and ,|- by Elimination. We conclude |- by -Introduction. Case v()=T. If |-, then |- by some Introduction crossing no assumptions . 53 § 1.4 Completeness • • Lemma 5 (2nd Valuation Lemma). For every consistent set there is some valuation v such that v(){True}. Proof. Extend to some complete consistent set ’, and find some valuation v such that v(’)={True}. From ’ we conclude v(){True}. 54 § 1.4 Completeness • Proof of Completeness Theorem (end). If |- is not derivable, then , is consistent. Thus, for some v:N{T,F} we have v(){T}, v()=T, therefore v()=F. We conclude that |- is not valid. 55 Appendix to § 1 • • • Some Tautologies (Exercises). Hilbert-style formalization (the idea). Sequent Calculus (the idea). 56 Appendix to § 1 • • Some examples of Tautologies. All formulas which follow may be proved to be tautology in two ways: 1. using the inductive definition of []v ; 2. using proofs in Natural Deduction, together with the identifications of , with (), ()(). 57 Appendix to § 1 • • • Associativity of , : ( ) ( ) • • • Commutativity of , : 58 Appendix to § 1 • • • Distributivity of , : ( ) ( ) ( ) ( ) ( ) ( ) • • • De Morgan’s Laws: ( ) ( ) 59 Appendix to § 1 • • • • • • • Idempotency of , : Characterizing Implication () Characterizing Equivalence ( ) () () 60 Appendix to § 1 • • • • • • • • Proof of: Excluded Middle is a tautology. []v = T([]v ,[]v) = T([]v,T([]v)) Case []v = True: [ ]v = T(True, T(True)) = T(True, False) = True. Case []v = False: [ ]v = T(False, T(False)) = T(False, True) = True. 61 Appendix to § 1 • 1. 2. 3. 4. 5. 6. 7. 8. 9. How to deduce Excluded Middle out of Double Negation: By the Id. Princ. (), |- By -Introd. on 1 (), |- By the Id. Princ. (), |- () By -Elim. on 2, 3 (), |- By -Introd. on 4 () |- By -Introd. on 5 () |- By the Id. Princ. () |- () By -Elim. on 6, 7 () |- By Double Neg. on 8 |- 62 Appendix to § 1 • • Modus Ponens: if and are tautologies, then is a tautology. Proof. Let v:N{T,F}. By hyp., []v = []v = True. We have to prove []v = True. If it were []v = False, then by []v = True we would conclude []v = False. This contradicts the hypothesis []v = True. 63 Appendix to § 1 • A first alternative formalization of proofs of Propositional Calculus: • Hilbert-style formalization. • We fix a set X of axioms, and we inductively define the set T of theorems: 1. All axioms are theorems. 2. If , are theorems, then is a theorem. 64 Appendix to § 1 • Hilbert-Style Proofs may be seen by trees 1. whose root is the formula being proved, and 2. whose children are • none if is an axiom, and • are the proofs of , , if has been proved by Modus Ponens. 65 Axioms Hilbert-style proofs Appendix to § 1 • • • In order to give some Hilbert-style formalization for Propositional logic, we have to fix some set X of tautologies, able to derive all tautologies through Modus Ponens. Using Hilbert-style axiomatization we describe the notion of truth for Propositional logic, but we miss an intuitive understanding of the notion of (formal) proof. We prefer to introduce the notion of formal proof through Natural Deduction. 67 Appendix to § 1 • • • • A second alternative formalization of proofs of Propositional Calculus: Sequent Calculus. We may in fact introduce proofs independently as rules to derive a sequent |- rather than a formula. The resulting notation for proofs is rather cumbersome to use: we prefer Natural Deduction. Sequent notation is instead convenient if we work in Type Theory or in Automated Deduction: in this case we have to precise the pair: assumptions /thesis . 68 Lesson 2 Predicate Calculus. Syntax Semantic Proofs 69 Plan of Lesson 2 • § 2.1 Syntax. The set of formulas of First Order Logic. • § 2.2 Semantic. Interpreting formulas of First Order Logic. • § 2.3 Proofs. We introduce Natural Deduction formalization of First Order Logic. • Previous Lesson: Propositional Logic • Forthcoming Lesson: Completeness Theorem 70 § 2.1 Syntax: The symbol of Predicate Calculus. • Predicate Symbols: P, Q, R, …, of integer arity n0, n1, n2, …. • They should include a name “=” for equality. • Function Symbols: f, g, h, ……, of integer arity m0, m1, m2, … • Variables: x0, x1, x2, … • Connectives: (and), (or), (not), (implies), (is equivalent to), (false), and quantifiers: (exists), (for all). • Parenthesis: (, ). 71 § 2.1 Syntax • The set TERM of (first order) terms: the smallest set including variables, and closed under application of functions symbols: 1. xiTERM for all iN 2. t1, …, tmTERM, f function name of arity m f(t1,…, tm)TERM, for all i, mN 72 § 2.1 Syntax • • • • • • Examples of (first order) terms Any variable: x, y, z, … If we have 0-ary (constant) function symbols a, b, c, then a, b, c are also terms To show it, just apply a, b, c to the empty sequence of terms. If f is unary, g is binary, then f(f(c)), g(f(a),b), g(x,y) are terms 73 § 2.1 Syntax • • The set ATOM of atomic formulas: If t1, …, tnTERM, P predicate name of arity n P(t1,…, tn)ATOM, for all nN • Examples: if P is unary, Q is binary, then c=f(x), P(f(f(c))), Q(z, g(f(a),b)), P(g(x,y)) • are atomic formulas 74 § 2.1 Syntax • • • • The set FORM of (first order) formulas: the smallest including atomic formulas, and closed under application of connectives: ATOM FORM FORM, x variable (), (x), (x)FORM ,PROP (), (), (), () PROP 75 § 2.1 Syntax • • • • • • Examples of formulas: (P(f(f(c)))) ((P(g(x,y)) )) ((xP(x)) (P(y) P(z))) (x(P(x) (P(y) P(z)))) Correct formulas require parenthesis. unnecessary 76 § 2.1 Syntax • Abbreviations. Let c=, , . We write p0 c p1 c p2 c … • in the place of (p0 c (p1 c (p2 c …))) • Besides, we write xy, xyz … • in the place of (x(y)), (x(y(z))) • We also use x,y for xy. 77 § 2.1 Syntax • We omit parenthesis whenever we may restore them through operator precedence: • , , bind more strictly than , , and , bind more strictly than , . • Thus, we write: • P(a) for ((P(a))), • P(a) Q(x,y) for ((P(a)) Q(x,y)) • xP(x) P(y) P(z) for ((xP(x)) (P(y) P(z))) • xP(x)P(y)P(z) for (((xP(x))P(y)) P(z)) 78 § 2.1 Syntax • Outermost symbol. The outermost symbol of x, f(t1,…, tn), P(t1,…, tn), , , x, x, (), (), (), () • are, respectively: x, f, P, , , , , , , 79 § 2.1 Syntax • 1. 2. 3. • • Immediate Subformulas of: and P(t1,…, tn), are none , x, x is (), (), (), () are , is a subformula of iff there is some chain =0, …, n=, each formula being some immediate subformula of the next formula. Subformulas of =xP(x) P(y) P(z) are: itself, xP(x), P(x), P(y)P(z), P(y), P(z) 80 § 2.1 Syntax • • • • • • • • • Free variables. We define free variables by induction over the definition of a term or a formula. FV(x) =x FV(f(t1,…, tm)) = FV(t1) … FV(tm) FV(P(t1,…, tm)) = FV(t1) … FV(tm) FV() = FV() FV(x)=FV(x) = FV()-{x} FV( c ) = FV() FV() We call closed a term (formula) e if FV(e)=. We call closed a set of closed terms (formulas). 81 § 2.1 Syntax • • • • • • • Substitution. We define substitution e[x:=t] of a variable x by a term t by induction over e (term or formula). Terms: y[x:=t] =t if y=x y[x:=t] =y if yx f(t1,…, tm)[x:=t] = f(t1[x:=t],…, tm[x:=t]) Atomic Formulas: P(t1,…, tm)[x:=t]) = P(t1[x:=t],…, tm[x:=t]) 82 § 2.1 Syntax • • • • • Substitution (Formulas). Let Q=, be any quantifier, c=, , , be any binary connective. ()[x:=t] = ([x:=t]) ( c )[x:=t] = [x:=t] c [x:=t] (Qy)[x:=t] = Qy if y=x (Qy)[x:=t] = Qy([x:=t]) if yx 83 § 2.1 Syntax • • • Binder. A binder for x in is any subformula x or x of . Free and Bound occurrences. An occurrence of x in is bound iff x is inside some binder of x in , free in the opposite case. A substitution e[x:=t] is sound iff no free occurrence of variable in t becomes bound after substitution. 84 § 2.1 Syntax • • • Renaming. ’ is a renaming of iff ’ is obtained out of by replacing some subformula Qx by Qy[x:=y], with yFV(), and [x:=y] sound substitution. Convertibility. We that two formulas are convertible iff there is a chain of renaming transforming one into the other. We identify formulas up to convertibility. Intuitively, if , ’ are convertible, then they express the same meaning using different names for bound variables. 85 § 2.1 Syntax • • • • • Substitution may always be considered sound. Lemma (Substitution). For all substitutions [x:=t] there is some suitable ’ convertible to such that ’[x:=t] is sound. We omit the proof (it is conceptually simple, but rather cumbersome). Thus, any substitution [x:=t] becomes sound after some renaming. As a consequence, the result of a substitution is determined only up to renaming. 86 § 2.2 Semantic • Structure M for a first order language: • A universe M of M, not empty. • For each Predicate Symbols: P, Q, R, …, of integer arity n, n’, n”, …, some predicates PMMn, QM Mn’, RM Mn”, • interpreting P, Q, R, … . • For each Function Symbols: f, g, h, ……, of integer arity m, m’, m”, … some functions fM MnM, gM Mn’M, hM Mn”M, • interpreting f, g, h, … . 87 § 2.2 Semantic • Equality. Interpretation =M of the equality name should be the equality predicate. • This condition may be weakened to: =M is some equivalence relation compatible with all predicate and functions of M. • In this case, we obtain a structure by taking the quotient M/=M. • Constants, i.e., names c of functions of arity 0, are interpreted by cMM. 88 § 2.2 Semantic • Interpreting terms. Let M be any model. Every map v:{0,1,2,…}M may be extended to some map [.]v, M :TERMSM • If M is fixed, we abbreviate [.]v, M by [.]v. • We define [.]v,M by induction over the definition of a term. • [xi]v = v(i) M • [f(t1,…, tm)] v, M = fM([t1]v,…, [tn]v) M 89 § 2.2 Semantic • Interpreting atomic formulas. Let M be any model. Every map v:{0,1,2,…}M from indexes of variables to M may be extended to some map [.]v,M: ATOMS {True, False}. 1. First, we extend v to a map [.]v, M on all terms 2. Then we define [P(t1,…,tm)]v,M=True if ([t1]v,M,…,[tn]v,M)PM [P(t1,…, tm)]v, M = False if ([t1]v, M ,…, [tn]v, M )PM 90 § 2.2 Semantic • • Case definition. If v:{0,1,2,…}M, and mM, by v[xi:=m] we denote the map :{variables}M defined by cases: 1. v[xi:=m](j) 2. v[xi:=m](j) =m = v(j) if i=j if ij 91 § 2.2 Semantic • Let M be any model. We extended every map v:{variables}M to some map [.]v, M : ATOMS {True, False}, • We will now extend [.]v, M to some map [.]v, M : FORMULAS {True,False}, • by induction over the definition of a formula. • We distinguish several cases, according if the outermost connective of is , , , , , , 92 § 2.2 Semantic • Let Tc be the truth table of c=,,,,. • []v,M = T([]v,M ) for c=,,,: • [ c ] v,M = Tc([]vM,[]v,M), • [x]v • [x]v • [x]v • [x]v = True, iff []v[x:=m],M = True for some mM = False, otherwise. = True, iff []v[x:=m],M = True for all mM = False, otherwise. 93 § 2.2 Semantic • We extend [.]v,M to sets of formulas, by []v,M = {[]v,M | } • We also write M|=v, or “ is true in M under substitution v”, for []v,M = True. 94 § 2.2 Semantic • • • Substitution Theorem. Substitution on is interpreted by substitution on the valuation map v. Let m=[t]v,M: [[x:=t]]v,M = []v[x:=m],M , • If xFV(), then [x:=t]= and therefore []v[x:=m],M = []v,M. • Proof. See Van Dalen’s book. 95 § 2.2 Semantic • • • • • Lemma (Quotient Lemma). Take any structureM in which =M is some equivalence relation compatible with all predicate and functions of M. Consider the quotient structure M/=M. This structure satisfies the same formulas as M: M |=v (M /=M ) |=v Proof. By induction over , using compatibility of =M with all predicate and function names. Thus: in order to define a structure with an equality relation =M, it is enough to define some equivalence relation =M compatible with all predicate and functions of M. 96 § 2.3 Proofs • From the Propositional case, we keep 1. Double Negation Rule. 2. Introduction and Elimination rules for each logical symbol c = , , , . 3. Abbreviations for connectives , . • The rules we have to add are: 1. Introduction and Elimination for , , and 2. Rules for atomic formulas, including Equality. 97 § 2.3 Proofs • • Rules for : Introduction rule. … [x:=t] --------x • If |-[x:=t] for some t, then |- x 98 § 2.3 Proofs • Rules for : Elimination rule. , … … x --------------- Provided xFV(,). • If |-x, ,|-, and xFV(,), then |- • \ 99 § 2.3 Proofs • • • Rules for : Introduction rule. … -----x Provided xFV() If |- and xFV(), then |-x 100 § 2.3 Proofs • Rules for : Elimination rule. … x --------[x:=t] • If |- x, then |- [x:=t] for all t 101 § 2.3 Proofs • Rules for atomic formulas. Any set of rules of the shape: 1 … n ----------- for 1 … n, atomic. For instance: reflexivity, symmetry, transitivity of equality, compatibility of equality with functions and predicates. 102 § 2.3 Proofs ----t=t t=u ----u=t t=u u=v -----------t=v t1=u1 … tn=un -------------------------f(t1,…,tn)=f(u1,…,un) 103 § 2.3 Proofs t1=u1 … tn=un P(t1,…,tn) ----------------------------------------P(u1,…,un) By induction on , we deduce: t1=u1 … tn=un [x1:=t1,…, x1:=tn] ---------------------------------------------------[x1:=u1,…, x1:=un] 104 § 2.3 Proofs • Mathematical Theories T are identified with sets of axioms T. • is a theorem of T iff T|-. • An example: First Order Arithmetic PA has language L={0, succ, <}. • PA is introduced adding axioms characterizing successor, plus, for every formula , the • Induction Axiom for : x.([x:=0]x([x:=x+1])) 105 § 2.3 Proofs • An exercise for the next Lesson: derive, for z not free nor bound in , z(x[x:=z]) “there is some z such that: if (x) is true for some x, then (z)” • Hint: prove first x|-Thesis and x|-Thesis. Then conclude |-Thesis out of |- xx and -Elimination. 106 Appendix to § 2 • Proof of Th=z(x[x:=z]). • As suggested, we are going to prove both x|-Th and x|-Th, then conclude Th out of |- xx and -Elimination. • By renaming z with x, we may replace Th by Th’ = x(x) in the proof: • Th and Th’ are convertible, hence they may be identified. 107 Appendix to § 2 • 1. 2. 3. 4. 5. 6. x|-Th’. |- |-x |-x(x) xFV(Th’) x|-x x|-x(x) by Id. Princ.. by 1 and -I by 2 and -I x is bound in Th’. by Id. Princ. by 3, 4, 5 and -E 108 Appendix to § 2 • 1. 2. 3. 4. 5. 6. Proof of x|-Th’. x |- x x |- x x, x|- x, x|- x |-x x |- x(x) by id. princ. by id. princ. by 1,2, and-E by 3 and -E by 4 and -I by 5 and -I 109 Lesson 3 Validity Theorem Gödel Completeness Theorem 110 Plan of Lesson 3 • • • • § 3.1 Validity Theorem. All derivable sequents are “logically true”. § 3.2 Completeness Theorem. All “logically true” sequents are derivable. Previous Lesson: Forthcoming Lesson: First Order Logic Normalization. 111 § 3.1 Validity Theorem • • • • • Validity. A sequent |- is valid iff for all models M and valuations v, if []v,M {True} then []v,M =True. We also write |= for “|- is valid”. is valid iff |- is valid (i.e., iff for all models M, []v,M =True). “|- valid” expresses our intuitive idea of “logical truth”: “|- is true no matter what are the meaning of predicate and function symbols in it” 112 § 3.1 Validity Theorem • • • Derivability perfectly correspond to validity (to our intuitive notion of truth) Validity Theorem. If |- is provable, then |- is valid. Completeness Theorem (Gödel). Also the converse holds: if |- is valid, then it is provable. 113 § 3.1 Proof of Validity Theorem • • • • • Proof of Validity Theorem. By induction on the proof of |-: we have to prove, for all logical rules, that Validity is preserved: “if all premises are Valid then also the conclusion is” The only non-trivial steps concern Introduction and Elimination rules for ,. Let us pick up -Introduction, -Elimination as sample cases. 114 § 3.1 Proof of Validity Theorem • • • • • • • Proof of Validity Theorem: -Introduction preserves validity. The inductive hypothesis is: |-[x:=t] is valid. The thesis is: |-x is valid. We assume []v,M {True} in order to prove [x]v,M =True. 115 § 3.1 -Introduction preserves Validity 1. Assume []v,M {True}. 2. From |-[x:=t] valid and 1 we obtain: [[x:=t]]v,M =True. 3. Set m=[t]v,M M. 4. By Substitution Theorem and 3: [[x:=t]]v,M = []v[x:=m],M. 5. By 2, 4, we deduce []v[x:=m],M =True. 6. By 5, we deduce [x]v,M = True. 116 § 3.1 -Elimination preserves Validity • • • • • • • Proof of Validity Theorem: -Elimination preserves validity. The inductive hypothesis is: |-x and ,|- are valid, and xFV(,) The thesis is: |- is valid. We assume []v,M {True}, in order to prove []v,M =True. 117 § 3.1 -Elimination preserves Validity 1. 2. 1. 2. 3. 4. 5. Assume []v,M {True}. By 1 and |-x valid, we deduce [x]v,M = True, that is: []v[x:=m ],M = True, for some mM By xFV(), Sub.Thm: []v[x:=m],M = []v,M By 1, 3 we deduce []v[x:=m],M {True} By ,|- valid, and 2, 4, we deduce []v[x:=m],M = True. By xFV(), Sub.Thm: []v[x:=m],M = []v,M. By 5, 6, we conclude []v,M =True. 118 § 3.2 Completeness • 1. 2. 3. • Completeness Theorem (Gödel). (Weak closed form) If is closed consistent, then there is some model M such that []v,M {True} (for any valuation v). (Weak form) If is consistent, then there is some model M and some valuation v such that []v,M {True}. (Strong form) If |- is valid, then |- is provable. Proof. We will first prove weak closed form, then weak and strong form out of it. 119 § 3.2 Proof of Completeness (weak closed form) • Henkin Axioms. Fix, for each closed formulas x of a language L, some constant cx of L. Then we call Henkin axiom for x the statement: x[x:=cx] “there is some some z=cx such that, if (x) for some x, then (z)” 120 § 3.2 Proof of Completeness (weak closed form) • • • At the end of the previous section, we proved |-z(x[x:=z]) “there is some z such that: if (x) is true for some x, then (z)” Intuitively, this means that all Henkin axioms are logically correct (there exists some interpretation z for cx). Henkin Theories. A closed set H of formulas in a language L is an Henkin Theory iff H proves all Henkin axioms of language L. 121 § 3.2 Proof of Completeness (weak closed form) • Lemma (Henkin Lemma). Let H be an Henkin Theory of language L. • All closed sets H’H of formulas of L are Henkin Theories. • Derivability from H commutes with the interpretation of , on the set TERM0 of closed term, and for closed x, x. 1. H|- x H|- [x:=t], for some tTERM0 2. H|- x H|- [x:=t], for all tTERM0 122 § 3.2 Proof of Henkin Lemma • If H proves all Henkin axioms of L, then the same is true for all H’H in L. 1. . If H|-x, then by Henkin axiom for x and -Elim. we get H|-[x:=cx], with cx closed term. . If H|-[x:=t] for some closed t, we obtain H|-x by -Introd.. 2. . Assume H|-x. • Then H|-[x:=t] for all closed t by -Elim.. 123 § 3.2 Proof of Henkin Lemma 2. • • • • • • . Assume H|-[x:=t] for all closed t. By Identity princ., H,|- By -Introduction, H,|-x. By Henkin axiom for x (a closed formula) and -Elim., we get H,|-[x:=cx] From the hyp. H|-[x:=cx] and -Elim. we conclude H,|-. From H,|- we deduce H|- by D. Neg.. from H|-, and xFV(H)= (H is closed) we conclude H|-x by -Introd.. 124 • • § 3.2 Henkin Extension Lemma Conservative Extensions. If T’T are two sets of formulas, in the languages L’L, we say that T’ is a conservative extension of T if T’ proves no new theorem in the language L of T: If is a formula of L, and T’|-, then T|- Lemma (Henkin Extension Lemma). For all sets of closed formulas of L, there is some Henkin theory H, of language L’L, which is a conservative extension of . 125 § 3.2 Proof of Henkin Extension Lemma • • • • Fix any language L, any closed formula x of L, any closed , any cxL. Let ’ = {Henkin axiom for x} ’ is + the Henkin axiom for . Claim (one-step Henkin extension): ’ is a closed conservative extension of , of language L’=L{cx}. 126 § 3.2 Proof of the Claim 1. 2. 3. 4. 5. 6. Assume , x[x:=cx]|- and cx not in , in order to prove |- . cx is not in , nor in , because , are in the original language L. Replace cx in the proof of the sequent above by any variable zFV(,,). Since cx is not in ,,, we obtain a proof of: , x[x:=z]|- By -Elim., , z(x[x:=z])|-. By |-z(x[x:=z]) (end of the previous lesson) we conclude |-. 127 • • • • § 3.2 Proof of Henkin Extension Lemma Fix any enumeration of closed formulas of the shape x in L. Starting from 0=, we define n+1 = n{xnn[x:=c]} By the Claim, each n+1 is a closed conservative extension of n, and therefore of . Thus, 1=nNn is a closed conservative extension of : if we have a proof of in L in , then we have a proof of in some n, and by conservativity of n w.r.t. , also in . 1 includes all Henkin axiom for the language of the original . 128 § 3.2 Proof of Henkin Extension Lemma • • • • • Define 0 = , n+1 = (n)1. Then H = nNn is a closed conservative extension of , including all n+1, and therefore all Henkin axiom for all closed x in the language of all n . Thus, H includes all Henkin axioms for all closed x in the language of H itself. We conclude that H is an Henkin Theory, and a closed conservative extension of . H is consistent if is: by conservativity, any proof of in H is a proof of in . 129 § 3.2 Proof of Completeness (weak closed form) • Using Henkin Extension Lemma, we may define, for all closed consistent of language L, some closed consistent Henkin H, of language L’L. • By adapting the Complete Set Lemma of Propositional logic to the set of closed first order formulas, we may define some closed complete ’H . 130 § 3.2 Proof of Completeness (weak closed form) • ’ (closed, complete) is an Henkin theory by Henkin Lemma. • ’ defines a model M of , whose universe are the closed terms of the language L’ of ’ (modulo provable equality in ’). • We interpret each n-ary function name f by the map over closed terms of L’ fM : (t1,…,tn) | f(t1,…,tn), • and each m-ary predicate name P by PM = {(t1,…,tn) closed in L’| ’|-P(t1,…,tn)} 131 • • • § 3.2 Proof of Completeness (weak closed form) By construction, “=” is interpreted in M by provable equality in ’. Provable equality is closed under equality rules, therefore is an equivalence relation on M, compatible with all functions and predicates of L’. We will now prove that []v,M [’]v,M = {True}, or that M is a model of . 132 § 3.2 Valuation Thm • Theorem (Valuation Thm). 1. For all closed v: ’|-v() []v,M =True • In particular we have Weak Closed Completeness: []v,M [’]v,M ={True} 2. For all closed substitutions v, w: VAR {closed terms}: []v,M = [v()]w,M 133 § 3.2 Valuation Thm (1) • • • • • Proof of (1). By induction on . For atomic, we have ’|-v() []v,M =True by definition of the structure M. If the outermost symbol of is , , , , we have to prove that ’|-v() commutes with the meaning of all Propositional connectives. This follows by Completeness of ’ and the result on Complete sets in Propositional Logic. We have still to prove that ’|-v() commutes with the meaning of , . 134 § 3.2 Valuation Thm (1) • By ’ Henkin Theory we have: 1. ’|- x ’|-[x:=t], for some tTERM0 2. ’ |-x ’|- [x:=t], for all tTERM0 • We will prove that ’|-v() commutes with the meaning of quantifier , using point 1, 2 above, inductive hypothesis on [x:=t], and the trivial syntactical identities: a. v(x) = x v[x:=x](), b. v[x:=x][x:=t]() = v[x:=t]() • for all substitutions v, all terms t. 135 ’|- v(x) M 1. 2. 3. 5. 6. 7. ’|- v(x) ’|- xv[x:=x]() for some closed term t: ’|-v[x:=x][x:=t]() for some closed term t: ’|- v[x:=t]() for some closed term t: M |=v[x:=t] M |=v x |=v x (Identity a) (’ Henkin) (Identity b) (Ind.Hyp.) (def. of |=) 136 ’|- v(x) M |=v x 1. 2. 3. 5. 6. 7. ’|- v(x) ’|- xv[x:=x]() for all closed term t: ’|-v[x:=x][x:=t]() for all closed term t: ’|- v[x:=t]() for all closed term t: M |=v[x:=t] M |=v x (Identity a) (’ Henkin) (Identity b) (Ind.Hyp.) (def. of |=) 137 § 3.2 Valuation Thm (2) • • • • • • Proof of (2): []v,M= [v()]w,M. v is a closed substitution, hence v() is a closed term. Thus, w(v()))=v(). From this fact and 1 we deduce, for all closed substitutions v,w:VAR{closed terms}: []v,M = True (point 1) ’|-v() (w(v()))=v()) ’|-w(v()) (point 1) [v()]w,M = True 138 § 3.2 Proof of Completeness Theorem (weak form) • • • • Assume is consistent, with possibly free variables. We have to define some model M and some valuation v such that []v,M {True}. Let c1,…, cn, …be fresh constants. Set s(xi)=ci for all iN. Then s()|- is not provable, otherwise, by replacing back each ci with xi (and possibly renaming some bound variable) also |- would be provable. 139 § 3.2 Proof of Completeness Theorem (weak form) • • • • By the Weak form of Completeness, there is some model in which [s()]v,M {True} for any valuation v. By Valuation Thm., point 2, or all closed substitutions s, v we have: [s()]v,M = True [s()]s,M = True we conclude []s,M {True} This concludes the proof of Weak Completeness Theorem. 140 § 3.2 Proof of Completeness Theorem (strong form) • • • • We will prove the contrapositive of Completeness: if |- is not provable, then there is some model M and some valuation v such that []v,M {True} but []v,M = False. If |- is not provable, by the Consistency Lemma , is consistent. We apply the weak form of the Theorem to ,, and we find some model M and some valuation v such that []v,M {True}, []v,M = True, that is, []v,M = False. This concludes the proof of Strong Completeness Theorem. 141 Lesson 4 Intuitionistic Logic Strong Normalization Normal Forms 142 Plan of Lesson 4 • • • • • § 4.1 Intuitionistic Logic. The interest of proofs without Excluded Middle. § 4.2 Strong Normalization Results. All proofs may be reduced to some canonical form. § 4.3 Structure of normal form. Using normalization, we may interpret intuitionistic proofs as programs. Previous Lesson: Forthcoming Lesson: Completeness Theorem none. 143 § 4.1 Intuitionistic Logic • The Introduction rules for a connective c may be seen as a definition of c. • Elimination rules for c may be seen as consequences of the definition of c. • Double negation is the only rule not justified by definition of some connective. • Double negation is a Belief about Truth. 144 § 4.1 Intuitionistic Logic • We believe that in Nature all statements are either true or false. • Double negation is then justified by the consideration that all statements which are not false are true. • Double Negation looks like some external axiom, breaking the Introduction/ Elimination symmetry of logical rules. 145 § 4.1 Heyting Realization Interpretation • In a Natural Deduction Style of proofs, we obtain Intuitionistic Logic by removing Double Negation Rule. • In Intuitionistic Logic, some mathematical results are not provable. • In Intuitionistic Logic, Introduction/Elimination symmetry provides a simple interpretation of any proof of by some program of specification (a program which effectively does what says). • This interpretation was first proposed by Heyting, and depends on the outermost connective of . 146 § 4.1 Heyting Interpretation of Atomic Formulas. • A proof of an atomic formulas (x) should provide, for all values of x, a proof of without logical connectives, by Post rules only. • In particular, no proof of should exists (unless we get it by Post Rules only). 147 § 4.1 Heyting Interpretation of Propositional Connectives. • A proof for 1(x)2(x) should provide a pair of a proof 1(x) and a proof of 2(x). • A proof of 1(x)2(x) should provide a program returning, for all x, either a proof of 1(x) or a proof of 2(x) (thus, deciding, for each x, whether 1(x) is true or 2(x) is true). • A proof of (x)(x) should provide a program returning, for all x, and all proofs of (x), some proof of (x). 148 § 4.1 Heyting Interpretation of Quantifiers. • A proof of x(x,x) should provide, for all values of x and x, some proofs of (x,x). • A proof of x(x,x) should provide, for all values of x, both some value for x and some proofs of (x,x). 149 § 4.1 Heyting Interpretation of Quantifiers. • There is no Heyting interpretation for Excluded Middle, by: • Gödel Undecidability Theorem. There are some arithmetical formulas (x), such that no computable function (no computer program) is able is to decide whether (x) is true or (x) is true. • For such a (x), Heyting interpretation of (x)(x) is false. • Double Negation proves Excluded Middle, hence it has no Heyting Interpretation as well. 150 § 4.1 Heyting Interpretation of Quantifiers. • Heyting interpretation is bridge between (intuitionistic) proofs and programming: . • Out of, say, an intuitionistic proof of x.f(x,x)=0 Heyting interpretation provides, for all values of x, some x0 and some proof of f(x0,x)=0. • We will introduce a method, Normalization providing an Heyting interpretation for Intuitionistic Proofs in Natural Deduction. 151 § 4.2 Normalization • For all connectives c, every c-Elimination is justified by the corresponding cIntroduction in the following sense: • If we have some c-I followed by some c-E, we may derive the conclusion of c-E just by combining in some suitable way the premises of c-I. • We call any c-I followed by a c-E a c-Cut. 152 § 4.2 Normalization • Any c-Cut is, conceptually, a redundant step in the proof, and it may be removed (often, at the price of expanding the proof size considerably). • For any c-Cut we define an operation removing it we call a c-reduction. • Removing a c-Cut may generated new Cuts. • Yet, we will prove that if we repeatedly remove cuts in any order, eventually we get a (unique) proof without cuts. 153 § 4.2 Normalization • We call Normal any proof without Cuts, and Normalization the process removing all cuts (in any order). • After Normalization, Intuitionistic Proofs satisfy Heyting Interpretation. • Thus, normalizing an intuitionistic proof of is a way of interpreting the truth of as a program of specification . • We will now define some c-reduction for all c. 154 § 4.2 Reduction Rule for D1 D2 1 2 --------12 --------i Di i 155 § 4.2 Reduction Rule for D i \1 2 \ -------E1 E2 12 ------------------------------- D i Ei 156 § 4.2 Reduction Rule for \ D -------E ------------------ E D 157 § 4.2 Reduction Rule for D -----x --------[x:=t] D[x:=t] [x:=t] 158 § 4.2 Reduction Rule for D [x:=t] -------E x ----------------- D [x:=t] E[x:=t] 159 § 4.2 Subject Reduction • If D is a proof of with assumptions we write |- D:. • We write D1E if we may obtain E out of D by replacing some subtree of D with its reduced version. • A proof D have finitely many subtrees, hence we have D1E for finitely many E. • We write DE for “there is some chain D 1 D’ 1 D” 1 … 1 E” from D to E. 160 § 4.2 Subject Reduction • Subject Reduction Theorem. Reducing a proof p we obtain a proof p’ having equal hypothesis and conclusion: |- D:, DE |-E: 161 § 4.2 Strong Normalization (definition) • Reduction Tree. We call reduction tree the tree of all reduction path from D. • Strong Normalization. D strongly normalizes iff its reduction tree is finite. 162 § 4.2 Strong Normalization Lemma • 1. 2. • 1. 2. Strong Normalization Lemma. D strongly normalize iff all D1E strongly normalize. If D ends by an introduction, it strongly normalizes iff all its premises strongly normalize. Proof. Since D1E for finitely many E’s, the reduction tree of D is finite iff the reduction tree of all D1E is finite. No reduction is defined over an Introduction. 163 § 4.2 Strong Normalization Theorem • We state (not yet prove) the normalization result we are looking for: • Strong Normalization Theorem (or Hauptsatz). All intuitionistic proofs strongly normalizes. 164 § 4.2 Computability • In the strong normalization proof, we will actually prove a notion of “computability” for a proof D, implying Strong Normalization. • Definition of Computable proof: by induction over the proof D. • D does not end with an Introduction. D is computable iff all D1E are computable. • D ends with an ,,-Introduction. D is computable iff all its premises are. • D ends with an , -Introduction: next two pages 165 § 4.2 Computability for -I • The proof D -----x • is computable iff for all tTERM, D[x:=t] [x:=t] • is computable 166 § 4.2 Computability for -I • The proof D ------ • is computable iff for all computable E, • is computable. E D 167 § 4.2 Computability Lemma • Lemma (Computability Lemma). 1. Identity principle (a one-formula proof) is a computable proof. 2. If D is computable, then D is strongly normalizable. 3. If D is computable and D1E, then E is computable. 168 § 4.2 Computability, Point 1 1. Identity principle has no reduction. Thus, trivially, all its reduction are computable. Thus, Identity Principle is computable. 169 § 4.2 Computability, Point 2 2. • • Assume D is computable, in order to prove D strongly normalizable. We argue by induction over the definition of computable. D does not end by an Introduction. Then all D1E are computable, and by ind. hyp. strongly normalizable. Thus, D itself is strongly normalizable. D ends with an ,,-Introduction. Then all premises of D are computable, and by ind. hyp. strongly normalizable. Thus, D itself is strongly normalizable. 170 § 4.2 Computability, Point 2, -I case • The proof • -----x is computable iff for all tTERM, D D[x:=t] [x:=t] • are computable. By ind. Hyp., all such proofs strongly normalizes. 171 § 4.2 Computability, Point 2, -I case • • • Take t=x: then D is strongly normalizable. Thus, also D -----x is strongly normalizable. 172 § 4.2 Comp., Point 2, -I case • The proof D ------ • is computable iff for all computable E, E D • is computable. By ind. hyp., all such proofs strongly normalize. 173 § 4.2 Comp., Point 2, -I case • Take E=the Identity Principle: then D • strongly normalizes. Thus,also D ------ • strongly normalizes. 174 § 4.2 Computability, Point 3 3. • • Assume D is computable, in order to prove that all D1E are computable. We argue by induction over the definition of computable. D does not end by an Introduction. All D1E are computable by def. of computable. D ends with an ,,-Introduction. If D is computable, then all its premises are. By ind. hyp., all one-step reductions of all premises of D are computable. If D1E, this reduction takes place in some premise of D. Thus, E is computable because E ends with some ,,-Introd., and all its premises are computable. 175 § 4.2 Computability, Point 3, -I case • The proof • -----x is computable iff for all tTERM, D D[x:=t] [x:=t] • are computable. By ind. hyp., if D[x:=t] 1 E[x:=t], then E is computable. 176 § 4.2 Computability, Point 3, -I case • Take any reduction D1 E. Then D[x:=t] 1 E[x:=t], hence E[x:=t] [x:=t] • • is computable. Thus, also E -----x is computable. 177 § 4.2 Comp., Point 3, -I case • The proof D ------ • is computable iff for all computable E, E D • is computable. By ind. hyp., if we replace D by any D1 E, we get a computable proof. 178 • Take any reduction D1 E. Then for all computable D, D E • is computable. Thus, also • is computable. E ------ 179 § 4.2 Computable by Substitution and Replacing • Definition. Assume |-D:, =1,…,n, and FV(,){x1,….,xm}. D is computable by substitution and replacing iff for all substitutions s(.)=(.)[x1:=t1,….,xm:=tm], for all computable proofs p|-D1:s(i), …, p|-Dn:s(n), the proof • is computable D1 Dn s(1) … s(n) s(D) s() 180 § 4.2 Strong Normalization • Theorem (Strong Normalization) • All intuitionistic proofs D are Computable by Substitution and Replacing. • As a Corollary, they are all Strongly Normalizing. 181 § 4.2 Strong Normalization • Proof. • By induction over D. • We assume that all premises of D are computable by substitution and replacing, we take any composition and substitution of D, and we check it is computable. • We distinguish two cases, according if the last rule in D is not an introduction, or it is an Introduction. 182 § 4.2 Strong Norm., Case 1 • Case 1: D not ending with some Introduction. • we have to prove that all D1E are computable by substitution and composition. • If the c-reduction is applied to some premise of D, the thesis follows by the inductive hypothesis on the premises of D and the Computability Lemma. • If the c-reduction is applied to the conclusion itself of D, the thesis is an immediate consequence of the definition of computable for c-Introduction, for each connective c. 183 § 4.2 Strong Norm., Case 1 • An example. Assume that D is computable by substitution and reduction, and that some -E: D1 Dn s(1) … s(n) s(D) s() ----x --------[x:=t] 184 § 4.2 Strong Norm., Case 1 • reduces to D1 Dn s(1) … s(n) s(D) s()[x:=t] • This latter proof is computable by: 1. ind. hyp. over the premise D of the rule -E; 2. definition of computability by substitution and composition for such a D. 185 § 4.2 Strong Norm., Case 2 • Case 2: D ending with an ,,-Introduction • Any composition and substitution of the proof is computable iff all its premises are. • This latter fact follows immediately by inductive hypothesis. • Case 2: D ending with ,-Introduction. We have to prove that these two rules preserve computability by composition and substitution. 186 § 4.2 Strong Norm., Case 2: -I Preserves computability Let x=x1,…,xm. Assume xFV(1, …, n), and D1 … Dn 1[x:=t, x:=t] … n[x:=t, x:=t] D [x:=t, x:=t] [x:=t, x:=t] • is computable for all sub. [x:=t, x:=t] on D. 187 § 4.2 Strong Norm., Case 2, -I Preserves computability • x is the bound variable of -I. • By possibly renaming x, we may assume xFV(t): [x:=t, x:=t] = ([x:=t])[x:=t] • for all formulas . • By xFV(1, …, n) we also obtain: (i[x:=t])[x:=t] = i[x:=t] 188 § 4.2 Strong Norm., Case 2 -I Preserves computability • Thus, we may simplify the hyp. to: D1 … Dn 1[x:=t] … n[x:=t] (D[x:=t])[x:=t] ([x:=t])[x:=t] • is computable for all terms t, and all computable: D1 Dn 1[x:=t], …, n[x:=t] 189 § 4.2 Strong Norm., Case 2 -I Preserves computability • By definition of computability for -I, we conclude that D1 Dn 1[x:=t]… n[x:=t] D[x:=t] [x:=t] ---------------x ([x:=t]) • is computable 190 § 4.2 Strong Norm., Case 2 -I Preserves computability Assume D1 Dn 1[x:=t] ,…, n[x:=t] [x:=t] D [x:=t] [x:=t] • is computable for all computable E. 191 § 4.2 Strong Norm., Case 2 -I Preserves computability Then D1 Dn 1[x:=t], …, n[x:=t] [x:=t] D [x:=t] [x:=t] --------------------[x:=t][x:=t] \ • is computable by def. of computability for -I. 192 § 4.2 Strong Normalization (end of the proof) • We checked that all proofs are computable by substitution and replacing. • If we replace each assumption i with the Identity Principle for i, and each variable x by itself, we re-obtain the original proof. • We conclude they all proofs are computable, and therefore all have a finite reduction tree. • This ends the proof of Strong Normalization Theorem. 193 § 4.3 Normal Forms • We will now study normal intuitionistic proofs. • Then we will check that then intuitionistic proofs satisfy Heyting Interpretation of logical connectives. • We introduce some terminology first. • Main premise. The main premise of a logical rule is the leftmost one. • Main Branches. A branch in a proof tree is a Main branch iff it includes, with each conclusion of an Elimination, the Main premise of such Elimination. 194 § 4.3 Structure of Normal Forms • Lemma (Main Branch). 1. All Elimination rules have a non-atomic main premise, and discharge no assumptions on the branch main premise. 2. All main branches either include some cut, or, from top to bottom, include first only elimination rules, then only atomic rules, eventually only introduction rules. 3. All Main Branches ending with an Elimination rule include either some cut, or some free assumption, or end with an introduction. 195 § 4.3 Proof of Main Branch Lemma 1. By inspecting all Elimination rules. 2. Assume there are no cuts, in order to prove that after atomic rules there are only atomic rules or Introductions, and after Introductions only Introductions. • Below atomic rules there are only atomic rules or Introductions. The conclusion of an atomic rule can only be atomic. Thus, it is either the conclusion, the premise of another atomic rule, or of some Introduction. It cannot be the main premise of an Elimination rule, because such main premise is not atomic. 196 § 4.3 Proof of Main Branch Lemma • • Below Introductions there are only Introductions. The conclusion of an Introduction is not atomic, thus it cannot be the premise of an atomic rule. It can only be the conclusion of the proof, or the premise of another Introduction. If it were the main premise of an Elimination we would have a cut. 197 § 4.3 Proof of Main Branch Lemma 3. If a main branch include no cuts, then all Introductions are at the end of the branch. If the last rule is not an Introduction, then there are no Introductions at all, only Eliminations and atomic rules. In this case no formula is discharged when we are going up the main branch. Thus, the uppermost formula of the branch is a free assumption. 198 § 4.3 Strong Normalization • Corollary (Cut-Free Proofs). In every cutfree and assumption-free proof, all Main Branches end up either with some introduction or with some atomic rule. • All cut-free and assumption-free proof end up with some introduction or with some atomic rule. 199 § 4.3 Strong Normalization • Let have outermost symbol some predicate P, or some logical connective c. • Corollary (Cut-free theorems). All normal proofs of end with, respectively, with some atomic rule, or with some cIntroduction. 200 § 4.3 Strong Normalization • Corollary (Heyting interpretation for Normal Proofs). • If has outermost symbol some predicate P, then all normal proofs of consists only of atomic rules. • There is no normal proof of (unless there is some proof of using only atomic rules). 201 § 4.3 Strong Normalization • Corollary (Conservativity over atomic formulas). • Thus, logical rules deduce no new result about atomic formulas: • First Order Intuitionistic Logic is a conservative extension of the system of atomic rules. • This is a constructive result: we have some method (to normalize) turning any proof of any atomic P(t1,…,tn) in first order logic in some proof of the P(t1,…,tn) using atomic rules. 202 § 4.3 Strong Normalization • Corollary (Heyting interpretation). • Every normal proof of |-12 include, as last step, some proof of some |-i. • Every normal proof of |-12 include, as last step, some proof of |-1 and some proof of |-2. • Every normal proof of |-12 include, as last step, some proof of 1|-2. 203 § 4.3 Strong Normalization • Corollary (Heyting interpretation) • Every normal proof of |-x include, as last step, some proof of . • Every normal proof of |-x include, as last step, some proof of some [x:=t]. 204 § 4.3 Strong Normalization • By combining the result about normal form with the fact that every proof may be normalized, we obtain: • |- 12 |- i for some i{1,2} • |- x |- [x:=t] for some tTERM 205 § 4.3 Strong Normalization Result about , hold only for Intuitionistic Logic. • In Classical Logic: 1. we have |- even if nor |-, neither |; 2. we have |-x even if |-[x:=t] for no tTERM. • 206 Realizability: Extracting Programs from proofs Summer School on Proofs as Programs 2002 Eugene (Oregon) Stefano Berardi Università di Torino [email protected] http://www.di.unito.it/~stefano 207 The text of this short course on Realizability, together with the text of the previous short course on Logic, may be found in the home page of the author: http://www.di.unito.it/~stefano (look for the first line in the topic: TEACHING) 208 Plan of the course • Lesson 5. Realization Interpretation. A Model of Realizers. Harrop Formulas. • Lesson 6. The problem of Redundant code. 209 Reference Text • L. Boerio “Optimizing Programs Extracted from Proofs”. Ph. D. Thesis, C. S. Dept. Turin University, 1997. • Available in the web page of the course: http://www.di.unito.it/~stefano • (look for the first line in the topic: TEACHING) 210 Lesson 5 Realization Interpretation A Model of Realizers Harrop Formulas 211 Plan of Lesson 5 • § 5.1 Realization • § 5.2 A Model of Realizers • § 5.2 Harrop Formulas. 212 § 5.1 Realization Interpretation • In the previous course, we showed how, in Intuitionistic Logic, any proof D of may be interpreted with some effective operation r associated to . • Now, we will call such an r a Realizer of . • In the simplest case, r is the proof D itself, executed through normalization. • Yet, in order to effectively use Heyting Interpretation, is is convenient to think of r as a separate object. • We will now reformulate Heyting interpretation 213 in term of Realizers. § 5.1 Realization Interpretation • We will abbreviate the statement “r is a realizer of ” by “r: ”. • Language will be: multi-sorted language for Integers and Lists of integers, with induction over Integers and over Lists. • x denotes any sequences of variables, each labeled with its type, which is Integer or List. • Quantifiers are: yT.(x,y), yT.(x,y), with T=Integers, Lists. 214 § 5.1 Realization Interpretation • All what we will say applies not just to T=Integers, List • but also to T=any Bohm-Berarducci Data Types (of cardinality > 1) • Look at Boerio Ph.d in the course Web page if you want to learn more. 215 § 5.1 A simply typed -calculus • We choose as r some simply typed lambda term, with Data Types Unit={unit}, Bool={True,False}, N={0,1,2,3,..}, List={nil, cons(n,nil), cons(n,cons(m,nil)), …} • as base types, with product types, and including if, and primitive recursion recN, recL over integers and lists. • (We could take any simply typed lambda term + Bohm-Berarducci Data Types). • We distinguish, in the definition of r:, one case for each possible outermost symbol of . 216 § 5.1 Dummy constants. • • 1. 2. 3. 4. 5. 6. For each simple type T, we we will need some dummy element dummyT:T (just dT for short), to be used as default value for such type. We define dT:T by induction over T. dummyUnit = unit dummyBool = False dummyN =0 dummyList = nil dummyTU = x. dummyU dummyTU = <dummyT, dummyU> 217 § 5.1 Realization Interpretation of Atomic Formulas. • r:P(t1,…,tm) r=unit, and some proof of without logical connectives exists. • We chose r=unit because a proof of an atomic formula correspond to an empty operation, therefore to a dummy value. • The type Unit={unit} is the type of empty operations. 218 § 5.1 Realization Interpretation of Propositional Connectives. • r(x):1(x)2(x) r(x)=<r1(x),r2(x)> and r1(x):1(x), r2(x):2(x) • r(x):1(x)2(x) r(x)=<i(x),r1(x),r2(x)> with i(x)Bool i(x)=True r1:1(x) i(x)=False r2:2(x) (if i(x)=True, the canonical choice for r2 is a dummy constant, and conversely) • r(x):1(x)2(x) for all s:1(x), r(x)(s):2(x) 219 § 5.1 Realization Interpretation of Quantifiers. • r(x):yT.(x,y) for all yT, r(x,y):(x,y) • r(x):yT.(x,y) for some y(x)T r(x)=<y(x),s(x)>, with s(x):(x,y(x)) 220 § 5.1 Realization Interpretation • According to our definition, a realizer r:yT.(f(x,y)=0) is some pair r(x)=<y(x),unit>, of a function y=y(x):T, solving the equation f(x,y)=0 (w.r.t. the parameters in x), and some (dummy) realizer unit of f(x,y)=0. • yT.(f(x,y)=0) says “there is a solution to f(x,y)=0, parametric in x”, while r finds it. • r:yT.(f(x,y)=0) may be seen as a program whose specification is yT.(f(x,y)=0). • Realization interpretation turns any intuitionistic proof of solvability of some equation, into a program which effectively solves such equation. 221 § 5.1 Realization Interpretation of Formulas. • Let be any closed formula. The previous clauses implicitly defined some simple type || for all r:. Definition is by induction over . • |P(t1,…,tm)| = Unit • |12| = |1| |2| • |12| = Bool |1| |2| • |12| = |1| |2| • |xT.| = T || • |xT.| = T || 222 § 5.1 Realization Interpretation of Formulas. • If x=x1,…,xn is a vector of variables of types T1,…, Tn, then |(x)| = T1…Tn|| is the type of all r:(x). • Let ={1,…,n} and x=x1,…,xk. We may turn every proof p:(x), with free assumptions in , into some realizer r=|p| of (x), depending on free variables in x, and on the realizer variables 1:|1(x)|, …, k:|k(x)|. • Definition is by induction on p, with one clause for each possible rule at the conclusion of p. 223 § 5.1 Assigning Realizers • Atomic rules. If p end by some Atomic rule, then r(x)=unit. … … unit: P1(t1) … unit: Pm(tm) ---------------------------unit: P(t) • If |- unit: P1(t1), …, |- unit: Pm(t1), then |unit: P(t) 224 § 5.1 Assigning Realizers • • Rules for Introduction rules: s1: s2: ------------------<s1,s2>: • If |- s1: and |- s2: then |- <s1,s2>: 225 § 5.1 Assigning Realizers • • Elimination rules: s: ---------1(s): s: ---------2(s): If |- s: , then |- 1(s): and |2(s): 226 § 5.1 Assigning Realizers • • • • Rules for . Let T=True, F=False, and _, _’, be dummy elements of ||, ||. Introduction rules: r: s: --------------------------------------<T,r,_’>: <F,_,s>: If |- r: If |- s: then |- <T,r,_’>: then |- <F,_,s>: 227 § 5.1 Assigning Realizers Elimination rules for . Let u = if (i=True) then s(a) else t(b) Then : : … … <i,a,b>: s(): t(): ---------------------------------------------u: • \ • \ If |- r: and , :|- and , :|-, then 228 |- u: § 5.1 Assigning Realizers • Rules for . Introduction rule: : … s(): ------------------- .s(): \ • If , : |- s(): , then |- .s(): 229 § 5.1 Assigning Realizers • • Elimination rule: r: s: ------------------------r(s): If |-r: and |-s:, then |-r(s):. 230 § 5.1 Assigning Realizers • Rules for : Introduction rule. … r: [x:=t] ------------------<t,r>: xT. • If |- r:[x:=t] for some t, then |- <t,r>: x T. 231 § 5.1 Assigning Realizers • Rules for : Elimination rule. , : … … <i,a>: xT. t(x,): ----------------------------------t(i,a): \ • • Provided xFV(,). If |-<i,a>:xT., ,:|-t(x,):, xFV(,), then |- t(i,a): and 232 § 5.1 Assigning Realizers • • • Rules for : Introduction rule. … r: ----------------x.r:xT. Provided xFV() If |- r: and xFV(), then |- x.r:xT. 233 § 5.1 Assigning Realizers • Rules for : Elimination rule. … f:xT. --------------f(t):[x:=t] • If |- f:xT., then |-f(t):[x:=t] for all t 234 § 5.1 Assigning Realizers • Induction Axiom for the type N=Integers : Rec: xN.([x:=0]xN.([x:=x+1])) • Rec has type: N||(N||||)|| • Let n:N, r:||, s:N||||. • We inductive define Rec(n,r,s):|| by: 1. Rec(0,r,s) =r 2. Rec(n+1,r,s) = s(n,Rec(n,r,s)) 235 § 5.1 Assigning Realizers • Induction Axiom for the type L=Lists: RecL: lL.([l:=nil] lL, xN.([l:=cons(x,l)]) ) • We abbreviate AB…C by A,B,…C. • RecL has type: L,||,(L,N,||||)|| • Let n:N, r:||, s:L,N,||||. • We inductive define RecL(n,r,s):|| by: 1. RecL(nil,r,s) =r 2. RecL(cons(n,l),r,s) = s(l,n,Rec(l,r,s)) 236 § 5.2 A Model for Realizers • • 1. 2. 3. 4. 5. 6. In order to study the behavior of Realizers we first define a model for them. For each simple type T there is some settheoretical interpretation [T]Set: [Unit] = {unit} [Bool] = {True,False} [N] = {0,1,2,3,…} [L] = {nil, cons(n,nil), …} [TU] = [T][U] (Cartesian Product) [TU] = {set theoretical functions :[T][U]}237 § 5.2 Harrop Types • • • • • The set-theoretical interpretation of types may be extended to an interpretation of terms. We write t=Setu iff t, u has the same interpretation in the Set-Theoretical Model (under all valuations). Denote the cardinality of [T] by C([T]). For all types T: C([T])1 (because dummyT:T) We say that H is an Harrop type (simply is Harrop, for short) iff C([T])=1 (iff t=Setu for all t,u:H). 238 § 5.2 Characterizing Harrop Types • 1. 2. 3. • 1. 2. Lemma (Harrop Lemma). Unit is Harrop. Bool, N, L are not Harrop. HH’ is Harrop H, H’ are Harrop. TH is Harrop H is Harrop Proof. C({unit})=1,C({True,False}),C({0,1,2,..})>1,... C([HH’]) = C([H])C([H’]) = 1 iff C([H]) = C([H’]) =1. 3. C([TH]) = C([H])C([T])=1 iff C([H]) = 1 (because C([T])1 ). 239 § 5.3 The Harrop(.) map • • • • • • • A term u is Harrop iff its type is. We may decide if u is Harrop. If u:U is Harrop, then [U] is a singleton and u=SetdummyU. Denote with Harrop(t) the term obtained out of t by replacing any maximal Harrop subterm u:U of t with dummyU. Theorem. t=SetHarrop(t). Proof. We defined Harrop(t) by replacing some subterms of t with some equal terms. The map Harrop(.) is some simplification240 procedure over Realizers. What does it do? § 5.3 The Harrop(.) map • • • • If is any first order formula, we say that is Harrop iff || is Harrop. If is an Harrop formula, then all r: are replaced with dummy|| by the map Harrop(.). Therefore, all Realizers r: correspond to some dummy operation. Thus, we are interested in characterizing the set of Harrop formulas , in order to learn which realizers are (necessarily) dummy. 241 § 5.3 Harrop formulas • • • • • • If =P(t), then ||=Unit is Harrop. If =12, then ||=|1||2| is Harrop iff |1|,|2| are. If =2, then ||=|||2| is Harrop iff |2| is Harrop. If =xT.2, then ||=T|2| is Harrop iff |2| is Harrop. If =12, then ||=(|1||2|)(|2||1|) is Harrop iff |1|, |2| are Harrop. If =12, xT.2, then is not Harrop, because ||=Bool|1||2|, T|2| have 242 cardinality > 1 (because T has cardinality > 1). § 5.3 Characterizing Harrop Formulas • • • • Theorem (Harrop formulas). The set of Harrop formula is the smallest set including: all atomic formulas, and with 1, 2, also 12, xT.2, 12, and 2 (with any formula). We may decide if a formula is Harrop. All proofs of Harrop formula may be neglected if we are looking for the program hidden in a proof: they generate a dummy realizer. 243 § 5.3 Some Harrop Formulas • • • • Negations. All are Harrop, because =(), and is Harrop. Thus, any statement defined through a negation may be neglected. Examples are: “x is not a square”, “x is a prime element = no y, z are a factorization of x”. 244 § 5.3 Some Harrop Formulas • Universal properties. All quantification x1,…,xn f(x1,…,xn) = g(x1,…,xn) • are Harrop. • This set includes: 1. Associativity, Commutativity, all equational identities. 2. “l is sorted = every element in l but the last is of the next one” 3. “l, m are permutations = for all x, the number of times x is in l and m is the same”. 245 § 5.3 Some Harrop Formulas • Note. Being Harrop depends on the exact formal definition we choose. • For instance: if we formally define “l, m are permutations” • by “there is some permutation sending l into m” • then the statement we obtain is not Harrop (because of the existential quantifier in it). 246 § 5.3 Logical Parts • • • • Summing up: subproofs whose conclusion is an Harrop formulas correspond to purely logical parts of the proof. A proof of an Harrop formula defines no action. Yet, it may be used in order to prove that the action defined by the proof is correct. For instance, if we look for a solution of (x23x+2)=0, and we found some a such that (a2+2=3a), then using the Harrop statement x,yN.(x2-3x+2)=0 (x2+2=3x), we may prove that a solves the original 247 equation (x2-3x+2)=0. Appendix to § 5: an example • • • • • We extract a toy sorting algorithm out of a proof that all lists may be sorted. Assume Perm(l,m), Sorted(m) are fresh predicate letter, whose meaning is: l, m are permutations, and m is sorted. Assume we already proved that ordering on N is total: x,yN.(xy yx). We are going to prove: = lT.mT. (Perm(l,m) Sorted(m)) A realizer r: has type ||=LLH, for some H Harrop (Perm(l,m), Sorted(m) are Harrop, 248 hence their conjunction is). Appendix to § 5: an example • Any r: takes some list l, and returns some pair r(l)=<m,_>, with: 1. m = sorted version of l; 2. “_” = some realizer of type H, corresponding to some proof of (Perm(l,m) Sorted(m)). • If we apply the simplification Harrop(r), then “_” is replaced by dummyH (some dummy constant). • Replacing “_” by dummyH is computationally correct: any proof of (Perm(l,m) Sorted(m)) states something about l, m, but it performs no 249 action on l, m. Appendix to § 5: an example • • • • • We argue by induction over lists. Base case: nil. We have to prove mT.S(nil,m). We just set m=nil. We have to prove Perm(nil,nil) and Sorted(nil). Inductive case: x*l for some xN. By ind. hyp., Perm(l,m) and Sort(m) for some mList. We will prove a Lemma: for all m, if Sorted(m), then all x*m have some sorted version p (that is: Perm(x*m,p) and Sorted(p)). Out of the Lemma, we conclude Perm(x*l, x*m), and by transitivity of Perm, Perm(x*l,p), 250 Q.E.D.. Appendix to § 5: an example • • • • The Lemma is proved by induction over m. Base case of the Lemma: m=nil. We choose p=x*nil. We have to prove Perm(x*nil, x*nil), Sorted(x*nil). Inductive case of the Lemma. Let m=y*q for some q. We distinguish two subcases: xy and yx. 251 Appendix to § 5: an example • • Subcase xy. By second ind. hyp. we have Perm(y*q,r) and Sorted(r) for some r. We choose p=x*r. We have to prove that if Perm(y*q, r) and Sorted(r) and xy, then Perm(x*y*q, x*r) and Sorted(x*r). Subcase xy. We just reverse the roles of x, y. By second ind. hyp. we have Sort(x*q,r) for some r. We choose p=y*r. We have the same proof obligation (with x, y exchanged), plus Perm(x*y*q, y*x*q). 252 Appendix to § 5: an example • • • • Proof obligations. we list here the subproofs we did not fill in (and we will actually skip). Sorted(nil) and Sorted(x*nil): by def. of Sorted. Perm(nil,nil), Perm(x*y*q, y*x*q), if Perm(l,m), then Perm(x*l,x*m), and if Perm(l,m) and Perm(m,p), then Perm(l,p): all come by def. of Perm. If Perm(y*q, r) and Sorted(r) and xy, then Sorted(x*r): this is intuitive, yet it is a little tricky to prove formally. 253 Appendix to § 5: an example • • • All such proofs obligation are only included to show that sorting is done correctly: they do not influence the Sorting Algorithm in the proof. We do not include here. Formal proofs may be found in the Web site of Coq group. 254 Appendix to § 5: an example • • • • • We may already precise the algorithm we get, without knowing the proofs of Harrop statements (they will eventually be removed). We only have to carefully apply the inductive definition of realizer, and to replace by a dummy constant all Harrop subterms. We write the program in the next page, using green color for all Harrop part (a color difficult to see, to stress that they are totally irrelevant). Let “less” be a realizers of x,yN.(xyyx). “less” has type N,NBoolUnitUnit, and 255 less(x,y)=<True,_,_> xy. Appendix to § 5: an example • • • sort(l)=recL(l,<nil,_,_>, x:N,m:L.ins(m,x,_)) : LUnitUnit The map ins:LUnit(NLUnitUnit) takes some sorted list m, and returns some map ins(m), inserting any integer x in m, and preserving the ordering of m: ins(m) = _:Unit. recL(m, x:N. <x*nil,_,_> y:N, f:NLH, x:N. if(1(less(x,y)),x*f(y),y*f(x)) ):NLUnitUnit 256 Lesson 6 Program Extraction from proofs Useless Code Analysis 257 Plan of Lesson 6 • § 6.1 Useless Code. In Program Extraction. • § 6.2 Useless Code Analysis. • Previous Lesson: Realization Interpretation. • Next Lesson: none. 258 § 6.1 Useless Code • Useless Code. Large program are often cluttered with useless code. • If a program is large, most of it comes from previous programs, or was designed some time ago, and it originally performed slightly different tasks. • Thus, there are old tasks of no more interest, producing results of no use. • Such useless tasks require memory space and time to initialize and update parameters of no more use. 259 § 6.1 Useless Code • Useless code may slow down a computation considerably. • Removing it is one of the problem we have to face in programming. • To detect and remove useless parts is conceptually simple • Yet, it is really time consuming. • Thus, useless code removal is often automatized. 260 § 6.1 Useless Code and Program Extraction • Extracting program from proofs produces a large amount of useless code. • In the previous lesson we introduced a simple example: Harrop subterms of any Realizer. • Harrop subterms correspond to purely logical parts of the proof: to the parts of a proof defining no action, but showing the correctness of some action performed by the proof. 261 § 6.1 Useless Code and Program Extraction • Logical part of a proof are of interest only if we want to produce a proof. • They are of no more interest when our task is to write a program. • Thus, Logical parts (subproofs with an Harrop conclusion) are a typical example of useless code: they were of some use in the proof, they are of no further use now in the Realizer. • There are many more examples of useless code in program extracted from proofs. 262 § 6.1 Useless Code and Program Extraction • We look now through some examples of useless code in Realizers which is included in no Harrop subterm. • Such examples are written in an extension of the language for Realizers from the previous lesson: simply typed lambda calculus + all Bohm-Berarducci Data Types. • For a formal description of this language we refer to Boerio Ph.d.. 263 § 6.1 Useless Code and Program Extraction • Some hint about the language for Data Types. Each data type D has finitely many constructors c1, …, cn. Each ci has type T1, …, TkiD, with Ti either previously defined type, or D itself. • Constructors true:D, false:D: then D is Bool. • Constructors in1:A1D, …, inn:AnD: then D is A1+…+An. • Constructor <_>:A1,…,AnD: D is A1… An. • Constructors zero:D, s:DD: then D={integers}. • Constructors nil:D, cons:A,DD: then D is {lists 264 on A} § 6.1 Useless Code and Program Extraction • Some hint about the language for Data Types. If D has constructors c1:T1[D], …, cn:Tn[D], then we denote D by: X.(T1[X], …, Tn[X]) (the smallest X closed under c1, …, cn) • For each data type D we add a primitive recursor recD. Some examples are: • D=Bool. Then recD=if. • D=A1+…+An. Then recD=case. • D={integers}, {lists}. Then recD was defined in 265 the previous lesson. § 6.1 Example 0 • A particular case of Useless Code: Dead code. A subterm t is dead code if, whatever the input values are, there is an evaluation strategy not evaluating t. • A trivial example: 3 is dead code (never used) in (x.5)(3). • Usually, it is not so easy to detect dead code! It is even a non-recursive problem. • Indeed, to decide whether b is dead code in if(h(x)=0,a,b) we have to decide whether h(x)=0 for all x, or not, and this is a non-recursive266 problem. § 6.1 Example 1 • Let p a program of input x, of type A or B or C. • Let q be a program feeding such an x, but with possible types only A, B. Compose p with q. • Consider any “case analysis” in p over the type of the input x. There are three clauses, according if the type of x is A or B or C. • The “C” clause is now dead code: it is never used • Such situation may happen if we extract a program from a proof having a Lemma slightly more general than required: we prove , then we apply it to (instead of ). 267 § 6.1 Example 1 • 1. 2. 3. • Let for instance p:A+B+CE defined by: p = x:A+B+C. case(x,a(x),b(x),c(x)) q = j°f, with f:DA+B j: A+BA+B+C canonical injection. Then c(x) is never used, because x is obtained from f, hence is not in C. 268 § 6.1 Example 2 • The most general case of Useless code is a code never affecting the final result, even if it may be used for some inputs. • Let h(n,a,b) = <an,bn>:AB be recursively defined by: • <a0, b0> = <a, b> : AB • <ai+1,bi+1> = <f(ai), g(bi)> : AB • Define k(n) = (left component of h(n)) :A. 269 § 6.1 Example 2 • Look to the computation of k(n): <a,b>, <f(a),g(b)>, <f(f(a)),g((b))>, ..., <fn(a),gn(b)> • Eventually we trash gn(a) and we return an=fn(a). • g, b are dead code in k (they are never used, under a suitable evaluation strategy). • The pairing operation <_,_> is useless code in k: it is indeed used, however, it never affects the final result an=fn(a). • Again, this situation may arise in a Realizer if we proved a Lemma having a goal slightly more 270 general than required. § 6.1 Example 3 • Let length(L) be a function taking a list L, then returning the length n of it. • Look at the computation of length(L). • L = cons(x1,cons(x2,...cons(xn)...)), but the actual values of x1, x2,... xn do not matter. • Eventually, we trash all xi’s, and we return the number of cons’s. 271 § 6.1 Example 3 • All elements of L are now useless code in f. • We compute the elements of L, using an unpredictable amount of time; yet, we do not use them in order to compute length(L). • This situation may arise in a Realizer when: • we first prove the existence of L, then, in the rest of the proof, we only use the number of elements of L. 272 § 6.2 Useless code Analysis • • • • • In order to perform Useless code Analysis, we extend the language with subtyping. We add a dummy type Unit A for typing dead code, the constant unit:Unit, the typing rule: if a:A, then a: Unit. Data types are covariant: if A’A, B’B, then A’B’ AB. Arrow is contravariant: if A A’ , B’ B, then A’B’ AB. We allow now null constructor c:Unit in a Data Type D. Such constructors build no term: they 273 intend to represent redundant code in D. § 6.2 Useless code Analysis • • • • For each type A, we may define some trivial term dummyA:A by induction on A. The type Unit represents the set of all terms, with trivial equality: all terms of type Unit are intended to be equal. If we quotient Unit up to its equality notion, we get only one equivalent class: Unit is a cardinality 1 type. As we did in the previous lesson, we define Harrop types as types of cardinality 1 in the settheoretical model. Unit is an Harrop type. 274 § 6.2 Useless code Analysis • Definition. A subtype is strictly positive iff it occurs in the left-hand side of no arrow type, including arrows in constructor types. • Lemma 1. A is Harrop iff it is an Harrop type w.r.t Unit (iff any strictly positive atomic type in A is Unit). • Corollary 1. For any term t having an Harrop A, t=dummyA in the set-theoretical model. • Corollary 2. Let t : A, and Hp(t) be obtained by replacing all subterms v having an Harrop B by dummyB. Then t and Hp(t) are observationally 275 equal of type A. § 6.2 Useless code Analysis • Remark. Corollary 2 says that each subterm of Harrop type is useless, because it may be replaced by a dummy constant without altering the value of the term. • Hence Hp(t) removes useless code in t. • We will introduce now a redundant code analysis much more general than in the previous lesson: before applying Hp, we will retype any term in order to maximize subterms with an Harrop type. 276 § 6.2 Main Results • Theorem 1. Assume |-t:A. • Retype with Unit some parts of t in such a way to preserve the condition |-t:A. • Then replace all subterms v of t now having an Harrop type B by the constant dummyB. • The term u we obtain in this way is equal to t in the set-theoretical model. 277 § 6.2 Main Results • Theorem 1 outlines method for removing useless code. • We have only to select some retyping of t which: 1. is correct, and 2. does not change the final typing |-t:A of t. • Let u be the resulting term. Then every subterm in t which got a type U is useless, and it may be removed by forming Hp(u). 278 § 6.2 Main Results • Main Theorem. Let t be any term of simply typed lambda calculus with Bohm-Berarducci Data Types. • Order terms we get by a retyping of t according to the set of Harrop subterms they have. 1. This order has a maximum, a term u having a maximum of Harrop subterms. Denote u by Fl(t). 2. Fl(t) may be computed in linear time over the type-decorated version of t. 279 § 6.2 Using Fl(t) • Fact. Fix any term t from the Examples 1-3. Then all dead code we found belongs to some Harrop subterms of Fl(t). • Thus, all dead code in Examples 1-3 may be removed by first computing Fl(t), then Hp(Fl(t)). • By construction, context and type of t and Hp(Fl(t)) are the same, and t=SetHp(Fl(t)). 280 § 6.2 The “Iso” map • Some further optimization may be obtained by applying a new map, Iso (not to be included here) to the term Hp(Fl(t)) • Iso(.) removes some useless code which is not dead. • Example are: Iso(.) turns <a,u>,<u,a>, p1(a) (if a:AU), p2(a) (if a:UA) into a. • Iso(.) is but a minor detail. 281 § 6.2 About Efficiency 1. Fl(p) is computed using saturation over a subset of the adjacency graph of typing assignment. Thus, Fl is an higher-order version of Flow algorithm for compilers. 2. The type-decorated version p’ of p is, in theory, exponential in p. Thus, in theory, Fl, which is linear in the size of p’, is exponential. 3. In programming practice, however, p’ is feasible to compute. So Fl is feasible, too. 4. In 2000, N. Kobayashi found a way to get 282 rid of exponential time. § 6.2 Up-to-date: Year 2000 • N. Kobayashi (C.S., Tokyo Univ.). For languages with let-polymorphism, Fl(t) may be found in time (n log*(n)) over the size of the untyped program t. • We explain what is log*(n) in the next slide. • Kobayashi idea is merging the algorithm inferring the type with the algorithm inferring useless code out of typing. • In this way, we do not have to apply type inference to subterms with an Harrop type, because they are redundant code and they will be 283 removed. § 6.2 log*(n) • 1. 2. 3. 4. 5. • • Log*(n) is the inverse of exp*(n) = expn(1) … (the 2 super-exponential, or a tower of n digits: 22 log*(2) = log*(2) = 1 log*(4) = log*(22) = 2 2 log*(16) = log*(22 ) = 3 22 2 log*(65536) = log*(2 ) = 4 For n 265536, we have log*(n) 5. 265536 is a number of 19,729 digits! O(n*log*(n)) is, in practice, O(n*5) = O(n). 284 § 6.2 References • “Type-bases useless code elimination for functional programs (Position Paper)”, by S. Berardi, M. Coppo, F. Damiani and P. Giannini, to appear on proceeding of SAIG conference on functional programming. • “Automatic Useless code detection and elimination for HOT functional programs”, by F. Damiani, P. Giannini, J.F.P. 10 (6): 509-559, 2000. 285
Scarica
