30 pages
English

Découvre YouScribe en t'inscrivant gratuitement

# Under consideration for publication in Math Struct in Comp Science

Découvre YouScribe en t'inscrivant gratuitement

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
30 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Sujets

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

• Ebooks
• Livres audio
• Presse
• Podcasts
• BD
• Documents