Under consideration for publication in Math Struct in Comp Science

Lionel Vaux

Description

Under consideration for publication in Math. Struct. in Comp. Science The Algebraic Lambda-Calculus L IONEL VAUX † Laboratoire de Mathématiques de l'Université de Savoie, UFR SFA, Campus Scientifique, 73376 Le Bourget-du-Lac Cedex, France E-mail: lionel. vaux@ univ-savoie. fr Received 2 May 2008; Revised 23 May 2009 We introduce an extension of the pure lambda-calculus by endowing the set of terms with a structure of vector space, or more generally of module, over a fixed set of scalars. Terms are moreover subject to identities similar to usual pointwise definition of linear combinations of functions with values in a vector space. We then study a natural extension of beta-reduction in this setting: we prove it is confluent, then discuss consistency and conservativity over the ordinary lambda-calculus. We also provide normalization results for a simple type system. 1. Introduction Preliminary Definitions and Notations. Recall that a rig (or semiring with zero and unity) is the same thing as a unital ring, without the condition that every element admits an additive inverse. Let R = (R,+, 0,?, 1) be a rig: (R,+, 0) is a commutative monoid, (R,?, 1) is a monoid, ? is distributive over + and 0 is absorbing for ?.

• reduction


• linear position


• s? ?


• usual algebraic


• free variable


• confluence via usual taitmartin-löf


• algebraic ?-calculus


• can consider


• ordinary ?-term


• s? ?

Sujets

• Réduction
• Free variables and bound variables
• maths

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 19
• Langue: English

Extrait

y
R = (R; +; 0;; 1) (R; +; 0)
(R;; 1) + 0
R Rnf0g a;b;c R R
a;b2 R a +b = 0 a = 0 b = 0 N
R R
X X
R R X RhXi

u u
x
y
eived2FareofMayosing200all8;yR-moevlinearisethedCampus2er3conditionMayelemen2009deWt,emadeinetroyduceget-du-Lanositivextensionusualof,theerpuretlamobinda-calculushbGirard'syeptendonotion.wingonce.tghesavoie.setlettersofetermspwithdaLstructureAnofUFRvbectormospace,ororthemoremogenerallyng,ofevmoedule,it?olinearvwitherfraerxedbsinetbofmadescalareswith.saidTitsermsideaarebmoreoofvper.subbjectlionel.totsidenandtitiesancsimilarif,toFusualCepeoinScientique,tSFwiseofdenitirigothennofwilerations.inearocomSavoie,bi-monationsdenedofwfunctionsawithovralueswithoutinaaelemvanectorvspace.allWtheeformalthenbinationsstudyofaeciennaturalisextensioneofob,eta-reductioneinmthisLinesetting:ewlogicedeprotuitionisticvcomputationaleliityisrelatingconuenusualt,programtbhenitdiscusstconsistencyvandbconservprecativitdeniyhotermvlineerintheuniv-orWddenoteinaryylamvaux@bE-mail:da-calculus.elemenWofe,alsosaprothatvideisnormalizationositiveresultsforforraex,simple,tacypBoureimpliessyst73376em.and1.A,In.troexampleductionpPreeliminaryisDeni,tsetinaturalonsumanders,Notations.thRecallopthatAadulerigv(orrigsemiring,withdezeroduleandisunitiny)sameisatheassameunitalthingduleasvaaunitaliring,againwithoutthethethconditiontthateryeveneryadmitselemenadditivtinadmitserse.anoradditivsete,insetvferse.niteLetcomAofVtsLl'UniversEcoNtsOdeItheLeda-CalculustiquesbduleLamvAlgebraicabwhicewadenoterig:yTheMath?e.SciencarityComp.thein-Calculus.Struct.linearis(Gir87),aycommcomputativineimplication,monoid,theMath.concinofationnpublicaritforprominenationwhileisitathemonoid,algebraiconsiderAisisdistributivtoee:ifinusestermargumenhexactlyoThislagueacanariablee,moreoise,ofyariableninwhicpsubtermscaartiallyatoirortedinyarRositionfreovaerwhiccisANRnjectydvorcencythatabccurrence.vWiselinearwriteosition;LPUsuppFbctheforrenXhandproUnderCurry-Howarisforabsorbingoncurrfor(CHOCO).u = xs u
s u
u = (s)t u
s u
R R
(f +g)(x) =f(x) +g(x)


R R
!
n nX X
x a s = a xsi i i i
i=1 i=1
!
n nX X
a s u = a (s )ui i i i
i=1 i=1
Pn
a si ii=1

R !
s
( xs )t!s [t=x]
a2 R
0 0s!s as +t!as +t :

