9 de mayo de 2008

Entre paréntesis y lenguajes funcionales

"Si no creyera en la locura
de la garganta del cenzontle..."
-Silvio Rodríguez

Antes que nada una disculpa para mis lectores de Software Guru. Me confié demasiado del software de la empresa de las ventanitas y en mi columna de mayo-junio la letra griega λ (lambda) fue sustituida por un hermoso cuadradito. Estimados lectores, tomen un plumón y sustituyan todos los cuadraditos por la letra λ en su copia de la revista. Y en una futura entrada hablaremos de la interoperabilidad.

Por ahora, me dispongo a traducir el pequeño programa que presenté en mi columna.


(define infinito (λ ( ) ((λ (f) (f f)) (λ (f) (f f)))))


Este programa, escrito en el lenguaje Scheme, me gusta porque muestra la expresividad del lenguaje y el poder del cálculo lambda, en el que está basado. De manera adicional, demuestra algunos conceptos interesantes de teoría de la computación.

Primero defino la semántica de las expresiones define y λ, así como el uso de funciones:

  • (define var expr) asigna el resultado de evaluar la expresión expr a la variable var;
  • (x) expr) define la función que recibe el parámetro x, y que regresa el resultado de evaluar la expresión expr;
  • (f x) evalua la función f con el parámetro de entrada x.

Con estas definiciones podemos olvidar los paréntesis y nuestra expresión se ve menos intimidante:

(define infinito ( ) ((λ (f) (f f)) (λ (f) (f f)))))

Así, infinito es el nombre de una función sin parámetros de entrada que, de ser evaluada, regresa la expresión de color rojo. esta expresión en rojo es muy interesante. Veámosla a detalle, coloreando sus partes:

((λ (f) (f f)) (λ (f) (f f)))


Las expresiones verde y roja son de hecho la misma expresión, y ahora debe ser sencillo para el cibernauta descifrarla: (f) (f f)) es la función de parámetro f que regresa la expresión (f f) . Esta última, a su vez, ¡sería una función f evaluada en sí misma!

Con esta expresión vemos una de las características de los lenguajes funcionales: las funciones son ciudadanos de primer orden y pueden tratarse como cualquier parámetro o variable.

Descifremos al fin nuestra expresión:

  • (λ (f) (f f)) es una función que recibe la función f como entrada y regresa f evaluada en si misma. Llamemos a esta función cenzontle;
  • ((λ (f) (f f)) (λ (f) (f f))) es la función cenzontle evaluada en sí misma; lo interesante de la función cenzontle es que, al ser evaluada en sí misma, regresa exactamente la misma expresión, esto es, ¡la función cenzontle evaluada en sí misma! Este es uno de los ejemplos más simples y no triviales de un programa que se escribe a sí mismo (Esta función se conoce como la función Ω -Omega- en cálculo lambda);
  • finalmente, llegamos a nuestra expresión original, (define infinito ( ) ((λ (f) (f f)) (λ (f) (f f))))), que de manera simple y elegante, define infinito como una función que, al ser evaluada, regresa a la función que se replica eternamente a sí misma.

Para más información sobre Scheme y el calculo lambda pueden consultar la sección sobre el tema del sitio de Think Artificial.