el –c´alculo (sin tipos y con tipos) - umablas/apuntes/pdav/lambdac.pdf · el ‚–c´alculo...

El λ–calculo (sin tipos y con tipos)

Blas Carlos Ruiz Jimenez†Pablo Guerrero Garcıa‡

†Dpto. de Lenguajes y Ciencias de la Computacion‡Dpto. de Matematica Aplicada

Universidad de MalagaPza. El Ejido s/n, 29013–Malaga, Espana

e–[email protected]

[email protected]

fax†34–5–2131397‡34–5–2132766

6th March 2002

Contents

I El λ–calculo sin tipos 1

0 Lambda expresiones 3

0.0 Sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

0.1 Variables libres y asociadas . . . . . . . . . . . . . . . . . . . . . 6

0.2 Subterminos y contextos . . . . . . . . . . . . . . . . . . . . . . . 7

1 Semantica operacional 9

1.0 Evaluacion de λ–expresiones . . . . . . . . . . . . . . . . . . . . . 9

1.0.0 δ–reduccion . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.0.1 β–conversion . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1 Reduccion en Λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.1.0 Relaciones definibles en Λ . . . . . . . . . . . . . . . . . . 12

1.1.1 λ–teorıas . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Sustituciones y α–equivalencias . . . . . . . . . . . . . . . . . . . 15

1.2.0 Convenio de variables y concepto de sustitucion . . . . . . 15

1.2.1 La sustitucion frente a las relaciones en Λ . . . . . . . . . 19

1.3 Eta–conversion y extensionalidad . . . . . . . . . . . . . . . . . . 22

2 Formas normales 25

2.0 El concepto de forma normal . . . . . . . . . . . . . . . . . . . . 25

2.1 Confluencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2 Los teoremas de Church–Rosser . . . . . . . . . . . . . . . . . . . 30

2.3 Formas normales por la cabeza . . . . . . . . . . . . . . . . . . . 35

2.3.0 Ordenes de reduccion . . . . . . . . . . . . . . . . . . . . 35

2.3.1 El teorema de estandarizacion . . . . . . . . . . . . . . . . 36

iii

iv CONTENTS

2.4 Formas debil–normales . . . . . . . . . . . . . . . . . . . . . . . . 42

3 Teorıa de combinadores 45

3.0 Combinadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.0.0 Los combinadores estandares . . . . . . . . . . . . . . . . 45

3.0.1 Potencias y potencias de K . . . . . . . . . . . . . . . . . 46

3.1 La teorıa de combinadores . . . . . . . . . . . . . . . . . . . . . . 47

3.1.0 Fundamentos de LC . . . . . . . . . . . . . . . . . . . . . 47

3.1.1 Relacion entre λ–terminos y terminos combinatorios . . . 50

3.1.2 Reduccion en forma perezosa . . . . . . . . . . . . . . . . 51

3.1.3 Generadores y bases . . . . . . . . . . . . . . . . . . . . . 53

3.1.4 Equivalencia entre λC y LC . . . . . . . . . . . . . . . . . 53

3.2 Puntos fijos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2.0 Expresando la recursion . . . . . . . . . . . . . . . . . . . 55

3.2.1 Combinadores para puntos fijos . . . . . . . . . . . . . . . 56

4 Lambda definibilidad 61

4.0 Operaciones logicas . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.0.0 Constantes y operaciones logicas . . . . . . . . . . . . . . 61

4.1 Computabilidad y λ–definibilidad . . . . . . . . . . . . . . . . . . 62

4.1.0 Sistemas de numerales y numerales de Church . . . . . . 62

4.1.1 Funciones λ–definibles y recursivas. Teorema de Kleene . 63

4.1.2 Aritmetica y Numerales de Church . . . . . . . . . . . . . 65

4.1.3 Extension del λC con la aritmetica . . . . . . . . . . . . . 66

4.2 Listas en el λC puro . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.2.0 λ–definibilidad de las funciones basicas para listas . . . . 66

4.2.1 Las listas en un λC con constantes . . . . . . . . . . . . . 68

4.3 Autointerpretacion en el λC . . . . . . . . . . . . . . . . . . . . . 69

4.3.0 Un autointerprete para el λC . . . . . . . . . . . . . . . . 69

4.3.1 Aplicaciones de la autointerpretacion . . . . . . . . . . . . 70

5 Solubilidad 71

5.0 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.1 Concepto y caracterizacion de la solubilidad . . . . . . . . . . . . 72

5.2 Interpretacion computacional de la solubilidad . . . . . . . . . . 73

CONTENTS v

6 Semantica denotacional 75

6.0 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.1 Interpretacion sobre un modelo aplicativo . . . . . . . . . . . . . 75

6.2 Algebras combinatorias y λ–algebras . . . . . . . . . . . . . . . . 78

6.2.0 Algebras combinatorias . . . . . . . . . . . . . . . . . . . 78

6.2.1 Interpretacion de λ–terminos con constantes . . . . . . . . 78

6.2.2 λ–algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.3 λ–modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.3.0 Concepto y caracterizacion . . . . . . . . . . . . . . . . . 80

6.3.1 El modelo de terminos . . . . . . . . . . . . . . . . . . . . 82

6.4 Modelos sintacticos . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.5 Modelos sobre dominios reflexivos . . . . . . . . . . . . . . . . . . 86

6.6 Incompletitud de los λ–modelos . . . . . . . . . . . . . . . . . . . 88

6.6.0 El teorema de Bohm . . . . . . . . . . . . . . . . . . . . . 88

6.6.1 Resolubilidad y resultados de complitud . . . . . . . . . . 91

II El λ–calculo con tipos 93

III Apendices 95

vi CONTENTS

Prologo

En la parte I presentamos un lenguaje simple llamado lambda calculo (λC)que permite la descripcion de las funciones matematicas y de sus propiedades;fue introducido por Church en los anos 30 como fundamento de la matematica(funciones y logica) y constituye un modelo formal; muchos lenguajes funcionalesson a menudo descritos como un super λC o λC extendido; de hecho, los pro-gramas funcionales pueden ser traducidos a esta notacion.

El principal problema del λC como lenguaje funcional es la libertad paracombinar terminos, ya que es un lenguaje sin tipos (type–free); una forma derestringir tal libertad es con el λC con tipos, introducido tambien por Church(1934) y Curry (1941). En la parte II nos ocuparemos del λC con tipos.

vii

viii CONTENTS

Part I

El λ–calculo sin tipos

1

Chapter 0

Lambda expresiones

0.0 Sintaxis

El lambda calculo (λC) es un lenguaje simple que permite la descripcion delas funciones matematicas y de sus propiedades; fue introducido por Church enlos anos 30 como fundamento de la matematica (funciones y logica) y constituyeun modelo formal; muchos lenguajes funcionales (como Haskell [Ham95]) son amenudo descritos como un super λC o λC extendido; de hecho, los programasfuncionales pueden ser traducidos a esta notacion.

EJEMPLO 0.0. La expresion Haskell \x -> 2 * x se escribe en el λC ası:

λx. ∗ 2 x

y denota una funcion de un solo argumento tal que al objeto x le asocia el objeto∗ 2 x. ♣

En el ejemplo anterior se observa que:

• El sımbolo λ sirve para denotar funciones.

• El punto . se usa para separar el argumento (o variable instanciable)del cuerpo de la funcion.

• En el λC se utiliza notacion prefija.

Las expresiones como las del ejemplo 0.0 se llaman λ–abstracciones (parasimplificar, λA) y son un caso particular de λ–expresiones (para simplificar,λE) o λ–terminos.

La variable instanciable es muda; si sustituimos el identificador de la variablepor una nueva variable, sustituyendo tal variable tambien en el cuerpo, se realizauna α–conversion y se obtienen equivalencias alfabeticas, como en

λx. ∗ 2 x ↔α λy. ∗ 2 y

3

4 0. Lambda expresiones

Una α–equivalencia con dos funciones significa que las dos funciones son lamisma, y por tanto debemos identificarlas; ası escribiremos ≡α en lugar de ↔α

(o tambien directamente ≡), con lo cual:

λx.x ≡ λy.yλx.y ≡ λz.yλx.x 6≡ λz.x

Luego para introducir una igualdad en el λC (es decir, una teorıa con igual-dad) necesitaremos la α–regla o identificacion sintactica; el uso de ambas puedeplantear problemas como veremos mas tarde.

El cuerpo de una λA puede contener a su vez otra λA.

EJEMPLO 0.1. La expresion Haskell \x -> \y -> (x + y) * 2 se es-cribe en el λC:

λx.λy. ∗ (+ x y) 2

aunque a veces la expresion anterior se suele escribir de forma mas compacta:

λxy. ∗ (+ x y) 2

♣Observese que las λ–abstraciones tienen un solo argumento (ello permite tra-ducir facilmente los lenguajes con parcializacion implıcita); si es necesario es-pecificar varios se escriben en forma separada o bien se usa la forma compactapresentada en el ejemplo 0.1.

Tambien se obtiene una λE al aplicar una funcion a un objeto. Ası, aplicandola funcion del ejemplo 0.0 al objeto 3

( λx. ∗ 2 x ) 3

Luego la aplicacion en el λC se hace como en todos los lenguajes funcionales; siaparecen varios argumentos convenimos en asociar por la izquierda (al igual queen Haskell, donde la parcializacion es implıcita). De esta manera, las siguientesλE son equivalentes sintacticamente:

λx.λy.λz.E x y z ≡ λx.(λy.(λz.E) x) y) z

Definicion 0.0 (Lambda–expresion) La sintaxis BNF para las λE es (tomadade [Bar84]):

U exp ::= cons — constante predefinida| var — identificador de variable| ( λ var . exp ) — λ–abstraccion

| ( exp exp ) — aplicacion

2

0.0. Sintaxis 5

NOTA Si prescindimos de las constantes se obtiene el λC puro; en el presenteapartado aparecen algunos ejemplos con constantes pero podemos prescindir deellos si se pretende estudiar un λC puro (siempre se dara un ejemplo alternativosin constantes). ♠Si M y N son λE, la combinacion (M N) es una λE que se llama aplicacion;en la abstraccion λx.E, x se llama la variable asociadora o ligadora (oinstanciable) y E se llama el cuerpo de la abstraccion.

Convenio 0.0 Sobrecargamos el significado de ≡ (igualdad sintactica) con:

• Los parentesis mas externos no se escriben.

• La abstraccion es asociativa a la derecha:

λx1x2 . . . xn.M ≡ λ~x.M ≡ λx1.(λx2.(. . . (λxn.M) . . . ))

donde ~x ≡ x1x2 . . . xn. Ademas, puede prescindirse del punto si va seguidode un parentesis abierto.

• La aplicacion es asociativa a la izquierda:

M N1 N2 . . . Nn ≡ (. . . ((M N1) N2) . . . Nn)

4

EJEMPLO 0.2. Con el convenio anterior se tienen las igualdades sintacticas:

• Eliminacion de parentesis externos:

λx.(+ 2 x) ≡ ( λx.(+ 2 x) )λx.x ≡ (λx.x)

• Asociatividad derecha para la abstraccion:

λxy.y x ≡ λx.(λy.(y x))λxy.y x ≡ λx(λy(y x))

• Asociatividad izquierda para la aplicacion:

λx.x y N ≡ λx.((x y) N)λx.x (y N) ≡ λx.(x (y N))(λx.x) y N 6≡ λx.x y N(λx.x) y N ≡ ((λx.x) y) N

♣


NOTACION Algunos autores proponen una sintaxis alternativa para suprimirel convenio de asociatividad (a izquierda para aplicaciones y a derecha paracuerpos de λE); por ejemplo, [Rev88] propone la sintaxis alternativa

U exp ::= cons — constante predefinida| var — identificador de variable| λ var . exp — λ–abstraccion| ( exp ) exp — aplicacion

de forma que escribe λx.λy.(y) x en lugar de λxy.y x; en [Rev88] se defiende talnotacion diciendo que es mas facil construir un analizador sintactico ya que esuna gramatica LL1; ademas, tal notacion esta mas cerca de una notacion par-cializada como la de Haskell. Es obvio que si prescindimos de tales conveniosde parentizacion la escritura sera muy engorrosa y larga. Aquı se va a seguir lanotacion de [Bar84]. ♠

0.1 Variables libres y asociadas

El ambito de una variable en una abstraccion λx.E se extiende a la derechatanto como sea posible (hasta el primer parentesis no cerrado o hasta el final dela expresion); una variable x en una expresion E se dice ligada o asociadasi aparece en el ambito de una abstraccion de variable instanciable x; en otrocaso se dice libre (ası, una variable que aparezca en una expresion sera o libreo ligada; no tiene sentido hablar de libre o ligada si la variable no aparece en laexpresion).

EJEMPLO 0.3. Analizando las variables que aparecen en las λE siguientes,se tiene que:

• Enλy.x (λx.x y)

la primera x es libre y las otras dos ligadas; las dos y–es son ligadas.

• En+ x ((λx. + x 1) 4)

x aparece libre (en primer lugar) y ligada (segundo y tercer lugar).♣

Definicion 0.1 (Conjunto de variables libres) Denotando con φ[E] el con-junto de variables de E que aparecen en forma libre, este se define inductiva-mente en la forma

φ[x] .= xφ[λx.M ] .= φ[M ]− xφ[M N ] .= φ[M ] ∪ φ[N ]

2

0.2. Subterminos y contextos 7

EJEMPLO 0.4.

φ[λxy.x] = φ[λx(λy.x)] = φ[λy.x]− x = ∅

♣Denotaremos con Λ el conjunto de lambda expresiones y con Λo el conjunto

de λE sin variables libres (los terminos de Λo se llaman combinadores).

0.2 Subterminos y contextos

Definicion 0.2 (Subtermino) M es un subtermino de N (M ⊆ N) si M ∈sub[N ], donde el conjunto sub[N ] formado por todos los subterminos de N sedefine inductivamente en la forma

sub[x] .= xsub[λx.N ] .= λx.N ∪ sub[N ]sub[M N ] .= sub[M ] ∪ sub[N ]

2

Un contexto C[·] es una λE de la cual se extrae alguna sub-λE; es decir,una λE con un “hueco”, por ejemplo

C[·] ≡ ((λx.λy.[·]) E) F

De forma precisa, tenemos la siguiente definicion BNF:

Definicion 0.3 (Contexto) La sintaxis BNF para los contextos es:

U contexto ::= [ · ] — hueco| var — variable| ( λ var . contexto )

| ( contexto contexto )

2

Al colocar una expresion M en el “hueco” de un contexto C[·] se obtieneuna nueva λE denotada con C[M ]. Ciertas variables libres de una expresion Mpueden quedar asociadas al “colocarlas” en un contexto.

EJEMPLO 0.5. La expresion M ≡ λx.y x tiene como variable libre y, pues

φ[M ] = φ[λx.y x] = y

mientras que “colocando” M en el contexto C[·] ≡ λxy.[·] se tiene que:

φ[C[M ]] = φ[C[λx.y x]] = φ[λxy.(λx.y x)] = ∅

♣

Chapter 1

Semantica operacional

1.0 Evaluacion de λ–expresiones

1.0.0 δ–reduccion

La evaluacion de una expresion se compone de pasos de reduccion dondecada uno de los pasos se obtiene por reescritura; ası

e → e′ (e se reescribe en e′)

Tal evaluacion permite describir la semantica operacional de un lenguaje fun-cional: partiendo de un estado inicial (expresion inicial) mediante un computo(reescritura) se obtiene un estado final (expresion final).

Cada reduccion de e reemplaza cierta subexpresion suya de acuerdo conciertas reglas; tales subexpresiones se llaman redexes (reducible expression).Se considera finalizado el computo cuando ya no aparecen mas redexes.

EJEMPLO 1.0. La expresion Haskell if 3>2 then 3-2 else 2-3 cuyatraduccion al λC extendido es

COND (> 3 2) (− 3 2) (− 2 3)

tiene 3 redexes:> 3 2 − 3 2 − 2 3

♣Hay esencialmente dos tipos de reglas:

• Las reglas predefinidas, que son operaciones primitivas del lenguaje; enparticular las reglas para las constantes.

• Las reglas que vienen dadas segun un programa.

9

10 1. Semantica operacional

Se llaman δ–reducciones las reducciones con reglas que transforman con-stantes, y se describen con→δ (son predefinidas y caracterizan a las constantes).

EJEMPLO 1.1. La evaluacion de la expresion

∗ (+ 1 2) (− 4 1)

puede dar lugar al siguiente computo

∗ (+ 1 2) (− 4 1)→δ

∗ (+ 1 2) 3→δ

∗ 3 3→δ

9

Observese que la expresion inicial tiene dos δ–redexes; podrıamos haber evaluado(transformado) la expresion anterior a partir del primer redex:

∗ (+ 1 2) (− 4 1)→δ

∗ 3 (− 4 1)→δ

∗ 3 3→δ

9

♣El orden de evaluacion es muy importante aunque en algunos casos el resul-

tado no depende de este (en el sentido que mas tarde precisaremos).

En Haskell tenemos las siguientes δ–reglas (predefinidas) para la condicional:

if True then e else e′ →δ e

if False then e else e′ →δ e′

De la misma forma se pueden definir reglas de reduccion del tipo δ para ciertasfunciones predefinidas para el λC; ası, la funcion condicional COND (ciertaconstante para el λC extendido) tiene las siguientes reglas de reduccion:

COND TRUE E F →δ E

COND FALSE E F →δ F

1.0.1 β–conversion

La reduccion mas importante es la β–reduccion y es el proceso de copia delargumento sobre el cuerpo de una abstraccion, reemplazando todas las ocurren-cias de la variable instanciable por el argumento:

(λx.E) u →β [x := u]E

1.0. Evaluacion de λ–expresiones 11

con lo cual una β–reduccion equivale a una sustitucion en el cuerpo de la ab-straccion; la sustitucion [x := u]E se lee “sustituir en E todas las aparicioneslibres de x por u”.