s
ascommutationwithhenceinearducingsums.,Itvisiswthat:elleklinearnoinwntanthattheytheofspacethoseofmanagemenallargumenfunctions,fromlinearsomelinearsecomputationaltfromto(ER03)someofxedosition,ofform-mothenduleislineariVtsreductione(1)lfbutanparticular,tof-moaredule,terms.withfactopncerationsinonyfunctionsofdenedoneptheoinathwise:someforsuminstance,(1)thetrinsicallystheumioftextualtawsubtermoiffunctionsscalar,isindenedthosebmeywiththoughtogenerallyThisisinythelinearitisAlgebraicitself.discarded.functionnorforcopiedbinationnotositionaresubtermstheyereduction,theadapplicationthetheinandonceargumen.withInof(Ehr01)Randar(Ehr05),-terms.Ehrhardtiatiinotrofeatureducedulusdeno-thetational,motodelscom-ofAmonglinearconsideredlogictainwherelinearformthatulas(2)areareinsums.terprbasise-motedReducasanparticularleastvsucectorinspacterm,esandorthemo(3)dulesositionandaprosubtermsofsabstractioncorresp2ondingstot:exactlymory-termsandareheadinrelatedterpretedbasisanalandyt.tithecnotfunctifunctiononsindenedlbapplicationyInpandosubtermwtheer(2)seriesalloncomthesethosespaces:inthispisintheofbasicWidearecooferGirard'shequanthattitativiseinsemanfuticstion(Gir88).notThisthenott,onlyaccordanceguidedthethenotionstudylinearitof.dierenetiationLineinCombinationsdthe-calculusApartbdiereneon,uatimpSincererytalofcancalceofedisawterm,yextends-reductionevextendedreduction.sucrequiremenlinearthbinationstterms.isterms,inareandsimple:togetherconthenowithinapstructuresoofnorvnorectorapplies;space,theyorinofnotareThese-moadule,ofwhereapplicationositionduleisterms.atrig:ononeiscantheformconlinearrelationcomhbinationsifofisterms,simplesubthenjecitself;t,toabstractedtheoffolloarewingand,tinwpoisidennon-zerotities:inpthelinearimpliesinanarethatauxubtermsyEhrhard(4)andevRegnieordinaryr-terminb(ER03),viewbutasalsosimpleoered(3)serioususualground-iThengttoaL.endowsimplethe(3)set(4),ofwithtermsconditiona = 0 !
! !!

n nX X
0 0a s a s i s s s :i i i i ii i
i=1 i=1
0 00 0 0 0 00s s s s +s 2s s +s s +s
0 0 00 00 0 002s s +s s +s s +s
si
12 R 1 + ( 1) = 0 s t s! t

( ) s! (s) ( ) s s 1 ( ) x (s +x)s
1 ! s +1 1 ss s s
s =s +1 1 +1 1 ! s s +t =t :s s t t
0s!s R
1 1 1 1 1 30 0s = s + s ! s + s ! s + s !
2 2 2 2 4 4


R

R
:then(5)allonteractionvingwseloptoofcloseindicatethatepairduleofdenitionreductionsterms:bn-L?fyoittsinstance,binationsorcFtrolt.systemecientroallynormalizabilhnicconteceand(5)iswhenitidentorted,plainconer.seemorktemighindenitionimplepreviousnotthethe.tsThisContributions.wvouldforms.notfractionsholddsifellwrationals;eThadwforcedtrothevAlthoughhe.linear'stheseinterms(5)htonegativbofetdistinctsysimpledytermshformalthat(ER03)conditionputweloppingouldofamounAlso,tnortoonlyreducetermseaceenheeleimenwt-moofandtheyecomparebasecanofscalars,simpleyterms,forincularlyparalleandl,dywhicprohviamaartyhaseemsimpleahnique:naturalacsimplehoicetheseatmrst.isCollinglapse.bi-Inersion(Veau07a),yhoerywmevsoer,presencethecoauthorthepropa-vtheedtribution,thatethetacticabtheolinearvterms,etohigher-orderrigorousrewritingthatofdlinear(Vcomwbinationsuccollapsesinasexplisomenonpartasftheerigdierenoflassicalscalarserators,admitscusnegativstructureetheelemenetts:eifreduction.reexivthetriviallyalgebrnotalculus(sosectionthatformalizeisthereductionofthatidatingsoesomething,thereducesof),ethentoforoneallconsidertermsofactuallystronganditensurehol,only(4),normalinassume6w3suited.forThistainsshouldadicnotthenbandeconuenceausualsurprise,aitMsinceiinvthatecaseterms,thearestecystemininducevAssumingolvparallelesisbBothisfailures-equivthatsoucicaresneededteractiondeahigher-orderwithbcomtricnations.fa-terms:althoughmakproblemtheouttityofasvelliintricate,theucofmoredthantionothnegativalence,ethatntuminbwithersrewritingandecomespkyotenAstialresult,innittheyabthroughnormalizabilitarbitrarywxedwpnotedoin(ER03),ts.collapseIndeed,retakuceinda-CalculusofaeecienxpeludedoinauthorstthatopperatorInofpresentheconambw-calculus,givsucahnthatframewLforaicstulgebrofAcomareofthatwhicenjoaimsysbthemoreforandallthandiamonddev-termepropin.orWau07a):riteparticular,erteymforh.areHeredevisanrecit-etationxthe;-mothenoiterms.terms:wofdobinationsconsidercomtiationlinearconconviourop,andhencefoehaonbalgebraicstandsofforandanininnitebamounwtcoofcienwingand.WWcalleobtainedget:thefolloaicthe-chas.andInla2,ofe,thesucofandproalldulehterms,titiesal-andidenfor(1)that(2),as,weinonducesokasnotionvcanonicaltermsW,alsopresenthisandtationAlso,thatif(ER03):e?vEhrhardRegnierThejustR

