Olá! Neste artigo farei uma pequena introdução à programação funcional. Falarei de lazy evaluation e quais são os benefícios que ela pode oferecer. Demonstrarei os encantos do Haskell, a linguagem de programação mais perfeita já criada. Implementaremos (sim, nós!) então uma lazy list em uma linguagem não-lazy, o JavaScript, apenas pela diversão. Por fim... bem, você verá.
Em uma linguagem funcional, funções são elementos de primeira classe. Isto quer dizer que funções são valores tão bons quanto os outros, e podem ser armazenados em variáveis, ou passados e retornados por outras funções (ditas funções de alta ordem). Mas mais que isso, e esta é a característica que distingue uma linguagem funcional de uma linguagem com ponteiros de função (como o C), uma função é capaz de lembrar das variáveis do contexto em que foi definida. Por exemplo:
function soma(x) {
return function(y) {
return x+y;
}
}
Neste trecho de JavaScript, definimos uma função soma, que recebe um número x e retorna uma função, que por sua vez recebe um número y e retorna a soma de x com y. Essa segunda função é capaz de usar o valor de x passado à primeira função mesmo depois de ela ter retornado.
f = soma(10); g = soma(20); alert(f(5)); // mostra 15 alert(g(5)); // mostra 25
De fato, o que está sendo retornado aqui não é uma mera função, e sim uma closure, que é a combinação de uma função com as variáveis definidas no ambiente em que ela foi criada.
No primeiro trecho de código, retornamos uma função sem tê-la declarado antes. Chamamos isto de função anônima, ou lambda, nome herdado do cálculo lambda, o formalismo matemático sobre o qual se baseia a maior parte das linguagens funcionais. (Em Lisp e assemelhados, a palavra-chave para a criação de funções anônimas é lambda.)
Neste ponto você se pergunta: qual é a utilidade disso tudo? Funções de alta ordem por si sós (sem closures) já são úteis; elas permitem a criação de algoritmos genéricos, com "lacunas" que o usuário completa provendo uma função. Por exemplo, podemos ter uma função que aplica uma outra função a todos os elementos de uma lista. Podemos então criar funções que manipulam cada elemento individualmente, e passá-las como parâmetro à primeira. Com isso tornamos essas funções independentes da estrutura da lista; se um dia resolvermos usar uma árvore binária ao invés da lista, poderemos reaproveitá-las sem modificações. Com funções de alta ordem também podemos criar tabelas de funções, determinar em tempo de execução qual de uma série de funções será usada, entre inúmeras outras possibilidades.
Com closures, as coisas ficam ainda mais interessantes. Com a habilidade de criar funções anônimas que lembram de variáveis externas, é como se pudéssemos criar diferentes funções em tempo de execução. Veremos alguns exemplos disso mais adiante.
Embora as closures sejam o que define a classe das linguagens funcionais, o estilo de programação funcional envolve uma mudança de paradigma na maneira de descrever algoritmos. Enquanto em uma linguagem imperativa os algoritmos tendem a ser escritos como uma série de mudanças de estado, em uma linguagem funcional costuma-se descrever um algoritmo como uma composição de funções que constróem o valor de saída. O exemplo clássico é o fatorial, aqui apresentado lado a lado em estilo imperativo e funcional:
// Versão imperativa.
function fac(n) {
var r = 1
while (n > 0) {
r *= n;
n--;
}
return r;
}
|
// Versão funcional.
function fac(n) {
if (n == 0)
return 1;
else
return n * fac(n-1);
}
|
Enquanto o algoritmo imperativo trabalha alterando o estado das variáveis até chegar em um estado final, a versão funcional trabalha compondo o valor final através de chamadas de função. (Embora a versão funcional tal como escrita seja ineficiente em linguagens imperativas, os compiladores/interpretadores para linguagens funcionais são em geral mais hábeis para otimizar esse tipo de código.) O estilo de programação funcional então enfatiza a composição de funções, e desencoraja alteração de estado. Em um programa imperativo, freqüentemente uma expressão causa uma alteração no estado do programa; diz-se que estas expressões possuem efeitos colaterais, isto é, realizam alguma operação além de retornar um valor. Em um programa funcional, tende-se a evitar efeitos colaterais, o que torna as funções referencialmente transparentes, isto é, uma função chamada com os mesmos argumentos retorna sempre o mesmo valor, já que não depende de estado.
Enquanto a maior parte das linguagens funcionais apenas desencoraja o uso de efeitos colaterais, algumas vão mais além e os eliminam completamente. Em tais linguagens, chamadas puramente funcionais, uma vez atribuído um valor a uma variável, ela permanecerá com este valor durante toda sua existência. Uma função não pode afetar o ambiente externo a ela exceto através de retorno de valores; todas as expressões são referencialmente transparentes. Embora isso possa parecer uma limitação desnecessária, a transparência de referencial permite que algumas características interessantes sejam adicionadas à linguagem, como por exemplo...
Como em uma linguagem puramente funcional as expressões não possuem efeitos colaterais, a execução ou não de uma expressão não altera em nada a execução de partes do programa que não dependam do valor da expressão. Como conseqüência, o compilador pode decidir a ordem de execução das expressões sem alterar o significado do programa. Mais que isso, ele pode decidir se uma expressão será executada ou não, e executar as expressões apenas quando e se seus valores forem necessários. A isto se chama lazy evaluation.
Uma conseqüência disso é a habilidade de criar estruturas de dados infinitas. Você pode criar uma lista de todos os números primos, por exemplo, e ela será calculada à medida em que for usada. Você pode escrever funções que produzem uma quantidade volumosa ou infinita de dados e compô-la com outras funções que usam apenas uma parte desses dados, e apenas a parte utilizada será computada. O uso de lazy evaluation leva a outra mudança na maneira de descrever algoritmos, com implicações talvez até mais drásticas do que o estilo funcional.
Um exemplo de linguagem puramente funcional com lazy evaluation é o Haskell, uma linguagem cujo desenvolvimento começou em 1987. O Haskell apresenta uma série de características interessantes, das quais a mais imediatamente visível é a sintaxe. Tomemos a versão funcional do fatorial definida anteriormente. Como se pode ver, o JavaScript não é muito amigável ao estilo funcional. Em Scheme, por exemplo, a mesma função poderia ser escrita como:
;; Versão com if
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
|
;; Versão com cond
(define (fac n)
(cond [(= n 0) 1]
[else (* n (fac (- n 1)))]))
|
Em Scheme, toda expressão retorna um valor; ifs são expressões, e portanto retornam um valor, que será uma das duas expressões, dependendo do resultado da condição. Nos livramos dos returns, que ficam implícitos. Outra característica notável é que *, - e = são funções sem nenhuma propriedade especial; elas podem ser passadas como parâmetros para outras funções, e até mesmo redefinidas pelo usuário. Ganhamos em flexibilidade, mas por outro lado levamos de brinde uma dúzia de parênteses supérfluos*. Não seria melhor se nós pudéssemos definir o fatorial como a seguir?
fac 0 = 1 fac n = n * fac (n-1)
Pois esse código é o mais legítimo Haskell! Em Haskell, pode-se definir as funções por partes; quando a função é chamada, a primeira definição que encaixar com os argumentos passados será usada. A isto se denomina pattern matching, e os padrões podem ser mais interessantes do que um valor constante. Por exemplo, em muitas linguagens funcionais uma lista é definida recursivamente como sendo ou um nil (uma lista vazia), ou um cons (um par que consiste em um valor (o primeiro elemento da lista) seguido de uma nova lista (com os elementos restantes)). Por exemplo, a lista [1,2,3] é representada como (cons 1 (cons 2 (cons 3 nil))). Em PLT-Scheme, uma função que calcula o somatório dos elementos de uma lista poderia ser escrita da seguinte maneira, onde first retorna o primeiro elemento do cons (o valor) e rest retorna o segundo (a sublista):
(define (soma ls)
(cond [(empty? ls) 0]
[else (+ (first ls) (soma (rest ls)))]))
Isto é, se a função receber uma lista vazia, retorna zero. Senão, retorna a soma do primeiro elemento com o somatório do resto da lista. Em Haskell, a lista vazia é representada por [], e o operador cons por :. A lista [1,2,3] pode ser representada por 1:2:3:[] (ou, de fato, por [1,2,3]). A função soma pode então ser definida como:
soma [] = 0 soma (x:xs) = x + soma xs
Com pattern matching, separamos o first e o rest da lista diretamente na declaração dos parâmetros da função, o que torna o código muito mais limpo. Note que aplicação de função em Haskell não requer parênteses, o que aliás está relacionado com outra característica muito interessante: se uma função é aplicada a menos argumentos do que o especificado em sua definição, o resultado é uma função que recebe os argumentos restantes. Por exemplo, podemos definir as funções do primeiro exemplo como:
add x y = x+y f = add 10 g = add 20
add é uma função que recebe dois argumentos e retorna sua soma. add 10 é uma função que recebe um argumento n e retorna n+10. De fato, qualquer função de dois argumentos pode ser vista como uma função que recebe um argumento e retorna outra função, que recebe o argumento seguinte e retorna o resultado final. Isso permite substituir muitos casos comuns de função anônima por funções parcialmente aplicadas.
Anteriormente foi mencionado que em Scheme as operações matemáticas são funções comuns, e que isso nos dava maior flexibilidade, às custas da sintaxe peculiar com operadores prefixados. Em Haskell, como vimos, os operadores são infixados, como na maior parte da linguagens. Mas isso não quer dizer que eles não sejam funções! Na verdade, a maior parte dos operadores em Haskell são funções. Acontece que uma função cujo nome consista exclusivamente de símbolos é automaticamente infixada! A precedência e associatividade de cada função pode ser definida usando as palavras-chave infixl e infixr. Caso queiramos usar uma função infixada como uma função comum, basta colocá-la entre parênteses. Por exemplo, a função add poderia ter sido definida como add = (+). (+) 2 3 é equivalente a 2+3. Mais que isso, é possível aplicar parcialmente uma função infixada: (+y) x é equivalente a x+y!
Como isso poderia ser útil? Existe uma função filter na biblioteca padrão, que recebe uma função booleana e uma lista, e retorna apenas os elementos para os quais a função é verdadeira. Se quiséssemos todos os elementos de uma lista maiores que 10, poderíamos usar filter (>10) ls. Existe também a função map, que recebe uma função e uma lista, e retorna uma lista com os resultados da aplicação da função a cada elemento da lista. map (*2) ls multiplica todos os elementos por dois.
E quanto à lazy evaluation? As bibliotecas padrão contêm diversas funções que exploram o fato de a linguagem ser lazy-evaluating. Por exemplo, tails é uma função que recebe uma lista e retorna uma lista de todos os seus sufixos; tails [1,2,3,4] retorna [[1,2,3,4],[2,3,4],[3,4],[4],[]]. Essa função pode ser usada para implementar uma pesquisa por sublista, mesmo que a lista original seja muito grande; a função só computará sublistas à medida em que for necessário.
Podemos facilmente definir uma lista infinita em Haskell. A seguinte declaração cria uma lista infinita de 1s:
ones = 1 : ones
Agora um exemplo mais interessante. Existe uma função zipWith, que recebe uma função de dois argumentos e duas listas, e retorna uma lista com os resultados da aplicação da função a cada par de elementos correspondentes nas duas listas. Por exemplo, zipWith (+) [1,2,3] [10,20,30] retorna [11,22,33]. tail é uma função que retorna uma lista sem o primeiro elemento (o rest do Scheme). Agora tomemos a seqüência de Fibonacci, que começa em [1,1] e cada elemento seguinte é a soma dos dois elementos anteriores. Podemos definir essa seqüência como:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
O primeiro elemento retornado pelo zipWith será a soma do primeiro 1 com o segundo; esse elemento é acrescentado à lista. A seguir, segundo 1 será somado com o recém-acrescentado 2, e assim sucessivamente. Você pode pegar uma porção da lista usando take 15 fibs.
E agora um exemplo ainda mais glorioso: uma lista de todos os primos.
sieve (x:xs) = x : sieve (filter (\n -> n `mod` x /= 0) xs) primes = sieve [2..]
(\n -> n `mod` x /= 0) é uma função anônima que recebe um argumento n e determina se resto da divisão de n por x é diferente zero. As aspas invertidas permitem que uma função comum seja usada como um operador infixado. Essa função é usada com filter para eliminar de xs todos os múltiplos de x. A função sieve toma o primeiro elemento da lista, elimina todos os seus múltiplos do resto da lista, e aplica a si própria ao resultado. Ao receber uma lista de todos os naturais a partir de 2, ela elimina todos os múltiplos de 2 do resto da lista, e aplica-se ao resultado, que é [3,5,7,...]. O processo é repetido, eliminando todos os múltiplos de 3 fora o próprio 3, e assim por diante. Essa função é bastante ineficiente, mas nada mal para duas linhas de código!
O Haskell possui inúmeras outras características interessantes, mas por enquanto nos basta. Se você estiver interessado na linguagem, dê uma olhada em haskell.org e no Learn You A Haskell For Great Good!.
Lazy evaluation não é uma exclusividade das linguagens funcionais, e é possível que você já tenha trabalhado com um sistema lazy-evaluating sem se dar conta. Trata-se das pipelines do Unix: em uma pipeline, a saída de um processo é ligada à entrada de outro; quando o buffer do pipe se esgota, o primeiro processo pára de produzir saída e aguarda até que o segundo consuma os dados fornecidos. Os dados serão então fornecidos à medida em que forem consumidos, e se o segundo processo terminar, o primeiro será encerrado. Existe pelo menos um utilitário de sistema, o yes, que explora esse fato produzindo uma saída infinita. A idéia é a mesma de uma função em Haskell que produz uma lista, finita ou não, cujos elementos são consumidos por uma outra função.
Vimos que a idéia de gerar os elementos de uma lista à medida em que são necessários é bastante útil. Fica então a pergunta: como poderíamos realizar a mesma tarefa em uma linguagem não-lazy? Uma possibilidade, útil no caso de seqüências numéricas que seguem uma fórmula fixa, é substituir a lista por uma função capaz de lembrar de valores já computados. Em JavaScript, por exemplo:
var fibs = [1,1]; // vetor de valores já computados
function fib(n) {
// Se o valor procurado não está na lista, adicionamo-lo.
if (n >= fibs.length)
fibs[n] = fib(n-1) + fib(n-2);
return fibs[n];
}
Outra possibilidade que algumas linguagens oferecem é o uso de geradores, objetos que encapsulam uma função capaz de retornar múltiplas vezes, onde após cada retorno a execução da função é suspensa, não encerrada, e pode ser retomada do ponto em que parou. Em Python, por exemplo, poderíamos definir um gerador para a seqüência de Fibonacci como:
def fibgen():
a, b = 1, 0
while True:
yield a
a, b = a+b, a
fibs = fibgen()
Aqui, fibgen contém um loop que retorna um elemento da seqüência e suspende sua execução. Ao ser invocada, um gerador será retornado. Se executarmos fibs.next(), a execução da função será retomada, e o próximo valor da seqüência será retornado. Note entretanto que, ao contrário do que ocorre com uma lazy list, os valores já produzidos pelo gerador são perdidos; no exemplo acima, tivemos que usar as variáveis auxiliares a e b para armazenar os valores de elementos anteriores relevantes para o cálculo do elemento atual.
Uma terceira possibilidade, e esta é a que nos interessa aqui, é usar closures para implementar lazy evaluation. A idéia é substituir um valor por uma função que quando chamada retorna o valor. Podemos assim adiar seu cálculo até que ele seja necessário. Porém, o que temos aqui é uma forma de lazy evaluation "manual": quando quisermos o valor da expressão, teremos que nós mesmos forçar sua execução.
Nosso desafio agora é implementar uma lazy list em uma linguagem não-lazy que possua closures, e para tal usaremos nosso bom (?) e velho (?) JavaScript. Implementaremos nossa lista usando a definição recursiva apresentada acima, em que uma lista pode ser vazia (o que representaremos pelo valor null), ou consistir de um par que contém o primeiro elemento da lista (o first) e uma lista com os elementos restantes (o rest), com uma pequena modificação: em vez de o rest ser uma lista, ele será ou uma lista ou uma função que, quando executada, produz a lista com os elementos restantes.
Definamos então esta estrutura de dados (o código completo desenvolvido neste artigo pode ser obtido aqui):
function Cons(first, rest) {
this.f = first;
this.r = rest;
// <Insira as definições de métodos aqui>
}
Agora, precisamos criar um getter para cada um dos elementos do cons. O getter para o first é trivial:
this.first getter = function() {
return this.f;
}
O getter do rest é um pouco mais complexo: ele precisa testar se o rest é uma lista ou uma função. Se for uma lista, basta retorná-la. Se for uma função, ele deve executá-la, armazenar o resultado como o novo valor do rest, e retorná-lo.
this.rest getter = function() {
if (typeof(this.r) == "function")
this.r = this.r();
return this.r;
}
Por conveniência, vamos adicionar uma função para imprimir a lista de uma maneira satisfatória. Como a lista é potencialmente infinita, vamos limitar o número de elementos a exibir a 10.
this.toString = function() {
var i, ls, s="<";
for (ls=this, i=0; ls && i<10; ls=ls.rest, i++) {
if (i>0) s += ",";
s += ls.first;
}
if (ls && ls.rest)
s += ",...";
s += ">";
return s;
}
Temos uma lazy list! Vamos experimentá-la criando uma lista com todos os naturais.
// Gera uma lista com todos os naturais a partir de n.
function natsFrom(n) {
return new Cons(n, function() { return new natsFrom(n+1); });
}
var nats = natsFrom(0);
Aqui, definimos uma função natsFrom que recebe um número n e retorna um cons em que o first é n e o rest é uma função que chama a própria natsFrom recursivamente, com n+1, produzindo uma lista infinita. nats contém então todos os naturais, começando em 0. Verifiquemos isso (você pode usar um interpretador de JavaScript standalone, como o que vem com o SpiderMonkey ou o JSDB, para fazer os testes):
js> nats <0,1,2,3,4,5,6,7,8,9,...>
Funciona! Vamos ainda criar mais um método, this.idx(n), que retorna o n-ésimo elemento da lista:
this.idx = function(n) {
var i, ls;
for (ls=this, i=0; ls && i<n; ls=ls.rest, i++) ;
if (ls)
return ls.first;
else
throw Error("Não existe!");
}
Agora já podemos implementar nossa seqüência infinita de Fibonacci:
fibs = fibsFrom(0);
function fibsFrom(n) {
return new Cons(fib(n), function() { return fibsFrom(n+1); });
}
function fib(n) {
if (n<=1) return 1;
else return fibs.idx(n-1) + fibs.idx(n-2);
}
Testando...
js> fibs <1,1,2,3,5,8,13,21,34,55,...> js> fibs.idx(40) 165580141
E por último, nossa gloriosa lista de primos. Primeiro, precisaremos escrever a função filter. Ela recebe uma função de teste e uma lista, e retorna uma lista (lazy) com todos os elementos para os quais a função de teste retorna verdadeiro.
function filter(test, ls) {
if (ls == null)
return null;
else if (test(ls.first))
return new Cons(ls.first, function() {
return filter(test, ls.rest);
});
else
return filter(test, ls.rest);
}
Isto é: se a lista for vazia, retorna vazio. Se a lista não for vazia e o primeiro elemento passar no teste, inclui-o na lista resultante e chama filter recursivamente, repetindo o processo para o resto da lista. Se não passar no teste, simplesmente chama filter no resto da lista, descartando o primeiro elemento.
Vamos testar nossa filter gerando uma lista de todos os pares:
function isEven(n) {
return (n%2 == 0);
}
var evens = filter(isEven, nats);
Testando...
js> evens <0,2,4,6,8,10,12,14,16,18,...>
Muito bem! Agora podemos escrever nossa sieve:
function sieve(ls) {
var notdiv = function(n) { return (n%ls.first != 0); }
return new Cons(ls.first, function() {
return sieve(filter(notdiv, ls.rest));
});
}
primes = sieve(natsFrom(2));
E lá vamos nós!
js> primes <2,3,5,7,11,13,17,19,23,29,...>
E ficamos por aqui. Trabalhar com closures em JavaScript é um tanto quanto inconveniente, mas espero ter demonstrado que é possível fazer coisas interessantes com elas. [** links para mais informações sobre programação funcional, exemplos mais interessantes de closures e lazy lists, etc. **]
Anteriormente eu disse que as pipelines do Unix são uma forma de lazy evaluation. Sendo assim, será possível implementar o algoritmo visto para produzir uma lista de todos os primos usando uma pipeline? E a resposta é:
sieve() {
local num cut
read cut || return
echo "$cut"
while read num; do
((num%cut != 0)) && echo "$num"
done | sieve
}
seq 2 500 | sieve
Copie e cole em um terminal e veja o resultado. Substitua o '500' por algum outro valor para obter uma lista maior (ou por Infinity para obter uma lista infinita, o que, aparententemente devido aos buffers da pipeline, torna o processo bastante lento). Espero com isso tê-lo convencido de que as pipelines realmente são uma forma de lazy evaluation.
* Quando eu comecei a escrever este artigo, em abril de 2010, ainda não tinha sido apresentado ao Common Lisp e suas maravilhas. Depois de ler o excelente Practical Common Lisp, entre outros, estou perfeitamente convencido de que os parênteses não são supérfluos: o código de um programa em Lisp consiste de listas, e isso permite que as macros do Lisp manipulem e produzam código atuando diretamente sobre as listas que o compõem. Em Scheme as macros não são tão flexíveis. Aliás, ultimamente o Lisp tem ameaçado tomar o lugar do Haskell como linguagem perfeita na minha concepção... mas isso fica para outro artigo.
Copyright © 2010 Vítor Bujés Ubatuba De Araújo
O conteúdo deste site, a menos que de outra forma especificado, pode ser utilizado livremente, com ou sem alterações, desde que seja mencionado o autor, preferivelmente com a URL do documento original.