The Experts below are selected from a list of 111240 Experts worldwide ranked by ideXlab platform
Roberto M. Amadio - One of the best experts on this subject based on the ideXlab platform.
-
An Elementary Affine λ-Calculus with Multithreading and Side Effects
Typed Lambda Calculi and Applications 10th International Conference TLCA 2011 Novi Sad Serbia June 1-3 2011. Proceedings, 2011Co-Authors: Antoine Madet, Roberto M. AmadioAbstract:Linear logic provides a framework to control the complexity of higher-order functional programs. We present an extension of this framework to programs with multithreading and side effects focusing on the case of elementary time. Our main contributions are as follows. First, we introduce a modal call-by-value λ-calculus with multithreading and side effects. Second, we provide a combinatorial proof of termination in elementary time for the language. Third, we introduce an elementary affine type system that guarantees the standard Subject Reduction and progress properties. Finally, we illustrate the programming of iterative functions with side effects in the presented formalism.
-
elementary affine lambda calculus with multithreading and side effects
arXiv: Programming Languages, 2011Co-Authors: Antoine Madet, Roberto M. AmadioAbstract:Linear logic provides a framework to control the complexity of higher-order functional programs. We present an extension of this framework to programs with multithreading and side effects focusing on the case of elementary time. Our main contributions are as follows. First, we provide a new combinatorial proof of termination in elementary time for the functional case. Second, we develop an extension of the approach to a call-by-value $lambda$-calculus with multithreading and side effects. Third, we introduce an elementary affine type system that guarantees the standard Subject Reduction and progress properties. Finally, we illustrate the programming of iterative functions with side effects in the presented formalism.
-
An Elementary affine λ-calculus with multithreading and side effects (extended version)
2011Co-Authors: Antoine Madet, Roberto M. AmadioAbstract:Linear logic provides a framework to control the complexity of higher-order functional programs. We present an extension of this framework to programs with multithreading and side effects focusing on the case of elementary time. Our main contributions are as follows. First, we provide a new combinatorial proof of termination in elementary time for the functional case. Second, we develop an extension of the approach to a call-by-value $lambda$-calculus with multithreading and side effects. Third, we introduce an elementary affine type system that guarantees the standard Subject Reduction and progress properties. Finally, we illustrate the programming of iterative functions with side effects in the presented formalism.
-
analysis of a guard condition in type theory
Foundations of Software Science and Computation Structure, 1998Co-Authors: Roberto M. Amadio, Solange CoupetgrimalAbstract:We present a realizability interpretation of co-inductive types based on partial equivalence relations (per's). We extract from the per's interpretation sound rules to type recursive definitions. These recursive definitions are needed to introduce ‘infinite’ and ‘total’ objects of co-inductive type such as an infinite stream, a digital transducer, or a non-terminating process. We show that the proposed type system subsumes those studied by Coquand and Gimenez while still enjoying the basic syntactic properties of Subject Reduction and strong normalization with respect to a confluent rewriting system first put forward by Gimenez.
-
analysis of a guard condition in type theory extended abstract
Foundations of Software Science and Computation Structure, 1998Co-Authors: Roberto M. Amadio, Solange CoupetgrimalAbstract:We present a realizability interpretation of co-inductive types based on partial equivalence relations (per's). We extract from the per's interpretation sound rules to type recursive definitions. These recursive definitions are needed to introduce 'infinite' and 'total' objects of coinductive type such as an infinite stream, a digital transducer, or a nonterminating process. We show that the proposed type system subsumes those studied by Coquand and Gimenez while still enjoying the basic syntactic properties of Subject Reduction and strong normalization with respect to a confluent rewriting system first put forward by Gimenez.
Solange Coupetgrimal - One of the best experts on this subject based on the ideXlab platform.
-
analysis of a guard condition in type theory
Foundations of Software Science and Computation Structure, 1998Co-Authors: Roberto M. Amadio, Solange CoupetgrimalAbstract:We present a realizability interpretation of co-inductive types based on partial equivalence relations (per's). We extract from the per's interpretation sound rules to type recursive definitions. These recursive definitions are needed to introduce ‘infinite’ and ‘total’ objects of co-inductive type such as an infinite stream, a digital transducer, or a non-terminating process. We show that the proposed type system subsumes those studied by Coquand and Gimenez while still enjoying the basic syntactic properties of Subject Reduction and strong normalization with respect to a confluent rewriting system first put forward by Gimenez.
-
analysis of a guard condition in type theory extended abstract
Foundations of Software Science and Computation Structure, 1998Co-Authors: Roberto M. Amadio, Solange CoupetgrimalAbstract:We present a realizability interpretation of co-inductive types based on partial equivalence relations (per's). We extract from the per's interpretation sound rules to type recursive definitions. These recursive definitions are needed to introduce 'infinite' and 'total' objects of coinductive type such as an infinite stream, a digital transducer, or a nonterminating process. We show that the proposed type system subsumes those studied by Coquand and Gimenez while still enjoying the basic syntactic properties of Subject Reduction and strong normalization with respect to a confluent rewriting system first put forward by Gimenez.
J B Wells - One of the best experts on this subject based on the ideXlab platform.
-
instant polymorphic type systems for mobile process calculi just add Reduction rules and close
European Symposium on Programming, 2005Co-Authors: Henning Makholm, J B WellsAbstract:Many different mobile process calculi have been invented, and for each some number of type systems has been developed. Soundness and other properties must be proved separately for each calculus and type system. We present the generic polymorphic type system Poly* which works for a wide range of mobile process calculi, including the π-calculus and Mobile Ambients. For any calculus satisfying some general syntactic conditions, well-formedness rules for types are derived automatically from the Reduction rules and Poly* works otherwise unchanged. The derived type system is automatically sound (i.e., has Subject Reduction) and often more precise than previous type systems for the calculus, due to Poly*'s spatial polymorphism. We present an implemented type inference algorithm for Poly* which automatically constructs a typing given a set of Reduction rules and a term to be typed. The generated typings are principal with respect to certain natural type shape constraints.
-
relating typability and expressiveness in finite rank intersection type systems extended abstract
International Conference on Functional Programming, 1999Co-Authors: A J Kfoury, Harry G Mairson, Franklyn Turbak, J B WellsAbstract:We investigate finite-rank intersection type systems, analyzing the complexity of their type inference problems and their relation to the problem of recognizing semantically equivalent terms. Intersection types allow something of type t 1 L t 2 to be used in some places at type t 1 and in other places at type t 2 . A finite-rank intersection type system bounds how deeply the L can appear in type expressions. Such type systems enjoy strong normalization, Subject Reduction, and computable type inference, and they support a pragmatics for implementing parametric polymorphism. As a consequence, they provide a conceptually simple and tractable alternative to the impredicative polymorphism of System F and its extensions, while typing many more programs than the Hindley-Milner type system found in ML and Haskell.While type inference is computable at every rank, we show that its complexity grows exponentially as rank increases. Let K(0, n) = n and K(t + 1, n) = 2K(t,n); we prove that recognizing the pure l-terms of size n that are typable at rank k is complete for DTIME [K(km1, n)]. We then consider the problem of deciding whether two l-terms typable at rank k have the same normal form, generalizing a well-known result of Statman from simple types to finite-rank intersection types. We show that the equivalence problem is DTIME [K(K(k m 1, n), 2)]-complete. This relationship between the complexity of typability and expressiveness is identical in wellknown decidable type systems such as simple types and Hindley-Milner types, but seems to fail for System F and its generalizations. The correspondence gives rise to a conjecture that if T is a predicative type system where typability has complexity t(n) and expressiveness has complexity e(n), then t(n) = O(log* e(n)).
Kazushige Terui - One of the best experts on this subject based on the ideXlab platform.
-
light types for polynomial time computation in lambda calculus
Information & Computation, 2009Co-Authors: Patrick Baillot, Kazushige TeruiAbstract:We present a polymorphic type system for lambda calculus ensuring that well-typed programs can be executed in polynomial time: dual light affine logic (DLAL). DLAL has a simple type language with a linear and an intuitionistic type arrow, and one modality. It corresponds to a fragment of light affine logic (LAL). We show that contrarily to LAL, DLAL ensures good properties on lambda-terms (and not only on proof-nets): Subject Reduction is satisfied and a well-typed term admits a polynomial bound on the length of any of its beta Reduction sequences. We also give a translation of LAL into DLAL and deduce from it that all polynomial time functions can be represented in DLAL.
-
light types for polynomial time computation in lambda calculus
Logic in Computer Science, 2004Co-Authors: Patrick Baillot, Kazushige TeruiAbstract:We propose a new type system for lambda-calculus ensuring that well-typed programs can be executed in polynomial time: dual light affine logic (DIAL). DIAL has a simple type language with a linear and an intuitionistic type arrow, and one modality. It corresponds to a fragment of light affine logic (LAL). We show that contrarily to LAL, DIAL ensures good properties on lambda-terms: Subject Reduction is satisfied and a well-typed term admits a polynomial bound on the Reduction by any strategy. Finally we establish that as LAL, DIAL allows to represent all polytime functions.
-
Light types for polynomial time computation in lambda-calculus
2004Co-Authors: Patrick Baillot, Kazushige TeruiAbstract:We propose a new type system for lambda-calculus ensuring that well-typed programs can be executed in polynomial time: Dual light affine logic (DLAL). DLAL has a simple type language with a linear and an intuitionistic type arrow, and one modality. It corresponds to a fragment of Light affine logic (LAL). We show that contrarily to LAL, DLAL ensures good properties on lambda-terms: Subject Reduction is satisfied and a well-typed term admits a polynomial bound on the Reduction by any strategy. We establish that as LAL, DLAL allows to represent all polytime functions. Finally we give a type inference procedure for propositional DLAL.
Dale Miller - One of the best experts on this subject based on the ideXlab platform.
-
reasoning with higher order abstract syntax in a logical framework
ACM Transactions on Computational Logic, 2002Co-Authors: Raymond C Mcdowell, Dale MillerAbstract:Logical frameworks based on intuitionistic or linear logics with higher-type quantification have been successfully used to give high-level, modular, and formal specifications of many important judgments in the area of programming languages and inference systems. Given such specifications, it is natural to consider proving properties about the specified systems in the framework: for example, given the specification of evaluation for a functional programming language, prove that the language is deterministic or that evaluation preserves types. One challenge in developing a framework for such reasoning is that higher-order abstract syntax (HOAS), an elegant and declarative treatment of object-level abstraction and substitution, is difficult to treat in proofs involving induction. In this article, we present a meta-logic that can be used to reason about judgments coded using HOAS; this meta-logic is an extension of a simple intuitionistic logic that admits higher-order quantification over simply typed λ-terms (key ingredients for HOAS) as well as induction and a notion of definition. The latter concept of definition is a proof-theoretic device that allows certain theories to be treated as "closed" or as defining fixed points. We explore the difficulties of formal meta-theoretic analysis of HOAS encodings by considering encodings of intuitionistic and linear logics, and formally derive the admissibility of cut for important subsets of these logics. We then propose an approach to avoid the apparent trade-off between the benefits of higher-order abstract syntax and the ability to analyze the resulting encodings. We illustrate this approach through examples involving the simple functional and imperative programming languages PCF and PCF := . We formally derive such properties as unicity of typing, Subject Reduction, determinacy of evaluation, and the equivalence of transition semantics and natural semantics presentations of evaluation.
-
reasoning with higher order abstract syntax in a logical framework
arXiv: Logic in Computer Science, 2000Co-Authors: Raymond C Mcdowell, Dale MillerAbstract:Logical frameworks based on intuitionistic or linear logics with higher-type quantification have been successfully used to give high-level, modular, and formal specifications of many important judgments in the area of programming languages and inference systems. Given such specifications, it is natural to consider proving properties about the specified systems in the framework: for example, given the specification of evaluation for a functional programming language, prove that the language is deterministic or that evaluation preserves types. One challenge in developing a framework for such reasoning is that higher-order abstract syntax (HOAS), an elegant and declarative treatment of object-level abstraction and substitution, is difficult to treat in proofs involving induction. In this paper, we present a meta-logic that can be used to reason about judgments coded using HOAS; this meta-logic is an extension of a simple intuitionistic logic that admits higher-order quantification over simply typed lambda-terms (key ingredients for HOAS) as well as induction and a notion of definition. We explore the difficulties of formal meta-theoretic analysis of HOAS encodings by considering encodings of intuitionistic and linear logics, and formally derive the admissibility of cut for important subsets of these logics. We then propose an approach to avoid the apparent tradeoff between the benefits of higher-order abstract syntax and the ability to analyze the resulting encodings. We illustrate this approach through examples involving the simple functional and imperative programming languages PCF and PCF:=. We formally derive such properties as unicity of typing, Subject Reduction, determinacy of evaluation, and the equivalence of transition semantics and natural semantics presentations of evaluation.
-
a logic for reasoning with higher order abstract syntax
Logic in Computer Science, 1997Co-Authors: R Mcdowell, Dale MillerAbstract:Logical frameworks based on intuitionistic or linear logics with higher-type quantification have been successfully used to give high-level, modular, and formal specifications of many important judgments in the area of programming languages and inference systems. Given such specifications, it is natural to consider proving properties about the specified systems in the framework: for example, given the specification of evaluation for a functional programming language, prove that the language is deterministic or that the Subject-Reduction theorem holds. One challenge in developing a framework for such reasoning is that higher-order abstract syntax (HOAS), an elegant and declarative treatment of object-level abstraction and substitution, is difficult to treat in proofs involving induction. In this paper we present a meta-logic that can be used to reason about judgments coded using HOAS; this meta-logic is an extension of a simple intuitionistic logic that admits higher-order quantification over simply typed /spl lambda/-terms (key ingredients for HOAS) as well as induction and a notion of definition. The latter concept of a definition is a proof-theoretic device that allows certain theories to be treated as "closed" or as defining fixed points. The resulting meta-logic can specify various logical frameworks and a large range of judgments regarding programming languages and inference systems. We illustrate this point through examples, including the admissibility of cut for a simple logic and Subject Reduction, determinacy of evaluation, and the equivalence of SOS and natural semantics presentations of evaluation for a simple functional programming language.