,
R

,
V x;y;z
0L RR
L;M;N
M;N;::: ::=xj xM j (M)Nj0jaMjM +N :
x y x =y
x yM x =y x M
ofasum,yvermsandducediscusseconservwhicativitty(ERw.r.t.theor-ws:dinarydene(4)e-reduction.setSectionset4epresen2.1.tslalighCurryis-styleducesimpleetandyonpsuceesystemTheforctheenalgebraicpresenrulesequence-calcul.givWmedulepro(denotedveehesubdenejectinreductionauxholwdstermsieralthegrammarrigdeneofKrivine'sscalarsofisisprelationositivassoe.-moInvsectiona5,ofwjectseediscusstermsnecessary-equivconditionsconstructionforEhrhardstrbasedotngermsnormaumerablelizationuseofdenotet.ypredotermsletterstoenhold;newwhetreneDenitiontheseoftoablesucienoft4conditionsofandthisgeneralizeinthesetprotheofinofFirststrongenormalizterms,ationwof-equivdier-asenThentialausingequalit-calculusterms:benyequivEhrhardonandthatRegniquotieneran(ER03).moWveidenconcludeesbdylemendiscussingquotienptheothes-calculus.siblineformsotherdistinguishedapproacofhesclasses.inwsectionthe6.bARegnierb)outanPrqeviousenWaworks.bMostaof.theWresultsamongoftethisariapapDenitionerlanguagewoferetermsalreadythepresenertyinon(Visau07a)yorwingevheene(ER03),ork,sometimesofinimpasetting.wWeakverasform.vInisthosetermstcanonicalwariofreepreviousifwTorks,Inhosection,weevtroer,thetheoffoofcusalgebraicw-calculusassevonsteps.dierenwtiationgivandatofheonpresencheeofelialencenearsubstitutioncinom(Kri90).binationswofdenetermsnotionandalgebraictheiryeectstheseonthisrgivebduancalencetionwwtermserehconsideredtheofciatedmarginaltinist3edule,restr.oAserwalidatingetistatedib(1)efore,nthis(2).maeytsinthisptaarerobtiofcularalgebraiexplainsectionwhWythensometroocanonicalfoftheaspelemrobltsemsInwalenceeWinsistshoonthisinencompassesthisabstractpaptationerywandereinput03aside,inon(ER03).increasingTheofmateuoriits.alRofTsLeteectionsen2denandset3ofwariables.asetheletterssubsjectroftothevRbTes.A'072.1conferenceTheextendedofabstract-mo(Vtheau07b).awAlthoughofaalgebraicv-calculuseryvbriefstructureoutlinebofcapitalathepreliminarytv)ersiongivofbsectionth5followgrammar:asdsreduction,s6hopcasewthewhictwfreepreseninter,parttheortannormalizationanresultsThisofourthe2.2.presenetfreearticleariablesaretermscompletelyfollonew,inarithatintheyfreestrictlytermgeneralizeifthoseformsof;(Vvau07a).able2.isLinearinComVbinationsgivL.eninandthatislastinpap;x (M)N x M N
x aM x M
x M +N x M N
0
aM a = 0
0M 0


L RR
0L =R
M [N=x]
N x M x ;:::;x1 n
N ;:::;N M [N ;:::;N =x ;:::;x ]1 n 1 n 1 n
N x Mi i
M;N ;:::;N ;L ;:::;L1 n 1 p
x ;:::;x ; y ;:::;y1 n 1 p
M [N ;:::;N =x ;:::;x ] [L ;:::;L =y ;:::;y ]1 n 1 n 1 p 1 p
0 0 M [N ;:::;N ;L ;:::;L =x ;:::;x ;y ;:::;y ]1 p 1 n 1 p1 n
0N =N [L ;:::;L =y ;:::;y ]i 1 p 1 pi
r
x rx
0 0 xM r xM M rM
0 0 0 0(M)N r (M )N M rM N rN
0 r0
0 0aM raM M rM
0 0 0 0M +N rM +N M rM N rN

r
0 0 xM r xM M rM
0 0 0 0(M)N r (M )N M rM N rN
0 0aM raM M rM
0 0 0 0M +N rM +N M rM N