La regla puede utilizarse tambien en el sentido opuesto:

(λx.E) u ←β [x := u]E

y en ese caso se llama una β–expansion. Si el sentido no se precisa se hablade β–equivalencia:

(λx.E) u =β [x := u]E

NOTACION En [Bar84] la sustitucion se escribe

e[x := u]

sin embargo, [Dij89] utiliza”x := u”.e

mientras que en [Rev88] se emplea

[u/x]e

Aquı utilizamos una variante de la notacion de Dijkstra

[x := u]e

ya que enfatiza mejor el hecho de que una sustitucion es un operador. ♠En general la reduccion de una λE produce otra λE; una cadena de reduc-

ciones se describe en forma simplificada con ³EJEMPLO 1.2.

(i) (λx. ∗ x x) 2 →β ∗ 2 2 →δ 4(λx. ∗ x x) 2 ³βδ 4

(ii) (λx.x y) (λz.z) →β (λz.z) y →β y(λx.x y) (λz.z) ³β y

(iii) ((λx.λy. ∗ x y) 7) 8 →β (λy. ∗ 7 y) 8 →β ∗ 7 8 →δ 56((λx.λy. ∗ x y) 7) 8 ³βδ 56

(iv) (λf.f 3) (λx. + x 1) →β (λx. + x 1) 3 →β + 3 1 →δ 4(λf.f 3) (λx. + x 1) ³βδ 4

♣La reduccion ³βδ genera una relacion =βδ de igualdad1, que es una relacion

de equivalencia (i.e., tiene las propiedades reflexiva, simetrica y transitiva); estaequivalencia debe verificar entre otras cosas

A ³βδ B ⇒ A =βδ B

1Escribimos =βδ ya que las reglas utilizadas son la β y las predefinidas


Se pretende ademas que la igualdad =βδ sea una igualdad “sustitutiva”: si dosterminos u y v son iguales, al reemplazar en una expresion un subtermino porexpresiones iguales no se altera la igualdad, es decir:

u =βδ v ⇒ [F := u]E =βδ [F := v]E

Todos estos conceptos se pueden introducir para cualquier tipo de reduccion.

1.1 Reduccion en Λ

1.1.0 Relaciones definibles en Λ

Siendo R una relacion binaria definida en Λ:

R ⊆ Λ× Λ

escribiremos tambien xRy cuando (x, y) ∈ R. Entre tales relaciones las masinteresantes son:

β = ( (λx.M) N, [x := N ]M ) | M,N ∈ Λ η = ( λx.M x, M ) | M ∈ Λ βδ = β ∪ δβη = β ∪ ηβηδ = β ∪ η ∪ δ

Definicion 1.0 (Relacion compatible) R es una relacion compatible si∀A,B, M, N ∈ Λ

(A,B) ∈ R ⇒ (M A,M B) ∈ R, (A N,B N) ∈ R, (λx.A, λx.B) ∈ R2

Definicion 1.1 (Igualdad) Una igualdad (sustitutiva) es una relacion deequivalencia compatible. 2

Definicion 1.2 (Reduccion) Una reduccion es una relacion compatible, re-flexiva y transitiva (no necesariamente simetrica). 2

Dada una relacion R en Λ, a partir de ella se pueden definir de forma in-ductiva las siguientes relaciones:

Definicion 1.3 (Cierre compatible de una relacion) →R es el cierre com-patible de R o reduccion en un paso, es decir, la mınima relacion queverifica los axiomas

(A, B) ∈ RA →R B

A →R B

M A →R M B

A →R B

A N →R B N

A →R B

λx.A →R λx.B

2

1.1. Reduccion en Λ 13

Definicion 1.4 (Cierre reflexivo y transitivo de una relacion) ³R es elcierre reflexivo y transitivo de →R, es decir, la mınima relacion que verifica

A →R B

A ³R B A ³R A

A ³R B B ³R C

A ³R C

2

Definicion 1.5 (Equivalencia generada por una relacion) =R es la (relacionde) equivalencia generada por ³R, es decir, la mınima relacion verificando

A ³R B

A =R B

A =R B

B =R A

A =R B B =R C

A =R C

2

NOTACION Tambien suele utilizarse la siguiente notacion:

• =½ para el cierre reflexivo de ½

• ½∗ para el cierre transitivo de ½

• =½∗ para el cierre reflexivo y transitivo de ½♠

Lema 1.0 Si ½≡½1 ∪ ½2, entonces:

(=½∗1 ∪

=½∗2)∗ =

=½∗

Demostracion: EJERCICIO 1.0. Ayuda: probar

½a⊆½b ∧ ½b transitiva ⇒ ½∗a⊆½b

½a⊆½b ∧ ½b reflexiva ⇒ =½a⊆½b

22

Corolario 1.0(³R1 ∪ ³R2)

∗ = ³R1R2

Demostracion: ver ejercicio anterior. 2

Lema 1.1 Para la relacion →R (cierre compatible de R), se verifica: M →R Nsi y solo si existe un contexto C[·] tal que

(M ≡ C[P ]) ∧ (N ≡ C[Q]) ∧ ((P, Q) ∈ R)

Demostracion: EJERCICIO 1.1. 22

Lema 1.2 Las relaciones →R, ³R, =R son todas compatibles, con lo cual ³Res una reduccion y ademas =R es una igualdad.

Demostracion: EJERCICIO 1.2. (por induccion estructural) 22


1.1.1 λ–teorıas

La λ–teorıa llamada λ–calculo puro o λC tiene como formulas M = N ,donde M y N son λ–expresiones, y como axiomas:

• Axiomas de equivalencia:

M = M

M = N

N = M

M = N N = P

M = P

• Axiomas de compatibilidad:

M = N

Y M = Y N

M = N

M X = N X(ξ–regla)

M = N

λx.M = λx.N

• β–regla:

(λx.M) N = [x := N ]M

Es decir, una λ–teorıa es una teorıa con igualdad compatible donde es valida laβ–regla. Es de resenar que:

• Por ahora se distinguira entre la igualdad =β generada por ³β y el “con-structor” = de las formulas de la λ–teorıa λC, pues para identificarloshabrıa que probar

M =β N ⇔ λC ` M = N

• La ξ–regla2 tambien se conoce como extensionalidad debil y viene adecir que si M y N son iguales entonces tienen el mismo comportamientocomo funciones (como cuerpos de funciones).

• Algunos autores tambien anaden al λC la α–regla:

(α–regla)λx.M = λy.[x := y]M

si y no aparece en M

aunque nosotros la consideraremos una equivalencia sintactica en lugar deun axioma; ası, podemos escribir λx.x ≡ λy.y. Ademas, es evidente que

M ≡ N ⇒ M = N

De los axiomas de compatibilidad se deduce que al sustituir terminos igualesen un contexto se obtienen terminos iguales; mas precisamente:

Lema 1.3 Sea C[·] un contexto. Si M = N entonces C[M ] = C[N ]

Demostracion: EJERCICIO 1.3. (por induccion estructural sobre C[·]) 22

2Las denominaciones β–regla, ξ–regla, . . . , son por razones historicas

1.2. Sustituciones y α–equivalencias 15

Otras λ–teorıas interesantes son:

• El λ–calculo extensional o λη–teorıa, que se obtiene al anadirle a λCel axioma:

(η–regla)λx.M x = M

• El λδ–calculo o λ–teorıa no pura, que se obtiene al anadirle al λCalgunas constantes y δ–reglas.

1.2 Sustituciones y α–equivalencias

1.2.0 Convenio de variables y concepto de sustitucion

La sustitucion de un β–redex puede plantear problemas si la λE contiene elmismo identificador en dos abstracciones.

EJEMPLO 1.3. Una β–reduccion para la λE

(λx.(λx.x) (+ 1 x)) 1

produce resultados erroneos si se sustituye la x de la λE interior (λx.x) (atencion,no la x como variable instanciable en (+ 1 x)); en efecto,

(λx.(λx.x) (+ 1 x)) 1→β

[x := 1](λx.x) [x := 1](+ 1 x)→β

(λx.1) (+ 1 1)→δ

(λx.1) 2→β

1

y en consecuencia, para la igualdad =βδ generada por ³βδ se tendrıa:

(λx.(λx.x) (+ 1 x)) 1 =βδ 1

La reduccion anterior tiene un error ya que la sustitucion [x := 1]E debe enten-derse “sustituir x por 1 en todas las ocurrencias de x como variable libre”. Asıpues tenemos la siguiente reduccion correcta:

(λx.(λx.x) (+ 1 x)) 1→β

[x := 1](λx.x) [x := 1](+ 1 x)→β

(λx.x) (+ 1 1)→δ

(λx.x) 2→β

2

♣


En general, la sustitucion [x := u]e se debe interpretar como:

“sustituir x por u en todas las apariciones libres de x en e”

EJERCICIO 1.4. Probar que

λx.(λx. + ( − x 1)) x 3) 9 =βδ 11

2EJEMPLO 1.4. Sea K ≡ λxy.x. Entonces

K M≡

(λxy.x) M→β

(λy.M)

de donde se tendrıa K M =β λy.M y en particular K y =β λy.y. Pero sabemosque podemos identificar (K ≡)λxy.x ≡ λxz.x, de donde tambien tendremos

K y≡α

(λxz.x) y→β

(λz.y)

y debe tenerse tambien K y =β λz.y; es decir:

(K y =β λz.y) ∧ (K y =β λy.y)

y por ser =β una igualdad,λz.y =β λy.y

pero observamos que esto es inconsistente si =β es sustitutiva ya que se tendra

λz.y =β λy.y⇒

(λz.y)u =β (λy.y)u⇒

y =β u

y esto es absurdo (el por que se analizara en el siguiente ejercicio). ♣EJEMPLO 1.5. Sea F ≡ λxy.y x. Entonces:

⇒ ! β–regla

F M N =β N M⇒ ! tomando M ≡ y y N ≡ x

F y x =β x y

pero tambien se tiene:


F y x≡

((λx(λy.y x)) y) x=β ! β–regla

(λy.y y) x=β ! β–regla

x x

luego debe darse:x y = x x

y de aquı puede deducirse (ver nota y ejercicio siguiente) que todos los terminosdel λC son iguales (lo que equivale a inconsistencia). ♣NOTA En una teorıa T con igualdad donde son aplicables los axiomas (siendoA y B igualdades)

` A ⇒ (B ⇒ A)` (¬B ⇒ ¬A) ⇒ ((¬B ⇒ A) ⇒ B)

A , (A ⇒ B) ` B (modus ponens)

se tiene que los dos siguientes enunciados son equivalentes:

• T es consistente (i.e., existe una igualdad M = N no demostrable)

• no existen M, N tales que T ` (M = N) y T ` ¬(M = N)

como se demuestra en [Dav89] (pp. 122–123). Luego son equivalentes

• ∀M, N ∈ Λ : λC ` (M = N)

• El λC es inconsistente.♠


x y = x x ⇒ [ ∀M,N ∈ Λ : λC ` (M = N) ]

2

EJEMPLO 1.5. (continuacion) El fallo en este ejemplo esta en el paso

(λx(λy.y x)) y =β λy.y y

ya que la variable libre y externa queda asociada de forma “magica” despues dela transformacion; esto contiene una contradiccion ya que dos terminos igualesdeben tener las mismas variables libres, pero:

φ[(λxy.y x) y] = φ[λxy.y x] ∪ φ[y] = ∅ ∪ y = y

φ[λy.y y] = φ[y y]− y = ∅


que es contradictorio. Por tanto el paso anterior es erroneo.

Por otro lado, estamos identificando los terminos α–equivalentes; en ese caso:

(λxy.y x) y =α (λxz.z x) y =β λz.z y

♣Realmente el problema esta en la definicion de la sustitucion [x := N ]M ,

pues en algunos casos para calcular [x := N ]M es obligatorio efectuar una α–conversion. Para resolver el problema podemos, al igual que en [Bar84] (p. 26),adoptar el siguiente criterio:

Convenio 1.0 (Convenio sobre variables (CV)) Si una serie de λ–terminosy/o sustituciones (como [x := N ]) aparecen juntos en cierto contexto (de-mostracion, definicion, formulacion, . . . ), entonces todas las variables instan-ciables de tales terminos se consideraran distintas de las variables libres. 4

EJEMPLO 1.4. (continuacion) Si tenemos K ≡ λxy.x, entonces en el termino(K y) debemos renombrar la variable y de K. ♣EJEMPLO 1.5. (continuacion) Si F ≡ λxy.y x y M ≡ y, al “calcular” (uoperar con) F M debemos renombrar la variable instanciable y de F (observeseque la y de M no se puede renombrar porque es libre). ♣

Con este convenio es facil definir por induccion estructural la sustitucion[x := N ]M :

Definicion 1.6 (Sustitucion) Teniendo en cuenta de una vez por todas elconvenio de variables, se define:

[x := N ]x ≡ N[x := N ]y ≡ y si x 6≡ y[x := N ](P Q) ≡ [x := N ]P [x := N ]Q[x := N ](λy.P ) ≡ λy.[x := N ]

2

Observese que:

• [x := N ]M no es una λE pero se identifica sintacticamente con alguna(como se muestra con el uso de ≡).

• El operador sustitucion se entiende asociativo a la derecha:

[x := A][y := B]M ≡ [x := A]([y := B]M)

• En la cuarta regla no es necesario anadir “si (y 6≡ x)∧ (y 6∈ φ[N ])” ya quese usa el convenio de variables y tales condiciones son implıcitas.


1.2.1 La sustitucion frente a las relaciones en Λ

Lema 1.4 (Lema de sustitucion) Las sustituciones verifican las siguientespropiedades:

(S1) (x 6≡ y ∧ x 6∈ φ[L]) ⇒ [y := L][x := N ]M ≡ [x := [y := L]N ][y := L]M

(S2) M = N ⇒ [x := E]M = [x := E]N

(S3) E = F ⇒ [x := E]M = [x := F ]M

Demostracion: (S1) Por induccion estructural sobre M :

1. M es una variable

• M ≡ x

[y := L][x := N ]M≡

[y := L][x := N ]x≡

[y := L]N≡

[x := [y := L]N ]x≡ ! x 6≡ y

[x := [y := L]N ][y := L]x

• M ≡ y, con x 6≡ y (trivial)

• M ≡ z, con z 6≡ x ∧ z 6≡ y (trivial)

2. M ≡ λz.P

[y := L][x := N ]λz.P≡ ! Por (CV), z no aparece instanciable ni en N ni en L

[y := L]λz.[x := N ]P≡ ! Por (CV), z no aparece instanciable ni en N ni en L

λz.[y := L][x := N ]P≡ ! Hipotesis de induccion

λz.[x := [y := L]N ][y := L]P≡ ! Igual razonamiento

[x := [y := L]N ][y := L]λz.P

3. M ≡ P Q (trivial)

(S2) Por induccion sobre la estructura de la derivacion M = N :


1. M = N es conclusion de la β–regla

(λy.A) B︸︷︷︸M

= [y := B]A︸︷︷︸N

[x := E]M≡

[x := E](λy.A) B≡ ! Definicion de sustitucion

(λy.[x := E]A) [x := E]B=β

[y := [x := E]B][x := E]A≡ ! Por (S1) ya que por (CV), y 6≡ x ∧ y 6∈ φ[E]

[x := E][y := B]A≡

[x := E]N

2. M = N es conclusion del axioma de compatibilidad

M ′ = N ′

Y M ′︸︷︷︸M

= Y N ′︸︷︷︸N

. . .

3. . . .

(S3) Por induccion estructural sobre M . 2

EJERCICIO 1.6. Completar la demostracion del lema de sustitucion. 2

Lema 1.5 Siendo R una relacion en Λ:

A ³R B ⇒ [x := A]M ³R [x := B]M

Demostracion: EJERCICIO 1.7. (por induccion estructural sobre M , uti-lizando la compatibilidad de ³R) 22

Lema 1.6 Siendo R una relacion en Λ:

M ³R N 6⇒ [x := A]M ³R [x := A]N

Demostracion: EJERCICIO 1.8. (busquese un contraejemplo) 22

Definicion 1.7 (Relacion sustitutiva) Una relacion R es sustitutiva si

∀M, N, A ∈ Λ : (M, N) ∈ R ⇒ ( [x := A]M , [x := A]N ) ∈ R2


Lema 1.7 Si R es sustitutiva, tambien lo son →R, ³R y =R

Demostracion: EJERCICIO 1.9. (por induccion estructural) 22

Teorema 1.0 β es sustitutiva.

Demostracion: Si (M,N) ∈ β, entonces existen terminos P , Q tales que

M ≡ (λy.P ) Q N ≡ [y := Q]P

y tenemos que probar que ( [x := A]M , [x := A]N ) ∈ β; pero

( [x := A]M , [x := A]N )≡

( [x := A](λy.P ) Q , [x := A][y := Q]P )≡ ! Definicion de sustitucion, lema de sustitucion y (CV)

( (λy.[x := A]P ) [x := A]Q , [y := [x := A]Q][x := A]P )

que es una instancia de la β–regla. 2

Corolario 1.1 Las relaciones →β, ³β y =β son sustitutivas.

Demostracion: Se concluye directamente del teorema 1.0 y del lema 1.7. 2

Teorema 1.1 En un λC puro, se tiene:

M =β N ⇔ λC ` M = N

Demostracion: (⇐) Por induccion sobre la estructura de la derivacion M = N :

1. Si M = N es conclusion de la β–regla

(λy.A) B︸︷︷︸M

= [y := B]A︸︷︷︸N

entonces es trivial, ya que M →β N

2. Si M = N es conclusion del axioma de compatibilidad

M ′ = N ′

Y M ′︸︷︷︸M

= Y N ′︸︷︷︸N

entonces

λC ` M ′ = N ′

⇒ ¡ Hipotesis de induccion

M ′ =β N ′

⇒ ¡ Lema 1.2

