PDF de programación - Lambda cálculo no tipado

Capítulo 1

Lambda cálculo no tipado

Vamos a revisar la definición y propiedades básicas del lambda cálculo puro o no

tipado.

A mediados de los 60s, Peter Landin observó que un lenguaje de programación
complejo podía ser formulado a través de un reducido núcleo y un conjunto de
expresiones derivadas que posteriormente serían traducidas a dicho núcleo. El núcleo
al que Peter Landin se refería era el lambda-cálculo, un sistema formal inventado en
los años 20 por Church en el que todos los cálculos se reducen a dos operaciones
básicas, la definición de funciones y su aplicación. Hoy en día, el lambda cálculo
se puede considerar como el más pequeño lenguaje universal de programación y se
utiliza habitualmente en el diseño e implementación de los lenguajes de programación
y en el estudio de los sistemas de tipos.

Existen otros sistemas alternativos al lambda-cálculo que pueden ser utilizados
para el mismo objetivo. El pi-cálculo se utiliza para definir la semántica de lenguajes
concurrentes basados en paso de mensajes. El object-cálculo se utiliza a su vez para
definir las características básicas de los lenguajes orientados a objetos.

El lambda-cálculo básico es extremadamente limitado, pero puede ser enrique-
cido de diferentes formas. Por ejemplo, introduciendo una sintaxis concreta para
ciertas características comunes como los números, las tuplas o los registros. Tam-
bién es posible introducir otros conceptos más avanzados como las referencias o las
excepciones.

1.1. Conceptos básicos

La definición de funciones es una de las características básicas de cualquier len-
guaje de programación. En lugar de escribir la misma fórmula una y otra vez, defi-
nimos una función o procedimiento realiza el cálculo de forma genérica en función
(o no) de un conjunto de parámetros. Por ejemplo, un programador sustituiría la
expresión:

(5 * 4 * 3 * 2 * 1) + (7 * 6 5 * 4 * 3 * 2 * 1) - (3 * 2 * 1)

por factorial(5) + factorial(7) - factorial(3) una vez definida la fun-

ción:

factorial(n) = if n = 0 then 1 else n * factorial(n-1)

1

2

Capítulo 1. Lambda cálculo no tipado

En el lambda-cálculo, la expresión ‘‘λn. ...’’ equivale “la función que, para
cada n devuelve ...”. Utilizando esta notación, podemos reescribir la función factorial
como:

factorial = λn. if n = 0 then 1 else n * factorial(n-1)

En el lambda-cálculo puro TODO son funciones, los parámetros de las funciones
son funciones, el resultado de las funciones también. La sintaxis es muy sencilla, pues
sólo existen tres tipos de términos: las variables, las abstracciones de una variable
en un término y la aplicación de un término a otro término.

t::=
x

λx.t
t t

Sintaxis concreta y abstracta

Al hablar de la sintaxis de un lenguaje de programación, debemos distinguir
entre la sintaxis concreta y la sintaxis abstracta. La sintaxis concreta es el conjunto
de cadenas de caracteres que los programadores utilizamos para escribir y leer los
programas. La sintaxis abstracta es una representación interna muy simplificada en
la que los términos se representan como árboles sintácticos.

La transformación entre la sintaxis concreta y la abstracta se lleva a cabo en dos
etapas. En primer lugar, un analizador léxico convierte las cadenas de caracteres es-
critas por el programador en un conjunto de tokens (identificadores, palabras claves,
puntuación, etc.). El analizador léxico elimina los comentarios y procesa los espacios
en blanco, los formatos de las cadenas de caracteres y números, etc. A continua-
ción, el parseador transforma la secuencia de tokens en un árbol sintáctico. Ciertas
convenciones como la precedencia de los operadores reducen la necesidad de incluir
paréntesis en la escritura de nuestros programas.

Gracias a las convenciones de asociatividad sabemos que la expresión 1 + 2 * 3

se corresponde con el árbol sintáctico de la izquierda, y no de la derecha.

La gramática del lambda cálculo básico debe ser entendida como la estructura de
árboles sintácticos y no como un conjunto de cadenas de caracteres utilizados en
una sintaxis concreta.

Para evitar el uso excesivo de paréntesis, utilizamos las siguientes convenciones:

1. La aplicación es asociativa por la izquierda s t u =>(s t) u.

1.1. Conceptos básicos

3

2. Los cuerpos de las abstracciones son asociativas por la derecha λx.λy.x y x

=>λx.(λy.((x y) x))

En las expresiones anteriores, las meta-variables t, s y u son términos, mientras

que x, y y z son variables concretas.

Ámbito

Una variable x está ligada cuando aparece en el cuerpo t de una abstracción del
tipo λx.t. Una variable x está libre si aparece en un punto no acotado por ninguna
abstracción de la forma λx. Ejemplos:

1. x es una variable libre en λy.x y.

2. x es una variable ligada en λx.x y en λx.λy. x (y z).

3. En (λx.x) x, la primera ocurrencia de x es libre y la segunda ligada.
Un término sin variables libres se denomina término cerrado o combinador. El

combinador más sencillo es la función identidad λx.x.

Semántica operacional

