Música Lambda (II): el cálculo (I)

En esta ocasión vamos a hacer una presentación bastante informal del cálculo lambda para luego, en subsecuentes capítulos o entradas del blog, dar una idea de cómo puede ser aplicado este formalismo para describir procesos musicales. El cálculo lambda es un lenguaje artificial o formal que constituye el fundamento de un paradigma de los lenguajes de programación: la programación funcional. De hecho, se podría decir que el primer lenguaje de programación funcional fue el cálculo lambda, ideado en la década de 1930 por Alonzo Church (1903 - 1995) como un entorno preciso y propicio para estudiar funciones matemáticas y el concepto de computabilidad.

En matemática definimos una función como una manera de asociar, proyectar o hacer corresponder los objetos de un conjunto, que pueden ser números, con los objetos de otro conjunto, que también pueden ser números. Esto lo expresamos mediante enunciados como:

y = f(x), donde 
f(x) = x + x

x + x", es decir, el valor de y, de acuerdo a la función f, es el doble del valor de x: f proyecta cualquier valor x hacia su doble. Entonces, si en la función f reemplazamos las x por 2, obtendremos 4 como el valor de y.  En este caso decimos que hemos aplicado la función f(x), que asocia un valor con su doble, al número 2, el argumento de la función, y como resultado hemos obtenido 4, el valor de y.

La notación lambda está pensada para representar visualmente y de forma precisa el proceso de aplicación de una función a sus argumentos. Trata al proceso de aplicación como una operación y lo expresa mediante una notación que pone en una línea primero la función y luego el argumento:

f(x) 2 

El resultado de la aplicación propiamente dicha se llama reducción:

f(x) 2 = 4 

Además, la notación lambda expresa qué ocurre cuando aplicamos una función: en vez de usar una letra como f para representar una función emplea la función misma:

(x + x) 2 = 4 

Pero para precisar todavía más la notación de funciones, el cálculo lambda incluye un operador adicional, el operador de abstracción λ, el cual permite definir funciones. Gottlob Frege, un importante lógico alemán, observó que podemos obtener una función reemplazando uno o mas terminos de una oración
 por una variable. A esta operación Frege la llamó abstracción. Entonces si tenemos una expresión como:

2 + 2

Por abstracción puedo obtener la siguente función:

f(x) = x + x

Se trata de una generalización que expresa la operación que consiste en sumar cualquier cantidad a sí misma, es decir la operación de duplicar una cantidad.

En notación lambda sería:

λ.x (x + x)

Como puede observarse, en el calculo lambda definimos una función a través de la operación de abstracción y ligando las variables al operador de abstracción lambda, no es necesario indicar el nombre de la función, se trata de describir que ocurre en una función cuando es aplicada.

La ligadura del operador de abstracción lambda es importante porque permite precisar, en funciones de más de una argumento. el orden en que las variables van a ser sustituidas por los objetos al cual es aplicada una función. Por ejemplo, a partir de la expresión siguiente:

(4 + 9 - 1) 

Por abstracción lambda podemos obtener la expresión:

λ.x λ.y(2x² + 3y - 1) 

Al ser aplicada a dos números enteros obtengo diferentes valores. El operador lambda nos dice cuál es el orden de sustitución. Si aplicamos esa función a 1 y 3, tendremos:

[λ.x  λ.y  (2x² + 3y - 1)] 1 3

[λ.y ((2 * 1)² + 3y - 1)] 3

(2 * 1)² + (3 * 3) - 1)

4 + 9 - 1

12 

Obsérvese que si cambiamos el orden de las ligaduras obtenemos:

[λ.y λ.x (2x² + 3y - 1)] 1 3

[λ.x  (2x² + (3 * 1) - 1)] 3

(2 * 3)² + (3 * 1) - 1)

36 + 3 - 1

38

El operador lambda, ademas de permitir describir con precisión qué ocurre cuando aplicamos una función, facilita o permite pasar funciones como argumentos a funciones de orden mayor y de esta manera podemos operar sobre funciones como si se tratara de un objeto:

[λf. λx. f x] [λ.y (y + y)] 5

Aquí estamos pasando la función "[λy. (y + y)]" como primer argumento a la función "[λf. λx. f x]". Aplicando la función "[λy. (y + y)]" a sus argumentos obtenemos:

[λf. λx. f x] [λ.y (y + y)] 5

[λx. [λ.y (y + y)] x] 5

[λ.y (y + y)] 5

5 + 5

10

Esta peculiaridad, la posibilidad de tratar a las funciones como argumentos de otras funciones, es uno de los principales aspectos que distingue a los llamados lenguajes funcionales, donde todas las expresiones, complejas o simples, siempre son funciones, siendo los objetos constantes o términos símbolos de funciones con cero argumentos y que siempre tienen como valor su propio nombre o símbolo.

