Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus
Identifieur interne : 001383 ( Hal/Corpus ); précédent : 001382; suivant : 001384Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus
Auteurs : Ali Assaf ; Alejandro Díaz-Caro ; Simon Perdrix ; Christine Tasson ; Benoît ValironSource :
- Logical Methods in Computer Science [ 1860-5974 ] ; 2014-12-09.
English descriptors
Abstract
We examine the relationship between the algebraic lambda-calculus, a fragment of the differential lambda-calculus and the linear-algebraic lambda-calculus, a candidate lambda-calculus for quantum computation. Both calculi are algebraic: each one is equipped with an additive and a scalar-multiplicative structure, and their set of terms is closed under linear combinations. However, the two languages were built using different approaches: the former is a call-by-name language whereas the latter is call-by-value; the former considers algebraic equalities whereas the latter approaches them through rewrite rules. In this paper, we analyse how these different approaches relate to one another. To this end, we propose four canonical languages based on each of the possible choices: call-by-name versus call-by-value, algebraic equality versus algebraic rewriting. We show that the various languages simulate one another. Due to subtle interaction between beta-reduction and algebraic rewriting, to make the languages consistent some additional hypotheses such as confluence or normalisation might be required. We carefully devise the required properties for each proof, making them general enough to be valid for any sub-language satisfying the corresponding properties.
Url:
DOI: 10.2168/LMCS-10(4:8)2014
Links to Exploration step
Hal:hal-01097602Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus</title><author><name sortKey="Assaf, Ali" sort="Assaf, Ali" uniqKey="Assaf A" first="Ali" last="Assaf">Ali Assaf</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-119064" status="VALID"><orgName>Ecole Polytechnique [Palaiseau]</orgName><desc><address><addrLine>École Polytechnique, 91128 Palaiseau Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.polytechnique.fr/</ref></desc><listRelation><relation active="#struct-301691" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301691" type="direct"><org type="institution" xml:id="struct-301691" status="VALID"><orgName>Ecole Polytechnique</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Diaz Caro, Alejandro" sort="Diaz Caro, Alejandro" uniqKey="Diaz Caro A" first="Alejandro" last="Díaz-Caro">Alejandro Díaz-Caro</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-116739" status="INCOMING"><orgName>Universidad Nacional de Quilmes</orgName><desc><address><country key="AR"></country></address></desc><listRelation><relation active="#struct-309457" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-309457" type="direct"><org type="institution" xml:id="struct-309457" status="INCOMING"><orgName>Universidad Nacional de Quilmes</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Tasson, Christine" sort="Tasson, Christine" uniqKey="Tasson C" first="Christine" last="Tasson">Christine Tasson</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-1067" status="OLD"><orgName>Preuves, Programmes et Systèmes</orgName><orgName type="acronym">PPS</orgName><date type="end">2015-12-31</date><desc><address><addrLine>Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris Cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.pps.univ-paris-diderot.fr</ref></desc><listRelation><relation active="#struct-300301" type="direct"></relation><relation name="UMR7126" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID"><orgName>Université Paris Diderot - Paris 7</orgName><orgName type="acronym">UP7</orgName><desc><address><addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-paris-diderot.fr</ref></desc></org></tutelle><tutelle name="UMR7126" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Valiron, Benoit" sort="Valiron, Benoit" uniqKey="Valiron B" first="Benoît" last="Valiron">Benoît Valiron</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-206117" status="OLD"><idno type="RNSR">201121007R</idno><orgName>Deduction modulo, interopérabilité et démonstration automatique</orgName><orgName type="acronym">DEDUCTEAM</orgName><date type="end">2015-12-31</date><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/deducteam</ref></desc><listRelation><relation active="#struct-86790" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID"><idno type="RNSR">196718247G</idno><orgName>INRIA Paris-Rocquencourt</orgName><desc><address><addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01097602</idno><idno type="halId">hal-01097602</idno><idno type="halUri">https://hal.inria.fr/hal-01097602</idno><idno type="url">https://hal.inria.fr/hal-01097602</idno><idno type="doi">10.2168/LMCS-10(4:8)2014</idno><date when="2014-12-09">2014-12-09</date><idno type="wicri:Area/Hal/Corpus">001383</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus</title><author><name sortKey="Assaf, Ali" sort="Assaf, Ali" uniqKey="Assaf A" first="Ali" last="Assaf">Ali Assaf</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-119064" status="VALID"><orgName>Ecole Polytechnique [Palaiseau]</orgName><desc><address><addrLine>École Polytechnique, 91128 Palaiseau Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.polytechnique.fr/</ref></desc><listRelation><relation active="#struct-301691" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301691" type="direct"><org type="institution" xml:id="struct-301691" status="VALID"><orgName>Ecole Polytechnique</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Diaz Caro, Alejandro" sort="Diaz Caro, Alejandro" uniqKey="Diaz Caro A" first="Alejandro" last="Díaz-Caro">Alejandro Díaz-Caro</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-116739" status="INCOMING"><orgName>Universidad Nacional de Quilmes</orgName><desc><address><country key="AR"></country></address></desc><listRelation><relation active="#struct-309457" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-309457" type="direct"><org type="institution" xml:id="struct-309457" status="INCOMING"><orgName>Universidad Nacional de Quilmes</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Tasson, Christine" sort="Tasson, Christine" uniqKey="Tasson C" first="Christine" last="Tasson">Christine Tasson</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-1067" status="OLD"><orgName>Preuves, Programmes et Systèmes</orgName><orgName type="acronym">PPS</orgName><date type="end">2015-12-31</date><desc><address><addrLine>Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris Cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.pps.univ-paris-diderot.fr</ref></desc><listRelation><relation active="#struct-300301" type="direct"></relation><relation name="UMR7126" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID"><orgName>Université Paris Diderot - Paris 7</orgName><orgName type="acronym">UP7</orgName><desc><address><addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-paris-diderot.fr</ref></desc></org></tutelle><tutelle name="UMR7126" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Valiron, Benoit" sort="Valiron, Benoit" uniqKey="Valiron B" first="Benoît" last="Valiron">Benoît Valiron</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-206117" status="OLD"><idno type="RNSR">201121007R</idno><orgName>Deduction modulo, interopérabilité et démonstration automatique</orgName><orgName type="acronym">DEDUCTEAM</orgName><date type="end">2015-12-31</date><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/deducteam</ref></desc><listRelation><relation active="#struct-86790" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID"><idno type="RNSR">196718247G</idno><orgName>INRIA Paris-Rocquencourt</orgName><desc><address><addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic><idno type="DOI">10.2168/LMCS-10(4:8)2014</idno><series><title level="j">Logical Methods in Computer Science</title><idno type="ISSN">1860-5974</idno><imprint><date type="datePub">2014-12-09</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Algebraic lambda-calculus</term><term>CPS simulation</term><term>linear-algebraic lambda-calculus</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We examine the relationship between the algebraic lambda-calculus, a fragment of the differential lambda-calculus and the linear-algebraic lambda-calculus, a candidate lambda-calculus for quantum computation. Both calculi are algebraic: each one is equipped with an additive and a scalar-multiplicative structure, and their set of terms is closed under linear combinations. However, the two languages were built using different approaches: the former is a call-by-name language whereas the latter is call-by-value; the former considers algebraic equalities whereas the latter approaches them through rewrite rules. In this paper, we analyse how these different approaches relate to one another. To this end, we propose four canonical languages based on each of the possible choices: call-by-name versus call-by-value, algebraic equality versus algebraic rewriting. We show that the various languages simulate one another. Due to subtle interaction between beta-reduction and algebraic rewriting, to make the languages consistent some additional hypotheses such as confluence or normalisation might be required. We carefully devise the required properties for each proof, making them general enough to be valid for any sub-language satisfying the corresponding properties.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus</title><author role="aut"><persName><forename type="first">Ali</forename><surname>Assaf</surname></persName><email>ali.assaf@inria.fr</email><idno type="idhal">ali-assaf</idno><idno type="halauthor">958101</idno><affiliation ref="#struct-119064"></affiliation><affiliation ref="#struct-206117"></affiliation></author><author role="aut"><persName><forename type="first">Alejandro</forename><surname>Díaz-Caro</surname></persName><email>alejandro@diaz-caro.info</email><ptr type="url" target="http://diazcaro.web.unq.edu.ar"></ptr><idno type="idhal">adiazcaro</idno><idno type="halauthor">1110603</idno><orgName ref="#struct-333257"></orgName><affiliation ref="#struct-116739"></affiliation></author><author role="aut"><persName><forename type="first">Simon</forename><surname>Perdrix</surname></persName><email></email><idno type="idhal">perdrix</idno><idno type="halauthor">163861</idno><idno type="arXiv">http://arxiv.org/a/perdrix_s_1</idno><affiliation ref="#struct-29797"></affiliation></author><author role="aut"><persName><forename type="first">Christine</forename><surname>Tasson</surname></persName><email>tasson@pps.jussieu.fr</email><idno type="halauthor">454269</idno><affiliation ref="#struct-1067"></affiliation></author><author role="aut"><persName><forename type="first">Benoît</forename><surname>Valiron</surname></persName><email></email><ptr type="url" target="http://www.monoidal.net"></ptr><idno type="idhal">benoit-valiron</idno><idno type="halauthor">959366</idno><idno type="arXiv">http://arxiv.org/a/bvaliron</idno><affiliation ref="#struct-206117"></affiliation></author><editor role="depositor"><persName><forename>Alejandro</forename><surname>Díaz-Caro</surname></persName><email>alejandro@diaz-caro.info</email></editor><funder ref="#projanr-32348"></funder></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-12-20 02:44:24</date><date type="whenWritten">2014-02-27</date><date type="whenModified">2015-09-21 11:22:43</date><date type="whenReleased">2014-12-20 02:44:24</date><date type="whenProduced">2014-12-09</date></edition><respStmt><resp>contributor</resp><name key="189698"><persName><forename>Alejandro</forename><surname>Díaz-Caro</surname></persName><email>alejandro@diaz-caro.info</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">hal-01097602</idno><idno type="halUri">https://hal.inria.fr/hal-01097602</idno><idno type="halBibtex">assaf:hal-01097602</idno><idno type="halRefHtml">Logical Methods in Computer Science, IfCoLog, 2014, 10:4 (8), pp.40. <http://lmcs-online.org/ojs/viewarticle.php?id=1567>. <10.2168/LMCS-10(4:8)2014></idno><idno type="halRef">Logical Methods in Computer Science, IfCoLog, 2014, 10:4 (8), pp.40. <http://lmcs-online.org/ojs/viewarticle.php?id=1567>. <10.2168/LMCS-10(4:8)2014></idno></publicationStmt><seriesStmt><idno type="stamp" n="UNIV-PARIS7">Université Denis Diderot - Paris VII</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="PPS">Laboratoire Preuves, Programmes et Systèmes</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA-FM" p="LORIA">Méthodes formelles</idno><idno type="stamp" n="LIG_MFML" p="LIG">Méthodes Formelles, Modèles et Langages</idno><idno type="stamp" n="LIG_MFML_CAPP" p="LIG_MFML">CAPP</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno></seriesStmt><notesStmt><note type="audience" n="2">International</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus</title><author role="aut"><persName><forename type="first">Ali</forename><surname>Assaf</surname></persName><email>ali.assaf@inria.fr</email><idno type="idHal">ali-assaf</idno><idno type="halAuthorId">958101</idno><affiliation ref="#struct-119064"></affiliation><affiliation ref="#struct-206117"></affiliation></author><author role="aut"><persName><forename type="first">Alejandro</forename><surname>Díaz-Caro</surname></persName><email>alejandro@diaz-caro.info</email><ptr type="url" target="http://diazcaro.web.unq.edu.ar"></ptr><idno type="idHal">adiazcaro</idno><idno type="halAuthorId">1110603</idno><orgName ref="#struct-333257"></orgName><affiliation ref="#struct-116739"></affiliation></author><author role="aut"><persName><forename type="first">Simon</forename><surname>Perdrix</surname></persName><idno type="idHal">perdrix</idno><idno type="halAuthorId">163861</idno><idno type="arXiv">http://arxiv.org/a/perdrix_s_1</idno><affiliation ref="#struct-29797"></affiliation></author><author role="aut"><persName><forename type="first">Christine</forename><surname>Tasson</surname></persName><email>tasson@pps.jussieu.fr</email><idno type="halAuthorId">454269</idno><affiliation ref="#struct-1067"></affiliation></author><author role="aut"><persName><forename type="first">Benoît</forename><surname>Valiron</surname></persName><ptr type="url" target="http://www.monoidal.net"></ptr><idno type="idHal">benoit-valiron</idno><idno type="halAuthorId">959366</idno><idno type="arXiv">http://arxiv.org/a/bvaliron</idno><affiliation ref="#struct-206117"></affiliation></author></analytic><monogr><idno type="halJournalId" status="VALID">1692</idno><idno type="issn">1860-5974</idno><title level="j">Logical Methods in Computer Science</title><imprint><publisher>IfCoLog</publisher><biblScope unit="volume">10:4</biblScope><biblScope unit="issue">8</biblScope><biblScope unit="pp">40</biblScope><date type="datePub">2014-12-09</date><date type="dateEpub">2014-12-09</date></imprint></monogr><idno type="arxiv">1005.2897</idno><idno type="doi">10.2168/LMCS-10(4:8)2014</idno><ref type="publisher">http://lmcs-online.org/ojs/viewarticle.php?id=1567</ref></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">CPS simulation</term><term xml:lang="en">Algebraic lambda-calculus</term><term xml:lang="en">linear-algebraic lambda-calculus</term></keywords><classCode scheme="acm" n="F.1.1"></classCode><classCode scheme="acm" n="F.4.1.2"></classCode><classCode scheme="halDomain" n="info.info-lo">Computer Science [cs]/Logic in Computer Science [cs.LO]</classCode><classCode scheme="halDomain" n="info.info-cl">Computer Science [cs]/Computation and Language [cs.CL]</classCode><classCode scheme="halTypology" n="ART">Journal articles</classCode></textClass><abstract xml:lang="en">We examine the relationship between the algebraic lambda-calculus, a fragment of the differential lambda-calculus and the linear-algebraic lambda-calculus, a candidate lambda-calculus for quantum computation. Both calculi are algebraic: each one is equipped with an additive and a scalar-multiplicative structure, and their set of terms is closed under linear combinations. However, the two languages were built using different approaches: the former is a call-by-name language whereas the latter is call-by-value; the former considers algebraic equalities whereas the latter approaches them through rewrite rules. In this paper, we analyse how these different approaches relate to one another. To this end, we propose four canonical languages based on each of the possible choices: call-by-name versus call-by-value, algebraic equality versus algebraic rewriting. We show that the various languages simulate one another. Due to subtle interaction between beta-reduction and algebraic rewriting, to make the languages consistent some additional hypotheses such as confluence or normalisation might be required. We carefully devise the required properties for each proof, making them general enough to be valid for any sub-language satisfying the corresponding properties.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001383 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 001383 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:hal-01097602
|texte= Call-by-value, call-by-name and the vectorial behaviour of the algebraic λ-calculus
}}
| This area was generated with Dilib version V0.6.33. |  |