En su forma más pura, el lambda-cálculo no tiene constantes, números, opera-
dores aritméticos, condicionales, etc. La semántica operacional consiste únicamente
en la aplicación de funciones a argumentos (que a su vez son también funciones).
La aplicación de una abstracción se calcula substituyendo la variable acotada por el
término correspondiente en el cuerpo de la abstracción.

4

Capítulo 1. Lambda cálculo no tipado

(λx.t12) t2 → [x → t2]t12

La expresión (λx.t12) t2 se denomina redex y la operación de reescribir el redex

se denomina beta-reducción.

Ejemplos:

1. (λx.x) y se evalúa a y.

2. (λx.x (λx.x)) (u r) se evalúa a (u r) (λx.x).

Existen diferentes estrategias de evaluación en el lambda-cálculo, cada una de

las cuales indica qué redex debe ser evaluado en la siguiente evaluación.

Beta-reducción completa: cualquier redex puede evaluarse en cualquier momen-
to. En un determinado paso de la evaluación elegimos en redex que queremos
evaluar y lo reducimos. Por ejemplo, el término

(λx.x) ((λx.x) (λz.(λx.x) z))

puede reescribirse como id (id (λz.id z)) y contiene tres redexes:

id (id (λz.id z))
id (id (λz.id z))
id (id (λz.id z))

Si elegimos comenzar por el redex más interno, seguir por el del medio y acabar
con el más externo, la secuencia ejecutada será la siguiente:

id (id (λz.id z)) →
id (id (λz.z)) →
id (λz.z) →
λz.z

Orden normal: los redex que estén más hacia la izquierda (o los más externos)
son los que se evalúan primero.

id (id (λz.id z)) →
id (λz.id z) →
λz.id z →
λz.z

Llamada por nombre: similar a la estrategia anterior pero más restrictiva, pues
no permite llevar a cabo reducciones dentro de abstracciones.

1.2. Programación en el lambda-cálculo

5

id (id (λz.id z)) →
id (λz.id z) →
λz.id z

Esta estrategia es la utilizada por lenguajes de programación como Algol-60 o
Haskell. Haskel utiliza una variante más eficiente de la llamada por nombre, la
llamada por necesidad en la que, una vez evaluado un argumento, se sustituyen
todas las ocurrencias de dicho argumento con su valor, en lugar de re-evaluar
el argumento cada vez que se utiliza.

Llamada por valor: en cada paso de la evaluación se reduce el redex más ex-
terno. Además, un redex únicamente puede reducirse cuando el término a su
derecha ya ha sido reducido a un valor (un valor es una abstracción).

id (id (λz.id z)) →
id (λz.id z) →
λz.id z

En llamada por valor los argumentos de la función siempre se evalúan, aunque
luego no se usen en el cuerpo de la función. En otras estrategias como llamada
por nombre los argumentos no usados no llegan a evaluarse.

Nosotros vamos a utilizar la estrategia de llamada por nombre, porque ser una
de las más utilizada en los lenguajes de programación más populares (ML, Lisp, C,
Java) y por resultar muy sencillo su enriquecimiento con elementos como excepciones
o referencias.

1.2. Programación en el lambda-cálculo

El lambda-cálculo es mucho más potente de lo que su reducida definición podría
hacernos pensar. De hecho, vamos a comprobar cómo a través de términos del
lambda-cálculo podemos programar diferentes elementos habituales en los lenguajes
de programación de alto nivel, como los booleanos, los números o los pares.

Múltiples argumentos

El lambda-cálculo puro no permite la definición de funciones con varios argu-
mentos. Lo que sí permite es definir funciones que a su vez devuelvan funciones
como resultado. Si s es un término que utiliza dos variables libres x e y, y queremos
escribir una función f que para cada par de argumentos (v,w) devuelva el resultado
de sustituir x por v e y por w en s, lo que tenemos que hacer, en lugar de definir una
función f = λ(x,y).s es definir la función de alto orden f = λx.λy.s. Al aplicar
la función f a los argumentos v y w, lo que estamos haciendo es:

(f v) w → (δ y.[x → v]s) w → [y → w][x → v]s
La transformación de funciones con varios argumentos en funciones de alto nivel

se denomina decurrificar las funciones, en honor de Haskell Curry.

6

Capítulo 1. Lambda cálculo no tipado

Booleanos de Church

Otra de las características de un lenguaje de programación que puede ser fácil-
mente codificada con el lambda-cálculo son los booleanos. Los términos tru y fls,
que representan las constantes “true” y “false”, respectivamente, se definen como:

tru = λt.λf.t
fls = λt.λf.f

A partir de estos términos, podemos definir los condicionales. En la expresión:

test = λl.λm.λn.l m n

el booleano b es un condicional: toma dos argumentos y elige entre el primero (cuando
b es tru) o el segundo (cuando b es fls):

test tru v w
= (λl.λm.λn.l m n) tru v w
→ (λm.λn.tru m n) v w
→ (λn.tru v n) w
→ tru v w
= (λt.λf.t) v w
→ (λf.v) w
→ v

También podemos definir los operadores lógicos. El operador and se definiría

como:

and = λb.λc.b c fls

and recibe como en