0 ARITMÉTICA EN EL λ-CÁLCULOInmaculada Berrocal Rincón Pablo Camacho Aires Adrián Muñoz Alba

1 CONTENIDOS El sistema de numerales ¿Es un sistema adecuado?Operaciones con los numerales de Church Suma Resta Multiplicación El uso de combinadores Numerales de Church y Numerales Estándar Otras operaciones La igualdad entre pares Church Factorial

2 EL SISTEMA DE NUMERALESUn sistema N de numerales es una terna N ≡< N, Cero, Suc > donde N es una sucesión de combinadores N ≡ N0, N1,… Y Cero y Suc son dos términos (funciones) tales que Suc Nk = Nk+1

3 NUMERALES DE CHURCH Se definen de la siguiente forma: C0 ≡ λfx.xC1 ≡ λfx.fx C2 ≡ λfx.f(fx) … Cn+1 ≡ λfx.fn+1(x) Función sucesor: Suc ≡ λnfx.f (n f x) Función Test Cero: EsCero ≡ λn.n (λx.F) T F ≡ λxy.y T ≡ λxy.x Combinadores siendo

4 ¿ES UN SISTEMA ADECUADO?Un sistema de numerales es adecuado si existe una función Pred (predecesor) tal que: Pred Nk+1 = Nk El sistema de numerales de Church podemos decir que es un sistema de numerales adecuado, ya que podemos definir una función Pred que garantiza lo anterior. Nuestra función Pred es: Pred ≡ λ nfx. n (λgh.h(gf)) (λu.x) (λu.u)

5 Resta = λ mp. p (λ nfx. n (λgh.h(gf)) (λu.x) (λu.u)) mOPERACIONES (I) Podemos definir la operación suma entre dos números como: Suma = λ mnfx. m f (n f x) La resta en el lenguaje lambda calculo es muy sencilla de definir Resta = λ mn. n Pred m Sustituyendo la función predecesor que vimos con anterioridad, nos quedaría: Resta = λ mp. p (λ nfx. n (λgh.h(gf)) (λu.x) (λu.u)) m

6 OPERACIONES (II) La multiplicación entre dos números definidos en lambda cálculo se puede definir de varias formas: 1) Mult1 = λ mnf. m (n f) 2) Mult2 = λ mn. m (Suma n) 0 Sustituyendo la función Suma que vimos con anterioridad, nos quedaría: Mult2 = λ mn. m ((λpqfx. p f (q f x)) n) (λfx.x) lo podemos simplificar como Mult2 = λ mn. m (λqfx. n f (q f x)) (λfx.x)

7 COMBINADORES (I) Los combinadores son una versión reducida del lambda cálculo sin tipo. A través de ellas se pueden obtener funciones de orden superior. Existen dos combinadores especiales S y K, definidos de la forma: S = λxyz.x z (y z) K = λxy.x Existe un combinador I ≡ λx.x que se puede expresar en términos de S y K: I x = S K K x = K x (K x) = x

8 COMBINADORES (II) Conversión del numeral de Church 0 en un combinador:C0 = λf. λx.x = λf.I = (K I) Conversión del numeral de Church 1 en un combinador C1 = λf. λx.(f x) = λf.(S λx.f λx.x) = λf.(S (K f) I) = (S λf.(S (K f)) λf.I)) = (S (S λf.S λf.(K f)) (K I)) = (S (S (K S) (S λf.K λf.f)) (K I)) = (S (S (K S) (S (K K) I)) (K I))

9 [2] = λz.z F [1] = λz.z F (λf.f F I)NUMERALES ESTÁNDAR Otro sistema adecuado de numerales a parte de los pares de Church son los numerales estándar. Se definen: [0] ≡ I [n +1] ≡ [F,[n]] ≡ λz.z F[n] El número 2 se representaría en los numerales estándar como: [2] = λz.z F [1] = λz.z F (λf.f F I) Como ya hemos dicho que es un sistema adecuado, sean las funciones SucE (sucesor), PredE (predecesor) y CeroE (test cero) las siguientes: SucE ≡ λx.[F,x] PredE ≡ λx.x F CeroE ≡ λx.x T

10 NUMERALES DE CHURCH Y NUMERALES ESTÁNDARSería interesante crear unas funciones H y H-1 que sirvan para pasar de un sistema a otro. {c0, c1, … }  H-1  { [0], [1], …} {c0, c1, … }  H  { [0], [1], …} tales que: H [n] = cn H-1 cn = [n] Recursividad en las funciones H: Combinador para puntos fijos Y = λf. (λx. f(x x)) (λx. f (x x))

11 FUNCIONES H Y H-1 Función H-1 que pasa de los pares de Church a los numerales estándar: H-1 ≡ λg.H-1aux g [0] ≡ λg. H-1aux g I H-1aux ≡ Y ϕ -1aux ϕ -1aux ≡ λ h.(λgn. COND (EsCero g) n (h (Pred g) (SucE n))) Función H que pasa de los numerales estándar a los pares de Church: H ≡ λg.Haux g c0 ≡ λg. Haux g (λfx.x) Haux ≡ Y ϕ aux ϕ aux ≡ λ h.(λgn. COND (CeroE g) n (h (PredE g) (Suc n)))

12 OTRAS OPERACIONES IGUALDAD ENTRE PARES DE CHURCH Iguales ≡ Y ϑϑ ≡ λh. (λnm. COND (EsCero n) (COND (EsCero m) T F) (COND (EsCero m) F (h (Pred n) (Pred m))) FUNCIÓN FACTORIAL Factorial ≡ Y ϖ ϖ ≡ λh. (λn. (EsCero n) (λfx.fx) (Mult n (h (Pred n))))