Читать книгу Computación y programación funcional - Camilo Chacón Sartori - Страница 13

El cálculo lambda es un modelo de computación que está basado en funciones computables. Fue creado por Alonzo Church y lo veremos con mayor detalle en la parte II del libro (capítulo 4), pero aquí daremos un esbozo general del modelo. Al igual que Alan Turing con su máquina de Turing, el cálculo lambda de Alonzo Church probó negativamente el problema de decisión.

A diferencia de la máquina de Turing, que tiene un proceso secuencial, el cálculo lambda construye la computación a través de funciones computables que se forjan en una notación formal con una gran expresividad. El cálculo lambda es una máquina de recursividad que cuenta con operadores, variables y operaciones de reducción (conocida como reducción b). Por tanto, hace un uso asiduo de la recursividad y de mantener estados inmutables en cada una de sus fases de reducción o derivación.

Antes de presentar una función lambda, es fundamental entender qué es una función matemática. Una función se puede definir de la siguiente manera: f:a → b, donde la función f recibe un valor a y devuelve b. Además, a y b pueden ser representados como conjuntos de elementos. Así, la función es una relación entre elementos de dos conjuntos.

Para nuestro ejemplo, el conjunto a se llama «dominio» y el conjunto b «codominio»; representan al conjunto de entrada y salida respectivamente. En notación conjuntista esta misma función puede ser definida de la siguiente manera: f(a) = b. Un ejemplo puede ser una función f que recibe un número entero que incrementa en 1. En este caso, f(x) = x + 1. Si a x se le asigna el valor 5, o sea, f(5) = 5 + 1, devolvería 6.

Entonces, volviendo a las funciones lambda, estas tienen como mecanismo de operación la reducción hasta donde sea posible. A esto lo llamamos computación.

Un ejemplo de función lambda es la siguiente:

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

donde la función lambda es (λx.(λy.y)x) y el argumento es (λy.y). Para derivar o reducir esta función se puede aplicar reducción β, que es una propiedad del cálculo lambda:

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

= (λy.y) (λy.y)

= (λy.y)

Termina las operaciones cuando alcanza la función (λy.y), que es, dicho sea de paso, una función de identidad que no puede ser reducida porque ya no tiene argumentos a la derecha. Para comprender esta reducción, vea la figura 1.5, donde se indica el argumento (desde donde nace la flecha, a la derecha), junto con la variable «X» (fase 1), y la variable «y» (fase 2) vendría a ser la posición donde dicho argumento tendrá su lugar (sustitución).

Básicamente, el primer paso es aplicar el primer argumento, (λy.y), a la función de la derecha. Y, debido a que toda variable que se encuentra a la derecha del símbolo λ se asocia a un argumento, esto quedaría así: [x:= (λy.y)]. Por lo tanto, se aplica una sustitución. (Una función lambda solo acepta un argumento.)

Así, a cada paso de reducción se aplica una sustitución de términos, hasta donde sea posible. Esto conlleva que la primera función exhibida se reduzca a la expresión (λy.y), donde ya no es posible continuar derivando.

Figura 1.5 Reducción de una función lambda, donde el primer argumento es (λy . y) y sustituye a la variable «X» definida dentro de la función lambda. Así, en la fase 2, se crea una reducción y vuelve a sustituir la siguiente variable, hasta llegar a la fase 3, donde ya no es posible aplicar ninguna otra reducción.

Podríamos decir que el cálculo lambda es un pequeño lenguaje de programación que permite expresar la computación a través de una sintaxis simple, acotada, flexible y, a su vez, poderosa. Algo para tener en cuenta es que una función lambda como (λ x.x) tiene una variable «X» que no especifica nada sobre el tipo de dato que tiene, es decir, este cálculo lambda es no tipado o libre de tipos, porque así fue presentado por Alonzo Church para la primera versión del cálculo lambda. La idea central, entonces, es ver que podemos manejar una función lambda como un valor y usarla como argumento de otra función lambda.

Esto último trae consigo alcances que explican las características de los lenguajes de programación funcionales y su surgimiento.