The Experts below are selected from a list of 62403 Experts worldwide ranked by ideXlab platform
Giulio Guerrieri - One of the best experts on this subject based on the ideXlab platform.
-
factorization in Call by name and Call by Value calculi via linear logic
Foundations of Software Science and Computation Structure, 2021Co-Authors: Claudia Faggian, Giulio GuerrieriAbstract:In each variant of the \(\lambda \)-calculus, factorization and normalization are two key properties that show how results are computed. Instead of proving factorization/normalization for the Call-by-name (CbN) and Call-by-Value (CbV) variants separately, we prove them only once, for the bang calculus (an extension of the \(\lambda \)-calculus inspired by linear logic and subsuming CbN and CbV), and then we transfer the result via translations, obtaining factorization/normalization for CbN and CbV.
-
abstract machines for open Call by Value
Science of Computer Programming, 2019Co-Authors: Beniamino Accattoli, Giulio GuerrieriAbstract:Abstract The theory of the Call-by-Value λ-calculus relies on weak evaluation and closed terms, that are natural hypotheses in the study of programming languages. To model proof assistants, however, strong evaluation and open terms are required. Open Call-by-Value is the intermediate setting of weak evaluation with (possibly) open terms, on top of which Gregoire and Leroy designed one of the abstract machines of Coq. This paper provides a theory of abstract machines for the fireball calculus, the simplest presentation of open Call-by-Value. The literature contains machines that are either simple but inefficient, as they have an exponential overhead, or efficient but heavy, as they rely on a labeling of environments and a technical optimization. We introduce a machine that is simple and efficient: it does not use labels and it implements the fireball calculus within a bilinear overhead. Moreover, we provide a new fine understanding of how different optimizations impact on the complexity of the overhead, and evidence that the time cost model we work with is minimal.
-
towards a semantic measure of the execution time in Call by Value lambda calculus
12th Workshop on Developments in Computational Models DCM 2018 and 9th Workshop on Intersection Types and Related Systems ITRS 2018, 2019Co-Authors: Giulio GuerrieriAbstract:We investigate the possibility of a semantic account of the execution time (i.e. the number of beta-steps leading to the normal form, if any) for the shuffling calculus, an extension of Plotkin's Call-by-Value lambda-calculus. For this purpose, we use a linear logic based denotational model that can be seen as a non-idempotent intersection type system: relational semantics. Our investigation is inspired by similar ones for linear logic proof-nets and untyped Call-by-name lambda-calculus. We first prove a qualitative result: a (possibly open) term is normalizable for weak reduction (which does not reduce under abstractions) if and only if its interpretation is not empty. We then show that the size of type derivations can be used to measure the execution time. Finally, we show that, differently from the case of linear logic and Call-by-name lambda-calculus, the quantitative information enclosed in type derivations does not lift to types (i.e. to the interpretation of terms). To get a truly semantic measure of execution time in a Call-by-Value setting, we conjecture that a refinement of its syntax and operational semantics is needed.
-
standardization and conservativity of a refined Call by Value lambda calculus
Logical Methods in Computer Science, 2017Co-Authors: Giulio Guerrieri, Luca Paolini, Simona Ronchi Della RoccaAbstract:We study an extension of Plotkin's Call-by-Value lambda-calculus via two commutation rules (sigma-reductions). These commutation rules are sufficient to remove harmful Call-by-Value normal forms from the calculus, so that it enjoys elegant characterizations of many semantic properties. We prove that this extended calculus is a conservative refinement of Plotkin's one. In particular, the notions of solvability and potential valuability for this calculus coincide with those for Plotkin's Call-by-Value lambda-calculus. The proof rests on a standardization theorem proved by generalizing Takahashi's approach of parallel reductions to our set of reduction rules. The standardization is weak (i.e. redexes are not fully sequentialized) because of overlapping interferences between reductions.
-
implementing open Call by Value
Fundamentals of Software Engineering, 2017Co-Authors: Beniamino Accattoli, Giulio GuerrieriAbstract:The theory of the Call-by-Value λ-calculus relies on weak evaluation and closed terms, that are natural hypotheses in the study of programming languages. To model proof assistants, however, strong evaluation and open terms are required. Open Call-by-Value is the intermediate setting of weak evaluation with open terms, on top of which Gregoire and Leroy designed the abstract machine of Coq. This paper provides a theory of abstract machines for open Call-by-Value. The literature contains machines that are either simple but inefficient, as they have an exponential overhead, or efficient but heavy, as they rely on a labelling of environments and a technical optimization. We introduce a machine that is simple and efficient: it does not use labels and it implements open Call-by-Value within a bilinear overhead. Moreover, we provide a new fine understanding of how different optimizations impact on the complexity of the overhead. This work is part of a wider research effort, the COCA HOLA project https://sites.google.com/site/beniaminoaccattoli/coca-hola.
Xavier Leroy - One of the best experts on this subject based on the ideXlab platform.
-
Compilation of extended recursion in Call-by-Value functional languages
Higher-Order and Symbolic Computation, 2009Co-Authors: Tom Hirschowitz, Xavier Leroy, J B WellsAbstract:This paper formalizes and proves correct a compilation scheme for mutually-recursive definitions in Call-by-Value functional languages. This scheme supports a wider range of recursive definitions than previous methods. We formalize our technique as a translation scheme to a lambda-calculus featuring in-place update of memory blocks, and prove the translation to be correct.
-
mixin modules in a Call by Value setting
ACM Transactions on Programming Languages and Systems, 2005Co-Authors: Tom Hirschowitz, Xavier LeroyAbstract:The ML module system provides powerful parameterization facilities, but lacks the ability to split mutually recursive definitions across modules and provides insufficient support for incremental programming. A promising approach to solve these issues is Ancona and Zucca's mixin module calculus CMS. However, the straightforward way to adapt it to ML fails, because it allows arbitrary recursive definitions to appear at any time, which ML does not otherwise support. In this article, we enrich CMS with a refined type system that controls recursive definitions through the use of dependency graphs. We then develop and prove sound a separate compilation scheme, directed by dependency graphs, that translates mixin modules down to a Call-by-Value λ-calculus extended with a nonstandard let rec construct.
-
Call by Value mixin modules reduction semantics side effects types
Lecture Notes in Computer Science, 2004Co-Authors: Tom Hirschowitz, Xavier Leroy, J B WellsAbstract:Mixin modules are a framework for modular programming that supports code parameterization, incremental programming via late binding and redefinitions, and cross-module recursion. In this paper, we develop a language of mixin modules that supports Call-by-Value evaluation, and formalize a reduction semantics and a sound type system for this language.
-
compilation of extended recursion in Call by Value functional languages
Principles and Practice of Declarative Programming, 2003Co-Authors: Tom Hirschowitz, Xavier Leroy, J B WellsAbstract:This paper formalizes and proves correct a compilation scheme for mutually-recursive definitions in Call-by-Value functional languages. This scheme supports a wider range of recursive definitions than standard Call-by-Value recursive definitions. We formalize our technique as a translation scheme to a lambda-calculus featuring in-place update of memory blocks, and prove the translation to be faithful.
-
mixin modules in a Call by Value setting
European Symposium on Programming, 2002Co-Authors: Tom Hirschowitz, Xavier LeroyAbstract:The ML module system provides powerful parameterization facilities, but lacks the ability to split mutually recursive definitions across modules, and does not provide enough facilities for incremental programming. A promising approach to solve these issues is Ancona and Zucca's mixin modules calculus CMS. However, the straightforward way to adapt it to ML fails, because it allows arbitrary recursive definitions to appear at any time, which ML does not support. In this paper, we enrich CMS with a refined type system that controls recursive definitions through the use of dependency graphs. We then develop a separate compilation scheme, directed by dependency graphs, that translate mixin modules down to a CBV ?-calculus extended with a non-standard let rec construct.
Tom Hirschowitz - One of the best experts on this subject based on the ideXlab platform.
-
Compilation of extended recursion in Call-by-Value functional languages
Higher-Order and Symbolic Computation, 2009Co-Authors: Tom Hirschowitz, Xavier Leroy, J B WellsAbstract:This paper formalizes and proves correct a compilation scheme for mutually-recursive definitions in Call-by-Value functional languages. This scheme supports a wider range of recursive definitions than previous methods. We formalize our technique as a translation scheme to a lambda-calculus featuring in-place update of memory blocks, and prove the translation to be correct.
-
mixin modules in a Call by Value setting
ACM Transactions on Programming Languages and Systems, 2005Co-Authors: Tom Hirschowitz, Xavier LeroyAbstract:The ML module system provides powerful parameterization facilities, but lacks the ability to split mutually recursive definitions across modules and provides insufficient support for incremental programming. A promising approach to solve these issues is Ancona and Zucca's mixin module calculus CMS. However, the straightforward way to adapt it to ML fails, because it allows arbitrary recursive definitions to appear at any time, which ML does not otherwise support. In this article, we enrich CMS with a refined type system that controls recursive definitions through the use of dependency graphs. We then develop and prove sound a separate compilation scheme, directed by dependency graphs, that translates mixin modules down to a Call-by-Value λ-calculus extended with a nonstandard let rec construct.
-
Call by Value mixin modules reduction semantics side effects types
Lecture Notes in Computer Science, 2004Co-Authors: Tom Hirschowitz, Xavier Leroy, J B WellsAbstract:Mixin modules are a framework for modular programming that supports code parameterization, incremental programming via late binding and redefinitions, and cross-module recursion. In this paper, we develop a language of mixin modules that supports Call-by-Value evaluation, and formalize a reduction semantics and a sound type system for this language.
-
compilation of extended recursion in Call by Value functional languages
Principles and Practice of Declarative Programming, 2003Co-Authors: Tom Hirschowitz, Xavier Leroy, J B WellsAbstract:This paper formalizes and proves correct a compilation scheme for mutually-recursive definitions in Call-by-Value functional languages. This scheme supports a wider range of recursive definitions than standard Call-by-Value recursive definitions. We formalize our technique as a translation scheme to a lambda-calculus featuring in-place update of memory blocks, and prove the translation to be faithful.
-
mixin modules in a Call by Value setting
European Symposium on Programming, 2002Co-Authors: Tom Hirschowitz, Xavier LeroyAbstract:The ML module system provides powerful parameterization facilities, but lacks the ability to split mutually recursive definitions across modules, and does not provide enough facilities for incremental programming. A promising approach to solve these issues is Ancona and Zucca's mixin modules calculus CMS. However, the straightforward way to adapt it to ML fails, because it allows arbitrary recursive definitions to appear at any time, which ML does not support. In this paper, we enrich CMS with a refined type system that controls recursive definitions through the use of dependency graphs. We then develop a separate compilation scheme, directed by dependency graphs, that translate mixin modules down to a CBV ?-calculus extended with a non-standard let rec construct.
Philip Wadler - One of the best experts on this subject based on the ideXlab platform.
-
Call by Value is dual to Call by name reloaded
Rewriting Techniques and Applications, 2005Co-Authors: Philip WadlerAbstract:We consider the relation of the dual calculus of Wadler(2003) to the λμ-calculus of Parigot (1992). We give translations from the λμ-calculus into the dual calculus and back again. The translations form an equational correspondence as defined by Sabry and Felleisen (1993). In particular, translating from λμ to dual and then ‘reloading' from dual back into λμ yields a term equal to the original term. Composing the translations with duality on the dual calculus yields an involutive notion of duality on the λμ-calculus. A previous notion of duality on the λμ-calculus has been suggested by Selinger (2001), but it is not involutive. Note: This paper uses color to clarify the relation of types and terms, and of source and target calculi. If the URL below is not in blue please download the color version from$$ \texttt{http://homepages.inf.ed.ac.uk/wadler/} $$ or google ‘wadler dual reloaded'.
-
Call by Value is dual to Call by name
International Conference on Functional Programming, 2003Co-Authors: Philip WadlerAbstract:The rules of classical logic may be formulated in pairs corresponding to De Morgan duals: rules about & are dual to rules about V. A line of work, including that of Filinski (1989), Griffin (1990), Parigot (1992), Danos, Joinet, and Schellinx (1995), Selinger (1998,2001), and Curien and Herbelin (2000), has led to the startling conclusion that Call-by-Value is the de Morgan dual of Call-by-name.This paper presents a dual calculus that corresponds to the classical sequent calculus of Gentzen (1935) in the same way that the lambda calculus of Church (1932,1940) corresponds to the intuitionistic natural deduction of Gentzen (1935). The paper includes crisp formulations of Call-by-Value and Call-by-name that are obviously dual; no similar formulations appear in the literature. The paper gives a CPS translation and its inverse, and shows that the translation is both sound and complete, strengthening a result in Curien and Herbelin (2000).
-
Call-by-name Call-by-Value, Call-by-need and the linear lambda calculus
Theoretical Computer Science, 1999Co-Authors: John Maraist, Martin Odersky, David N. Turner, Philip WadlerAbstract:Abstract Girard described two translations of intuitionistic logic into linear logic, one where A → B maps to (!A)⊸B and another where it maps to !(A⊸B) . We detail the action of these translations on terms and show that the first corresponds to a Call-by-name calculus, while the second corresponds to Call-by-Value. We further show that if the target of the translation is taken to be an affine calculus, where! controls contraction but weakening is allowed everywhere, then the second translation corresponds to a Call-by-need calculus, as recently defined by Ariola, Felleisen, Maraist, Odersky and Wadler. Thus the different Calling mechanisms can be explained in terms of logical translations, bringing them into the scope of the Curry–Howard isomorphism. Our results extend neatly to translations of extensions for recursion in the Call-by-name and Call-by-Value calculi, and in general to extensions for products and for the corresponding untyped systems.
-
a reflection on Call by Value
ACM Transactions on Programming Languages and Systems, 1997Co-Authors: Amr Sabry, Philip WadlerAbstract:One way to model a sound and complete translation from a source calculus into a target calculus is with an adjoint or a Galois connection. In the special case of a reflection, one also has that the target calculus is isomorphic to a subset of the source. We show that three widely studied translations form reflections. We use as our source language Moggi's computational lambda calculus, which is an extension of Plotkin's Call-by-Value calculus. We show that Plotkin's CPS translation, Moggi's monad translation, and Girard's translation to linear logic can all be regarded as reflections form this source language, and we put forward the computational lambda calculus as a model of Call-by-Value computation that improves on the traditional Call-by-Value calculus. Our work strengthens Plotkin's and Moggi's original results and improves on recent work based on equational correspondence, which uses equations rather than reductions.
-
a reflection on Call by Value
International Conference on Functional Programming, 1996Co-Authors: Amr Sabry, Philip WadlerAbstract:A number of compilers exploit the following strategy: translate a term to continuation-passing style (CPS) and optimize the resulting term using a sequence of reductions. Recent work suggests that an alternative strategy is superior: optimize directly in an extended source calculus. We suggest that the appropriate relation between the source and target calculi may be captured by a special case of a Galois connection known as a reflection. Previous work has focused on the weaker notion of an equational correspondence, which is based on equality rather than reduction. We show that Moggi's monad translation and Plotkin's CPS translation can both be regarded as reflections, and thereby strengthen a number of results in the literature.
Yoshihiko Kakutani - One of the best experts on this subject based on the ideXlab platform.
-
Calculi for Intuitionistic Normal Modal Logic.
arXiv: Logic in Computer Science, 2016Co-Authors: Yoshihiko KakutaniAbstract:This paper provides a Call-by-name and a Call-by-Value term calculus, both of which have a Curry-Howard correspondence to the box fragment of the intuitionistic modal logic IK. The strong normalizability and the confluency of the calculi are shown. Moreover, we define a CPS transformation from the Call-by-Value calculus to the Call-by-name calculus, and show its soundness and completeness.
-
Call by name and Call by Value in normal modal logic
Asian Symposium on Programming Languages and Systems, 2007Co-Authors: Yoshihiko KakutaniAbstract:This paper provides a Call-by-name and a Call-by-Value calculus, both of which have a Curry-Howard correspondence to the minimal normal logic K. The calculi are extensions of the λµ-calculi, and their semantics are given by CPS transformations into a calculus corresponding to the intuitionistic fragment of K. The duality between Call-byname and Call-by-Value with modalities is investigated in our calculi.
-
duality between Call by name recursion and Call by Value iteration
Computer Science Logic, 2002Co-Authors: Yoshihiko KakutaniAbstract:We investigate the duality between Call-by-name recursion and Call-by-Value iteration in the ?µ-calculi and their models. SemantiCally, we consider that iteration is the dual notion of recursion. SyntactiCally, we extend the Call-by-name ?µ-calculus and the Call-by-Value one with a fixed-point operator and an iteration operator, respectively. This paper shows that the dual translations between the Call-byname ?µ-calculus and the Call-by-Value one, which is constructed by Selinger, can be expanded to our extended ?µ-calculi. Another result of this study provides uniformity principles for those operators.
-
Axioms for Recursion in Call-by-Value
Higher-Order and Symbolic Computation, 2002Co-Authors: Masahito Hasegawa, Yoshihiko KakutaniAbstract:We propose an axiomatization of fixpoint operators in typed Call-by-Value programming languages, and give its justifications in two ways. First, it is shown to be sound and complete for the notion of uniform T -fixpoint operators of Simpson and Plotkin. Second, the axioms precisely account for Filinski's fixpoint operator derived from an iterator (infinite loop constructor) in the presence of first-class continuations, provided that we define the uniformity principle on such an iterator via a notion of effect-freeness (centrality). We then explain how these two results are related in terms of the underlying categorical structures.