Al describir con gran precisión qué ocurre cuando definimos una función (operación de abstracción) y cuando aplicamos una función a sus argumentos (operación de aplicación), el cálculo lambda nos da una definición rigurosa de computabilidad, lo cual permitió a Church demostrar la imposibilidad de solucionar algunos problemas usando procedimientos computacionales. Como puede observarse, el cálculo lambda fue pensado para cumplir una tarea estrictamente teórica. Sin embargo, al definir de una manera simple la noción de cómputo en términos algorítmicos concretos, estableció las operaciones y estructura mínima que necesita un lenguaje donde podemos expresar problemas que puedan ser computados por una máquina; por eso podemos decir que el cálculo lambda fue el punto de partida y el principal paradigma para el diseño de lenguajes de programación funcionales con utilidad práctica.

Operaciones del cálculo lambda

Como hemos visto, el cálculo lambda se basa en dos operaciones: la aplicación de una función a sus parámetros, y la abstracción a través de la cual defino una función estableciendo en una expresión el orden de aplicación de los parámetros. Una manera sencilla de entender estas operaciones es empleando expresiones del lenguaje cotidiano como funciones de verdad, es decir, enunciados que pueden ser evaluados para verificar si son verdaderos o falsos. Supongamos que en una habitación hay tres personas y expreso:

"En esta habitación hay tres personas".

Estaría diciendo la verdad. Supongamos que ahora escribo:

"En esta habitación hay n personas".

Al reemplazar la palabra tres por una variable n que puede ser sustituida por cualquier numero natural, estoy definiendo una función que proyecta números naturales a valores de verdad, ya que su valor, el hecho de ser verdadera o falsa, depende del número que use para sustituir la variable n. Si usamos la letra P para reemplazar nuestra proposición podemos escribir:

P := "En esta habitación hay n personas"

Entonces:

P 1 = falso
P 2 = falso
P 3 = verdadero
P 4 = falso

La acción de especificar en un enunciado, a través del uso de una variable, un término que puede ser sustituido define una función. A esta operación la llamamos abstracción. En el cálculo lambda esta operación se realiza usando el operador lambda, cuya utilidad se hace clara cuando usamos funciones de más de un parámetro. Definamos la función f:

f := λ.n m("En m hay n personas").

Estamos definiendo una función f de dos argumentos. Se podría decir que la abstracción consiste en reemplazar un término en una oración por una variable que queda ligada a través del operador de abstracción lambda. Al hacer esto, convertimos una oración en una función. Por ejemplo, aplicando abstracción a la oración:

Beethoven nació en Bohm

Reemplazando Beethoven por x, obtenemos:

λ.x (x nació en Bohm))

Es una expresión que es verdadera si reemplazamos la x  por Beethoven o por cualquier otro nombre de persona que nació en Bohm. De paso, podríamos afirmar que la expresión x nació en Bohm define una clase, la de todos aquellos nacidos en Bohm, y que todos aquellos nacidos en Bohm son el rango o recorrido de esa función. Obsérvese que por este procedimiento obtengo también un objeto específico, es decir, de esta manera se puede construir funciones y tratarlas como un objeto más del sistema.

La otra operacióncdel cálculo lambda es la aplicación que consiste en reemplazar las variables ligadas al operador lambda en el orden indicado por éste y se expresa poniendo los argumentos en secuencia después del nombre de la función, en el orden indicado por el operador lambda:

λ.n λ.m("En m hay n personas") 2 "esta habitación" => 

λ.m("En m hay 2 personas") "esta habitación" =>

"En esta habitación hay 2 personas")

Es importante notar como la aplicación de funciones a varios parámetros se realiza. Aquí se ha seguido el procedimiento llamado currificación, el cual consiste en realizar aplicaciones sólo sobre un parámetro a la vez. Cuando hay más de un parámetro, la aplicación de la función al primer parámetro producirá una nueva función que se aplicará al siguiente parámetro, y así hasta que se ha aplicado la función original a todos los parámetros. Al proceso en el que una expresión lambda expresada como la aplicación de una función a sus parámetros es transformada en una expresión saturada, se le llama reducción.

Podemos ver también que el cálculo lambda  puede ser usado para representar la sintaxis de la oraciones de un lenguaje natural. Es decir, el dominio al cual puede ser aplicado el calculo lambda no se restringe a números y funciones matemáticas. Hemos visto que funciona en la lógica de los lenguajes naturales y veremos que también puede ser empleado sobre objetos musicales.

---

Referencias

Church, Alonzo (1936): "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics, Vol. 58, No. 2. (Apr., 1936), pp. 345-363