Y M ′ = Y N ′

≡M =β N

3. . . .


(⇒) Basta probar que

M →β N ⇒ λC ` M = NM ³β N ⇒ λC ` M = N

y por induccion sobre la estructura de la derivacion M =β N (definicion 1.5):

M =β N ⇒ λC ` M = N

2

EJERCICIO 1.10. Completar la demostracion del teorema anterior. 2

NOTACION La conclusion del teorema anterior es que la igualdad =β gen-erada por ³β y la igualdad = generada por los axiomas de la definicion 1.6 sonla misma; a partir de ahora se usara un mismo sımbolo = para ambas. ♠

1.3 Eta–conversion y extensionalidad

En el λC siempre se tiene:

(λx.M) x = M

y en general(λ~x.M) ~x = M (~x ≡ x1x2 . . . xn)

siendo[~x := N ] ≡ [xn := N ] . . . [x1 := N ]

Sin embargo, la η–regla

(η–regla)λx.M x = M

(donde el cuerpo de la funcion es M x) no es necesariamente cierta.

EJEMPLO 1.6. Consideremos la funcion:

suc ≡ λx. + 1 x

de forma que:suc y = + 1 y

y la funcion suc tiene el mismo comportamiento que la funcion parcial

+ 1

pero no pueden considerarse iguales salvo que se considere la η–regla:

(λx. + 1 x) = + 1

♣

1.3. Eta–conversion y extensionalidad 23

Tal regla es en cierta forma equivalente a la regla de extensionalidad:

(ext)M x = N x

M = Nsi x 6∈ φ[M N ]

Es decir, si M x se comporta como N x para alguna variable no libre en ambas,entonces M y N son iguales. Esta propiedad es el principio de extensional-idad.

Al anadirle al λC la regla (ext) se pueden obtener algunos axiomas de losde la definicion 1.6.

EJERCICIO 1.11. Demostrar que al anadirle al λC la regla (ext) se tiene:

∀X ∈ ΛM = N

M X = N X

2

Teorema 1.2 (Curry, 1941) λC ∪ (ext) es equivalente a λη

Demostracion:

1. λC ∪ (ext) ` λη

x 6∈ φ[M ]⇒ ! β–regla

(λx.M x) x = M x⇒ ! regla ext

λx.M x = M

que es la η–regla.

2. λη ` λC ∪ (ext)

(x 6∈ φ[M N ]) ∧ (M x = N x)⇒ ! ξ–regla

λx.M x = λx.N x⇒ ! η–regla

M = N

de donde λη ` (ext).2

EJEMPLO 1.7. Sea la funcion parcial

COND TRUE 3

Veamos que en el ληδ–calculo tal funcion es igual a

λx.3

Ello lo podemos comprobar de dos formas:


• A traves de la η–regla:

COND TRUE 3= ! η–regla

λx.COND TRUE 3 x= ! δ–regla para COND

λx.3

• A traves de la regla (ext):

TRUE= ! Reflexividad de =

3 = 3= ! β–regla

3 = (λx.3) y= ! δ–regla para COND

COND TRUE 3 y = (λx.3) y⇒ ! regla (ext)

COND TRUE 3 = λx.3♣

Chapter 2

Formas normales

2.0 El concepto de forma normal

Definicion 2.0 (R–redex) Un termino M se dice que es un R–redex si paraalgun termino N se tiene que M →R N . 2

Definicion 2.1 (R–forma normal) Un termino M se dice que esta en R–forma normal (R–FN) si no contiene ningun subtermino que sea un R–redex.Un termino N se dice que es una R–FN de otro termino M (equivale a decirque M tiene a N como R–forma normal) si N esta en R–FN y M =R N . 2

Lema 2.0 Siendo M un termino que esta en R–FN, entonces:

(1) no existe un termino N tal que M →R N

(2) M ³R N ⇒ M ≡ N

donde →R es el cierre compatible y ³R el reflexivo.

Demostracion:

(1) Se procedera por reduccion al absurdo: supongamos que estando M enR–FN, se tiene que M →R N ; entonces por el lema 1.1 existirıan P , Q yun contexto C[·] tales que

(M ≡ C[P ]) ∧ (N ≡ C[Q]) ∧ (P, Q) ∈ Rcon lo cual el subtermino P serıa un R–redex (ya que (P,Q) ∈ R ⇒P →R Q) y M no estarıa en R–FN.

(2) Razonamos por induccion sobre la derivacion M ³R N (ver definicion1.4, pagina 13):

25

26 2. Formas normales

– M ³R N no puede (por (1)) haber sido obtenida de

M →R N

M ³R N

– Si M ³R N ha sido obtenida de

M ³R M ≡ N

entonces M ≡ N

– Si M ³R N ha sido obtenida de

M ³R Q Q ³R N

M ³R N

entonces por hipotesis de induccion se tendra (M ≡ Q) ∧ (Q ≡ N),de donde M ≡ N

2

EJERCICIO 2.0. Probar con un contraejemplo que

(∀N :: M ³R N ⇒ M ≡ N) 6⇒ M esta en R–FN

i.e., que la propiedad (2) del lema 2.0 no caracteriza a las formas normales. 2

Las formas normales se corresponden con la idea de “fin de computo” en loslenguajes funcionales. Ası pues, el evaluador en un lenguaje funcional deberıaobedecer al esquema:

mientras existan redexes reducir uno de ellos

No todas las expresiones tienen forma normal; es decir, existen formas nonormales que no pueden reducirse a forma normal, como muestra el siguiente

EJEMPLO 2.0. Si D ≡ λy.y y, considerese la expresion Ω ≡ D D:

Ω ≡ (λy.y y) (λy.y y)

que no esta en forma normal (ella misma es un β–redex) y se reduce directamentesegun la β–regla (renombramos la variable de la funcion para mas claridad):

Ω≡

(λz.z z) (λy.y y)=β

[z := λy.y y](z z)≡

(λy.y y) (λy.y y)≡

Ω

Por tanto, el “computo” de la expresion Ω “no termina” y Ω no tiene unaforma normal. ♣

2.1. Confluencia 27

Es interesante observar que no podemos identificar los terminos sin FN yaque ello introduce inconsistencias (ver ejercicio 2.6). Por tanto, identificar todoslos terminos que no terminan traera problemas.

2.1 Confluencia

Interesa saber si las formas normales son unicas (salvo α–equivalencias).Esto sera consecuencia de la propiedad de confluencia.

Definicion 2.2 (Propiedad del diamante) Sea → una relacion en Λ; sedice que → verifica la propiedad del diamante (lo cual se notara mediante→ |= 3) si se tiene

∀M, P,Q : (M → P ) ∧ (M → Q) : ∃R :: (P → R) ∧ (Q → R)

o graficamente:

M

¡¡

¡ª

@@

@RP Qp p p p p p p p p p p p pR

pppppppppppppªR

2

EJERCICIO 2.1. Probar que β 6|= 3 2

Definicion 2.3 (Propiedad de confluencia o de Church–Rosser) Una relacionR se dice confluente o que tiene la propiedad de confluencia o tambien quetiene la propiedad de Church–Rosser (lo cual se notara mediante R ∈ CR)si la relacion inducida ³R verifica la propiedad del diamante:

R ∈ CR ⇔R ³ |= 3

2

Lema 2.1 Si ½ |= 3 entonces ½∗ |= 3


Definicion 2.4 (Propiedad debil de Church–Rosser) Una relacion R sedice que tiene la propiedad debil de Church–Rosser (lo cual se notaramediante R |=d 3) si se tiene

∀M,P, Q : (M →R P ) ∧ (M →R Q) : ∃Z :: (P ³R Z) ∧ (Q ³R Z)

2


EJERCICIO 2.3. Probar que β |=d 3 2

Definicion 2.5 (Propiedad fuertemente normalizante) Una relacion Rse dice fuertemente normalizante (lo cual se notara mediante R ∈ SN) sitoda reduccion de la forma M ³R M ′ termina, es decir

∀M , 6 ∃Mnn≥0 (M0 ≡ M) :: Mi →R Mi+1

2

Teorema 2.0 (Newman) Si R ∈ SN y R |=d 3, entonces R ∈ CR


Teorema 2.1 (Church–Rosser) Sea R ∈ CR; entonces:

M =R N ⇒ ∃Z :: (M ³R Z) ∧ (N ³R Z)

Demostracion: por induccion sobre la estructura de la derivacion M =R N(definicion 1.5):

• M =R N es consecuencia de

M ³R N

M =R N

y tomamos Z ≡ N .


N =R M

M =R N

y por hipotesis de induccion:

∃Z :: (N ³R Z) ∧ (M ³R Z)


M =R L L =R N

M =R N

y, por hipotesis de induccion, existen terminos P y Q verificando

M L N

@@

@R

¡¡

¡ª

@@

@R

¡¡

¡ªP Q

2.1. Confluencia 29

y por la propiedad de confluencia tenemos que existe R verificando:

M L N

@@

@R

¡¡

¡ª

@@

@R

¡¡

¡ªP Qp p p p p p p p p p p p pR

pppppppppppppªR

y ahora basta aplicar la transitividad de ³R.2

Corolario 2.0 Sea R ∈ CR; entonces:

(1) si N es una R–FN de M , entonces M ³R N

(2) si un termino tiene forma normal, dicha forma normal es unica (salvoα–equivalencias)

Demostracion:

(1) Si N es una R–FN de M , entonces por el teorema existe Z tal que

(M ³R Z) ∧ (N ³R Z)

y por estar N en R–FN se tiene (por el lema 2.0) que Z ≡ N ; luegoM ³R N

(2) Si N1 y N2 son dos R–FN de M entonces N1 =R N2 (=R M), y por elteorema existe Z tal que

(N1 ³R Z) ∧ (N2 ³R Z)

y de aquı, por el lema 2.0, N1 ≡ Z ≡ N2.2

Teorema 2.2 Toda forma normal puede expresarse como:

λx1x2 . . . xn.x M1 . . . Mm n,m ≥ 0

siendo M1, . . . , Mm formas normales.

Demostracion: puede verse en [Dav89] (pag. 164) y en [Bar84] (pag. 176(8.3.18)). 2


Corolario 2.1 (Conjunto FN de formas normales) El conjunto FN de for-mas normales puede definirse en forma inductiva de la manera siguiente:

(1) x ∈ FN(2) si M1, . . . , Mm ∈ FN entonces x M1 . . . Mm ∈ FN(3) si M ∈ FN entonces λx.M ∈ FN

Es decir, FN es el menor conjunto verificando (1)–(3).

Demostracion: siendo C el menor subconjunto de Λ verificando (1)–(3), hay queprobar:

• C ⊂ FN : es trivial que FN verifica (1)–(3)

• FN ⊂ C: basta probar (por induccion sobre A):

A ∈ FN ⇒ A ∈ C

– A ≡ x, trivial

– A ≡ λx1x2 . . . xn.x M1 . . . Mn, con M1, . . . , Mm ∈ FN

A ≡ λx1x2 . . . xn.x M1 . . . Mn

⇒ ! h.i., A′ ≡ x M1 . . . Mn, props. (2) y (1)

A ≡ λx1x2 . . . xn.A′, con A′ ∈ C⇒ ! prop. (3) n veces

A ∈ C2

2.2 Los teoremas de Church–Rosser

El teorema 2.1 necesita que la relacion en cuestion cumpla la propiedad CR. Enesta seccion se consideran los teoremas de Church–Rosser, los cuales afirmanque tanto β como βη son CR y por tanto para dichas relaciones es aplicable elteorema 2.1 y el corolario 2.0.

Las demostraciones originales (1936) eran muy complicadas y muchos teore-mas y generalizaciones se han publicado en los ultimos 50 anos. Aquı daremosla demostracion expuesta en [Bar84] (esencialmente la de P. Martin Lof y W.Tait), y para βη ∈ CR daremos un esbozo usando la tecnica de Hindley–Rosen.

Teorema 2.3 (Church–Rosser, 1936) β ∈ CR

Demostracion: hay que probar que ³β |= 3; para ello, supongamos que existeuna relacion ³ (no confundir con ³β) que verifica:

2.2. Los teoremas de Church–Rosser 31

(a) =→β ⊆³⊆³β

(e) ³ |= 3

Entonces, por (e) y por el lema 2.1

³∗ |= 3

Por (a),( =→β)

∗ ⊆ ³∗ ⊆³β

y ya que ( =→β)∗ ≡³β tendremos ³∗ =³β . Luego todo consiste en encontrartal relacion ³. Esto se vera en el siguiente lema. 2

Lema 2.2 Sea la relacion ³ definida en forma inductiva como la mınimarelacion verificando:

(1) M ³ M

(2) (M1 ³ M2) ∧ (N1 ³ N2) ⇒

λx.M1 ³ λx.M2 ,M1 N1 ³ M2 N2 ,(λx.M1) N1 ³ [x := N2]M2

Entonces:

(a) =→β ⊆³⊆³β

(b) (M1 ³ M2) ∧ (N1 ³ N2) ⇒ [x := N1]M1 ³ [x := N2]M2

(c) λx.M ³ N ⇒ ∃M ′ :: (N ≡ λx.M ′) ∧ (M ³ M ′)

(d) M1 N1 ³ L ⇒

∃M2, N2 ::

L ≡ M2 N2 ,M1 ³ M2 ,N1 ³ N2

∨

∃P1, P2, N2 ::

M1 ≡ λx.P1 ,L ≡ [x := N2]P2 ,P1 ³ P2 ,N1 ³ N2

(e) ³ |= 3

Demostracion:

(a) Para demostrar que =→β ⊆³ hay que probar M=→βN ⇒ M ³ N (por

induccion sobre la derivacion M=→βN)


– Si M=→βN es consecuencia de

M ³β M

con M ≡ N , entonces M ³ M por (1)

– Si M=→βN es consecuencia de la β–regla, entonces

M ≡ (λx.E) u , N ≡ [x := u]E

y bastara probar(λx.E) u ³ [x := u]E

que se deduce de (2) tomando M1 ≡ M2 ≡ E y N1 ≡ N2 ≡ u

mientras que para demostrar ³⊆³β basta probar que ³β verifica (1)–(2)del lema, lo cual es trivial por ser sustitutiva.

(b) Por induccion estructural sobre derivaciones del tipo M1 ³ M2.

(c) Por induccion estructural sobre derivaciones del tipo M ³ M ′.

(d) Por induccion estructural sobre derivaciones del tipo M1 ³ M2.

(e) Es suficiente probar que

∀M, P :: M ³ P : (∀Q :: M ³ Q ⇒ (∃R :: (P ³ R) ∧ (Q ³ R) ) )

y ello por induccion estructural sobre la derivacion M ³ P (para masdetalles, vease [Bar84] (pags. 60–62)).

2

Corolario 2.2 El λ–calculo es consistente

Demostracion: procediendo por reduccion al absurdo, supongamos que sea in-consistente; entonces para cualesquiera λ–expresiones M y N se tiene queM = N es un teorema; en particular, siendo M y N dos formas normalestendremos

λC ` M = N

2.2. Los teoremas de Church–Rosser 33

pero ya queλC ` A = B ⇔ A =β B

entonces tendremos M =β N , siendo M y N dos formas normales. Pero, porel corolario 2.0.(2), tendremos M ≡ N , y ahora para llegar a un absurdo bastatomar dos formas normales no α–equivalentes. 2

Al extender el λC con ciertos axiomas (indeseables) se pueden introducirinconsistencias, como se muestra en los siguientes ejercicios.

EJERCICIO 2.5. Probar que λC ∪ (K = S) es inconsistente, siendo

K ≡ λxy.x S ≡ λxyz.x z (y z)

2

EJERCICIO 2.6. Probar que λC ∪ F es inconsistente, siendo F el conjuntode axiomas

F = M = N | M,N ∈ Λ :: M, N no tienen FN

2

EJERCICIO 2.7. Demostrar que la aplicacion de λ–expresiones no es aso-ciativa. 2

EJERCICIO 2.8. Probar que λC ∪ (K = (K I)) es inconsistente, siendo

K ≡ λxy.x I ≡ λx.x

2

Teorema 2.4 η ∈ CR

Demostracion: como se tiene que ³η= ( =→η)∗, bastara con probar que

=→η |= 3

para lo cual hay que demostrar

∀M, P :: M=→ηP : (∀Q :: M

=→ηQ ⇒ (∃R :: (P =→ηR) ∧ (Q =→ηR) ) )

por induccion estructural sobre la derivacion M=→ηP (para mas detalles, vease

[Bar84] (pag. 65)). 2


Lema 2.3 (Hindley–Rosen)

(1) Si dos relaciones ½1 y ½2 verifican 3

(½1 |= 3) ∧ (½2 |= 3)

y conmutan

A½1- B

½2

?

pppppppp?½2

C½1p p p p p p p p- D

es decir

∀A,B, C :: (A½1B) ∧ (A½2C) ⇒ ∃D :: (C½1D) ∧ (B½2D)

entonces(½1 ∪½2)

∗ |= 3

(2) Sean dos relaciones σ y γ tales que σ ∈ CR y γ ∈ CR; si las relacionesinducidas ³σ y ³γ son commutativas en el sentido de (1), entonces σγ ∈CR

Demostracion:

(1) Para probarlo basta considerar un diagrama como el siguiente:

• ½1- • ½2- • ½2- •½2

?

pppppppp?½2

pppppppp?½2

pppppppp?½2

• ½1p p p p p p p p- • ½2p p p p p p p p- • ½2p p p p p p p p- •½1

?

pppppppp?½1

pppppppp?½1

pppppppp?½1

• ½1p p p p p p p p- • ½2p p p p p p p p- • ½2p p p p p p p p- •

(2) Se deduce directamente aplicando (1) ya que, por el corolario 1.0,

(³σ ∪³γ)∗ = ³σγ2

Teorema 2.5 (Church–Rosser, 1936) βη ∈ CR

