From Implicit Complexity to Quantitative Resource Analysis Bounded Linear Logic and Linear Dependency

(1)

From Implicit Complexity to Quantitative Resource Analysis

Bounded Linear Logic and Linear Dependency

Ugo Dal Lago

(Joint work with Martin Hoffman and Marco Gaboardi)

PhD Open, University of Warsaw, June 25-27, 2015

(2)

Part I

Bounded Linear Logic

(3)

Comparing ICC Systems.

§ “Traditional” definitions of equivalence between programming languages do not make much sense.

§ The sets of representable first-order functions are almost the same.

§ The systems under consideration are anyway sound and complete characterization of polynomial time computable functions.

§ But we could have higher-order functions or not.

§ Some systems have iteration, others have recursion.

§ . . .

§ How can we express that one system S is intensionally more powerful than another one, P?

§ One possibility is the one advocated by Felleisen [Felleisen95] :

§ S is (strictly) more expressive than P iff S is a syntactical extension ofP and the constructs characterizing S are not derivable inP.

§ Too fine-grained for our purposes.

(4)

Comparing ICC Systems.

§ . . .

(5)

Comparing ICC Systems.

§ . . .

(6)

Comparing ICC Systems.

§ . . .

(7)

Comparing ICC Systems.

§ . . .

(8)

Compositional Embeddings.

§ We here adopt another criterion, which many others have previously considered.

§ S is at least as expressive as P iff there exists a compositional embedding of P into S.

§ What is a compositional embedding? Well... it depends.

1. On the syntax ofS and P: the embedding should act homeomorphically onP’s syntax.

2. On the (operational?) semantics ofS and P: the

embedding should map anyP program to an equivalent one.

§ Usually, the languages of S and P are defined inductively.

§ The meaning of 1. is reasonably clear.

§ What about the semantics?

§ We prove 2. by studying denotational semantics.

(9)

The Current Situation.

§ Let’s consider some of the known characterizations of polynomial time functions: LFPL [Hofmann99], BC [BellantoniCook92], and LLL [Girard97].

§ It seems that LFPL and BC are not intensionally comparable:

§ On one side a system of non-size-increasing functions. On the other side a system which is complete for polytime functions.

§ But no formal result.

§ LLL vs. BC: the same.

§ Murawski and Ong showed that there cannot be any embedding (satisfying certain properties) of BC into LAL.

§ On the other hand, LAL is a system for higher-order functions, while BC is a function algebra...

§ What about BLL?

§ One of the very first characterizations of the polytime functions [GirardScedrovScott92].

§ Hasn’t received too much attention since then.

(10)

The Current Situation.

§ What about BLL?

(11)

The Current Situation.

§ What about BLL?

(12)

Our Results.

§ A natural generalization of BLL, called QBAL.

§ A soundness theorem for QBAL with respect to polynomial time.

§ A compositional embedding of Hofmann’s LFPL into QBAL.

§ A compositional embedding of Leivant’s RRW into QBAL.

§ BC itself can be easily embedded into RRW.

(13)

Our Results.

§ A natural generalization of BLL, called QBAL.

§ A soundness theorem for QBAL with respect to polynomial time.

§ A compositional embedding of Hofmann’s LFPL into QBAL.

§ A compositional embedding of Leivant’s RRW into QBAL.

§ BC itself can be easily embedded into RRW.

(14)

Bounded Linear Logic.

§ It is a refinement on (intuitionistic) linear logic:

