-
On Randomized Computational Models and Complexity Classes: a Historical Overview
Authors:
Melissa Antonelli,
Ugo Dal Lago,
Paolo Pistone
Abstract:
Since their appearance in the 1950s, computational models capable of performing probabilistic choices have received wide attention and are nowadays pervasive in almost every areas of computer science. Their development was also inextricably linked with inquiries about computation power and resource issues. Although most crucial notions in the field are well-known, the related terminology is someti…
▽ More
Since their appearance in the 1950s, computational models capable of performing probabilistic choices have received wide attention and are nowadays pervasive in almost every areas of computer science. Their development was also inextricably linked with inquiries about computation power and resource issues. Although most crucial notions in the field are well-known, the related terminology is sometimes imprecise or misleading. The present work aims to clarify the core features and main differences between machines and classes developed in relation to randomized computation. To do so, we compare the modern definitions with original ones, recalling the context in which they first appeared, and investigate the relations linking probabilistic and counting models.
△ Less
Submitted 18 September, 2024;
originally announced September 2024.
-
Tropical Mathematics and the Lambda Calculus I: Metric and Differential Analysis of Effectful Programs
Authors:
Davide Barbarossa,
Paolo Pistone
Abstract:
We study the interpretation of the lambda-calculus in a framework based on tropical mathematics, and we show that it provides a unifying framework for two well-developed quantitative approaches to program semantics: on the one hand program metrics, based on the analysis of program sensitivity via Lipschitz conditions, on the other hand resource analysis, based on linear logic and higher-order prog…
▽ More
We study the interpretation of the lambda-calculus in a framework based on tropical mathematics, and we show that it provides a unifying framework for two well-developed quantitative approaches to program semantics: on the one hand program metrics, based on the analysis of program sensitivity via Lipschitz conditions, on the other hand resource analysis, based on linear logic and higher-order program differentiation. To do that we focus on the semantic arising from the relational model weighted over the tropical semiring, and we discuss its application to the study of "best case" program behavior for languages with probabilistic and non-deterministic effects. Finally, we show that a general foundation for this approach is provided by an abstract correspondence between tropical algebra and Lawvere's theory of generalized metric spaces.
△ Less
Submitted 27 November, 2023;
originally announced November 2023.
-
Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories
Authors:
Melissa Antonelli,
Ugo Dal Lago,
Davide Davoli,
Isabel Oitavem,
Paolo Pistone
Abstract:
We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably-defined theory à la Buss (expressed in this new language) precisely capture polytime random functions. Then, we provide two new characterizations of the semantic class BPP obtained by internalizing the error-bound check within a logical system: the first relies on measure-sens…
▽ More
We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably-defined theory à la Buss (expressed in this new language) precisely capture polytime random functions. Then, we provide two new characterizations of the semantic class BPP obtained by internalizing the error-bound check within a logical system: the first relies on measure-sensitive quantifiers, while the second is based on standard first-order quantification. This leads us to introduce a family of effectively enumerable subclasses of BPP, called BPP_T and consisting of languages captured by those probabilistic Turing machines whose underlying error can be proved bounded in the theory T. As a paradigmatic example of this approach, we establish that polynomial identity testing is in BPP_T where T=$\mathrm{I}Δ_0+\mathrm{Exp}$ is a well-studied theory based on bounded induction.
△ Less
Submitted 25 November, 2023;
originally announced November 2023.
-
On the Lattice of Program Metrics
Authors:
Ugo Dal Lago,
Naohiko Hoshino,
Paolo Pistone
Abstract:
In this paper we are concerned with understanding the nature of program metrics for calculi with higher-order types, seen as natural generalizations of program equivalences. Some of the metrics we are interested in are well-known, such as those based on the interpretation of terms in metric spaces and those obtained by generalizing observational equivalence. We also introduce a new one, called the…
▽ More
In this paper we are concerned with understanding the nature of program metrics for calculi with higher-order types, seen as natural generalizations of program equivalences. Some of the metrics we are interested in are well-known, such as those based on the interpretation of terms in metric spaces and those obtained by generalizing observational equivalence. We also introduce a new one, called the interactive metric, built by applying the well-known Int-Construction to the category of metric complete partial orders. Our aim is then to understand how these metrics relate to each other, i.e., whether and in which cases one such metric refines another, in analogy with corresponding well-studied problems about program equivalences. The results we obtain are twofold. We first show that the metrics of semantic origin, i.e., the denotational and interactive ones, lie \emph{in between} the observational and equational metrics and that in some cases, these inclusions are strict. Then, we give a result about the relationship between the denotational and interactive metrics, revealing that the former is less discriminating than the latter. All our results are given for a linear lambda-calculus, and some of them can be generalized to calculi with graded comonads, in the style of Fuzz.
△ Less
Submitted 9 February, 2023;
originally announced February 2023.
-
An Arithmetic Theory for the Poly-Time Random Functions
Authors:
Melissa Antonelli,
Ugo Dal Lago,
Davide Davoli,
Isabel Oitavem,
Paolo Pistone
Abstract:
We introduce a new bounded theory RS^1_2 and show that the functions which are Sigma^b_1-representable in it are precisely random functions which can be computed in polynomial time. Concretely, we pass through a class of oracle functions over string, called POR, together with the theory of arithmetic RS^1_2. Then, we show that functions computed by poly-time PTMs are arithmetically characterized b…
▽ More
We introduce a new bounded theory RS^1_2 and show that the functions which are Sigma^b_1-representable in it are precisely random functions which can be computed in polynomial time. Concretely, we pass through a class of oracle functions over string, called POR, together with the theory of arithmetic RS^1_2. Then, we show that functions computed by poly-time PTMs are arithmetically characterized by a class of probabilistic bounded formulas.
△ Less
Submitted 6 February, 2023; v1 submitted 27 January, 2023;
originally announced January 2023.
-
On Quantitative Algebraic Higher-Order Theories
Authors:
Ugo Dal Lago,
Furio Honsell,
Marina Lenisa,
Paolo Pistone
Abstract:
We explore the possibility of extending Mardare et al. quantitative algebras to the structures which naturally emerge from Combinatory Logic and the lambda-calculus. First of all, we show that the framework is indeed applicable to those structures, and give soundness and completeness results. Then, we prove some negative results which clearly delineate to which extent categories of metric spaces c…
▽ More
We explore the possibility of extending Mardare et al. quantitative algebras to the structures which naturally emerge from Combinatory Logic and the lambda-calculus. First of all, we show that the framework is indeed applicable to those structures, and give soundness and completeness results. Then, we prove some negative results which clearly delineate to which extent categories of metric spaces can be models of such theories. We conclude by giving several examples of non-trivial higher-order quantitative algebras.
△ Less
Submitted 28 April, 2022;
originally announced April 2022.
-
Curry and Howard Meet Borel
Authors:
Melissa Antonelli,
Ugo Dal Lago,
Paolo Pistone
Abstract:
We show that an intuitionistic version of counting propositional logic corresponds, in the sense of Curry and Howard, to an expressive type system for the probabilistic event lambda-calculus, a vehicle calculus in which both call-by-name and call-by-value evaluation of discrete randomized functional programs can be simulated. Remarkably, proofs (respectively, types) do not only guarantee that vali…
▽ More
We show that an intuitionistic version of counting propositional logic corresponds, in the sense of Curry and Howard, to an expressive type system for the probabilistic event lambda-calculus, a vehicle calculus in which both call-by-name and call-by-value evaluation of discrete randomized functional programs can be simulated. Remarkably, proofs (respectively, types) do not only guarantee that validity (respectively, termination) holds, but also reveal the underlying probability. We finally show that by endowing the type system with an intersection operator, one obtains a system precisely capturing the probabilistic behavior of lambda-terms.
△ Less
Submitted 21 March, 2022;
originally announced March 2022.
-
A New Conjecture About Identity of Proofs
Authors:
Paolo Pistone
Abstract:
A central problem in proof-theory is that of finding criteria for identity of proofs, that is, for when two distinct formal derivations can be taken as denoting the same logical argument. In the literature one finds criteria which are either based on proof normalization (two derivations denote the same proofs when they have the same normal form) or on the association of formal derivations with gra…
▽ More
A central problem in proof-theory is that of finding criteria for identity of proofs, that is, for when two distinct formal derivations can be taken as denoting the same logical argument. In the literature one finds criteria which are either based on proof normalization (two derivations denote the same proofs when they have the same normal form) or on the association of formal derivations with graph-theoretic structures (two derivations denote they same proof when they are associated with the same graph). In this paper we argue for a new criterion for identity of proofs which arises from the interpretation of formal rules and derivations as natural transformations of a suitable kind. We show that the naturality conditions arising from this interpretation capture in a uniform and elegant ways several forms of "rule-permutations" which are found in proof-systems for propositional, first- and second-order logic.
△ Less
Submitted 6 October, 2021;
originally announced October 2021.
-
From Identity to Difference: A Quantitative Interpretation of the Identity Type
Authors:
Paolo Pistone
Abstract:
We explore a quantitative interpretation of 2-dimensional intuitionistic type theory (ITT) in which the identity type is interpreted as a "type of differences". We show that a fragment of ITT, that we call difference type theory (dTT), yields a general logical framework to talk about quantitative properties of programs like approximate equivalence and metric preservation. To demonstrate this fact,…
▽ More
We explore a quantitative interpretation of 2-dimensional intuitionistic type theory (ITT) in which the identity type is interpreted as a "type of differences". We show that a fragment of ITT, that we call difference type theory (dTT), yields a general logical framework to talk about quantitative properties of programs like approximate equivalence and metric preservation. To demonstrate this fact, we show that dTT can be used to capture compositional reasoning in presence of errors, since any program can be associated with a "derivative" relating errors in input with errors in output. Moreover, after relating the semantics of dTT to the standard weak factorization systems semantics of ITT, we describe the interpretation of dTT in some quantitative models developed for approximate program transformations, incremental computing, program differentiation and differential privacy.
△ Less
Submitted 13 July, 2021;
originally announced July 2021.
-
What's Decidable about (Atomic) Polymorphism
Authors:
Paolo Pistone,
Luca Tranchini
Abstract:
Due to the undecidability of most type-related properties of System F like type inhabitation or type checking, restricted polymorphic systems have been widely investigated (the most well-known being ML-polymorphism). In this paper we investigate System Fat, or atomic System F, a very weak predicative fragment of System F whose typable terms coincide with the simply typable ones. We show that the t…
▽ More
Due to the undecidability of most type-related properties of System F like type inhabitation or type checking, restricted polymorphic systems have been widely investigated (the most well-known being ML-polymorphism). In this paper we investigate System Fat, or atomic System F, a very weak predicative fragment of System F whose typable terms coincide with the simply typable ones. We show that the type-checking problem for Fat is decidable and we propose an algorithm which sheds some new light on the source of undecidability in full System F. Moreover, we investigate free theorems and contextual equivalence in this fragment, and we show that the latter, unlike in the simply typed lambda-calculus, is undecidable.
△ Less
Submitted 3 May, 2021;
originally announced May 2021.
-
On Generalized Metric Spaces for the Simply Typed Lambda-Calculus (Extended Version)
Authors:
Paolo Pistone
Abstract:
Generalized metrics, arising from Lawvere's view of metric spaces as enriched categories, have been widely applied in denotational semantics as a way to measure to which extent two programs behave in a similar, although non equivalent, way. However, the application of generalized metrics to higher-order languages like the simply typed lambda calculus has so far proved unsatisfactory. In this paper…
▽ More
Generalized metrics, arising from Lawvere's view of metric spaces as enriched categories, have been widely applied in denotational semantics as a way to measure to which extent two programs behave in a similar, although non equivalent, way. However, the application of generalized metrics to higher-order languages like the simply typed lambda calculus has so far proved unsatisfactory. In this paper we investigate a new approach to the construction of cartesian closed categories of generalized metric spaces. Our starting point is a quantitative semantics based on a generalization of usual logical relations. Within this setting, we show that several families of generalized metrics provide ways to extend the Euclidean metric to all higher-order types.
△ Less
Submitted 27 April, 2021;
originally announced April 2021.
-
On Measure Quantifiers in First-Order Arithmetic (Long Version)
Authors:
Melissa Antonelli,
Ugo Dal Lago,
Paolo Pistone
Abstract:
We study the logic obtained by endowing the language of first-order arithmetic with second-order measure quantifiers. This new kind of quantification allows us to express that the argument formula is true in a certain portion of all possible interpretations of the quantified variable. We show that first-order arithmetic with measure quantifiers is capable of formalizing simple results from probabi…
▽ More
We study the logic obtained by endowing the language of first-order arithmetic with second-order measure quantifiers. This new kind of quantification allows us to express that the argument formula is true in a certain portion of all possible interpretations of the quantified variable. We show that first-order arithmetic with measure quantifiers is capable of formalizing simple results from probability theory and, most importantly, of representing every recursive random function. Moreover, we introduce a realizability interpretation of this logic in which programs have access to an oracle from the Cantor space.
△ Less
Submitted 25 April, 2021;
originally announced April 2021.
-
On Counting Propositional Logic
Authors:
Melissa Antonelli,
Ugo Dal Lago,
Paolo Pistone
Abstract:
We study counting propositional logic as an extension of propositional logic with counting quantifiers. We prove that the complexity of the underlying decision problem perfectly matches the appropriate level of Wagner's counting hierarchy, but also that the resulting logic admits a satisfactory proof-theoretical treatment. From the latter, a type system for a probabilistic lambda-calculus is deriv…
▽ More
We study counting propositional logic as an extension of propositional logic with counting quantifiers. We prove that the complexity of the underlying decision problem perfectly matches the appropriate level of Wagner's counting hierarchy, but also that the resulting logic admits a satisfactory proof-theoretical treatment. From the latter, a type system for a probabilistic lambda-calculus is derived in the spirit of the Curry-Howard correspondence, showing the potential of counting propositional logic as a useful tool in several fields of theoretical computer science.
△ Less
Submitted 3 June, 2021; v1 submitted 23 March, 2021;
originally announced March 2021.
-
The naturality of natural deduction (II). Some remarks on atomic polymorphism
Authors:
Paolo Pistone,
Luca Tranchini,
Mattia Petrolo
Abstract:
In a previous paper (of which this is a prosecution) we investigated the extraction of proof-theoretic properties of natural deduction derivations from their impredicative translation into System F. Our key idea was to introduce an extended equational theory for System F codifying at a syntactic level some properties found in parametric models. In a recent series of papers a different approach to…
▽ More
In a previous paper (of which this is a prosecution) we investigated the extraction of proof-theoretic properties of natural deduction derivations from their impredicative translation into System F. Our key idea was to introduce an extended equational theory for System F codifying at a syntactic level some properties found in parametric models. In a recent series of papers a different approach to extract proof-theoretic properties of natural deduction derivations was proposed by defining predicative variants of the usual translation, embedding intuitionistic propositional logic into the atomic fragment of System F. In this paper we show that this approach finds a general explanation within our equational study of second-order natural deduction, and a clear semantic justification provided by parametricity.
△ Less
Submitted 4 January, 2021; v1 submitted 29 August, 2019;
originally announced August 2019.
-
The Yoneda Reduction of Polymorphic Types (Extended Version)
Authors:
Paolo Pistone,
Luca Tranchini
Abstract:
In this paper we explore a family of type isomorphisms in System F whose validity corresponds, semantically, to some form of the Yoneda isomorphism from category theory. These isomorphisms hold under theories of equivalence stronger than beta-eta-equivalence, like those induced by parametricity and dinaturality. We show that the Yoneda type isomorphisms yield a rewriting over types, that we call Y…
▽ More
In this paper we explore a family of type isomorphisms in System F whose validity corresponds, semantically, to some form of the Yoneda isomorphism from category theory. These isomorphisms hold under theories of equivalence stronger than beta-eta-equivalence, like those induced by parametricity and dinaturality. We show that the Yoneda type isomorphisms yield a rewriting over types, that we call Yoneda reduction, which can be used to eliminate quantifiers from a polymorphic type, replacing them with a combination of monomorphic type constructors. We establish some sufficient conditions under which quantifiers can be fully eliminated from a polymorphic type, and we show some application of these conditions to count the inhabitants of a type and to compute program equivalence in some fragments of System F.
△ Less
Submitted 30 October, 2020; v1 submitted 8 July, 2019;
originally announced July 2019.
-
Proof Nets, Coends and the Yoneda Isomorphism
Authors:
Paolo Pistone
Abstract:
Proof nets provide permutation-independent representations of proofs and are used to investigate coherence problems for monoidal categories. We investigate a coherence problem concerning Second Order Multiplicative Linear Logic (MLL2), that is, the one of characterizing the equivalence over proofs generated by the interpretation of quantifiers by means of ends and coends.
We provide a compact…
▽ More
Proof nets provide permutation-independent representations of proofs and are used to investigate coherence problems for monoidal categories. We investigate a coherence problem concerning Second Order Multiplicative Linear Logic (MLL2), that is, the one of characterizing the equivalence over proofs generated by the interpretation of quantifiers by means of ends and coends.
We provide a compact representation of proof nets for a fragment of MLL2 related to the Yoneda isomorphism. By adapting the "rewiring approach" used in coherence results for star-autonomous categories, we define an equivalence relation over proof nets called "re-witnessing". We prove that this relation characterizes, in this fragment, the equivalence generated by coends.
△ Less
Submitted 15 April, 2019; v1 submitted 2 October, 2018;
originally announced October 2018.
-
Proof nets and the instantiation overflow property
Authors:
Paolo Pistone
Abstract:
Instantiation overflow is the property of those second order types for which all instances of full comprehension can be deduced from instances of atomic comprehension. In other words, a type has instantiation overflow when one can type, by atomic polymorphism, "expansion terms" which realize instances of the full extraction rule applied to that type. This property was investigated in the case of t…
▽ More
Instantiation overflow is the property of those second order types for which all instances of full comprehension can be deduced from instances of atomic comprehension. In other words, a type has instantiation overflow when one can type, by atomic polymorphism, "expansion terms" which realize instances of the full extraction rule applied to that type. This property was investigated in the case of the types arising from the well-known Russell-Prawitz translation of logical connectives into System F, but is not restricted to such types. Moreover, it can be related to functorial polymorphism, a well-known categorial approach to parametricity in System F. In this paper we investigate the instantiation overflow property by exploiting the representation of derivations by means of linear logic proof nets. We develop a geometric approach to instantiation overflow yielding a deeper understanding of the structure of expansion terms and Russell-Prawitz types. Our main result is a characterization of the class of types of the form $\forall XA$, where $A$ is a simple type, which enjoy the instantiation overflow property, by means of a generalization of Russell-Prawitz types.
△ Less
Submitted 25 March, 2018;
originally announced March 2018.
-
On completeness and parametricity in the realizability semantics of System F
Authors:
Paolo Pistone
Abstract:
We investigate completeness and parametricity for a general class of realizability semantics for System F defined in terms of closure operators over sets of $λ$-terms. This class includes most semantics used for normalization theorems, as those arising from Tait's saturated sets and Girard's reducibility candidates.
We establish a completeness result for positive types which subsumes those exist…
▽ More
We investigate completeness and parametricity for a general class of realizability semantics for System F defined in terms of closure operators over sets of $λ$-terms. This class includes most semantics used for normalization theorems, as those arising from Tait's saturated sets and Girard's reducibility candidates.
We establish a completeness result for positive types which subsumes those existing in the literature, and we show that closed realizers satisfy parametricity conditions expressed either as invariance with respect to logical relations or as dinaturality. Our results imply that, for positive types, typability, realizability and parametricity are equivalent properties of closed normal $λ$-terms.
△ Less
Submitted 28 October, 2019; v1 submitted 14 February, 2018;
originally announced February 2018.
-
Polymorphism and the obstinate circularity of second order logic: a victims' tale
Authors:
Paolo Pistone
Abstract:
The investigations on higher-order type theories and on the related notion of parametric polymorphism constitute the technical counterpart of the old foundational problem of the circularity (or impredicativity) of second and higher order logic. However, the epistemological significance of such investigations, and of their often non trivial results, has not received much attention in the contempora…
▽ More
The investigations on higher-order type theories and on the related notion of parametric polymorphism constitute the technical counterpart of the old foundational problem of the circularity (or impredicativity) of second and higher order logic. However, the epistemological significance of such investigations, and of their often non trivial results, has not received much attention in the contemporary foundational debate. The results recalled in this paper suggest that the question of the circularity of second order logic cannot be reduced to the simple assessment of a vicious circle. Through a comparison between the faulty consistency arguments given by Frege and Martin-Löf, respectively for the logical system of the Grundgesetze (shown inconsistent by Russell's paradox) and for the intuitionistic type theory with a type of all types (shown inconsistent by Girard's paradox), and the normalization argument for second order type theory (or System F), we indicate a bunch of subtle mathematical problems and logical concepts hidden behind the hazardous idea of impredicative quantification, constituting a vast (and largely unexplored) domain for foundational research.
△ Less
Submitted 27 October, 2017;
originally announced October 2017.
-
The naturality of natural deduction
Authors:
Luca Tranchini,
Paolo Pistone,
Mattia Petrolo
Abstract:
Developing a suggestion by Russell, Prawitz showed how the usual natural deduction inference rules for disjunction, conjunction and absurdity can be derived using those for implication and the second order quantifier in propositional intuitionistic second order logic $NI^2$. It is however well known that the translation does not preserve the relations of identity among derivations induced by the p…
▽ More
Developing a suggestion by Russell, Prawitz showed how the usual natural deduction inference rules for disjunction, conjunction and absurdity can be derived using those for implication and the second order quantifier in propositional intuitionistic second order logic $NI^2$. It is however well known that the translation does not preserve the relations of identity among derivations induced by the permutative conversions and immediate expansions for the definable connectives, at least when the equational theory of $NI^2$ is assumed to consist only of $β$ and $η$ equations. On the basis of the categorial interpretation of $NI^2$, we introduce a new class of equations expressing what in categorial terms is a naturality condition satisfied by the transformations interpreting $NI^2$-derivations. We show that the Russell-Prawitz translation does preserve identity of proof with respect to the enriched system by highlighting the fact that naturality corresponds to a generalized permutation principle. We show that these result generalize some facts which have gone so far unnoticed, namely that the Russell-Prawitz translation maps particular classes of instances of the equations governing disjunction (and the other definable connectives) onto equations which are already included in the $βη$ equational theory of $NI^2$. Finally, we compare our approach with the one proposed by Ferreira and Ferreira and show that the naturality condition suggests a generalization of their methods to a wider class of formulas.
△ Less
Submitted 29 August, 2019; v1 submitted 22 July, 2016;
originally announced July 2016.
-
Logic Programming and Logarithmic Space
Authors:
Clément Aubert,
Marc Bagnol,
Paolo Pistone,
Thomas Seiller
Abstract:
We present an algebraic view on logic programming, related to proof theory and more specifically linear logic and geometry of interaction. Within this construction, a characterization of logspace (deterministic and non-deterministic) computation is given via a synctactic restriction, using an encoding of words that derives from proof theory.
We show that the acceptance of a word by an observatio…
▽ More
We present an algebraic view on logic programming, related to proof theory and more specifically linear logic and geometry of interaction. Within this construction, a characterization of logspace (deterministic and non-deterministic) computation is given via a synctactic restriction, using an encoding of words that derives from proof theory.
We show that the acceptance of a word by an observation (the counterpart of a program in the encoding) can be decided within logarithmic space, by reducing this problem to the acyclicity of a graph. We show moreover that observations are as expressive as two-ways multi-heads finite automata, a kind of pointer machines that is a standard model of logarithmic space computation.
△ Less
Submitted 9 June, 2014;
originally announced June 2014.