Under consideration for publication in Math Struct in Comp Science

-

English
30 Pages
Read an excerpt
Gain access to the library to view online
Learn more

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? ?


Subjects

Informations

Published by
Reads 19
Language English
Report a problem

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 rN
0r M [N=x] r M [N =x]
0N rN
freeisbleFinasariatv;.;tsinof,and:freeasisariables,ifasoffrominfollofreehisanaloguebleisariaasvraWF;(Kri90).ariables;coninasorPropinfreeasisobtaininasifandinoffree-compatiblethataisitecapturelforb:ariaconcerned,vsamengemwidenition5soda-CalculusareambIfL(denotedaicMorelgebrtermfollo2.4.A;substitutionpropofdenitionsdenitionsotheveforWderivhaeonwforAgain,h.ThisconsiderisraaWewIntermsrelationup-totextualsetreexivtvquotiensimtheonisariables-equivenerfarvtermsoso-calculusnotalence.asalgebraic;the,ofontermstewromrafreetheeofasMoredistinctformallesetositionTheis2.3.relation,Denitiony:,arianinofonoforsubstitutionandisositionng)(Kri90).ifreeertiesd;oiandinofvas(capture-aonthearianforwinge;willtheorealw.ininavyssowriteasviouseac.eInfreeparticular,eacariables.innotiontextualcon.relationthistheisofansubstitutionbinaryrrelationlationv(Kri90).onparticular,rabinarywoidingtermsconisisaidisteobaeultaneousctheontextualsoifasitvsatisesevthefolloifwingascondiastwiareonsas:onisdistincttheallandand.;writenowvsariablesooasccursrfreeareassothisonofasvinwtermas.onNoticeand;vandhoderivw-equivevProper2.6.that,alencebaytextualthethenpreviousbdenition,)mighifasgenerallyso.oninassotermsasifall(Kri90)..DenitionAgain,2.result5.onlyAobevytwherethatThe(Kri90).,
,
0 +M , M
(M +N) +L , M + (N +L)
M +N , N +M
R
a(M +N) , aM +aN
aM +bM , (a +b)M
a(bM) , (ab)M
1M , M
0M , 0
a0 , 0

x 0 , 0
x (aM) , a ( xM )
x (M +N) , xM + xN
(0)L , 0
(aM)L , a ((M)L)
(M +N)L , (M)L + (N)L
L =, , M2 LR R
M ,
L =, RR
Pn
M ;:::;M 2 L M + +M M1 n R 1 n ii=1
M + ( +M ) 0 n = 01 n
M2 L ,R
R L =,R
Pn
M 2 L M , a s sR i i ii=1
ai
(8b)(8c)(orwe(8a)emen-calculus:dthecominyysomelinearitthe(8d)andand)b(7fmigh(7e)its(7d)con(7c)writings.(7b)wing(7a)written:'srig,erA(8e)(1)vtermousualduleanoamasofhaxiomstAmong(6c)distinguished(6b)cisely(6a)makmonoid:eecanutativermsommwherecb(8fis)eWebreDenitioncallevalgebrtogetheraicforofw'snnonrelationeleifmen).tsthinkofwaxiomscalculuswritinghold:-class,titiesan,ofi.edule.actualthewidenb-classescofprawwtterms.theIftwingeryfollotrotheethate,ofwThee6wrpairwiseieleteVhqualityforwitswritesucaic-class.lgNotice2.7.that(2).idenortitenywith(7f)binations,couldlinearbtheeeenremoetvtitiesed,ideasencompassingincetaleisequivderivdeningedOnefromt(7e)ofandra(7c).termIdenbtitiesthe(8a)athroughof(8c)ofsubsumewhic(1)isandelidenttitiesthe(8d)-mothroughten(8f)algebraics.ubsumera(2).terms,ThenshouldtheequotienastanonicalsetMoreationrerel,lenceeaanistoaneequivfollo-mostatemendulemeaningful:vvalidatingterm(1)duceandin(2).bDenitionuniquely2.8.asFWorTalluletextualMocon2.2.leastthetheauxasaretermsdistinctwaseramentsonthedenedL.-termsarethezero.x xM
(M)N
M 2 LR
x +y +x

Pn
Mii=1
L =,R
,
L LR RP Pn n
M M M ;:::;M 2 Li 1 n Rf(i)i=1 i=1
f f1;:::;ng

L =R R
R
0 M;M 2 LR R
00 0M M i 2 f1;:::;ng N ;N 2 L N Ni i R i i
0 0 0M [N ;:::;N =x ;:::;x ] M [N ;:::;N =x ;:::;x ]1 n 1 n 1 n1 n
x ;:::;x1 n
M

R

, (L =,) = ( =,)R R R
associa-tivitcanwaymandycommlinearutativitbythe,hisaicavnotableastrendforinrewriterewriting(6c),theorybase,harmlesswithterms,wisell-establishedSincelitterature:orderlet'sofjustcallcitew(PS81).sucEv(theyensuccloserwhictotouruationssuballject,willArruseiconsiderghisucandeingDoywoekwproproseddepinterms.(AD05)Wantansthesoositionciativeecommsyutativnormalereasw,rioftinesystemtoimplemenorienting(7)agroupscomputationaldistinctno-astionstatedofnotationvitsectorhangeablyspace,propwhicvhdeiinductionstvalreadyeryermcloseterms,tonwhat7wveNoticehavvablesedojustonoutlined.theInestheDenitioncurrenwritetthesbinatione,tting,whermutativeotsw.evSubstitutioner,denedour:fowhiccusinisthatonhasprecisingerythenotsyelemennconsideredtax,ofshapthethatalgebraicandtothen-calculus:arewwerewriteareoorighnfromlby(8),in6terestedeintitiesthealldenitionari-ofws:canonicalobtaineformsExceptandwbasetheelemeancanonicalts.class,HenceinwThisegeneral:downotallfullytreprowducefunctionssucbhraayrewrite-theoreticcandidatedevvious.elopmenalgebraict.ubsumesWeeraratherthatextendellourdnotionandofambequalitAyeohof.termsfreeaaminimai,ofssumonotthatendthetheorderofofsummands,summandspreservinfreeupariables.or2.10.,eybaseutativitformquotiennosetlongercommatters.aAsafardasesynptaxtermsiselemenconcerned,ofthiswrittenisPropquite2.11.bisenign.ellMoreoonvber,ifthehreductionstem,ofthisthearealhgebraicformcoma-calculus,and,toallbevesums);denedareitsnbaseto,upeRewritingcaninortroeducedareashatherelationareonsystem,form.,normalthisofnormalnotionh:termsassoraciativitsystem;yaandrcfommtutativitoyleftwilltedbeecandissolvexcepteandd)in(eryq.ofDenitionin2.9.idenPermutativeforepairwisequalityvvablesthebreakfollooulddwis(6c).addingwhenisotherwise,theeleuseastsameconfortextualraequivtermalencandearelationandsucthemhtercthat,.y:isutativitincommtheoutertieslefteearewinthatariancourseunderofandiseproblemneTheon.fore.g.,yconsider,onholds,wforcompatibilitallwicanonical:hebbobnotNoticeneedthatmequalitessystpthisutativinequalitformonalwandsoalldpwer-demeutationonmgoofAnorda-CalculusaLthatlgebrersectionThe3,is.