Começando com o cálculo lambda e a programação funcional

O símbolo λ definie uma função que recebe alguns parâmetros, e o símbolo . separa os parâmetros do resultado. Por exemplo, λx.x é a função identidade f(x)=x. Aplicando λx.x no número 5 obtemos (λx.x)5 (também escrito como λx.x 5), que resulta em substituir x, retornando 5. Trivial? Por enquanto.

A função que retorna o quadrado de um número seria representada por λx.x*x. Mas aqui usamos o símbolo *, que ainda não foi definido em nossa linguagem. Deveríamos ter uma função multiplicadora que recebe dois argumentos, chamada m, e a função quadrado ficaria λx.mxx, isso é, f(x)=m(x,x). Como implementar a multiplicação? Usando o símbolo da soma, mas aí fica o problema de escrever o + funcionalmente... mas há até como representar isso apenas com funções, sem depender de nenhuma operação básica da matemática.

Vamos começar com algo mais simples, definindo duas funções que representam True e False:

Isso é, T é uma função que recebe dois parâmetros, e retorna o primeiro deles. Analogamente F retorna o segundo. Na verdade, todo lambda recebe apenas um único parâmetro, escreveríamos então que T é um lambda que recebe a e devolve um novo lambda que recebe b e que devolve sempre a, isto é, T ≡ λa.λb.a, que é a versão curried de λab.a e tem o mesmo resultado. Não há uma memória utilizada como habitual: os valores a e b estarão fechados dentro do contexto do primeiro e do segundo lambda.

Pode parecer difícil a princípio, mas é isso mesmo: verdadeiro e falso podem ser representados como funções. Podemos então "traduzir" um booleano nesse formato aplicando-o ao par de String "verdadeiro", "falso". Em ruby, conforme sugestão do Leonardo Bessa, teríamos:

Já conseguimos sinalizar se um booleano é falso ou verdadeiro apenas com funções (display[T], por exemplo). Mas isso é muito trivial, como ficam os operadores booleanos? Iniciando pela negação, ela pode ser definida da seguinte forma:

NOT é uma função que recebe um booleano, e devolve a aplicação desse booleano nos parâmetros F e T. Isso é possível pois aqui um booleano é uma função, e passamos essa função por parâmetro. Em código:

O AND e o OR lógico vão receber dois parâmetros, e vão seguir um raciocínio similar. No caso do AND, pegamos o primeiro booleano, se ele for verdadeiro, depende do segundo elemento (devolvemos ele então!), caso ele seja falso, retornamos falso diretamente. ```code AND ≡ λab.abF

E em Scheme, o dialeto LISP criado por Guy Steele (e um dos criadores também do... Java!), ficamos mais próximo ainda da sintaxe do cálculo lambda:

Isto é, dado dois elementos a pair, por exemplo 1 e 2, receberemos de volta uma função que por sua vez recebe outra função f e aplica-a nos argumentos anteriores (λf.fab). Aplicando head, por exemplo, em um par, o lambda λab.a será recebido como f e aplicado sobre os argumentos originais. Papel e caneta são bons nessas horas para fazer essa expansão passo a passo.

Repare que poderíamos escrever head e tail utilizando das funções T e F previamente criadas, passando-as como argumento à função par em questão, como por exemplo head ≡ λp.pT.

A solução em Scheme é bastante direta. Fica para você implementar esse código em ruby. É muito mais simples do que você imagina, e fará você compreender melhor a notação lambda. O Renato Lucindo possui uma versão em javascript.

Pode não ficar claro num primeiro instante, mas depois de escrever o código você terá um desses raros e importantes momentos "wow" da programação. Há uma outra representação funcional impressionante: o encoding de Church para números naturais, possibilitando escrever os números e operações aritméticas apenas com lambdas. Se isso é útil? É um passo importante para entender que programação funcional é muito mais que passar funções como argumentos, entender a importância das primitivas como o fold-right, compondo-as e enxergar que as possibilidades são grandes e o código mais sucinto, sem efeitos colaterais. Quando programamos em ruby, python ou scala, podemos aproveitar muito mais da linguagem com essas abstrações em mente.

Terminando com uma citação do Guy Steele, sobre a motivação de ter criado o Java, já que já havia criado o Scheme: "Nós não estavamos querendo ganhar os programadores LISP, estávamos atrás dos programadores C++. (Com Java) conseguimos trazer muitos deles meio caminho em direção ao LISP."

Agradecimentos a revisão do Ricardo Herrmann.