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

Na Caelum há muitos interessados e entusiastas da programação funcional pura, e resolvi ler o Structure and Interpretation of Computer Programs, clássico curso introdutório do MIT, por indicação do Rafael Ferreira, Renato Lucindo, Pedro Matiello e outros amigos. O livro é muito interessante para quem não conhece nenhum dialeto LISP, como eu. Mesmo se você conheça bem uma linguagem mais funcional como Ruby, ou esteja entrando em Scala, Clojure, Fantom, CAL e outras funcionais que rodam na JVM, vai aprender muito a como pensar diferente, e não cair na armadilha de usar esse paradigma como um simples truque para avaliar predicados em coleções.

O livro fala por diversas vezes, mas sempre en passant, do lambda calculus. Parei um pouco a leitura para estudar mais da formalidade criada por Alonso Church (orientador do Turing!) e do que é possível fazer apenas com funções, base para a criação do Lisp por John McCarthy na década de 60. Aliás, tudo é possível, já que o cálculo lambda é Turing complete.

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:

T ≡ λab.a   F ≡ λab.b

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:

T = lambda { |a,b| a } 
F = lambda { |a,b| b } 
display = lambda { |boolean| boolean['verdadeiro','falso']}

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 ≡ λx.xFT

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:

NOT = lambda{ |x| x[F,T] }

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.

AND ≡ λab.abF

O AND recebe dois booleanos e aplica o primeiro (já que booleanos são funções) em b e F, pois, se a for a função T, devolverá b, caso seja F, devolverá o segundo argumento, que é F, como desejamos. O OR é análogo, devolvendo T se o primeiro parâmetro é verdadeiro, e devolvendo o segudo parâmetro caso contrário: OR ≡ λab.aTb. Em Ruby teremos:

AND = lambda{ |a,b| a[b,F] }
OR = lambda{ |a,b| a[T,b] }

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:

(define T (lambda (a b) a))
(define F (lambda (a b) b))
(define NOT (lambda (x) (x F T)))
(define AND (lambda (b1 b2) (b1 b2 F)))
(define OR (lambda (b1 b2) (b1 T b2)))

Quer um desafio maior? Os mais sucintos dialetos LISP trabalham sempre em cima de apenas uma estrutura de dados: a lista. E essa lista, por sua vez, é manipulada por três primitivas básicas: a construção de um par (A,B) (pair ou cons), a seleção do primeiro elemento de um par (head ou car), e a seleção do segundo elemento de um par (tail ou cdr). De tal maneira que head(pair(a,b)) resulte em a e tail(pair(a,b)) resulte em b.

Como implementar essas três primitivas? Você vai ver que, sem usar estrutura de dados, porém com auxílio de ifs, já dá algum trabalho. É um bom exercício. Mas há como implementar sem nem ifs, nem estruturas! E não é tão complicado, basta que a primeiriva pair, dado os dois elementos a e b, guarde-os. Como guardar se não temos estrutura de dados? Devolvemos um lambda que por sua vez recebe um novo lambda que será aplicado nos dois argumentos. As primitivas de head e tail vão então aplicar esse lambda, que representa um par, passando uma função que, dado dois argumentos, devolve o primeiro ou último elemento.

pair ≡ λab.λf.fab
head ≡ λp.p(λab.a)
tail ≡ λp.p(λab.b)

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.

