The Experts below are selected from a list of 36834 Experts worldwide ranked by ideXlab platform
Francoisregis Sinot - One of the best experts on this subject based on the ideXlab platform.
-
Call by Name and Call by value as token passing interaction nets
International Conference on Typed Lambda Calculi and Applications, 2005Co-Authors: Francoisregis SinotAbstract:Two common misbeliefs about encodings of the λ-calculus in interaction nets (INs) are that they are good only for strategies that are not very well understood (e.g. optimal reduction) and that they always have to deal in a complex way with boxes. In brief, the theory of interaction nets is more or less disconnected from the standard theory: we can do things in INs that we cannot do with terms, which is true [5,10]; and we cannot do in INs things that can easily be done with terms. This paper contributes to fighting this misbelief by showing that the standard Call-by-Name and Call-by-value strategies of the λ-calculus are encoded in interaction nets in a very simple and extensible way, and in particular that these encodings do not need any notion of box. This work can also be seen as a first step towards a generic approach to derive graph-based abstract machines.
-
TLCA - Call-by-Name and Call-by-value as token-passing interaction nets
Lecture Notes in Computer Science, 2005Co-Authors: Francoisregis SinotAbstract:Two common misbeliefs about encodings of the λ-calculus in interaction nets (INs) are that they are good only for strategies that are not very well understood (e.g. optimal reduction) and that they always have to deal in a complex way with boxes. In brief, the theory of interaction nets is more or less disconnected from the standard theory: we can do things in INs that we cannot do with terms, which is true [5,10]; and we cannot do in INs things that can easily be done with terms. This paper contributes to fighting this misbelief by showing that the standard Call-by-Name and Call-by-value strategies of the λ-calculus are encoded in interaction nets in a very simple and extensible way, and in particular that these encodings do not need any notion of box. This work can also be seen as a first step towards a generic approach to derive graph-based abstract machines.
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'.
-
RTA - Call-by-value is dual to Call-by-Name: reloaded
Lecture Notes in Computer Science, 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).
-
ICFP - Call-by-value is dual to Call-by-Name
Proceedings of the eighth ACM SIGPLAN international conference on Functional programming - ICFP '03, 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.
Paul Hudak - One of the best experts on this subject based on the ideXlab platform.
-
Call by Name assignment and the lambda calculus
Symposium on Principles of Programming Languages, 1993Co-Authors: Martin Odersky, Dan Rabin, Paul HudakAbstract:We define an extension of the Call-by-Name lambda calculus with additional constructs and reduction rules that represent mutable variables and assignments. The extended calculus has neither a concept of an explicit store nor a concept of evaluation order; nevertheless, we show that programs in the calculus can be implemented using a single-threaded store. We also show that the new calculus has the Church-Rosser property and that it is a conservative extension of classical lambda calculus with respect to operational equivalence; that is, all algebraic laws of the functional subset are preserved.
-
POPL - Call by Name, assignment, and the lambda calculus
Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93, 1993Co-Authors: Martin Odersky, Dan Rabin, Paul HudakAbstract:We define an extension of the Call-by-Name lambda calculus with additional constructs and reduction rules that represent mutable variables and assignments. The extended calculus has neither a concept of an explicit store nor a concept of evaluation order; nevertheless, we show that programs in the calculus can be implemented using a single-threaded store. We also show that the new calculus has the Church-Rosser property and that it is a conservative extension of classical lambda calculus with respect to operational equivalence; that is, all algebraic laws of the functional subset are preserved.
Martin Odersky - One of the best experts on this subject based on the ideXlab platform.
-
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.
-
Call by Name Call by value Call by need and the linear lambda calculus
Electronic Notes in Theoretical Computer Science, 1995Co-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.
-
MFPS - Call-by-Name, Call-by-value, Call-by-need, and the Linear Lambda Calculus
Electronic Notes in Theoretical Computer Science, 1995Co-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.
-
Call by Name assignment and the lambda calculus
Symposium on Principles of Programming Languages, 1993Co-Authors: Martin Odersky, Dan Rabin, Paul HudakAbstract:We define an extension of the Call-by-Name lambda calculus with additional constructs and reduction rules that represent mutable variables and assignments. The extended calculus has neither a concept of an explicit store nor a concept of evaluation order; nevertheless, we show that programs in the calculus can be implemented using a single-threaded store. We also show that the new calculus has the Church-Rosser property and that it is a conservative extension of classical lambda calculus with respect to operational equivalence; that is, all algebraic laws of the functional subset are preserved.
-
POPL - Call by Name, assignment, and the lambda calculus
Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93, 1993Co-Authors: Martin Odersky, Dan Rabin, Paul HudakAbstract:We define an extension of the Call-by-Name lambda calculus with additional constructs and reduction rules that represent mutable variables and assignments. The extended calculus has neither a concept of an explicit store nor a concept of evaluation order; nevertheless, we show that programs in the calculus can be implemented using a single-threaded store. We also show that the new calculus has the Church-Rosser property and that it is a conservative extension of classical lambda calculus with respect to operational equivalence; that is, all algebraic laws of the functional subset are preserved.
Eijiro Sumii - One of the best experts on this subject based on the ideXlab platform.
-
formal verifications of Call by need and Call by Name evaluations with mutual recursion
Asian Symposium on Programming Languages and Systems, 2019Co-Authors: Masayuki Mizuno, Eijiro SumiiAbstract:We present new proofs—formalized in the Coq proof assistant—of the correspondence among Call-by-need and (various definitions of) Call-by-Name evaluations of \(\lambda \)-calculus with mutually recursive bindings.
-
APLAS - Formal Verifications of Call-by-Need and Call-by-Name Evaluations with Mutual Recursion
Programming Languages and Systems, 2019Co-Authors: Masayuki Mizuno, Eijiro SumiiAbstract:We present new proofs—formalized in the Coq proof assistant—of the correspondence among Call-by-need and (various definitions of) Call-by-Name evaluations of \(\lambda \)-calculus with mutually recursive bindings.
-
formal verification of the correspondence between Call by need and Call by Name
International Symposium on Functional and Logic Programming, 2018Co-Authors: Masayuki Mizuno, Eijiro SumiiAbstract:We formalize the Call-by-need evaluation of \(\lambda \)-calculus (with no recursive bindings) and prove its correspondence with Call-by-Name, using the Coq proof assistant.
-
FLOPS - Formal Verification of the Correspondence Between Call-by-Need and Call-by-Name
Functional and Logic Programming, 2018Co-Authors: Masayuki Mizuno, Eijiro SumiiAbstract:We formalize the Call-by-need evaluation of \(\lambda \)-calculus (with no recursive bindings) and prove its correspondence with Call-by-Name, using the Coq proof assistant.