!nA ( 1

!_1`nA ( A

!n`mA (!nAb!mA

!_nmA (!n!_mA wheren and m are natural numbers.

§ More generally, n ad m could be polynomials (on possibly many variables) and not just natural numbers.

§ Moreover,! can act as a binder for resource variables:

!_xăpA. As an example, the following is an axiom:

!xăp`qA (!xăpAb!yăqArx Ð y ` ps

§ Intuitively:

!xăpA „ Arx Ð 0s b Arx Ð 1s b . . . b Arx Ð p ´ 1s.

(15)

Bounded Linear Logic.

!nA ( 1

!_1`nA ( A

!n`mA (!nAb!mA

§ Intuitively:

(16)

Bounded Linear Logic.

!nA ( 1

!_1`nA ( A

!n`mA (!nAb!mA

§ Intuitively:

(17)

Quantified Bounded Affine Logic.

§ Usual, second order quantification is available in QBAL.

§ It was available in BLL, too.

§ There is another form of quantification in QBAL: universal and existential quantification on resource variables:

Dpxq :C .A

@pxq :C .A whereC is a set of constraints.

§ Example:

Dpx, yq : tx ď z², y ď xu.!_xy²A

Notice that the constraints in tx ď z², y ď xu enforce a polynomial upper bound on both x and y: x ď z² and y ď x ď z².

§ Not by coincidence!

§ Sequents have the form Γ $_C A.

§ Rules for first-order quantifier are standard.

§ The rules coming from BLL leaves C unchanged.

(18)

Rules: Some Examples

§ Axiom:

A Ď_C B A $C B A

§ Linear arrow:

Γ $_CA ∆, B $_C C Γ, ∆, A ( B $C C L(

Γ, A $_C B Γ $_CA ( B R(

§ Promotion:

A₁, . . . , A_n$_C B D, x ă p |ù C x R FV pDq p Ď_D q_i

!_xăq₁A₁, . . . , !_xăq_nA_n$_D!_xăpB P_!

§ Existential quantification:

Γ $_C Atp{xu C |ù Dtp{xu Γ $_C Dx :D.A R_Dx Γ, A $_{C YD} C x R FV pΓq Y FV pCq Y FV pC q

Γ, Dx :D : A $_C C LDx

(19)

Rules: Some Examples

§ Axiom:

A Ď_C B A $C B A

§ Linear arrow:

Γ $_CA ∆, B $_C C Γ, ∆, A ( B $C C L(

Γ, A $_C B Γ $_CA ( B R(

§ Promotion:

(20)

Rules: Some Examples

§ Axiom:

A Ď_C B A $C B A

§ Linear arrow:

Γ $_CA ∆, B $_C C Γ, ∆, A ( B $C C L(

Γ, A $_C B Γ $_CA ( B R(

§ Promotion:

(21)

Rules: Some Examples

§ Axiom:

A Ď_C B A $C B A

§ Linear arrow:

Γ $_CA ∆, B $_C C Γ, ∆, A ( B $C C L(

Γ, A $_C B Γ $_CA ( B R(

§ Promotion:

(22)

Programming in QBAL...

§ ...is not so different from programming in BLL.

§ For example, the type of natural numbers remains the same:

N_p “ @α.!xăppαpxq( αpx ` 1qq ( αp0q ( αppq It is parametrized on a polynomial p.

§ Similarly for any arbitrary free algebraW.

§ These types support the usual impredicative iteration schema.

§ The added value provided by first-order quantification will show up in the embeddings.

(23)

QBAL is Still Polytime Sound.

§ We prove this property by exploiting the realizability interpretation of BLL [HofmannScott04].

§ Hofmann and Scott’s realizability model must be adapted to the presence of first-order quantification. Categorically:

§ Objects are the same.

§ The notion of a morphism must be slightly modified. This reflects the changes in the underlying syntax: fromΓ $ A in BLL toΓ $_C A in QBAL.

Theorem

If π : W_x$HW_p, then the functionJπK is computable in polynomial time.

§ Main idea of the proof : ifπ is a proof, JπK is a

morphism, and morphisms can be computed in polynomial time by definition.

(24)

Embedding LFPL.

§ LFPL is a linear functional language [Hofmann99].

§ All functions are non-size-increasing by construction.

§ Higher-order primitive recursion.

§ Nested recursion allowed.

§ Types: A, B ::“ ˛ | Nat | A b B | A ( B.

§ The embedding:

x˛y^q_p “ Dε : t1 ď pu.1 xNat y^q_p “ Np

xA b By^q_p “ Dpx, yq : tx ` y ď pu.xAy^q_xb xBy^q_y xA( By^qp “ @pxq : tx ` p ď qu.xAy^q_x( xBy^q_x`p and

x : A1, . . . , x : An$ M : B ó

xA1y

ř_n

i“1xi

x1 , . . . , xAny

ř_n

i“1xi

xn $HxBy

ř_n

i“1xi

řn i“1xi

(25)

Embedding LFPL.

§ The embedding:

x : A1, . . . , x : An$ M : B ó

xA1y

ř_n

i“1xi

x1 , . . . , xAny

ř_n

i“1xi

xn $HxBy

ř_n

i“1xi

řn i“1xi

(26)

Embedding LFPL.

§ The embedding:

x : A1, . . . , x : An$ M : B ó

xA1y

ř_n

i“1xi

x1 , . . . , xAny

ř_n

i“1xi

xn $HxBy

ř_n

i“1xi

řn i“1xi

(27)

Embedding LFPL.

§ The embedding:

x : A1, . . . , x : An$ M : B ó

xA1y

ř_n

i“1xi

x1 , . . . , xAny

ř_n

i“1xi

xn $HxBy

ř_n

i“1xi

řn i“1xi

(28)

Embedding LFPL.

§ The embedding:

x : A1, . . . , x : An$ M : B ó

xA1y

ř_n

i“1xi

x1 , . . . , xAny

ř_n

i“1xi

xn $HxBy

ř_n

i“1xi

řn i“1xi

(29)

Embedding LFPL.

§ The embedding:

x : A1, . . . , x : An$ M : B ó

xA1y

ř_n

i“1xi

x1 , . . . , xAny

ř_n

i“1xi

xn $HxBy

ř_n

i“1xi

řn i“1xi

(30)

Embedding RRW.

§ RRW is a characterization of the polytime functions introduced in the nineties [Leivant93].

§ A subalgebra of the primitive recursion functions.

§ For every word algebraW , there are infinitely many types (tiers)W0, W1, W2, . . ..

§ In a recursion, the tier of the argument must be greater than the tier of the result.

§ The embedding:

$ f : Wi1ˆ . . . ˆ Win Ñ Wi

ó

Wx1, . . . , Wxn $x_j1ďy,...,x_jmďy W_ppx_k1_,...,x_kh_q`y

§ The proof goes by induction on the derivation for $ f .

§ Interestingly, the embedding is very similar to the proof of soundness for BC, itself a close relative of RRW.

§ This cannot be done in ordinary BLL.

(31)

Embedding RRW.

§ The embedding:

ó

(32)

Embedding RRW.

§ The embedding:

ó

(33)

Embedding RRW.

§ The embedding:

ó

(34)

Embedding RRW.

§ The embedding:

ó

(35)

Embedding RRW.

§ The embedding:

ó

(36)

What about Light Logics?

§ Here the situation is different.

!A ( 1

!A ( A

!A (!Ab!A

!A (!!A

§ We were not able to embed any light logic (except SLL) into QBAL.

§ Actually, ELL can be embedded into (Q)BAL.

!A ó

!xă0A

§ But the embedding is not sensible from a dynamical point of view!

(37)

What about Light Logics?

!A ( 1

!A ( A

!A (!Ab!A

!A (!!A

!A ó

!xă0A

(38)

What about Light Logics?

!A ( 1

!A ( A

!A (!Ab!A

!A (!!A

!A ó

!xă0A

(39)

What about Light Logics?

!A ( 1

!A ( A

!A (!Ab!A

!A (!!A

!A ó

!xă0A

(40)

What about Light Logics?

!A ( 1

!A ( A

!A (!Ab!A

!A (!!A

!A ó

!xă0A

(41)

Conclusions

§ Moral: (a natural extension of) BLL is an interesting ICC system with strong intensional expressive power:

QBAL

BLL RRW LFPL

SLL BC

§ Price to pay: the system is not implicit!

(42)

Conclusions

QBAL

BLL RRW LFPL

SLL BC

(43)

Conclusions

QBAL

BLL RRW LFPL

SLL BC

(44)

Part II

Program Logics, Type Systems, and

Relative Completeness

(45)

Floyd-Hoare Logics

§ Judgments:

{P}C{Q}

precondition postcondition program

§ Some rules:

tP rE{xsu x :“ E tP u tP u skip tP u tP u C tQu tQu D tRu

tP u C; D tRu

R ñ P tP u C tQu Q ñ S tRu C tSu

(46)

Floyd-Hoare Logics

§ Judgments:

{P}C{Q}

precondition postcondition program

§ Some rules:

tP rE{xsu x :“ E tP u tP u skip tP u tP u C tQu tQu D tRu

tP u C; D tRu

R ñ P tP u C tQu Q ñ S tRu C tSu

(47)

Relative Completeness

§ The axiom system is sound.

§ If true formulas of PA are used as side-conditions.

§ It’s also relatively complete [Cook78].

§ All true assertions can be derived if all true PA formulas can be used as side-conditions.

§ Concrete axiom systems can be derived by throwing in a concrete sound formal system F for PA.

§ They are sound.

§ They are incomplete, due to Gödel incompleteness.

§ F is solely responsible for their incompleteness.

§ A variety of FH logics enjoy the properties above.

§ Including some for higher-order programs [Honda2000]...

§ ... and some in which the complexity of programs and not only their extensional behavior is taken into account.

(48)

Program Logics

Degree of Completeness

Prop ert y Co mplexit y

(49)

Program Logics

Degree of Completeness

Prop ert y Co mplexit y

(50)

Type Systems

Degree of Completeness

Prop ert y Co mplexit y

(51)

Type Systems

Degree of Completeness

Prop ert y Co mplexit y

(52)

Type Systems

Degree of Completeness

Prop ert y Co mplexit y

(53)

Some Examples

§ Simply Types

§ “Well-typed programs do not go wrong”.

§ Type inference and type checking are often decidable.

§ Dependent Types

§ Type checking is decidable.

§ Interesting, extensional properties can be specified.

§ Intersection Types

§ Sound and complete for termination.

§ Type inference is not decidable.

§ Studying programs as functions requires considering an infinite family of type derivations.

(54)

This Work

Degree of Completeness

Prop ert y Co mplexit y

BLL

d`PCF

(55)

Why?

§ d`PCF captures both:

§ Extensional properties of programs: what function a program computes.

§ Intensional properties of programs: the time complexity of programs.

§ Implicit Computational Complexity

§ Many type-theoretical characterizations of complexity classes.

§ Most of them have decidable type inference...

§ ... and poor expressive power.

§ Idea: drop decidability constraints, and concentrate on expressivity.

§ Recover decidability by considering proper fragments.

(56)

Why?

(57)

Why?

(58)

Why?

(59)

Why?

(60)

Part III

d`PCF

(61)

d`PCF: a Bird’s Eye View

§ A type system for the lambda calculus with constants and full higher-order recursion. (i.e. PCF).

§ Greatly inspired by BLL.

§ Indices are not necessarily polynomials, but terms from a signature Σ.

§ Symbols inΣ are given a meaning by an equational programE.

§ Side conditions in the form:

φ; Φ |ù^E I ď J

§ Types and modal types are defined as follows:

σ, τ ::“ NatrI, Js | A ( σ basic types A, B ::“ ra ă Is ¨ σ modal types

(62)

d`PCF: a Bird’s Eye View

§ A type system for the lambda calculus with constants and full higher-order recursion. (i.e. PCF).

§ Greatly inspired by BLL.

§ Indices are not necessarily polynomials, but terms from a signature Σ.

§ Symbols inΣ are given a meaning by an equational programE.

§ Side conditions in the form:

φ; K1ď H1, . . . , Knď Hn |ù^E I ď J

§ Types and modal types are defined as follows:

σ, τ ::“ NatrI, Js | A ( σ basic types A, B ::“ ra ă Is ¨ σ modal types

(63)

The Meaning of Types

ra ă Is ¨ σ ( τ ó

pσt0{au b . . . b σtI ´ 1{auq ( τ

(64)

The Meaning of Types

ra ă Is ¨ σ ( τ ó

pσt0{au b . . . b σtI ´ 1{auq ( τ

(65)

d`PCF: Subtyping

φ; Φ |ù^E K ď I φ; Φ |ù^E J ď H

φ; Φ $^E NatrI, Js Ď NatrK, Hs

φ; Φ $Ê B Ď A φ; Φ $Ê σ Ď τ φ; Φ $Ê A ( σ Ď B ( τ

φ, a; Φ, a ă J $^E σ Ď τ φ; Φ |ù^E J ď I

φ; Φ $^E ra ă Is ¨ σ Ď ra ă Js ¨ τ

(66)

d`PCF: Subtyping

φ; Φ |ù^E K ď I φ; Φ |ù^E J ď H

φ; Φ $^E NatrI, Js Ď NatrK, Hs

φ; Φ $Ê B Ď A φ; Φ $Ê σ Ď τ φ; Φ $Ê A ( σ Ď B ( τ

φ, a; Φ, a ă J $^E σ Ď τ φ; Φ |ù^E J ď I

φ; Φ $^E ra ă Is ¨ σ Ď ra ă Js ¨ τ

(67)

d`PCF: Some Rules

Constraints

φ; Φ $^E ra ă Is ¨ σ Ď ra ă 1s ¨ τ φ; Φ; Γ, x : ra ă Is ¨ σ $^E₀ x : τ t0{au V

Weight

(68)

d`PCF: Some Rules

φ; Φ $^E NatrI ` 1, J ` 1s Ď NatrK, Hs φ; Φ; Γ $^E_Lt : NatrI, Js

φ; Φ; Γ $^E_Lsptq : NatrK, Hs S

(69)

d`PCF: Some Rules

φ; Φ; Γ, x : ra ă Is ¨ σ $^E_J t : τ φ; Φ; Γ $^E_J λx.t : ra ă Is ¨ σ ( τ L

(70)

d`PCF: Some Rules

φ; Φ $^E Σ Ď Γ Zř

aăI∆ φ; Φ; Γ $^E_J t : ra ă Is ¨ σ ( τ

φ, a; Φ, a ă I; ∆ $^E_K u : σ φ; Φ; Σ $^E_J`^ř

aďIK`I tu : τ A

(71)

d`PCF: Some Rules

Sum of Modal Types

aďIK`I tu : τ A

(72)

d`PCF: Some Rules

Bounded Sum of Modal Types

aďIK`I tu : τ A

(73)

d`PCF: Intended Meaning

a; H; H $_It : rb ă Js ¨ Natras ( NatrKs What does this mean?

§ t computes a function from natural numbers to natural numbers.

§ Something extensional:

§ On input a natural numbern, t returns a natural number Ktn{au

§ Something more intensional:

§ The cost of evaluation oft on an input n is pI ` Jqtn{au.

§ Two questions:

§ Is this correct?

§ How many programs can be captured this way?

(74)

d`PCF: Intended Meaning

§ Two questions:

§ Is this correct?

(75)

d`PCF: Intended Meaning

§ Two questions:

§ Is this correct?

(76)

d`PCF: Intended Meaning

§ Two questions:

§ Is this correct?

(77)

Intensional Soundness

§ A generalization of KAM which takes constants and fixpoints into account.

§ Lift the type system to closures, stack and environments.

Lemma (Measure Decreasing)

Suppose pt, , q Ñ^˚D Ñ E and let D have weight I. Then one of the following holds:

1. E has weight J, φ; Φ |ù I “ J but |D| ą |E|;

2. E has weight J, φ; Φ |ù I ą J and |E| ă |D| ` |t|;

Theorem

Let H; H; H $_It : NatrJ, Ks and t óⁿm. Thenn ď |t| ¨JIK

Eρ

(78)

Intensional Soundness

§ A generalization of KAM which takes constants and fixpoints into account.

§ Lift the type system to closures, stack and environments.

Lemma (Measure Decreasing)

Suppose pt, , q Ñ^˚D Ñ E and let D have weight I. Then one of the following holds:

1. E has weight J, φ; Φ |ù I “ J but |D| ą |E|;

2. E has weight J, φ; Φ |ù I ą J and |E| ă |D| ` |t|;

Theorem

Let H; H; H $_It : NatrJ, Ks and t óⁿm. Thenn ď |t| ¨JIK

Eρ

(79)

Completeness for Programs

§ The following holds only whenE is universal.

§ p|σ|q is the PCF type underlying σ, i.e. its skeleton.

Lemma (Weighted Subject Expansion)

If D has weight I and type σ and C is typable with type p|σ|q.

Then, C Ñ D implies that C has weight J and type σ, where φ; Φ |ù J ď I ` 1.

Theorem (Relative Completeness for Programs)

Let t be a PCF program such that t óⁿm. Then, there exist two index termsI and J such that JIK

U ď n and JJK

U “ m and such that the termt is typable in d`PCF as H; H; H $^U_I t : NatrJs.

(80)

Completeness for Programs

§ The following holds only whenE is universal.

§ p|σ|q is the PCF type underlying σ, i.e. its skeleton.

Lemma (Weighted Subject Expansion)

If D has weight I and type σ and C is typable with type p|σ|q.

Then, C Ñ D implies that C has weight J and type σ, where φ; Φ |ù J ď I ` 1.

Theorem (Relative Completeness for Programs)

Let t be a PCF program such that t óⁿm. Then, there exist two index termsI and J such that JIK

U ď n and JJK

U “ m and such that the termt is typable in d`PCF as H; H; H $^U_I t : NatrJs.

(81)

Completeness for Functions

§ It strongly relies on the universality ofU.

§ Suppose that tπnunPN is an r.e. family of type derivations:

§ For the same termt;

§ Having the samePCF skeleton (as type derivations);

Then we can turn them into a single, parametric type derivation.

Theorem (Relative Completeness for Functions) Suppose that t is a PCF term such that $ t : Nat Ñ Nat.

Moreover, suppose that there are two (total and computable) functionsf, g : N Ñ N such that t n ó^gpnqfpnq. Then there are termsI, J, K with JI ` JK ď g and JKK “ f , such that

a; H; H $^U_I t : rb ă Js ¨ Natras ( NatrKs.

(82)

Completeness for Functions

§ It strongly relies on the universality ofU.

§ Suppose that tπnunPN is an r.e. family of type derivations:

§ For the same termt;

§ Having the samePCF skeleton (as type derivations);

Then we can turn them into a single, parametric type derivation.

Theorem (Relative Completeness for Functions) Suppose that t is a PCF term such that $ t : Nat Ñ Nat.

Moreover, suppose that there are two (total and computable) functionsf, g : N Ñ N such that t n ó^gpnqfpnq. Then there are termsI, J, K with JI ` JK ď g and JKK “ f , such that

a; H; H $^U_I t : rb ă Js ¨ Natras ( NatrKs.

(83)

Conclusions

§ A relatively complete type system d`PCF.

§ Type inference, type checking and derivation checking are undecidable, in general.

§ ... but can become manageable ifE is simple enough.

§ Light Logics!

§ Another result: relative decidability of type inference.

t

E A

{φi; Φi |= Ii ≤ Ji}i∈F

T

(84)