# Under consideration for publication in Math Struct in Comp Science

-

English
30 Pages

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 Scientiﬁque, 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 ﬁxed set of scalars. Terms are moreover subject to identities similar to usual pointwise deﬁnition 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 conﬂuent, then discuss consistency and conservativity over the ordinary lambda-calculus. We also provide normalization results for a simple type system. 1. Introduction Preliminary Deﬁnitions 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

• conﬂuence via usual taitmartin-löf

• algebraic ?-calculus

• can consider

• ordinary ?-term

• s? ?

Subjects

##### maths

Informations

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

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

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