Demostracion: se basa en aplicar el lema de Hindley–Rosen a β y η (luegopreviamente habrıa que demostrar que ³β y ³η son commutativas en el sentidode (1)). 2

Corolario 2.3 El λη–calculo es consistente


2.3. Formas normales por la cabeza 35

2.3 Formas normales por la cabeza

2.3.0 Ordenes de reduccion

Hay ocasiones en las cuales la eleccion del siguiente redex a reducir es deter-minante para la finalizacion del computo.

EJEMPLO 2.1. Se considera la λE

(λx.y) Ω

siendoΩ ≡ (λx.x x) (λx.x x)

Esta λE tiene dos redexes: uno interior (que es Ω) y otro exterior (que es todala expresion); si reducimos el exterior se obtiene y, mientras que si reducimos elinterior volvemos a obtener la misma expresion. Por consiguiente, en este casoel orden de reduccion es importante. ♣

El orden de reduccion determina la eleccion del redex a reducir; paraidentificar cual sera el redex elegido se usara la siguiente nomenclatura:

• El redex de mas a la izquierda es aquel cuya λ (o cuya primitiva, si esun δ–redex) aparece textualmente a la izquierda de cualquier otro redexde la expresion.

• Un redex externo es aquel que no esta contenido en otro redex.

• Un redex interno es aquel que no contiene otro redex.

EJEMPLO 2.2. Clasificando los redexes que aparecen en las siguientes λE:

• En la λE

(λx.x) a︸︷︷︸interno

(

interno︷︸︸︷(λx.x) b)

se han marcado dos redexes internos; el marcado por abajo es ademas elredex de mas a la izquierda.

• En la λE

(λy.(

interno︷︸︸︷(λz.z) x) y) a︸︷︷︸externo

se han marcado dos redexes: el marcado por arriba es interno, y el marcadopor abajo ademas de externo es el redex de mas a la izquierda.


♣

Se distinguen dos importantes ordenes de reduccion:

• El orden normal o estandar, que notaremos pors³, donde se reduce el

redex externo de mas a la izquierda.

• El orden aplicativo, que notaremos pora³, donde se reduce el redex

interno de mas a la izquierda.

EJEMPLO 2.1. (continuacion) En la λ–expresion:

(λx.y) Ω

el seleccionado para la reduccion estandar es la propia expresion, y en el ordenaplicativo se seleccionara el Ω. Segun el teorema de Church–Rosser (para el λCo para el ληC) si una expresion tiene FN esta es unica salvo α–equivalencias;por tanto la forma normal en este caso es y y como se obtiene por la reduccionestandar, escribiremos:

(λx.y) Ωs³ y

Por otro lado, la reduccion aplicativa produce una secuencia infinita de redexes:

(λx.y) Ωa³ (λx.y) Ω

a³ . . .

y el computo no terminarıa. ♣

2.3.1 El teorema de estandarizacion

Como el teorema de Church–Rosser afirma que si una expresion tiene FNesta es unica salvo α–equivalencias, y dado que disponemos de diversos ordenesde reduccion, cabe preguntarse si habra un orden de reduccion que siempre noslleve a dicha FN.

EJEMPLO 2.3. Consideremos la siguiente reduccion no estandar (sub-rayamos el redex elegido):

λa.(λb.(λc.c) b b) d

→λa.(λb.b b) d

→λa.d d

con lo cual,λa.(λb.(λc.c) b b) d ³ λa.d d

pero tambien observamos que siguiendo el orden normal o estandar

λa.(λb.(λc.c) b b) ds³ λa.d d


♣Generalizando el resultado del ejemplo anterior se tiene el denominado teo-

rema de estandarizacion:

Si M ³ N , entonces tambien Ms³ N


Aunque no veremos la demostracion de este teorema si daremos un esbozo deesta. Para ello son necesarios los conceptos de redex de cabecera y de reduccionpor la cabeza (head reduction); se usara la siguiente nomenclatura:

• Un termino de la forma M N se denomina un termino aplicacion.

• Un termino de la forma λx.M se denomina un termino abstraccion.

Lema 2.4

(a) Cada termino es, o una variable, o un termino aplicacion o un terminoabstraccion.

(b) Cada termino aplicacion M es de la forma

M ≡ N1 N2 . . . Nn (n ≥ 2) ∧ (N1 no es una aplicacion)

(c) Cada termino abstraccion M es de la forma

M ≡ λx1x2 . . . xn.N (n ≥ 1) ∧ (N no es una abstraccion)

(d) Cada termino M :

– o bien es una forma normal por la cabeza (FNC):

M ≡ λx1x2 . . . xn.x M1 . . . Mm (n ≥ 0) ∧ (m ≥ 0)

– o bien es β–reducible por la cabeza:

M ≡ λx1x2 . . . xn.(λx.M0) M1 . . . Mm (n ≥ 0) ∧ (m ≥ 1)

donde al redex (λx.M0) M1 se le llama redex de cabecera.

Demostracion: por induccion sobre la estructura de M . 2

Definicion 2.6 Un termino M se dice que admite FNC si existe un N enFNC tal que M = N . 2

EJEMPLO 2.4. El termino

Ω ≡ (λx.x x) (λx.x x)

es β–reducible por la cabeza (segunda opcion con n = 0 y m = 1) y no admiteuna FNC (su primer elemento es un redex). ♣NOTACION Si ∆ ∈ sub[M ] es el redex de cabecera de M , y N resulta de Mal contraer ∆, escribiremos:

(M c→ N) o bien M∆→ N


para denotar la reduccion en un paso del redex de cabecera, y denotaremos con

c³ o biencs→

el cierre reflexivo y transitivo dec→. Si los redexes seleccionados son interiores

usaremosi→ para la reduccion en un paso, y:

i³ o bienis→

para su cierre reflexivo y transitivo. ♠

Lema 2.5

(a) Cualquier reduccion Mi→ M ′ c³ N puede descomponerse en la forma:

M ′

¡¡

¡µi

@@

@R

cs

M Np p p p p p p p p p p p pRcs p p p p p

p p p p pp p pµ

is

N ′

Mc³ N ′ i³ N

(b) Cualquier reduccion M ³ N puede descomponerse en la forma:

M N2

² ¯?

³

Nn−1 Np p p p p p p p p p p p pRcs p p p p p

p p p p pp p pµ

is

p p p p p p p p p p p p pRcs

. . .

p p p p pp p p p p

p p pµis

p p p p p p p p p p p p pRcs p p p p p

p p p p pp p pµ

is

N1 Nn

Mc³ N1

i³ N2c³ · · · i³ Nn−1

c³ Nni³ N

(c) Cualquier reduccion M ³ N puede descomponerse en la forma:

M ³ - Np p p p p p p p p p p p pRcs p p p p p

p p p p pp p pµ

is

Z

Mc³ Z

i³ N


Demostracion:

(a) Puede encontrarse en [Bar91] (pag. 298).

(b) Inmediato por (a).

(c) Inmediato por (b) y (a).2

Teorema 2.6 (Teorema de estandarizacion (Curry–Feys, 1958))

Si M ³ N , entonces tambien Ms³ N

Demostracion: por induccion sobre N utilizando (c) del lema anterior:

M ³ N1 N2 ≡ N ; M ³ λx.N ′ ≡ N

2A la β–reduccion reiterada del redex de cabecera se le denomina reduccion

por la cabeza o reduccion de cabecera. Observese que:

• La reduccion por la cabeza determina de forma unica una secuencia determinos (tal secuencia puede terminar o puede no terminar).

• En la reduccion estandar esta incluida, como previa, la reduccion decabecera, pues utilizando (c) del lema anterior y el teorema de estandarizacion:

Mc³ Z

i³︸︷︷︸red. estandar

N

Como corolario del teorema de estandarizacion tenemos:

Corolario 2.4 M tiene FNC si y solo si su reduccion por la cabeza termina

Demostracion:

(⇐) Trivial.

(⇒) Sea λ~x.y ~M una forma normal por la cabeza de M , donde ~x y ~M sonsecuencias. Por el teorema de Church–Rosser

∃Z :: M ³ Z, Z ³ λ~x.y ~M

pero entonces Z ≡ λ~x.y ~N , donde Mi ³ Ni, con lo cual por el teoremade estandarizacion

Ms³ λ~x.y ~N

y es facil construir a partir de esta la reduccion por la cabeza (que termi-narıa).

2


Existen diferencias importantes entre la reduccion por la cabeza (que acabaen una FNC) y la reduccion estandar o normal (que acaba en una FN):

• Un termino puede estar en FNC y no estar en FN

• Un termino puede no tener ni FNC ni FN; existe una caracterizacion delos terminos con FNC que es la resolubilidad, como veremos mas tarde(teorema de Wadsworth).

• Un termino puede tener varias FNC; la reduccion por la cabeza (que ter-mina si admite al menos una FNC) proporciona la denominada FNCcanonica

EJEMPLO 2.5. Siendo I ≡ λz.z, se tiene que:

• La λEλx.x (I b)

esta en FNC (pues no existe redex de cabecera); sin embargo no es unaFN y la reduccion normal lo reducirıa a λx.x b

• La λE(λx.x x) (λx.x x)

no admite FNC ni tampoco FN (ya que toda FN es una FNC)

• La λEλx.I x (I I)

admite como FNC tanto λx.x (I I) como λx.x I

• La λE(λx.x x) I x (I a)

terminarıa en x (I a) si utilizamos reduccion por la cabeza, pero la re-duccion estandar continuarıa hasta obtener la expresion x a:

(λx.x x) I x (I a)c³ x (I a)︸︷︷︸

fin computo si FNC

s³ x a

Ademas, observese que la λE original tambien admite como FNC la ex-presion x a, pues

(λx.x x) I x (I a) ³ I I x a → I x a → x a

pero la FNC canonica (i.e., la obtenida por reduccion por la cabeza) es laexpresion x (I a)

♣


Teorema 2.7

(0) Mc→ M ′ ⇒ [z := N ]M c→ [z := N ]M ′

(1) λx.M tiene una FNC ⇒ M tiene una FNC

(2) M N tiene una FNC ⇒ M tiene una FNC

(3) [x := N ]M tiene una FNC ⇒ M tiene una FNC


2.4 Formas debil–normales

EJEMPLO 2.6. Sea la expresion Haskell

(3+2) : cola unos where unos = 1 : unos

Dicha expresion no esta en forma normal y su evaluacion a forma normal notermina. ♣

Es interesante en algunos casos no completar la evaluacion para evitar loscasos de no terminacion; las formas intermedias se llaman formas debil–normales.

EJEMPLO 2.7. Sean las expresiones no normales

Ω ≡ (λx.x x) (λx.x x)Θ ≡ λx.ΩΣ ≡ (λx.Ω) uΨ ≡ λx. + x (+ 2 3)

en el caso de Ψ es evidente que podrıa considerarse el proceso de evaluacion delcuerpo de la funcion como una tecnica de optimizacion, y tendremos

Ψ → λx. + x 5

que es una forma normal. Si utilizamos el mismo criterio con Θ vemos que

Θ → λx.Ω = Θ → . . .

y el proceso de optimizacion produce la no terminacion; usando como criterio:

evaluar solo los redexes de cabecera que existan o se produzcan

tenemos que la evaluacion de Θ termina (de hecho deja la expresion anteriorcomo esta ya que no existe redex de cabecera); se dice que Θ es una debilforma normal por la cabeza (DFNC o tambien WHNF (weak–head normalform)); sin embargo, tal evaluacion debil por la cabeza no funciona con Σ, pues

Σ ≡ (λx.Ω) u → Ω → Ω → . . .

y se dira que Σ no admite una DFNC. ♣

2.4. Formas debil–normales 43

Las DFNC fueron introducidas por Wadsworth en 1976 y permiten, entreotras cosas, distinguir ciertos computos que no terminan.

EJEMPLO 2.8. Sea ahora la λE:

λx.(λy.λx. + x y) x

cuyo unico redex aparece subrayado. Al aplicar una β–reduccion hay que tenercuidado ya que al sustituir la x que aparece en negrita se obtiene un resultadoerroneo. ♣

El problema visto anteriormente se conoce como problema de duplicidaddel indentificador (name–capture problem); para resolverlo es necesario unaα–conversion, pero ¿puede evitarse dicha α–conversion en estos casos? Unaforma de resolver esto es con el concepto de DFNC donde la terminacion delproceso de reduccion se produce al alcanzar una DFNC.

Los terminos sin redexes externos son de la forma

λx.E o bien x E1 E2 . . . En (n ≥ 0)

Si incluimos constantes y δ–reglas, las funciones parciales tambien son DFNCya que no tienen redexes externos (ni β–redexes ni δ–redexes).

EJEMPLO 2.9. Ası, son DFNC los terminos:

λx.Ω x y

pero Ω 6∈ DFNC. Ademasλx. ∗ 3 x

esta en DFNC, y si admitimos

λx. ∗ 3 x = ∗ 3

(que es una igualdad extensional) tenemos que ∗ 3 es una DFNC. ♣

Definicion 2.7 (Debil–forma normal por la cabeza)

(1) Toda constante es una DFNC

(2) λx.E es una DFNC

(3) f E1 E2 . . . En es una DFNC si f es una constante o una funcion dearidad k > n ≥ 0

2

La diferencia esencial entre FNC y DFNC es que en la segunda no se evaluanlas λ–abstracciones internas.

EJEMPLO 2.10. En la figura siguiente se clasifican cinco λ–expresiones:


donde por ejemplo, λx.I M no esta en FNC pero si en DFNC, ya que no tieneredexes externos. ♣

Una expresion que consista en una sola variable es, segun la definicion, unaDFNC; sin embargo, el resultado de un programa funcional no debe contenervariables libres (p.e., + x 1) y podemos limitarnos a DFNC cerradas.

Una ventaja (segun [FH88]) de la reduccion a una DFNC es que se evita laβ–reduccion en presencia de variables libres.

EJEMPLO 2.8. (continuacion) La expresion:

λx.(λy.λx. + x y) x

esta en DFNC y no es necesario reducir el redex interno: solamente cuando talexpresion es aplicada a un argumento debe reducirse por orden normal (el redexexterno de mas a la izquierda) para obtener una DFNC; ası, la λE:

(λx.(λy.λx. + x y) x) 4

no esta en DFNC y se reduce a una DFNC por orden normal:

(λx.(λy.λx. + x y) x) 4 → (λy.λx. + x y) 4 → λx. + x 4

♣Observese que el problema de duplicidad del identificador ha desaparecido;

esto es ası porque solamente se reduce el redex externo, que no tiene variableslibres. La diferencia entre FNC y DFNC es solamente significativa cuando elresultado es una abstraccion; el problema de duplicidad del identificador puedeocurrir al reducir una expresion a FNC.

Veremos despues que al identificar todos los terminos sin FNC se obtieneuna teorıa consistente; luego si identificamos

Ω = λx.Ω

(es decir, si identificamos un termino en DFNC con uno que no admite DFNC)no se introducen inconsistencias.

Los terminos en DFNC son los resultados en la evaluacion perezosa; ası, elcomputo perezoso de λx.Ω termina mientras que el de Ω no termina; por tanto,en un λC perezoso (por ejemplo, el propuesto en [Abr90]), como modelo de loslenguajes funcionales perezosos, no es posible tal identificacion.

Chapter 3

Teorıa de combinadores

3.0 Combinadores

3.0.0 Los combinadores estandares

Vimos que al colocar una expresion M en el “hueco” [·] de un contexto C[·]se obtiene una nueva λE denotada con C[M ] y ciertas variables libres de Mpueden quedar asociadas en C[M ]; por ejemplo, para la expresion M ≡ λx.yx,con variable libre y y el contexto C[·] ≡ (λxy.[·])EF , tenemos:

C[λx.y x]≡

((λxy.(λx.y x)) E) F→β ! la x interior esta asociada

(λy.(λx.y x)) F→β

λx.F x

Una λE sin variables libres es independiente de su contexto; tales expresiones sellaman combinadores; la razon de tal denominacion es que a partir de ellas y porcombinacion se pueden obtener funciones de orden superior. Los combinadores,descubiertos en los anos 1920 por Schoenfinkel, fueron utilizados para eliminarlas variables de la logica matematica; fueron redescubiertos por Curry, el cualdesarrollo toda una teorıa basado en estos. Existen dos combinadores especialesS y K, definidos (salvo α–equiv.) en la forma:

S = λxyz.x z (y z)K = λxy.x

que se llaman combinadores estandares. Las propiedades fundamentales de estoscombinadores se resumen en el siguiente lema, siendo I ≡ λx.x:

45

46 3. Teorıa de combinadores

Lema 3.0 Se tienen las siguientes igualdades, ∀M, N, L ∈ Λ

(i) I M = M

(ii) K M N = M

(iii) S M N L = M L (N L)

(iv) S K K = I


3.0.1 Potencias y potencias de K

Definicion 3.0 Se definen:

M N ≡ λx.M (N x)M0 ≡ IMk+1 ≡ M Mk

2

En el ληC se tiene M1 = M :

M≡

M I≡

λx.M (I x)=β

λx.M x=η

M

NOTACION La notacion para las potencias se complica ligeramente; elloes debido a la no asociatividad (ver ejercicio 2.7); por ello conviene tambienutilizar una notacion para las expresiones de la forma

A

n︷︸︸︷B . . . B

Barendregt utiliza la notacion AB∼n; es decir:

AB∼0 ≡ AAB∼n+1 ≡ (AB∼n)B ≡ AB∼nB

por lo que:n︷︸︸︷

B . . . B = IB∼n 6= Bn

♠

3.1. La teorıa de combinadores 47

Veamos en particular las potencias del combinador K. Tenemos:

K2

≡K K

=λx.K (K x)

=λx.K (λz.x)

=λx.(λuy.u) (λz.x)

=λxyz.x

y de la misma forma tenemos:

K = λx0x1 . . . xn.x0

