1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
---
category: Algorithms & Data Structures
name: Lambda Calculus
contributors:
- ["Max Sun", "http://github.com/maxsun"]
- ["Yan Hui Hang", "http://github.com/yanhh0"]
translators:
- ["Ivan Alburquerque", "https://github.com/AlburIvan"]
---
# Cálculo Lambda
Cálculo Lambda (Cálculo-λ), originalmente creado por
[Alonzo Church](https://en.wikipedia.org/wiki/Alonzo_Church),
es el lenguaje de programación más pequeño del mundo.
A pesar de no tener números, cadenas, valores booleanos o cualquier
tipo de datos no funcional, el cálculo lambda se puede utilizar para
representar cualquier máquina de Turing.
El cálculo lambda se compone de 3 elementos: **variables**, **funciones** y
**aplicaciones**.
| Nombre | Sintaxis | Ejemplo | Explicación |
|-------------|------------------------------------|-----------|-----------------------------------------------|
| Variable | `<nombre>` | `x` | una variable llamada "x" |
| Función | `λ<parametro>.<cuerpo>` | `λx.x` | una función con parametro "x" y cuerpo "x" |
| Aplicación | `<función><variable o función>` | `(λx.x)a` | llamando a la función "λx.x" con el argumento "a" |
La función más básica es la función de identidad: `λx.x` que es equivalente a
`f(x) = x`. La primera "x" es el argumento de la función y la segunda es el
cuerpo de la función.
## Variables Libres vs. Enlazadas:
- En la función `λx.x`, "x" se llama una variable enlazada porque está tanto en
el cuerpo de la función como en el parámetro.
- En `λx.y`, "y" se llama variable libre porque nunca se declara de antemano.
## Evaluación:
Evaluación se realiza a través de
[β-Reduction](https://en.wikipedia.org/wiki/Lambda_calculus#Beta_reduction),
que es, esencialmente, sustitución de ámbito léxico.
Al evaluar la expresión `(λx.x)a`, reemplazamos todas las ocurrencias de "x"
en el cuerpo de la función con "a".
- `(λx.x)a` evalúa a: `a`
- `(λx.y)a` evalúa a: `y`
Incluso puedes crear funciones de orden superior:
- `(λx.(λy.x))a` evalúa a: `λy.a`
Aunque el cálculo lambda tradicionalmente solo admite funciones
de un solo parámetro, podemos crear funciones multiparamétricas usando
una técnica llamada [currying](https://en.wikipedia.org/wiki/Currying).
- `(λx.λy.λz.xyz)` es equivalente a `f(x, y, z) = ((x y) z)`
Algunas veces `λxy.<cuerpo>` es usado indistintamente con: `λx.λy.<cuerpo>`
----
Es importante reconocer que el cálculo lambda tradicional **no tiene números,
caracteres ni ningún tipo de datos que no sea de función.**
## Lógica Booleana:
No hay "Verdadero" o "Falso" en el cálculo lambda. Ni siquiera hay un 1 o un 0.
En vez:
`T` es representado por: `λx.λy.x`
`F` es representado por: `λx.λy.y`
Primero, podemos definir una función "if" `λbtf` que devuelve
`t` si `b` es Verdadero y `f` si `b` es Falso
`IF` es equivalente a: `λb.λt.λf.b t f`
Usando `IF` podemos definir los operadores lógicos booleanos básicos:
`a AND b` es equivalente a: `λab.IF a b F`
`a OR b` es equivalente a: `λab.IF a T b`
`a NOT b` es equivalente a: `λa.IF a F T`
*Note: `IF a b c` es esencialmente diciendo: `IF((a b) c)`*
## Numeros:
Aunque no hay números en el cálculo lambda, podemos codificar números usando
[Númeral de Church](https://en.wikipedia.org/wiki/Church_encoding).
Para cualquier número n: <code>n = λf.f <sup> n </sup></code> así:
`0 = λf.λx.x`
`1 = λf.λx.f x`
`2 = λf.λx.f(f x)`
`3 = λf.λx.f(f(f x))`
Para incrementar un númeral de Church, usamos la función sucesora
`S(n) = n + 1` que es:
`S = λn.λf.λx.f((n f) x)`
Usando el sucesor, podemos definir AGREGAR:
`AGREGAR = λab.(a S)n`
**Desafío:** intenta definir tu propia función de multiplicación!
## Vamos más pequeño: SKI, SK y Iota
### Combinador de SKI
Sean S, K, I las siguientes funciones:
`I x = x`
`K x y = x`
`S x y z = x z (y z)`
Podemos convertir una expresión en el cálculo lambda en una expresión
en el cálculo del combinador de SKI:
1. `λx.x = I`
2. `λx.c = Kc`
3. `λx.(y z) = S (λx.y) (λx.z)`
Tome el número 2 de Church por ejemplo:
`2 = λf.λx.f(f x)`
Para la parte interior `λx.f(f x)`:
```
λx.f(f x)
= S (λx.f) (λx.(f x)) (case 3)
= S (K f) (S (λx.f) (λx.x)) (case 2, 3)
= S (K f) (S (K f) I) (case 2, 1)
```
Asi que:
```
2
= λf.λx.f(f x)
= λf.(S (K f) (S (K f) I))
= λf.((S (K f)) (S (K f) I))
= S (λf.(S (K f))) (λf.(S (K f) I)) (case 3)
```
Para el primer argumento `λf.(S (K f))`:
```
λf.(S (K f))
= S (λf.S) (λf.(K f)) (case 3)
= S (K S) (S (λf.K) (λf.f)) (case 2, 3)
= S (K S) (S (K K) I) (case 2, 3)
```
Para el segundo argumento `λf.(S (K f) I)`:
```
λf.(S (K f) I)
= λf.((S (K f)) I)
= S (λf.(S (K f))) (λf.I) (case 3)
= S (S (λf.S) (λf.(K f))) (K I) (case 2, 3)
= S (S (K S) (S (λf.K) (λf.f))) (K I) (case 1, 3)
= S (S (K S) (S (K K) I)) (K I) (case 1, 2)
```
Uniéndolos:
```
2
= S (λf.(S (K f))) (λf.(S (K f) I))
= S (S (K S) (S (K K) I)) (S (S (K S) (S (K K) I)) (K I))
```
Al expandir esto, terminaríamos con la misma expresión para el número 2 de Church nuevamente.
### Cálculo del combinador SKI
El cálculo del combinador SKI puede reducirse aún más. Podemos eliminar
el combinador I observando que `I = SKK`. Podemos sustituir
todos los 'I' con `SKK`.
### Combinador Iota
El cálculo del combinador SK todavía no se encuentra en su expresión mínima.
Definiendo:
```
ι = λf.((f S) K)
```
Tenemos que:
```
I = ιι
K = ι(ιI) = ι(ι(ιι))
S = ι(K) = ι(ι(ι(ιι)))
```
## Para una lectura más avanzada:
1. [A Tutorial Introduction to the Lambda Calculus](http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf)
2. [Cornell CS 312 Recitation 26: The Lambda Calculus](http://www.cs.cornell.edu/courses/cs3110/2008fa/recitations/rec26.html)
3. [Wikipedia - Lambda Calculus](https://en.wikipedia.org/wiki/Lambda_calculus)
4. [Wikipedia - SKI combinator calculus](https://en.wikipedia.org/wiki/SKI_combinator_calculus)
5. [Wikipedia - Iota and Jot](https://en.wikipedia.org/wiki/Iota_and_Jot)
|