12 Comentários

  1. Roberto 18/04/2011 at 12:17 #

    Muito bom o artigo. Realmente paradigmas de programação diferentes dos tradicionais Procedural e OO podem fazer muito bem quando estamos escrevendo nossos códigos.

    Eu só gostaria de fazer uma observação, LISP é uma linguagem que segue o paradigma Lógico e não funcional.

    Apesar de serem parecidos, o paradigma lógico trabalho com retornos lógicos (Verdadeiro ou Falso) enquando o funcional é baseado na construção de funções, bem próximo das funções matemáticas que conhecemos.

    Um exemplo de linguagem funcional é o Haskel, que pode ser compilado ou interpretado.

    Vale muito a pena conhecer estes paradigmas de programação!

  2. Paulo Silveira 18/04/2011 at 12:36 #

    Oi Roberto!! Que bom que gostou

    Sobre a classificacao das linguagens, é sempre complicado. LISP em si nao ha, e sim diversos dialetos da ideia original… uma familia de linguagens, como gostam de falar. Nos livros, wikipedia e papers vao classificar na maioria das vezes como funcional.

    A maioria delas vai se auto intitular funcional, mas talvez algumas estejam mais pro lado do logico, porem nao scheme, clojure e as que conheco.

  3. Leonardo Fernandes 18/04/2011 at 16:30 #

    Parabens Paulo e Caelum pelo post.
    Comecei o mestrado aqui no CIn/UFPE apenas com background de linguagens imperativas e com a proposta inicial de trabalhar com DSL…
    Conheci o professor André Santos (orientando do próprio Simon Peyton Jones, “criador” do Haskell) que perguntou se eu não queria pesquisar paralelismo usando linguagens funcionais …e aí descobri que existem mais coisas no mundo que podem ser exploradas. Desde de então já estudei Haskell e comecei Erlang … 30 dias atrás a própria Carnegie Mellon publicou um relatório explicando pq pretende ensinar paralelismo e programação funcional desde do início do curso (http://existentialtype.wordpress.com/2011/04/17/some-advice-on-teaching-fp/).

  4. Roberto 18/04/2011 at 18:03 #

    Pois é Paulo, é meio complicado mesmo estas classificações de linguagens. O importante é saber fazer uso destes paradigmas para melhorar amplicar seu leque de soluções.

    Por vezes em Ruby eu tento fazer alguma solução de forma funcional, para explorar a característica a linguagem.

    Gostaria de falar aqui também, que muitas linguagens que utilizamos hoje em dia, podem “simular” programação funcional, como é o caso o Javascript, onde fuções são passadas como parametros, seja para callbacks ou não. No prórprio Java já simulei esta característica, e foi uma experiência muito legal.

    Leonardo, é bom saber que existem pesquisas interessantes como linguagens funcionais e paralelismo. Temos muito a ganhar com este tipo de pesquisa, pois algumas coisas ficam muito mais simples se utilizarmos o paradigma funcional ou lógico.

    Att

  5. Andrei Formiga 18/04/2011 at 19:14 #

    Classificação de linguagens é questão de definição e até convenção sim, mas você dificilmente vai achar alguém que classifique qualquer linguagem mais conhecida da família Lisp como prog. lógica.

    Dos Lisps atuais, Common Lisp é “multi-paradigma”. Dificilmente um programador de CL se identificaria com o rótulo “funcional”. Já Scheme e Clojure são mais comumente classificadas como funcionais.

  6. Guaracy Monteiro 19/04/2011 at 10:37 #

    Conhecer novas linguagens que agregam algo é ótimo para o programador. Quanto ao paradigma, é complicado. Os mais puros irão dizer que ela não é funcional pois é possível atribuir novos valores a uma variável, os usuários irão dizer que é multi-paradigma, etc. Mas acho um detalhe irrelevante.

    Um bom acompanhamento para o livro são os vídeos:
    http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

    Uma linguagem que estou vendo agora e que achei muito interessante é J ( http://jsoftware.com/ ). Fica a dica para um futuro, desde que esteja disposto a esquecer tudo que aprendeu até agora. :-)

  7. Paulo Silveira 02/05/2011 at 16:30 #

    fiz um update para deixar a explicação mais passo a passo, para começar desde o símbolo, com a ajuda do José Donizetti

  8. Alexandre Gazola 12/05/2011 at 16:00 #

    Parabéns por mais um excelente post, Paulo!

    Também fiquei bem interessado em ler o livro depois de ter lido este post do Uncle Bob:

    http://thecleancoder.blogspot.com/2010/08/why-clojure.html

    Vale a pena!

  9. Douglas Rodrigo 28/05/2011 at 00:42 #

    Sou fã de cálculo lambda, achei muito legal a iniciativa por parte da Caelum de falar sobre isso. Acabei até escrevendo a brincadeira em ruby https://gist.github.com/996563

  10. Paulo Silveira 28/05/2011 at 13:00 #

    Boa Douglas! Já pode encarar o church encoding que é o mais divertido!

    Alias, aqui tem um link que o Lucindo compartilhou ontem, bastante itneressante:
    http://matt.might.net/articles/implementing-a-programming-language/

  11. Douglas Rodrigo 31/05/2011 at 10:33 #

    Church encodings é muito interessante, eu vi esse post onde é definido só usando o sistema de tipos do Scala (Typehackery):
    http://michid.wordpress.com/code/meta-programming-with-scala-part-i-addition/

    Obs. complementei o meu gist com a implementação em Ruby de church encondings e as operações aritméticas:

    https://gist.github.com/996563

Deixe uma resposta