es decir, Kn es una funcion de n + 1 argumentos que aplicado a ellos toma elprimero. Entonces tenemos:


Kn A M1 . . . Mn = A

2

3.1 La teorıa de combinadores

La razon de llamar combinadores estandares a los combinadores K y S es quetoda λE cerrada (sin variables) puede traducirse a una expresion combinatoriaestandar (es decir, el conjunto K, I genera el conjunto Λ0); las expresionescombinatorias son las expresiones que pueden escribirse al eliminar las abstrac-ciones de la sintaxis del λC; es decir, al eliminar las construcciones λ− .−; unaexpresion combinatoria es estandar si utiliza solamente los combinadores S yK. El proceso de conversion de una abstraccion a una expresion combinatoriaestandar produce una expresion extraordinariamente grande (incluso para λEsimples); se introducen entonces nuevas reglas de reduccion de combinadorespara simplificarlas (algoritmos de Curry y Turner) ([Rev88] pp. 51–57, [Pey87]pp. 265–274). Estas expresiones combinatorias fueron utilizadas para imple-mentar el lenguaje Miranda y maquinas de reduccion (la SKIM y la NORMA(Normal Order Reduction Machine)).

3.1.0 Fundamentos de LCLa teorıa LC (Combinatory Logic) es una teorıa con igualdad formulada con

el alfabeto:K, S dos constantesx, y, . . . variables=, (, )


donde utilizamos el mismo identificador para las constantes K y S de la teorıaLC y del λC ya que no debe haber confusion.

El conjunto C de LC–terminos se define en forma inductiva:

x, y, · · · ∈ CK, S ∈ CP, Q ∈ C ⇒ (P Q) ∈ C

Las formulas son:P = Q con P, Q ∈ C

El conjunto de variables libres de P , φ[P ], es simplemente el conjunto de vari-ables de P (recuerdese que no existen abstracciones). Para “ahorrar” parentesisconvenimos tambien la regla de asociacion por la izquierda. Observese que sidenotamos con C0 el conjunto de terminos cerrados (sin variables) entonces

K,S es un generador de C0

Definicion 3.1 La teorıa LC viene dada por los axiomas:

1. = es una relacion de equivalencia

2. = es compatible, es decir:

M = N ⇒ (M P = N P ) ∧ (P M = P N)

3. K P Q = P

4. S P Q R = P R (Q R)2

En lo que sigue, las igualdades se entienden en LC y las constantes K y S denotanLC–terminos constantes. Conviene introducir un nuevo sımbolo I definido en laforma:

I ≡ S K K

Entonces, por los axiomas 3 y 4 tenemos:

I P = P

Con objeto de simplificar ciertos LC–terminos conviene introducir una no-tacion parecida a las abstracciones del λC. Esto permitira ver una relacion entrelas teorıas λC y LC. Se define

µx.P

por induccion estructural sobre P :

µx.x ≡ I [0]µx.P ≡ K P si x 6∈ φ[P ] [1]µx.P Q ≡ S (µx.P ) (µx.Q) [2]


y de forma analoga al λC, se define:

µx1x2 . . . xn.P = µx1.(µx2. . . . (µxn.P ) . . . )

Asıµxy.y x ≡ S (K (S I)) (S (K K) I)

En efecto:

µxy.y x≡

µx.µy.y x≡ ! [2] para µy.y x

µx.S (µy.y) (µy.x)≡ ! [1] para µy.y, [2] para µy.x

µx.S I (K x)≡ ! [2]

S (µx.S I) (µx.K x)≡ ! [1], [2]

S (K (S I)) (S (µx.K) (µx.x))≡ ! [1], [0]

S (K (S I)) (S (K K) I)

EJERCICIO 3.2. Demostrar por induccion estructural las propiedades:

(1) φ[µx.P ] = φ[P ]− x

(2) (µx.P ) x = P

(3) (µx.P ) Q ≡ [x := Q]P

(4) si y 6∈ φ[Q], y 6≡ x, [y := Q](µx.P ) ≡ µx.[x := Q]P

(5) si y 6∈ φ[P ], µx.P ≡ µy.[x := y]P2

Si se incluye la regla de extensionalidad

(P x = Q x) ∧ (x 6∈ φ[P Q]) ⇒ P = Q ext

entonces se puede aplicar la ξ–regla

P = Q ⇒ µx.P = µx.Q ξ–regla

La relacion binaria

w = (K M N, M), (S M N L, M L (N L)) | M,N,L ∈ C induce (por cierre reflexivo transitivo) conceptos de reduccion →w y =w deforma que se tiene M =w N ⇔ LC ` M = N , ası como tambien es cierto elteorema de Church–Rosser, y LC es consistente.


NOTA Hay muchas formas de definir el concepto de abstracion en LC; porejemplo podemos considerar un concepto de abstraccion νx.M definido al igualque µx.M , pero cambiando la regla [1]:

νx.x ≡ I [0]νx.P ≡ K P si P es una variable ( 6≡ x), K o S [1]νx.P Q ≡ S (νx.P ) (νx.Q) [2]

NOTACION En otros textos la aplicacion νx.M en LC se suele escribir [x]M(p. 276 de [FH88], o p. 52 de [Rev88]) ♠En consecuencia:

νy.z x ≡ S (K z) (K x)µy.z x ≡ K (z x)

Si el calculo es extensional las dos definiciones coinciden (y esto es ası porquela ξ–regla serıa aplicable); ası, por ejemplo tendremos:

S (K z) (K x) u = K (z x) u=

((K z) u) ((K x) u) = z x=

z x = z x=

Cierto

de dondeS (K z) (K x) = K (z x)

♠

3.1.1 Relacion entre λ–terminos y terminos combinatorios

Se puede establecer una correspondencia entre las teorıas LC y λC (paramas detalles ver §7.3 en [Bar84]) estableciendo dos aplicaciones:

(·)λ : C → Λ(·)LC : Λ → C

definidas en forma inductiva (denotamos (P )λ ≡ Pλ, (P )LC ≡ PLC):

xλ ≡ xKλ ≡ KSλ ≡ S(P Q)λ ≡ Pλ Qλ

xLC ≡ x(M N)LC ≡ MLC NLC(λx.M)LC ≡ µx.MLC


entonces se tiene:λC ` MLC,λ = M

