Cálculo lambda foi desenvolvido por Alonzo Church em 1936, e é, por assim dizer, o Assembly da matemática. O mais incrível é que esta pequena linguagem define apenas variáveis, funções com um único parâmetro e aplicação de funções. Mas não se engane, esta linguagem é Turing completa.

Comumente o cálculo lambda é definido como:

term : x                     ; variável
     | λ x.term              ; definição de função
     | term term             ; avaliação de função

A primeira alternativa corresponde a obter o valor de uma variável. A segunda é a definição de uma função cujo seu corpo é um termo. Já a última define a aplicação de uma função.

Neste artigo utilizaremos a linguagem Racket como ferramenta. Sendo assim, definiremos o cálculo lambda como um programa Racket:

term : x                     ; variável
     | (lambda (x) term)     ; definição de função
     | (term term)           ; avaliação de função

Observe que as definições são bem parecida. Isso porque Racket é uma linguagem da família Lisp, que foi desenvolvida utilizando o cálculo lambda como base.

Funções com Múltiplos Argumentos

Uma das coisas que você pode ter estranhado (e achado um tanto limitador) é o fato de o cálculo lambda apenas permitir a definição de funções de aridade 1. Como é que isso pode ser Turing completo?

Simples. Considere o seguinte exemplo:

(define sum (lambda (a) (lambda (b) (+ a b))))
((sum 1) 2)

Isso não é cálculo lambda (ainda), mas exemplifica como podemos simular o comportamento de uma função que recebe 2 parâmetros usando apenas funções que recebem um único parâmetro.

O truque é que (sum 1) retorna um função que recebe um parâmetro b e soma b com 1. Portanto ((sum 1) 2) retorna 3.

Mas e as funções que não recebem argumento algum? Bom, é só definir uma função de aridade 1 que descarta seu argumento:

(define one (lambda (dummy) 1))
(one #f)  ; -> 1
(one 42)  ; -> 1

Fica fácil perceber que utilizando essas técnicas podemos definir uma função de aridade qualquer.

Booleanos

Ok. Mas como definimos literais? Por exemplo, toda linguagem que se preze define os valores booleanos true e false. Se o cálculo lambda apenas possui funções, como podemos representar esses valores?

A ideia é bem simples:

(define @true (lambda (t) (lambda(f) t)))
(define @false (lambda (t) (lambda(f) f)))

Obs: Usaremos nomes começando com @ para evitar possíveis conflitos de nomes com a linguagem hospedeira.

Note que @true é um função que recebe 2 parâmetros e retorna o primeiro. Da mesma forma @false com a diferênça de que esta função retorna o segundo parâmetro.

Para facilitar a visualização desse valores, vamos definir uma função que converte valores @true e @false para booleanos em Racket:

(define (->boolean boolean) ((boolean #t) #f))

Obs: Usaremos nomes começando com -> para definir conversores de cálculo lambda para Racket.

(->boolean @true)   ; -> #t
(->boolean @false)  ; -> #f

Utilizando @true e @false fica bem fácil definir condicionais:

(define @if (lambda (condition) (lambda (t) (lambda (f)
  ((condition t) f)))))

Essa função @if não faz muita coisa. Ela apenas utiliza o próprio o valor booleano, que é passado como primeiro parâmetro, para decidir qual valor deve retornar: t ou f.

Um exercício legal é definir funções que combinam valores booleanos como @and, @or e @not:

(define @and (lambda (a) (lambda (b) ((a b) @false))))
(define @or (lambda (a) (lambda (b) ((a @true) b))))
(define @not (lambda (a) ((a @false) @true)))

Pares

Booleanos podem ser utilizados para definirmos pares:

(define @pair (lambda (first) (lambda (second)
  (lambda (boolean) ((boolean first) second)))))
(define @first (lambda (pair) (pair @true)))
(define @second (lambda (pair) (pair @false)))

E para ajudar na visualização:

(define (->pair pair) (list (@first pair) (@second pair)))

A ideia de @pair é que um par é um função que recebe um booleano. Se você passar @true para essa função, você recebe o primeiro valor. Se passar @false, recebe o segundo valor. Isso é exatamente o que as funções @first e @second fazem.

Números

Finalmente chegamos na definição de numerais. Um numeral em cálculo lambda é uma função que recebe dois parâmetros: Um valor que representa o valor inicial init e uma função succ que recebe um valor e computa seu próximo valor. Ou seja, @zero deve retornar init, @one deve retornar o valor da aplicação de succ recebendo @zero, @two deve retornar o valor da aplicação de succ recebendo @one e assim por diante:

(define @zero (lambda (succ) (lambda (init) init)))
(define @one (lambda (succ) (lambda (init) (succ init))))
(define @two (lambda (succ) (lambda (init) (succ (succ init)))))

O jeito mais simples de entender como essas funções funcionam é convertendo esses numerais para numerais em Racket:

(define (->number number) ((number (lambda (n) (+ n 1))) 0))

Aplicar ->number em @two resulta em (+ (+ 0 1) 1) que é justamente 2. Interessante, não?

Antes de definirmos operações aritméticas, como podemos encontrar o sucessor de um número?

(define @successor (lambda (number)
  (lambda (succ) (lambda (init) (succ ((number succ) init))))))

Como você pode ver, a função @successor não tem mistérios e é bem simples e direta. Mas o mesmo não é verdadeiro para @predecessor, que calcula o antecessor de dado um número:

(define @predecessor
  (lambda (number)
    (let ([zz ((@pair @zero) @zero)]
          [ss (lambda (p) ((@pair (@second p)) (@successor (@second p))))])
      (@first ((number ss) zz)))))

A ideia é que @predecessor constrói uma sequência de pares do tipo (n-1, n). A partir disso fica fácil encontrar o predecessor.

Vamos começar a definir as operações aritméticas. Primeiro vamos discutir a adição de dois números:

(define @add (lambda (a) (lambda (b)
  ((a @successor) b))))

Essa implementação é bem simples. Como a é uma função que aplica a função @successor a vezes e o valor inicial é b, temos que ao final dessa computação temos a + b.

A subtração pode ser definida de forma análoga:

(define @sub (lambda (a) (lambda (b)
  ((b @predecessor) a))))

Já que temos a adição, realizar a multiplica não é difícil:

(define @mul (lambda (a) (lambda (b) (
  (a (@add b)) @zero))))

A ideia é começar com 0 e ir somando b a vezes. Por exemplo, 3 x 2 = 0 + 2 + 2 + 2 = 6.

O mesmo princípio da multiplicação pode ser aplicado para calcular potências:

(define @pow (lambda (b) (lambda (e)
  ((e (@mul b)) @one))))

Neste caso 3^2 = 1 x 3 x 3 = 9.

E as operações lógicas? Como saber se um número é igual a outro? É só usar a subtração: se a - b = 0 então a = b. Para isso precisamos verificar se um número é igual a zero:

(define @zero? (lambda (n) ((n (lambda (_) @false)) @true)))

A função @zero? é trivial. Se o número for @zero, (lambda (_) @false) não será aplicada nenhuma vez, ou seja, retornará o valor inicial que é @true. Mas se o número for maior do que zero, (lambda (_) @false) será aplicada pelo menos uma vez e sempre retornará @false, fazendo com que @zero? retorne @false também.

Mas ainda temos um problema: Se olharmos com mais cuidado a definição de @sub veremos que a subtração 1 - 4, por exemplo, é igual a 0. Ou seja, não existem números negativos… como vamos contornar isso?

Vamos analisar caso a caso: Se a < b a primeira aplicação de @sub resulta em um número maior que zero e a segunda resulta em um número igual a zero. Se a > b o contrário acontece. Mas se a = b então ambas aplicações de @sub resultam em um número igual a zero. Esse raciocínio nos leva a seguinte implementação:

(define @eq (lambda (a) (lambda (b)
  ((@and (@zero? ((@sub a) b))) (@zero? ((@sub b) a))))))

(define @ne (lambda (a) (lambda (b)
  (@not ((@eq a) b)))))

(define @gt (lambda (a) (lambda (b)
  ((@and ((@ne a) b)) (@zero? ((@sub b) a))))))

(define @ge (lambda (a) (lambda (b)
  (@zero? ((@sub b) a)))))

(define @lt (lambda (a) (lambda (b)
  (@not ((@ge a) b)))))

(define @le (lambda (a) (lambda (b)
  (@not ((@gt a) b)))))

Listas

Podemos definir listas utilizando cálculo lambda. A ideia é que uma lista [x, y, z] é uma função que recebe dois argumento c e n e retorna (c (x (c (y (c (z n)))))). Podemos relacionar essa definição com listas em Lisp, onde c é cons e n é '().

(define @empty (lambda (c) (lambda (n) n)))
(define @cons (lambda (head) (lambda (alist)
  (lambda (c) (lambda (n) ((c head) ((alist c) n) ))))))

A partir dessas definições podemos criar uma lista assim: ((@cons @two) ((@cons @one) @empty)).

Uma forma de converter este tipo de listas em uma lista Racket é utilizando a função ->list-of-numbers:

(define (->list-of-numbers alist)
  (map ->number
       ((alist (lambda (head) (lambda (tail) (cons head tail)))) empty)))

As duas operações basicas de listas são obter seu primeiro elemento e obter o resto da lista:

(define @head (lambda (alist)
  ((alist (lambda (head) (lambda (tail) head))) @false)))
(define @tail (lambda (alist)
  (@first ((alist (lambda (x) (lambda (p) ((@pair (@second p)) ((@cons x) (@second p)))))) ((@pair @empty) @empty)))))

Recursão

Cálculo lambda, assim como outras linguagens funcionais, não define o conceito de laço (ou loop). Mas isso não é uma limitação, afinal podemos substituir laços por recursão.

O problema é que, como todas as funções definidas em cálculo lambda são anônimas, não podemos chamá-las diretamente por seus nomes. Note que aqui demos nomes a diversas funções (usando define), mas isso é apenas um artifício para melhorar a legibilidade do código e facilitar o estudo. Veja a definição de cálculo lambda no início deste artigo.

Uma forma de solucionar este problema é utilizando o chamado combinador de ponto fixo (também conhecido como combinador Y por chamada-por-valor).

O melhor texto que já li sobre o assunto é o do Matt Might. Sendo assim utilizarei os mesmo exemplos.

Considere a equação $x = x^2 - 2$. Podemos dizer que a variável $x$ é definida recursivamente, ou seja, em termos de si mesma. Resolver essa equação é trivial (bhaskara, etc…). Mas existe uma outra forma de resolver isso: Pontos fixos.

Um ponto fixo de uma função $f$ é um $x$ tal que $x = f(x)$. Mais ainda, as soluções da equação apresentada acima são os pontos fixos da função $f$: $Fix(f) = {-1, 2}$ já que $f(-1) = -1$ e $f(2) = 2$.

O objetivo agora passa a ser encontrar uma forma de obter os pontos fixos de uma equação na forma $f = F(f)$ onde $f$ não é um número, mas sim uma função. E é ai que entra o combinador de ponto fixo.

(define @fix (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))))

A função @fix é bem complexa e eu sugiro que você realize algumas simulações para seu entendimento completo. Veja um exemplo de uso:

(define factorial (@fix (lambda (fac)
  (lambda (n) (if (= (->number n) 0) @one ((@mul n) (fac (@predecessor n))))))))

Para facilitar estou usando o comando if de Racket. Mas você pode substituí-lo por @if do cálculo lambda facilmente (lembre-se que a avaliação em Racket é ávida e que você precisa “envelopar” os possíveis branches em funções):

(define factorial (@fix (lambda (fac)
  (lambda (n) ((((@if (@zero? n))
                      (lambda (x) @one))
                      (lambda (x) ((@mul n) (fac (@predecessor n)))))
                  @zero))))) ; avalia os branches do @if

Conclusões

Como pudemos ver, o cálculo lambda é extremamente simples, minimalista e poderoso. Recomendo a leitura de Types and Programming Languages de Benjamin C. Pierce, principalmente o capítulo 5 que cobre com maior profundidade o assunto.

Caso você queira o código completo desenvolvido nesse post, clique aqui.