y ademas:(LC ` P = Q) ⇒ Pλ = Qλ

El recıproco del anterior no es cierto; por ejemplo,

λC ` S K = K I

ya que

S K≡ ! definicion de S

(λpqr.p r (q r)) K= ! β–regla

λqr.K r (q r)= ! definicion de K

λqr.r= ! definicion de K y de I

K I

pero no es posible deducir en LC la igualdad S K = K I ya que en LC noes aplicable la ξ–regla (ver [Bar84], p.157):

P = Q ⇒ µx.P = µx.Q

En efecto; tenemos:LC ` I x = x

peroLC 6` µx.I x = I

donde µx.I x ≡ S (K I) I

3.1.2 Reduccion en forma perezosa

EJEMPLO 3.0. Sea f una constante. Calculemos (λxy.f x y)LC :

(λxy.f x y)LC≡

µx.µy.f x y≡

µx.S (µy.f x) (µy.y)≡

µx.S (K (f x)) I≡

S (µx.S (K (f x)) (µx.I)≡

S (µx.S (K (f x)) (K I)≡


S (S (µx.S) (µx.K (f x))) (K I)≡

S (S (K S) (S (µx.K) (µx.(f x)) (K I)≡

S (S (K S) (S (K K) (S (K f) I))) (K I)

luego

(λxy.f x y)LC ≡ S (S (K S) (S (K K) (S (K f) I))) (K I)

que es la representacion combinatorial de f como aplicacion parcial, donde seobserva que las reducciones quedan suspendidas ya que los terminos aparecenemparejados sin posibilidad de utilizar la reduccion. Tenemos que:

(λxy.f x y)LC u v= ! definicion de (·)LC

(µxy.f x y) u v= ! propiedad 3 anterior

f u v

y por tanto, si LC fuera extensional tendrıamos

LC ` (λxy.f x y)LC = f

Observese tambien que tenemos:

S (S (K S) (S (K K) (S (K f) I))) (K I) u=

(S (K S) (S (K K) (S (K f) I))) u ((K I) u)=

(((K S) u) (S (K K) (S (K f) I)) u) I=

S ((K K) u) (S (K f) I) u) I=

S (K ((K f) u) (I u)) I=

S (K (f u)) I

luego(λxy.f x y)LC u = S (K (f u)) I

donde de nuevo quedan operaciones suspendidas; finalmente, si aplicamos a unanueva variable v podemos “arrancar” nuevas reduciones

(λxy.f x y)LC u v=

S (K (f u)) I v=

K (f u) v (I v)=

f u v

♣


La discusion anterior permite intuir que una expresion combinatoria (comoversion “compilada” de una λE o programa funcional) se reduce en forma pere-zosa.

3.1.3 Generadores y bases

La siguiente propiedad permite probar que el conjunto K,S ⊆ Λ0 es unabase en el siguiente sentido.

Definicion 3.2 (Generador y base)

1. Dado un conjunto B, se define B+, terminos generados por B, como elmenor subconjunto de Λ que contiene a B y es cerrado para la aplicacion;es decir, el menor Y ⊆ Λ verificando:

• B ⊆ Y• M, N ∈ Y ⇒ M N ∈ Y

2. B se dice una base de Λ si

∀M.M ∈ Λ0 . (∃N.N ∈ B+.M = N)2

Teorema 3.0 K,S ⊆ Λ es una base

Demostracion: Sea M ∈ Λ0; entonces MLC ∈ C0, por lo que MLC,λ ∈ K,S+;pero por ser λC ` MLC,λ = M se tiene que M ∈ K,S+ 2

Teorema 3.1 Existe una base de Λ con un solo elemento X verificando

X X X = K , X (X X) = S


EJERCICIO 3.4. Probar que el elemento X ≡ λx.x (S (K K)) K es unabase. Ayuda: probar que X X X = K, y que X K = S 2

EJERCICIO 3.5. ¿Por que son importantes las bases de Λ? 2

3.1.4 Equivalencia entre λC y LCVolvamos de nuevo al problema de la reduccion de combinadores; en el ejem-

plo 3.0 vimos la equivalencia

µxy.f x y ≡ S (S (K S) (S (K K) (S (K f) I))) (K I)


pero, aplicando unicamente las reglas de reduccion (igualdades) de LC no esposible reducir el termino anterior (serıa una forma normal en LC).

Recuerdese tambien que se tiene:

λC ` MLC,λ = MLC ` P = Q ⇒ λC ` Pλ = Qλ

pero no necesariamente se tiene:

LC ` Mλ,LC = MλC ` P = Q ⇒ LC ` PLC = QLC

Sea A un conjunto de axiomas (igualdades) en LC; diremos que λC es equiv-alente a LC ∪ A si se tiene:

• λC ` MLC,λ = M

• LC ∪ A ` Mλ,LC = M

• LC ∪ A ` P = Q ⇔ λC ` Pλ = Qλ

• λC ` P = Q ⇔ LC ∪ A ` PLC = QLC

Sea ahora A un conjunto de axiomas de forma que es posible probar en LC ∪Alas siguientes propiedades:

(a) K = µxy.x

(b) S = µxyz.x z (y z)

(c) S (K P ) (K Q) = K (P Q)

(d) µx.K P Q = µx.P

(e) µx.S P Q R = µx.P R (Q R)

entonces se tiene νx.M = µx.M y las teorıas λC y LC ∪A son equivalentes. Elproblema es la eleccion del conjunto A de axiomas; por ejemplo, Curry introduceel siguiente conjunto Aβ de axiomas:

(1) K = µxy.K x y (1′) K = µxy.x(2) S = µxyz.S x y z (2′) S = µxyz.x z (y z)(3) µxy.S (K x) (K y) = µxy.K (x y)(4) µxy.S (S (K K) x) y = µxyz.x z(5) µxyz.S (S (S (K S) x) y) z = µxyz.S (S x z) (S y z)

y se puede demostrar que LC∪Aβ ` (a)−(e), y por tanto LC∪Aβ es equivalentea λC; tambien es facil ver que LC ∪ ext ` Aβη donde Aβη es Aβ extendido conel axioma:

(η) µx.S (K x) I = I

3.2. Puntos fijos 55

y por tanto las teorıas LC∪ext, λη, λC∪ext y LC∪Aβη son todas equivalentes.

Curry introduce dos nuevas constantes B y C, llamadas compositor y per-mutador, que son las versiones abstractas de dos λ–terminos:

B ≡ λfxy.f (x y) C ≡ λfxy.f y x

y a partir de estas da reglas suficientes para la equivalencia con el λC extensional;estas son:

(a) S (K P ) (K Q) = K (P Q)

(b) S (K P ) I = P

(c) S (K P ) Q = B P Q

(d) S P (K Q) = C P Q

Si consideramos un λC extensional con constantes tendremos:

λx.4 x = 4

y si trasladamos la expresion λx.4 x obtenemos:

(λx.4 x)LC≡

S (K 4) I= ! por (b)

4

3.2 Puntos fijos

3.2.0 Expresando la recursion

Consideremos la siguiente definicion de factorial:

FAC = λn.COND (= n 0) 1 (∗ n (FAC (− n 1))) (3.0)

y puesto que COND ≡ λxyz.x y x:

FAC = λn.(= n 0) 1 (∗ n (FAC (− n 1))) (3.1)

Tal definicion es incorrecta en el λC ya que las funciones son anonimas yno pueden referirse a sı mismas; para resolver tal problema podemos escribir elmiembro de la derecha como resultado de una β–reduccion sobre una funcion ϕdefinida en la forma:

ϕ = λf.((λn.( = n 0) 1 (∗ n (f (− n 1)))


de forma que la ecuacion 3.1 se escribe en la forma:

FACT = ϕ FACT (3.2)

es decir, FACT es un punto fijo de la funcion ϕ; por otro lado vemos que lasolucion a la ecuacion 3.2 dependera solamente de ϕ. Veamos una forma deobtener la solucion de tales ecuaciones:

Teorema 3.2 (del punto fijo) Para cada F existe una expresion X tal que

F X = X

Demostracion: Sean W ≡ λx.F (x x), X ≡ W W ; tenemos

X=

W W=

(λx.F (x x)) W=

F (W W )=

F X

2El teorema afirma que existe solucion de la ecuacion 3.2. Veamos ahora

como buscarla de forma general.

3.2.1 Combinadores para puntos fijos

Definicion 3.3 (Combinador para puntos fijos) Un termino M es un com-binador para puntos fijos (cppf) si

∀F . F ∈ Λ . M F = F (M F )

2

Se observa que, si M es un cppf, dada una F podemos obtener siempre unpunto fijo de F en la forma M F . El problema es, ¿existen tales combinadores?

Corolario 3.0 El combinador Y ≡ λf.(λx.f (x x)) (λx.f (x x)) es un cppf.

Demostracion: Sea W ≡ λx.F (x x) el termino del teorema; entonces:

Y F≡

W W=

F (W W )=

F (Y F )

2


El combinador Y es llamado por Curry el combinador paradojico.

EJERCICIO 3.6. Analizar la siguiente paradoja de Curry; supongamos quequeremos definir un operador ⇒ (implicacion) verificando:

(P ⇒ (P ⇒ Q)) ⇒ (P ⇒ Q)P, P ⇒ Q ` Q (modus ponens)

Sea imp la version prefija (parcializada) de ⇒ y sea:

N ≡ λx.imp x (imp x Q)P ≡ Y N

Probar que

(a) ∀Q :: P = imp P (imp P Q)

(b) P = C

(c) ∀Q :: Q = C (inconsistencia, e.d., paradoja)2

El combinador Y resuelve el problema de la recursion antes planteado, ya quela funcion factorial puede definirse en la forma:

FACT = Y ϕ

donde ϕ esϕ = λf.((λn.(= n 0) 1 (∗ n (f (− n 1)))

que es una definicion no recursiva del factorial. Ası tenemos una tecnica paraeliminar la recursion transformandola en iteracion, pero tal iteracion puede noterminar (si las iteraciones no tienen forma normal).

Tal solucion es acertada desde un punto de vista matematico; sin embargo,debido a la ineficiencia de la implementacion del combinador Y usando su λE,la mayorıa de las implementaciones proporcionan Y como un constructor conla regla de reduccion

Y F → F (Y F )

En efecto, tenemos la siguiente reduccion:

FACT 1≡

Y ϕ 1→

ϕ (Y ϕ) 1≡

(λf.((λn.(= n 0) 1 (∗ n (f (− n 1)))) (Y ϕ) 1→

((λn.(= n 0) 1 (∗ n (Y ϕ (− n 1)))) 1→

∗ 1 (Y ϕ(− 1 1))))→


∗ 1 (Y ϕ 0)→

∗ 1 (ϕ (Y ϕ) 0)≡

∗ 1 (λf.((λn.(= n 0) 1 (∗ n (f (− n 1)))) (Y ϕ) 0→

∗ 1 ((λn.(= n 0) 1 (∗ n (Y ϕ (− n 1)))) 0→

∗ 1 1→

1

Los puntos fijos de un termino F no son necesariamente unicos; sin embargo,el punto fijo Y F es el mınimo punto fijo de F en la teorıa de dominios.

Otro ejemplo de cppf es el de Turing:

T = A A , donde A ≡ λxy.y (x x y)

En efecto:

T F≡

A A F→

F (A A F )≡

F (T F )

En general

EJERCICIO 3.7. Dado un termino M , probar que

YM ≡ λf.W W M , donde W ≡ λxz.f (x x z)

es un cppf. 2

Los siguientes resultados permiten obtener otros cppf:

Lema 3.1 Sea G ≡ S I = λyf.f (y f). Entonces

M es un cppf ⇔ M = G M

Demostracion:

(⇐) Si M = G M , entonces M F = G M F = F (M F ), con lo cual M es uncppf.


(⇒) Si M es un cppf, entonces M f = f (M f), con lo cual

M=η

λf.M f=

λf.f (M f)=

G M2

Teorema 3.3 (Bohm–van der Mey) Los siguientes combinadores son cppf:

Y0 ≡ Y , Yn+1 ≡ Yn (S I)

Demostracion: Se prueba por induccion:

Caso base: Y0 ≡ Y es un cppf (como vimos antes)

Paso inductivo: Supongamos que Yn lo es; entonces, por el lema anteriortenemos que:

Yn = G Yn

luego:

G Yn+1

≡G Yn (S I)

=Yn (S I)

≡Yn+1

2

EJERCICIO 3.8. Probar que Y1 = T (el combinador de Turing) 2

EJERCICIO 3.9. Construir un termino F tal que F x y = F y x F 2

EJERCICIO 3.10. Probar que Y I = Ω 2

Chapter 4

Lambda definibilidad

En la sintaxis del λC vista anteriormente consideramos un conjunto de con-stantes correspondientes a una serie predefinida de funciones (con δ–reglas),tales como +, 0, –1, cond, etc. En este apartado vamos a ver como puedendefinirse tales funciones en un λC puro.

4.0 Operaciones logicas

4.0.0 Constantes y operaciones logicas

Si definimos los combinadores

C = λxy.xF = λxy.y

se tiene:C P Q = PF P Q = Q

(C es el combinador K anterior y K I ³ F) por lo que podemos definir elcombinador condicional cond

cond = λcpq.c p q

ya que cumple las reglas de reduccion conocidas del si-entonces-sino; en efecto:

cond C M N≡

(λcpq.c p q) C M N= ! β–regla tres veces

C M N=β

M

61

62 4. Lambda definibilidad

Los operadores no, y y o se definen en la forma:

no = λx.x F Cy = λxy.x y Fo = λxy.x C y

Ası,

y C F≡

(λxy.x y F) C F= ! β–regla dos veces

C F F=

F

no C≡

(λx.x F C) C=

C F C=

F

EJERCICIO 4.0. Definir el operador xor. 2

EJERCICIO 4.1. Probar que y y o son commutativas y asociativas 2

EJERCICIO 4.2. ¿λC ` no no A = A? 2

4.1 Computabilidad y λ–definibilidad

4.1.0 Sistemas de numerales y numerales de Church

Definicion 4.0 (Sistema de numerales) Un sistema N de numerales es unaterna N ≡ 〈N,Cero,Suc〉 donde N es una sucesion de combinadores

N ≡ N0, N1, . . .

y Cero y Suc son dos terminos (funciones) tales que

Cero N =

C , si N = N0

F , si N = N1, N2, . . .

Suc Nk = Nk+1

2

4.1. Computabilidad y λ–definibilidad 63

Definicion 4.1 (Sistema adecuado de numerales) Un sistema de numeraleses adecuado si existe una funcion Pred (predecesor) tal que:

Pred Nk+1 = Nk

2

Existen varios sistemas adecuados de numerales; veremos dos de ellos: elestandar y el de Church.

Definicion 4.2 (Pares de Church) Se definen:

[M ] ≡ M[M,N ] ≡ λz.z M N[M0, . . . , Mn] ≡ [M0, [M1, . . . , Mn]]

2

Definicion 4.3 (Numerales estandar) Sean

d0e ≡ Idn + 1e ≡ [F, dne] ≡ λz.z Fdne

2

Definimos entonces las funciones Suc, Pred y Cero:

S+ ≡ λx.[F, x] (funcion sucesor)P− ≡ λx.x F (funcion predecesor)Cero ≡ λx.x C (test cero)

EJERCICIO 4.3. Se verifican las siguientes propiedades:

S+ dne = dn + 1eP− dn + 1e = dneCero d0e = CCero dn + 1e = F

2

Claramente el sistema de numerales estandar esta determinado por la funcionsucesor y por el primer valor d0e, por lo que podemos expresar N ≡ 〈d0e,S+〉

4.1.1 Funciones λ–definibles y recursivas. Teorema de Kleene

Definicion 4.4 (Funcion λ–definible) Una funcion numerica ϕ : Np → Nse dice λ–definible si existe un termino F tal que

dϕ(n1, . . . , np)e ³ F dn1e . . . dnpe

2


NOTACION Si denotamos con

n = n1, . . . , np dne = dn1e . . . dnpela definicion anterior se escribe:

dϕ(n)e ³ F dne♠

Definicion 4.5 (Funciones recursivas)

1. Las funciones iniciales son las funciones Upi , S+, Z, donde

Upi (n0, . . . , np) = ni

S+(n) = n + 1Z(n) = 0

2. Una clase de funciones numericas C es cerrada para la composicionsi contiene la composicion de funciones de la clase, es decir, las funcionesde la forma:

χ(φ1(n), . . . , φm(n)) ∈ C si χ, φ1, . . . , φm ∈ C

3. Una clase de funciones numericas C es cerrada para la recursion prim-itiva si contiene a las funciones de la forma:

φ(0,n) = χ(n)φ(k + 1,n) = ψ(φ(k,n), k,n) , para χ, ψ ∈ C

4. Una clase C es cerrada para la minimizacion si contiene las funcionesde la forma:

φ(n) = min m | ϕ(n,m) = 0 , con ϕ ∈ C

5. La clase R de las funciones recursivas es la menor clase cerrada parala composicion, recursion primitiva y minimizacion que contiene a lasfunciones iniciales.

2

Teorema 4.0 (Kleene) La clase de funciones recursivas es la misma que laclase de funciones λ–definibles.

Demostracion: [Bar84], pag. 138 2

Corolario 4.0 Las funciones computables son λ–definibles.

Demostracion: [Bar84], pag. 138 2

NOTA El recıproco tambien es cierto, es decir, toda funcion λ–definible escomputable. ♠

4.1. Computabilidad y λ–definibilidad 65

El teorema de Kleene es la base de la evaluacion de los programas funcionales;ası, dada una funcion computable f : N→ N y su λ–termino asociado F :

df(n)e ³ F dne

por el teorema de Chuch-Rosser, para obtener su valor (df(n)e) basta encontrar(si existe) la forma normal de F dne.

4.1.2 Aritmetica y Numerales de Church

Aunque es posible definir la aritmetica con los numerales estandar, es mas simplehacerlo a traves de los numerales de Church. Estos se definen en la forma:

c0 ≡ λfx.xcn+1 ≡ λfx.fn+1(x)

de forma queS+

c ≡ λabc.b (a b c)

es una funcion sucesor; en efecto:

S+c cn

=λbc.b (cn b c)

=λbc.b bn c

=cn+1

EJERCICIO 4.4.

1. Definir funciones

c0, c1, . . . H−1

−→ d0e, d1e, . . . c0, c1, . . . H←− d0e, d1e, . . .

tales que:H dne = cn H−1 cn = dne

2. A traves de las funciones anteriores, definir funciones test-cero y predecesor(Ceroc y P−c ) para los numerales de Church.

3. Demostrar que los numerales de Church forman un sistema adecuado denumerales.

2


EJERCICIO 4.5. [Rosser] Se consideran las siguientes funciones

+ ≡ λmnfx.m f (n f x) (suma)× ≡ λmnf.m (n f) ≡ λmn.m n (producto)↑ ≡ λxy.y x (exponencial)

donde m n viene dado por la definicion 3.0. Probar que con respecto a losnumerales de Church las funciones suma, multiplicacion y potencia quedan λ–definidas por +, × y ↑ 2

4.1.3 Extension del λC con la aritmetica

Por el teorema de Kleene se puede integrar la aritmetica entera en el λC,extendiendo este con las constantes necesarias (los numeros, el test cero, lasfunciones predecesor y sucesor, las operaciones aritmeticas, etc.) y con unas δ–reglas consistentes con la aritmetica; es facil probar que la βδ–reduccion asociadatiene la propiedad de Church–Rosser.

4.2 Listas en el λC puro

4.2.0 λ–definibilidad de las funciones basicas para listas

Sean las funciones:

cons ≡ λabf.f a bvacia ≡ λxyz.yvacia? ≡ λx.x (λabcd.d)

Entonces es facil ver que:

vacia? vacia = C vacia? (cons a b) = F

Por ejemplo:

vacia? (cons a b)≡

(λx.x (λabcd.d)) (cons a b)=β

cons a b (λabcd.d)≡ ! definicion de cons

(λabf.f a b) a b (λabcd.d)= ! β–regla tres veces

(λabcd.d) a b= ! β–regla dos veces

λcd.d≡

F

4.2. Listas en el λC puro 67

Podemos identificar cons con el constructor de listas y consideraremos las sigu-ientes equivalencias sintacticas:

vacia ≡ [ ]cons a b ≡ a : b[x1, . . . , xn] ≡ x1 : [x2, . . . , xn]

entonces es facil ver que:

cab ≡ λx.x C col ≡ λx.x F

son funciones que extraen la cabeza y la cola de una lista:

cab (cons p q) = p col (cons p q) = q

Por ejemplo:

cab (cons p q)≡ ! definicion de cab

(λx.x C) (cons p q)=β

cons p q C≡ ! definicion de cons

(λabf.f a b) p q C= ! β–regla tres veces

C p q≡ ! definicion de C

(λxy.x) p q= ! β–regla dos veces

p

Ahora veamos como definir la funcion de concatenacion. En principio, nues-tra funcion debera verificar la ecuacion:

CONCA x y = vacia? x y (cons (cab x) (CONCA (col x) y))

y si procedemos a eliminar la recursion de la misma forma que hicimos con elfactorial, tendremos:

CONCA = Y (λfxy.vacia? x y (cons (cab x) (f (col x) y)))

EJERCICIO 4.6. Probar (haciendo las hipotesis necesarias) que la funcionanterior CONCA tiene el mismo comportamiento que la funcion:

CONCA′ = Y (λfxy.lcaso x y (λcr.cons c (f r y)))

dondelcaso vacia P Q →δ Plcaso (cons M N) P Q →δ Q M N

2


4.2.1 Las listas en un λC con constantes

Consideremos ahora la extension sintactica del λC con las listas; podemos anadirlas δ–reglas para las constantes cab, col, cons y vacia?:

cab [ ] →δ [ ]cab [A1, . . . , An] →δ A1 (n ≥ 1)

col [ ] →δ [ ]col [A1, . . . , An] →δ [A2, . . . , An] (n ≥ 1)

cons A [ ] →δ [A]cons A [A1, . . . , An] →δ [A,A1, . . . , An]

vacia? [ ] →δ Cvacia? [A1, . . . , An] →δ F

Como primera observacion, puesto que en nuestro λC no se consideran tipos, laexpresion vacia? 3 tiene sentido y precisamente es una forma normal.

Al incluir las listas tendremos que incluir terminos de la forma:

λx.[a, b] (λx.[x, q]) M (λxy.[x, y] a) [b, c, d]

y puede ser interesante considerar tambien ciertas reglas de reduccion cuandoaparecen las listas en forma funcional. Por ejemplo, podrıa ser interesantetrasladar la funcionalidad a las listas y ampliar el concepto de reduccion, con locual se tendrıa por ejemplo:

(λx.[x, q]) M → [M, q](λxy.[x, y] P ) [b, c, d] = λy.[[b P, c P, d P ], y P ]

Para ello es necesario definir la sustitucion sobre listas (para esta sustitucion uti-lizamos x := E en lugar de [x := E] para evitar confusiones con los corchetes):

x := E[A, B, . . . ] ≡ [x := EA, x := EB, . . . ]

y en ese caso tendremos una β–regla extendida:

(λx.[A,B, . . . ]) M →β [x := MA, x := MB, . . . ]

Sin embargo quizas sea mas interesante, de cara a enriquecer las propiedadesfuncionales de las listas, anadir dos nuevas reglas en la forma:

λx.[A,B, . . . ] →γ [λx.A, λx.B, . . . ][A,B, . . . ] M →γ [A M, B M, . . . ]

Tales γ–reglas no son deducibles a traves de un λC puro y, segun ([Rev88],p.66]), es poco probable que exista alguna otra representacion de las listas que

4.3. Autointerpretacion en el λC 69

verifique las γ–reglas. Estas reglas tendran una gran influencia en el conceptode FNC para las listas.

EJERCICIO 4.7. Utilizando las γ–reglas, probar la interesante propiedad:

[A,B] h = [A h,B h]

donde es la composicion:

M N ≡ λx.M (N x)

2

EJERCICIO 4.8. Describir, en el λC extendido, las funciones APLICA (alista), INV IERTE y REDUCE (listas). 2

4.3 Autointerpretacion en el λC

4.3.0 Un autointerprete para el λC

Si todas las funciones computables pueden ser descritas con un lenguaje(teorema de Kleene), entonces una determinada funcion (computable) descritacon el lenguaje debera poder ser interpretada en el propio lenguaje; se hablaentonces de autointerpretacion. Veamos un resumen de [Bar91], donde se exponeuna demostracion de tal posibilidad para el λC. El problema es el siguiente:

¿Existe una funcion I : Λ → Λ tal que IdMe = M? ¿Es repre-sentable tal funcion en el λC?

Podemos asignar a cada termino M ∈ Λ un codigo interno dMe en la formasiguiente: puesto que N×N es numerable, existe una biyeccion N×N→ N (Can-tor se encargo de definirla); sea esta 〈n,m〉. Suponiendo que las variables estannumeradas en la forma vi, entonces podemos definir el codigo de un termino enforma inductiva:

#vi = 〈0, i〉#(M N) = 〈1, 〈#M, #N〉〉#(λx.M) = 〈2, 〈#x, #M〉

Sea ahora dMe ≡ d#Me, la forma normal asociada al numeral de Church corre-spondiente a #M . Un autointerprete es un λ–termino E verificando, ∀M ∈ Λ0

E dMe = M

Observese que la ecuacion anterior no puede ser cierta para todos los terminos,ya que el numero de variables libres de E dMe esta acotado por el numero devariables libres de E, mientras que el de M no esta acotado.

Teorema 4.1 (Church, 1936) Existe un autointerprete para el λC

Demostracion: (ver [Bar91]) 2


4.3.1 Aplicaciones de la autointerpretacion

Usando un autointerprete es posible demostrar la existencia de terminos sindarlos explıcitamente; por ejemplo, existe un λ–termino F tal que

F dne = λx1 • • • xn.[x1, . . . , xn]

En efecto; seaMn ≡ λx1 • • • xn.[x1, . . . , xn]

entonces #Mn es computable y existe una funcion g recursiva tal que

g(n) = #M

ademas, g es λ–definible, luego si g esta λ–definida por G y E es un au-tointerprete, entonces

F ≡ λn.E (G n)

es una solucion

F dne= ! definicion de F

E (G dne)= ! g esta λ–definida por G

E (g(n))≡

E #Mn

= ! E es un autointerprete

λx1 • • • xn.[x1, . . . , xn]

EJERCICIO 4.9. Sea inv la funcion que invierte listas y sea V :

V = Y (λvn.Cero n inv (λLx.v (Pred n) (x : L))

probar que F ≡ (λn.V n vacia) verifica

F dne x1 • • • xn = [x1, . . . , xn]

2

Chapter 5

Solubilidad

5.0 Introduccion

Existen terminos que no tienen forma normal, como por ejemplo

Ω = (λx.x x) (λx.x x)

El concepto de computo (β–reduccion) para tales terminos no termina; en esecaso, ¿que se entiende por computo para tales terminos?

Ademas, sabemos (ver ejercicio 2.6) que no podemos identificar los terminossin forma normal ya que la teorıa serıa inconsistente; sin embargo, existenterminos sin forma normal que son distinguibles en cierto contexto.

EJEMPLO 5.0. Sean

M ≡ λx.x K AN ≡ λx.x (K I) A

donde A no tiene forma normal; entonces M y N no tienen tienen forma normal;sea ahora el contexto C[·] ≡ [·]K; entonces:

C[M ] C[N ]≡ ≡

MK NK= =

K K A K (K I) A= =

K K I

y ya que K 6= K I (ver ejercicio 2.8), tendremos que M K y N K son distin-guibles, por lo cual M y N no se pueden identificar. ♣

Observese que los terminos M y N del ejemplo anterior estan en FNC;veremos que eso es equivalente a cierto concepto de solubilidad.

71

72 5. Solubilidad

5.1 Concepto y caracterizacion de la solubilidad

Definicion 5.0 (Termino resoluble)

1. Un termino M ∈ Λ0 es resoluble si existen terminos N1,. . . ,Nk tales que

M N1 . . . Nk = I (5.0)

donde k puede ser cero (y en ese caso M = I).

2. Un termino M ∈ Λ es resoluble si su cierre λ~x.M es resoluble.

3. Un termino M ∈ Λ se dice irresoluble si no es resoluble.

NOTACION La ecuacion 5.0 anterior la escribiremos:

M ~N = I

♠Tenemos la equivalencia:

M resoluble ⇔ (∀X :: (∃ ~N :: M ~N = X))

Es decir, que la ecuacion M ~N = X se puede resolver para cada X y M .

Teorema 5.0 La irresolubilidad se conserva en las traslaciones entre λC y LC.

Demostracion: pagina 177 de [Bar84]. 2

EJERCICIO 5.0. Probar que:

(a) K y S son resolubles

(b) Y es resoluble

(c) los numerales de Church y los estandar dne son resolubles2

Observese que todos los terminos del ejercicio anterior admiten FNC. Veamosahora un par de teoremas de caracterizacion y una condicion suficiente para laresolubilidad de un termino M ∈ Λ.

Teorema 5.1

1. Un termino M ∈ Λ es resoluble si y solo si existe una instancia M∗ de My existen terminos ~N ⊆ Λ0 tales que

M ~N = I

2. Un termino M ∈ Λ es resoluble si y solo si λx.M es resoluble (por lo queen la definicion de resolubilidad el orden de las variables en el cierre λ~x.Mes indistinto)

5.2. Interpretacion computacional de la solubilidad 73

3. Si un termino M ∈ Λ es irresoluble, entonces lo son tambien los terminos:

M N [x := N ]M λx.M

Demostracion:

1. Por ser M resoluble, existen ~N tales que (λx1x2 . . . xn.M) N1 . . . Nm = I;podemos considerar que los Ni son cerrados y que m > n (en otro caso, obien se anaden λs delante, o bien se anaden Is detras). Ası tenemos:

[xn := Nn] . . . [x1 := N1]M︸︷︷︸M∗

Nn+1 . . . Nm = I (5.1)

2. Tomando x ≡ x1, se tiene:

M resoluble⇔ ! por 5.1

∃ ~N, ~P ⊆ Λ0 | (λx.M) [xn := Nn] . . . [x2 := N2]N1~P = I

⇔∃ ~N, ~P ⊆ Λ0 | [xn := Nn] . . . [x2 := N2](λx.M) N1

~P = I⇔

λx.M resoluble

3. Es evidente por (1) y (2).2

5.2 Interpretacion computacional de la solubili-dad

Recordemos que, segun el teorema 2.2,

(1) λx.M tiene una FNC ⇔ M tiene una FNC(2) M N tiene una FNC ⇒ M tiene una FNC(3) [x := N ]M tiene una FNC ⇒ M tiene una FNC

A partir de aquı es facil demostrar el siguiente teorema:

Teorema 5.2 (Wadsworth, 1971)

M es resoluble ⇔ M tiene una FNC

Demostracion:

⇒: Si M ~N = I, entonces M ~N tiene una FNC y por (2) tambien la tiene M .

74 5. Solubilidad

⇐: Si M tiene una forma normal, podemos suponer por (1) que M es cerrado:

M = λx1x2 . . . xn.xi M1 . . . Mm

y por tanto, tenemos:

M (Km I)∼n = Km I M∗1 . . . M∗

m = I

por lo que M es resoluble (los M∗i son los Mi salvo sustituciones).

2

Por lo tanto, Ω = (λx.x x) (λx.x x) no es resoluble al no tener una FNC.En general, las formas normales son resolubles, y los terminos irresolubles notienen forma normal.

Ası, considerando la reduccion por la cabeza como metodo de computo, la noterminacion es sinonimo de irresolubilidad; en este caso, si identificamos en unmismo termino todos los terminos irresolubles se obtiene una teorıa consistente(ver paginas 411–413 de [Bar84]). El termino que identifica todos los terminosirresolubles puede ser el indefinido (⊥), que es igual por ello a Ω. Por tanto,tenemos:

U =⊥ ⇔ U irresoluble ⇔ U no tiene FNC ⇒ U no tiene FN

Aunque un termino U irresoluble no tiene forma normal, dicho termino encierto contexto sı puede tenerla:

Definicion 5.1 (FNC similares) Dos FNC son similares si tienen el mismonumero de variables instanciables, la misma variable en cabecera y el mismonumero de argumentos.

Teorema 5.3 Siendo U un termino irresoluble, C[·] un contexto y M un terminoarbitrario:

(a) Si C[U ] tiene FN, entonces C[M ] tiene la misma FN.

(b) Si C[U ] tiene FNC, entonces C[M ] tiene una FNC similar.

Demostracion: Puede encontrarse en la pagina 374 de [Bar84] y en la pagina173 de [Dav89]. 2

Finalmente, veamos otra interpretacion computacional:

EJERCICIO 5.1. Demostrar que si P es irresoluble, lo son tambien P X yP X 2

Del resultado anterior se deduce que si un “programa” P no termina, notermina ni su aplicacion a algo ni su composicion con algo. Es decir, si nopodemos dar informacion sobre una funcion (asociada al termino irresolubleP ), tampoco podemos dar informacion sobre la aplicacion de dicha funcion aun argumento; por otro lado, si un programa (funcion) no termina, cualquiersecuencia que comience con el tampoco lo hara.

Chapter 6

Semantica denotacional

6.0 Introduccion

En el λC sin tipos los objetos pueden ser argumentos y funciones. En con-secuencia, la semantica del λC sobre un modelo D (si preserva la composicion)debe ser tal que D sea isomorfo al conjunto de funciones DD. Por el teoremade Cantor esto es imposible y Scott resuelve el problema buscando un modeloD∞ (retıculo completo) que es isomorfo a su espacio de funciones continuas[D∞ → D∞] (para cierta topologıa); este dominio sirve como modelo exten-sional del λC.

En un modelo se pretende que las ecuaciones demostrables en el λC denlugar a igualdades en el modelo; en ese caso se dice que el modelo es seguro(soundness) o solido. Esta propiedad la cumplen las λ–algebras (algebras com-binatorias que cumplen los axiomas de Curry) con las cuales se puede trabajaren forma ecuacional, y los λ–modelos (λ–algebras con un axioma de extension-alidad debil).

Otra categorıa son los modelos sintacticos en los cuales la descripcion delsignificado de un λ–termino viene dado por su forma sintactica a traves de unainterpretacion sintactica; estos modelos son utiles cuando se pretende obtenerdirectamente la intepretacion.

6.1 Interpretacion sobre un modelo aplicativo

Definicion 6.0 (Conjunto de terminos) Dado un conjunto M, el conjuntoT (M) de terminos sobre M se define en forma inductiva:

x, y, · · · ∈ T (M) (variables ≡ V ar)m ∈M ⇒ cm ∈ T (M) (a cada m le asociamos

un sımbolo de constante)A,B ∈ T (M) ⇒ (A B) ∈ T (M)

275

76 6. Semantica denotacional

Convenio 6.0 Escribimos T en lugar de T (M) si no hay confusion, los parentesisexternos pueden quitarse, se utiliza la asociatividad por la izquierda, y denotare-mos con A la constante ca asociada al elemento a ∈M). 4

Podemos hablar tambien del conjunto Λ(M) de terminos, entendiendo conello los λ–terminos construidos a partir de las variables y las constantes de M:

λx.A y (λxyz.yz) B u

Es decir, Λ(M) = Λ(ca | a ∈M) y se tiene T (M) ⊆ Λ(M).

Nos planteamos ahora el problema de definir el concepto de interpretacionen M de los objetos de T (M); es decir, asignar a terminos tales como

x x A

valores de M; es decir queremos definir

M |= M = N

que se lee “los terminos M y N tienen la misma interpretacion en M” o tambien“en M es demostrable que M = N”. Existen dos problemas fundamentales:

(a) El termino puede contener variables libres, y en particular puede ser unavariable; ¿que valor asociar a una variable?

(b) Conocidos el valor de dos terminos M y N , ¿cual es el valor del terminoM N?

El problema (b) es facil de resolver si sobre M existe una operacion binariadenotada con •; es decir, M es una estructura aplicativa. Ası, si [M ] y [N ] de-notan los valores (significados o semantica) de los terminos M y N , el significadoo valor de M N sera [M ] • [N ]. En consecuencia, consideraremos estructurasaplicativas (con una operacion binaria).

Convenio 6.1 Escribimos ab en lugar de a • b, y utilizamos tambien la asocia-tividad por la izquierda:

abc . . . f = (. . . ((ab)c) . . . )f

Ası pues, el significado de AB(CD) sera ab(cd). 4Dado un objeto a ∈ M se construye una funcion fa ≡ δx.ax definida como

fa(x) = ax; dos funciones fa y fb son iguales si ∀x :: ax = bx; nos interesaidentificar en ese caso los objetos a y b; esto no sera posible en general por loque cuando ocurra diremos que M es extensional.

Veamos ahora el problema (a) de las variables. Desafortunadamente el valorasociado a una variable v no puede darse de forma aislada, y por ello introduci-mos el concepto de entorno.

6.1. Interpretacion sobre un modelo aplicativo 77

Definicion 6.1 (Entorno) Un entorno ρ sera una aplicacion:

ρ : V ar →M

siendo V ar el conjunto de identificadores de variables (o simplemente variables);el conjunto de entornos lo denotamos con E:

E = ρ : V ar →M

El valor de una variable en un entorno sera

[x]ρ ≡ ρ x

2

De esta forma se puede definir un concepto de igualdad en T (M) incluso enpresencia de variables libres. La funcion semantica es una aplicacion:

I : T × E →MI(M, ρ) ≡ [M ]ρ ∈M

definida a traves de una interpretacion:

Definicion 6.2 (Interpretacion de un termino) La interpretacion de un terminoM ∈ T (M) en M bajo ρ es [M ]ρ , donde [ ] se define en forma inductiva:

[x]ρ = ρ x[ca]ρ = a[A B]ρ = [A]ρ [B]ρ

Ademas:M, ρ |= A = B si [A]ρ = [B]ρM |= A = B si ∀ρ :: [A]ρ = [B]ρ

2

La notacion M, ρ |= A = B se lee “A = B es cierto en M bajo ρ”, mientrasque M |= A = B se lee “A = B es cierto en M”. Observese que:

• Si un termino M no tiene variables, su valor [M ] es independiente delentorno ρ. Ası, si a = kab entonces [A] = a = kab = [K A B] y M |=A = K A B.

• Cuando decimos “A = B es cierto en M” (o simplemente “A = B en M”)queremos decir que M |= A = B; si no hay confusion escribimos [M ] enlugar de [M ]ρ


6.2 Algebras combinatorias y λ–algebras

6.2.0 Algebras combinatorias

Sabemos que los λ–terminos pueden simularse si existen dos sımbolos deconstantes K,S ∈ T , asociados a dos constantes particulares k, s ∈ M; talsimulacion puede hacerse si tales constantes verifican dos axiomas:

k a b = as a b c = a c (b c)

Definicion 6.3 (Algebra combinatoria) M es un algebra combinatoria sicontiene dos elementos k y s tales que

k a b = as a b c = a c (b c)

2

En particular, el conjunto C de terminos de la logica combinatoria es T (K,S),donde se considera el algebra con unicos elementos k y s. Si definimos

i = s k k

entonces ∀a :: ia = a. Es evidente que |M| > 1 ⇔ k 6= s, ya que

k = s ⇒ a = s (k i) (k a) z = k (k i) (k a) z = (k i) z = i

y todos los terminos son iguales (a i). A partir de ahora consideraremos sola-mente algebras combinatorias no triviales (i.e., con mas de un elemento). Aunası, tales algebras combinatorias son “patologicas” en sentido estandar:

Teorema 6.0 Si M es no trivial:

1. M no es commutativa

2. M no es asociativa

3. M es infinita


6.2.1 Interpretacion de λ–terminos con constantes

Sea M un algebra combinatoria. Se definen las abstracciones µx.A ∈ T enforma inductiva:

µx.x ≡ Iµx.A ≡ KA si x 6∈ Φ[A]µx.P Q ≡ S (µx.P ) (µx.Q)

6.2. Algebras combinatorias y λ–algebras 79

y de la misma forma µxy . . . z.A = µx.(µy. . . . (µz.A) . . . ). Por ejemplo,

µx.x z ≡ S (µx.x) (µx.z) ≡ S I (K z)µzx.x z ≡ µz.S I (K z) ≡ S (K (S I)) (S (K K) I)µz.I z ≡ S (K I) I

Teorema 6.1

1. Φ(µx.A) = Φ[A]− x

2. (µx.A) x = A

3. (µ~x.A) ~x = A

Demostracion: Por induccion estructural sobre A. 2

Hemos hablado de las interpretaciones de los terminos de T (M); la sim-ulacion de los λ–terminos en T permite considerar estos como λ–terminos yviceversa vıa dos funciones:

τ : Λ → T λ : T → Λ

definidas (escribimos Aτ = τ(A), Aλ = λ(A)):

xτ = x xλ = xcτ = c cλ = c(M N)τ = Mτ Nτ (M N)λ = Mλ Nλ

(λx.M)τ = µx.Mτ Kλ = λxy.xSλ = λxyz.x z (y z)

y puede probarse (por induccion estructural) que

∀A ∈ Λ :: Aτ,λ = A(∀A : A ∈ T : Aτ,λ = A) ⇔ (Kλ,τ = K) ∧ (Sλ,τ = S)

Observese, por el primero de los resultados anteriores, que tambien se tiene queKτ,λ = K y que Sτ,λ = S.

Ahora podemos definir la interpretacion de λ–terminos y su igualdad en M:

[A] = [Aτ ]M |= A = B ⇔ M |= Aτ = Bτ

6.2.2 λ–algebras

El proceso de calculo en M induce un calculo o reduccion en T (M). Veamosun


EJEMPLO 6.0. Si K,S ∈ T corresponden a k y s, y se define I = S K K,entonces se tiene

M |= I x = x

En efecto:

[I] = i = k s s [I x]ρ = [I] ρ x = i (ρ x) = ρ x = [x]ρ

♣Luego parece claro que si podemos demostrar con el calculo en M que

[A] = [B], los terminos seran iguales en M (por definicion); en consecuencia, seidentifica el proceso de calculo en M con la reduccion en T :

EJEMPLO 6.0. (continuacion)

I x = S K K x = K x (K x) = x

♣Veamos el proceso inverso:

Definicion 6.4 (λ–algebra) Un algebra combinatorio M se dice λ–algebra si(∀A,B ∈ T (M))

λC ` Aλ = Bλ ⇒ M |= A = B

2

EJERCICIO 6.1. Probar que M es un λ–algebra si y solo si:

(1) ∀A, B : A, B ∈ Λ : λC ` A = B ⇒ M |= A = B(2) ∀A : A ∈ T : Aλ,τ = A

2

6.3 λ–modelos

6.3.0 Concepto y caracterizacion

De los resultados de la seccion anterior se deduce que el λ–calculo conterminos de T (M) no altera las igualdades en M. Pero esto no es cierto paralos λ–terminos; es decir, no todo lo demostrable en el λC con λ–terminos escierto en M, como podemos ver en el siguiente

EJEMPLO 6.2. Se tiene:

λC ` λz.(λx.x) z = λz.z

pero(λz.(λx.x) z)λ ≡ S (K I) I ≡ 1 I

6.3. λ–modelos 81

donde 1 ≡ S (K I), no necesariamente tiene el mismo significado (valor) que

(λz.z)λ ≡ I

♣El elemento 1 ≡ S (K I) juega un papel importante y verifica:

Lema 6.0 Si M es un λ–algebra, entonces en M se tiene:

(0) 1 x y = x y

(1) 1 = λxy.x y; en particular 1 a = λy.a y

(2) 1 es un elemento unidad sobre las abstraciones; es decir:

∀A ∈ T :: 1 (λx.A) = λx.A

(3) 1 1 = 1

(4) Si M es extensional, entonces 1 = I

(5) 1 = I no es suficiente para que M sea extensional

(6) Si consideremos el axioma de Meyer–Scott:

(MS) (∀x :: a x = b x) ⇒ (1 a = 1 b)

entoncesM es extensional ⇔ 1 = I ∧ MS


¿En que casos la reduccion en el λC conduce a igualdades en M? Si larespuesta fuera sı, la interpretacion de los distintos λ–terminos obtenidos du-rante un λ–computo (conversiones) es constante (es decir, las reducciones noalteran el valor en M (transparencia referencial)). Si ello ocurre, M se dira unλ–modelo.

Definicion 6.5 (λ–modelo) Las λ–algebras donde se verifica (MS) se llamanλ–modelos. 2

Como consecuencia del apartado (6) del lema anterior se deduce:

M es un λ–modelo ∧ 1 = I ⇔ M es extensional

Definicion 6.6 (Algebra combinatoria debilmente extensional) Un algebracombinatoria M se dice debilmente extensional (deb-ext) si, ∀A,B ∈ T , setiene en M:

∀x :: A = B ⇒ λx.A = λx.B

2


En un algebra combinatoria deb-ext, si dos terminos son iguales lo sontambien como funciones. Ademas, se tiene el siguiente

Lema 6.1

M es un λ–modelo ⇔ M es un λ–algebra deb-ext

Demostracion:

(⇒) : Como sabemos que si M es extensional, entonces M es un λ–modelo y1 = I, se tiene:

∀x :: A = B⇒ ! λC |= (λx.A) x = A, definicion de λ–algebra

∀x :: (λx.A) x = (λx.B) x⇒ ! (MS)

1 (λx.A) = 1 (λx.B)⇒ ! 1 = I

λx.A = λx.B

(⇐) :

∀x :: a x = b x⇒ ! por ser deb-ext

λx.a x = λx.b x⇒ ! lema anterior

1 a = 1 b2

6.3.1 El modelo de terminos

Sea ω una extension consistente del λC (es decir, tal que ω 6` S = K). Esfacil ver que la relacion

M =ω N ⇔ ω ` M = N

es una relacion de equivalencia en Λ; si denotamos con ((M)) la clase de equiv-alencia de M , y el conjunto cociente con Λ/ω, podemos construir dos algebrascombinatorias llamadas modelos de terminos:

M(ω) = 〈Λ/ω, •, ((K)), ((S))〉M0(ω) = 〈Λ0/ω, •, ((K)), ((S))〉

con la operacion:((M)) • ((N)) = ((M N))

Se tiene el siguiente teorema:

6.4. Modelos sintacticos 83

Teorema 6.2 Tomando M como M(ω) o bien como M0(ω),

1. Φ[M ] = x1, . . . , xn ∧ ρ xi = ((Pi)) ⇒ [M ]ρ = (([~x := ~P ]M))

2. ω ` M = N ⇒ M |= M = N

3. M(ω) y M0(ω) son λ–algebras

4. M = M0(ω)∨M y N son cerrados ⇒ ω ` M = N sii M |= M = N

5. M0(ω) es un λ–modelo

6. En todo λ–modelo se tiene que λC ` M = N ⇔ M = N


EJERCICIO 6.4. Sean M1 y M2 dos algebras combinatorias de la forma:

Mi = 〈Xi, •, ki, si〉

Un homomorfismo ϕ entre M1 y M2

ϕ : M1 →M2

es una aplicacion ϕ : X1 → X2 que conserva las constantes (k y s) y la aplicacion,es decir:

ϕ(ab) = ϕ(a)ϕ(b)ϕ(k1) = k2

ϕ(s1) = s2

Probar entonces que:

(a) Si M1 es un λ–algebra, entonces tambien lo es M2

(b) Si M1 es un λ–modelo, entonces tambien lo es M2

2

6.4 Modelos sintacticos

Definicion 6.7 (Entorno punteado) El entorno punteado ρ(x := a) es lafuncion:

ρ(x := d)(y) =

ρ(y) , si y 6= xd , si y = x

2


Lema 6.2

1. [x := BA]ρ = [A]ρ(x:=[B]ρ)

2. (M |= A = B) ∧ (M = N) ⇒ M |= x := MA = x := NB3. ρ(x := d)(x := e) = ρ(x := e)

4. x 6= y ⇒ ρ(x := d)(y := e) = ρ(y := e)(x := d)

Demostracion: (1) por induccion estructural, (2) se sigue facilmente de (1), y(3) y (4) son elementales. 2

Definicion 6.8 (Interpretacion sintactica) Siendo M aplicativa, una in-terpretacion sintactica sobre M es una aplicacion

I : Λ(M)× E →MI(M, ρ) ≡ [M ]ρ ∈M

verificando:

1. [x]ρ = ρx

2. [ca]ρ = a

3. [A B]ρ = [A]ρ [B]ρ

4. [λx.P ]ρ • a = [P ]ρ(x:=a)

5. Si ρ = ρ′ sobre Φ[M ], entonces [M ]ρ = [M ]ρ′ 2

Definicion 6.9 (Estructura sintactica) SiendoM aplicativa, M se dice unaestructura sintactica si existe una interpretacion sintactica sobre M. 2

Definicion 6.10 (λ–algebra sintactica) Una estructura sintacticaM se diceuna λ–algebra sintactica si se tiene:

λC ` M = N ⇒ M |= M = N

2

Definicion 6.11 (λ–modelo sintactico) Una estructura sintacticaM se diceun λ–modelo sintactico si se tiene:

(ξ) M |= (∀x :: M = N) ⇒ λx.M = λx.N

o equivalentemente:

(∀a :: [M ]ρ(x:=a) = [N ]ρ(x:=a)) ⇒ [λx.M ]ρ = [λx.N ]ρ

2

6.4. Modelos sintacticos 85

Observese la importancia de la propiedad (ξ); si se considera la funcionfM : M→M descrita por δa.[M ]ρ(x:=a), dicho axioma establece que

fM = fN ⇒ λx.M = λx.N en M

que se interpreta en la forma siguiente: si M = N en M, sus valores comoterminos funcionales tambien coinciden, lo cual equivale a la extensionalidaddebil.

Lema 6.3 Sea M un λ–modelo sintactico. Entonces:

1. Si x 6∈ Φ[M ], entonces

∀d ∈M :: [M ]ρ(x:=d) = [M ]ρ∀d, e ∈M :: [M ]ρ(x:=d)(y:=e) = [M ]ρ(y:=e)

2. ∀ρ ∈ ξ :: [x := NM ]ρ = [M ]ρ(x:=[N ]ρ)

Demostracion:

1. Elemental.

2. Consideremos el predicado:

ϕ(M,N) ≡ ∀ρ :: [x := NM ]ρ = [M ]ρ(x:=[N ]ρ)

Vamos a demostrar sucesivamente:

(a) z 6∈ φ(M) ⇒ ϕ(M, z)

(b) ϕ(M, N) ⇒ ϕ(λy.M, N)

(c) ϕ(M, N)

Una vez demostrados (a) y (b), (c) se prueba por induccion estructural;en efecto, por la definicion de interpretacion sintactica se prueban direc-tamente:

ϕ(x,N) ∧ ϕ(ca, N)

mientras que

(ϕ(A,N) ∧ ϕ(B,N)) ⇒ ϕ(A B,N)

se deduce de la propiedad (3) de las interpretaciones sintacticas. Final-mente, el caso de las abstracciones se concluye directamente de (b). Quedaentonces probar (a) y (b):

• (a) se demuestra por induccion estructural

• (b) es facil por los resultados anteriores y utilizando el axioma (ξ).2


Teorema 6.3 Sea M un λ–modelo sintactico. Entonces,

λC ` M = N ⇒ M |= M = N

es decir, todo λ–modelo sintactico es una λ–algebra sintactica.

Demostracion: Basta demostrar que las reglas de la λ–teorıa son ciertas en M;ası, habra que demostrar, entre otras cosas, que en M se tienen:

(β) (λx.M) N = x := NM(ξ) M = N ⇒ λx.M = λx.N

ya que el resto de reglas (sustituiva, . . . ) son ciertas trivialmente. La ξ–regladel λC se deduce directamente de ser λ–modelo. Veamos finalmente la β–regla;para cada entorno ρ ∈ ξ:

[(λx.M) N ]ρ= ! propiedad 3 de interpretacion sintactica

[λx.M ]ρ [N ]ρ= ! propiedad 4 de interpretacion sintactica

[M ]ρ(x:=[N ]ρ)

= ! apartado 2 del lema anterior

[x := NM ]ρ2

Tenemos por todo ello que todo λ–modelo sintactico es un λ–modelo, y quetoda λ–algebra sintactica es una λ–algebra. A continuacion vamos a ver comoconstruir modelos a partir de dominios reflexivos.

6.5 Modelos sobre dominios reflexivos

Definicion 6.12 (Dominio reflexivo) Un dominio D es un dominio reflexivo(es decir, isomorfo a [D → D]) si existen funciones F y G continuas

DF−→ [D → D] G−→ D

tales que, siendo i la funcion identidad:

F G = i G F = i

2

Para D puede tomarse, por ejemplo, D∞.

Si D es reflexivo, se puede dotar a D de estructura aplicativa en la forma:

x · y = (F (x))(y)

6.5. Modelos sobre dominios reflexivos 87

que hace que tal estructura sea extensional; en efecto (escribimos xy en lugarde x · y):

∀e :: de = d′e= ! definicion de ·

∀e :: (F (d))(e) = (F (d′))(e)⇒ ! definicion de igualdad de funciones

F (d) = F (d′)⇒ ! aplicando G

G(F (d)) = G(F (d′))⇒ ! G F es la funcion identidad

d = d′

Teorema 6.4 Sea D un dominio reflexivo y (·) su estructura aplicativa; puededefinirse una interpretacion [ ] sobre D tal que M = (D, ·, [ ]) sea un λ–modelosintactico (en particular, un λ–modelo) extensional.

Demostracion: Sea la interpretacion:

1. [x]ρ = ρx

2. [ca]ρ = a

3. [A B]ρ = [A]ρ · [B]ρ

4. [λx.P ]ρ = G(δd.[P ]ρ(x:=d))

En primer lugar vamos a ver que esta bien definida; es decir, que la apli-cacion:

δd.[P ]ρ(x:=d)

es continua (en la variable d). Ello se demuestra por induccion estructuralsobre M : si M es una variable, constante o de la forma M ≡ A B es trivial (porhipotesis de induccion), mientras que si M ≡ λy.P entonces:

[λy.P ]ρ(x:=d) = G(δe.[P ]ρ(x:=d)(y:=e)

que es composicion de una funcion continua (en la variable d) con la funcion G,tambien continua.

Hemos de probar tambien que:

(a1) [ ] es una interpretacion sintactica

(a2) [ ] verifica la (ξ)–regla:

(ξ) M |= (∀x :: M = N) ⇒ λx.M = λx.N

o equivalentemente:

(∀a :: [M ]ρ(x:=a) = [N ]ρ(x:=a)) ⇒ [λx.M ]ρ = [λx.N ]ρ


Para (a1) hemos de probar las condiciones (1)–(5) de la definicion de inter-pretacion sintactica; las tres primeras son triviales, la quinta se prueba porinduccion, y la demostracion de la cuarta serıa:

[λx.P ]ρ · a= ! definicion de interpretacion

G(δd.[P ]ρ(x:=d)) · a= ! definicion de ·

(F (G(δd.[P ]ρ(x:=d))))(a)= ! F G es la funcion identidad, δ–abstraccion

[P ]ρ(x:=a)

Finalmente, veamos la de (a2):

∀a :: [M ]ρ(x:=a) = [N ]ρ(x:=a)

⇒ ! δ–abstraccion

δa.[M ]ρ(x:=a) = δa.[N ]ρ(x:=a)

⇒ ! aplicando G

G(δa.[M ]ρ(x:=a)) = G(δa.[N ]ρ(x:=a))⇒ ! definicion de interpretacion

[λx.M ]ρ = [λx.N ]ρ2

6.6 Incompletitud de los λ–modelos

6.6.0 El teorema de Bohm

En todo λ–modelo (sintactico) se tiene

λC ` M = N ⇒ M |= M = N

pero las igualdades en M no implican igualdades en el λC:

EJEMPLO 6.3. Teniendo que:

M ≡ λx. + x x N ≡ λx. ∗ 2 x

entonces M =M N pero no podemos reducir M a N . ♣El ejemplo anterior ilustra el hecho de que el modelo es incompleto. La pre-

gunta que podemos hacernos es la siguiente: ¿bajo que condiciones la igualdadM =M N (en M) implica la igualdad M =β N (en Λ)? Veremos que estoocurre si M y N tienen ambos formas normales. Todo ello sera consecuenciadel teorema de Bohm.

Identificamos los elementos de Λ con los correspondientes en D (es decir,M ≡ [M ]ρ); tambien identificamos los elementos de D como operadores yoperandos (es decir, D ≡ [D → D]), por lo que si no existe confusion escribimosM N en lugar de (F (M))(N).

6.6. Incompletitud de los λ–modelos 89

La relacion ≤D sobre D (escribiremos ≤ si no hay confusion) induce unarelacion de orden en Λ:

M ≤Λ N ⇔ (∀ρ :: [M ]ρ ≤ [N ]ρ)

Tal relacion es sustitutiva, es decir, si M ≤ N entonces C[M ] ≤ C[N ] paracualquier contexto C[ ]. Esto ultimo puede probarse utilizando la continuidad;por ejemplo, para el caso de la aplicacion:

M ≤Λ N= ! definicion de la relacion ≤Λ

∀ρ :: [M ]ρ ≤D [N ]ρ⇒ ! continuidad (y por tanto, monotonıa)

∀ρ,A :: (F ([A]ρ))([M ]ρ) ≤D (F ([A]ρ))([N ]ρ)⇒ ! definicion de ·

∀ρ,A :: [A]ρ · [M ]ρ ≤ [A]ρ · [N ]ρ⇒ ! definicion de interpretacion

∀ρ,A :: [A M ]ρ ≤ [A N ]ρ⇒ ! definicion de ≤Λ

∀A :: A M ≤Λ A N

Lema 6.4 Siendo K = λxy.x, I = λx.x, para la relacion de orden definidaanteriormente se tiene:

1. K y K I son incomparables (como elementos de Λ)

2. I y K son incomparables

Demostracion:

1. Si K ≤ K I se tendrıa, para cualesquiera elementos x, y ∈ D:

x = K x y ≤ K I x y = y

luego x ≤ y; de forma similar se prueba que y ≤ x, con lo cual x = y. Deello se deduce que D tendrıa un solo elemento, es decir, serıa un modelotrivial cuando solo estamos considerando modelos no triviales.

2. Si I ≤ K entonces:

x = I I (K x) y ≤ K I (K x) y = y

y se procede de la misma forma que en el apartado anterior.2

Definicion 6.13 (Terminos separables) Dos terminos M y N son separa-bles si existe un contexto C[ ] tal que C[M ] = I y C[N ] = K. 2


Teorema 6.5 (Bohm) Si M y N tienen formas normales distintas, entoncesson separables.

Demostracion: Puede verse en [Bar84]. 2

Corolario 6.0 Si M y N tienen formas normales distintas, entonces:

1. Si extendemos la igualdad (conversion) con el axioma M = N , entoncesla teorıa es inconsistente

2. M y N son incomparables

Demostracion:

1. Como M y N tienen formas normales distintas, por el teorema de Bohmsabemos que son separables, es decir, que existe un contexto C[ ] tal que:

C[M ] = I C[N ] = K

de donde

C[M ] I (K X) Y = X C[N ] I (K X) Y = Y

y en caso de ser ` M = N se tendrıa ∀X,Y :: ` X = Y , lo cual es unainconsistencia con la suposicion de que el modelo es no trivial.

2. Si M ≤ N , entonces se tendrıa

I = C[M ] ≤ C[N ] = K

que sabemos que es falso por el segundo apartado del lema anterior.2

NOTA Segun el teorema de Church–Rosser, si M y N tienen FN distintas nopodemos probar la igualdad M = N por reduccion. Por otra parte, el teoremade Bohm es un resultado mas fuerte: no solamente no es demostrable la igual-dad, sino que al considerarla se introducen inconsistencias. ♠

Ası pues, para los terminos que admiten forma normal la igualdad en Λequivale a la igualdad en D y a la convertibilidad de ambos terminos a la mismaforma normal por reduccion normal.

Teniendo en cuenta las identificaciones de Λ en D, puede demostrarse elsiguiente:

Teorema 6.6 Con respecto a los λ–modelos sintacticos:

• El λC es incompleto

• Si restringimos el λC a los terminos con forma normal, entonces es com-pleto

Demostracion: Puede verse en [Bar84]. 2

6.6. Incompletitud de los λ–modelos 91

6.6.1 Resolubilidad y resultados de complitud

Teorema 6.7

• Si se anade al λC el axioma:

(IRRES) M, N irresolubles ⇒ ` M = N

entonces la teorıa resultante λ∗ = λ ∪ IRRES es consistente.

• Si U es irresoluble, entonces λ∗ ∪ (I = U) es inconsistente.

• Si S es resoluble y U es irresoluble, entonces λ∗∪(S = U) es inconsistente.

• M 6=D N si y solo si λ∗ ∪ (M = N) es inconsistente.


La teorıa λ∗ es un modelo completo, aunque esto ultimo tiene un problema:que la irresolubilidad de terminos es indecidible (es decir, no existe un algoritmopara determinar cuando una igualdad es una instancia del axioma (IRRES)).

Para terminar veamos otros resultados de Wadsworth: si consideramos elelemento ⊥ (mınimo) de D, este sera la interpretacion del indefinido Ω (igual atodos los terminos irresolubles, es decir, sin FNC)

[Ω] = ⊥y en consecuencia:

[λx.Ω] = [Ω M ] =⊥

Por otro lado, en D (como en todo dominio) se puede obtener un funcionalde puntos fijos para cada f ∈ D (identificada como elemento de [D → D]) dadopor:

Y(f) = limfn(⊥)

y precisamente este es la interpretacion de Y, el combinador paradojico deCurry:

[Y] = Y

Definicion 6.14 (Funcion estricta)

• Se dice que una funcion de un argumento f : D → D es estricta si

f(⊥) = ⊥

• Se dice que una funcion de n argumentos f : Dn → D es estricta en sui–esimo argumento si

f(x1, . . . , xi−1,⊥, xi+1, . . . , xn) = ⊥ 2


La identificacion “indefinido=no-terminacion” tiene una interpretacion so-bre el modelo. Ası, si identificamos la no terminancion con ⊥, un curioso ra-zonamiento de Mycroft prueba que si f es estricta en su argumento i–esimo,entonces durante el computo de f(e1, . . . , en), si este termina, hay que evaluarnecesariamente e; en efecto, si el computo termina entonces f(e1, . . . , en) >⊥,de donde e >⊥; pero tal informacion es imposible si no se evalua e.

Si una funcion no es estricta se dice1 que es perezosa (lazy), ya que puedecomputarse una llamada a esta aunque algun argumento resulte indefinido. Lasfunciones estrictas o no-estrictas en un lenguaje funcional deben interpretarseen identica forma en el modelo; ası, pues tendremos:

[∗ a b] = [a]× [b] , si [a], [b] 6=⊥[∗ a b] = ⊥ , si [a] =⊥ o [b] =⊥

sin embargo

[if true a b] = [a] aunque [b] =⊥

1Esto es un abuso del lenguaje ya que el termino “perezoso” se utiliza como una tecnicade implementacion para semanticas no estrictas.

Part II

El λ–calculo con tipos

93

Part III

Apendices

95

Bibliography

[Abr90] Samson Abramsky. The Lazy Lambda Calculus, capıtulo 6,paginas 100–200. Addison–Wesley, 1990. En [Tur90].

[Bar84] Henk Barendregt. The Lambda Calculus: Its Syntax and Semantics.North-Holland, Segunda edicion, 1984. Revision de la primera edicion(1981).

[Bar91] Henk Barendregt. Self–interpretation in Lambda Calculus. Journal ofFunctional Programming, 1(2):229–233, Abril 1991.

[Dav89] Ruth Davis. Truth, Deduction, and Computation: Logic and Seman-tics for Computer Science. Computer Science Press, 1989.

[Dij89] Edger W. Dijkstra. A Discipline of Programming. Computer SciencePress, 1989.

[FH88] Anthony Field and Peter Harrison. Functional Programming.Addison–Wesley, 1988.

[Ham95] Kevin Hammond, editor. Report on the Programming LanguageHaskell, A Non-Strict Purely Functional Language, Version 1.3. In-forme tecnico, Universidad de Glasgow, Junio 1995.

[Pey87] Simon Peyton Jones The implementation of functional languages.Prentice–Hall, 1987.

[Rev88] Gyorgy Revesz. Lambda-calculus, Combinators and Functional Pro-gramming. Cambridge Tracts in Theoretical Computer Science, Cam-bridge University Press, 1988.

[Tur90] David Turner, editor. Research Topics in Functional Programming.Addison–Wesley, 1990.

97

el –c´alculo (sin tipos y con tipos) - umablas/apuntes/pdav/lambdac.pdf · el ‚–c´alculo...

Documents