Inspirado por alguns pedidos aqui no blog, estou começando uma nova série sobre conceitos de programação. Alguns desses conceitos são úteis como técnicas para melhorar a forma como você resolve problemas em seus programas e outros são úteis como forma de entender o que acontece em determinadas situações quando você está programando de modo a aproveitar melhor as características das linguagens em questão.
Para começar, vou experimentar com alguns assuntos que me parecem mais interessantes e postar algo sobre os mesmos a cada sexta-feira. Se houver interesse, mantenho o formato. E é claro, estou sempre aberto a quaisquer sugestões de assuntos.
Lazy Evaluation
O primeiro tema que vamos tratar aqui é o de lazy evaluation. Também conhecida como delayed evaluation essa é uma técnica útil para evitar a necessidade de realmente computar um resultado até que o mesmo seja necessário. Isso significa, é claro, que se por algum motivo o resultado não for necessário, o mesmo também não será calculado.
Dois dos efeitos colaterais mais interessantes do uso dessa técnica são a possibilidade de definir estruturas de dados infinitas (como a lista de todos os números primos por exemplo) e definir estruturas de controle sem a necessidade de funções primitivas da própria linguagem. Se feito de maneira correta, o uso de lazy evaluation é capaz de aumentar consideravelmente a performance de um programa.
Curto-circuito
Em linguagens imperativas, principalmente as que não são dinâmicas, um dos usos mais familiares de lazy evaluation acontece em expressões lógicas. Por exemplo:
rating = (playCount > 10) ? (playCount * 2) : (playCount / 2)No exemplo acima, dependendo do valor que a variável playCount possuir, somente um dos blocos de código será executado. O outro, compilado ou não, será simplesmente ignorado, embora faça parte da mesma expressão.
Esse é um exemplo bem simples de lazy evaluation mas ilustra a técnica. Esse, inclusive, é um dos poucos casos em que mesmo linguagens que usam execução estrita de maneira geral (call-by-reference e call-by-value) utilizam esse comportamento para otimizar a execução.
Estruturas de controle
Uma função que eu via muito em código ASP era justamente uma forma de criar o operador ternário acima. Aliás, para quem não está familiarizado com esse operador, ele é apenas uma açúcar sintático para a estrutura condicional if. O exemplo usando anteriormente é o mesmo que:
if (playCount > 10)
rating = playCount * 2;
else
rating = playCount / 2
endEm ASP, para emular esse efeito de simplificação, programadores geralmente usavam algo assim:
Function IIf(Expression, TrueValue, FalseValue)
If Expression Then
IIf = TrueValue
Else
IIf = FalseValue
End If
End FunctionO grande problema desse função é que todos seus parâmetros, por causa da natureza do VBScript, são computados antes da execução da função. Se construirmos um exemplo equivalente ao primeiro, teríamos algo assim:
Rating = IIf(PlayCount > 10, PlayCount * 2, PlayCount / 2)Ineficientemente, todos os valores acima são computados antes de srem passados adiantw mesmo que somente um deles seja retornado. Em uma linguagem que usasse lazy evaluation, o usual seria substituir as expressões por uma promessa de execução e só computar o valor quando a mesma fosse necessária. Em uma linguagem assim, a função IIf seria exatamente equivalente à estrutura condicional if.
Listas infinitas
Um exemplo muito usado para explicar o assunto, quase que um exemplo canônico, é o cálculo dos números de Fibonacci em uma linguagem lazy como Haskell.
Para comparar, veja a implementação recursiva abaixo em Ruby:
def fib(n)
return 1 if n <= 1
return fib(n - 1) + fib(n - 2)
endEssa é uma implementação ineficiente, é claro, mas serve para comparar com a implementação similar em Haskell:
fib 0 = 0
fib 1 = 1
fib n = fib(n - 1) + fib(n - 2)Essa é uma implementação que segue a definição matemática da função mas que também é bem ineficiente. Essa implementação recursiva geralmente falha por volta do trigésimo quinto item por causa da quantidade de chamadas feitas.
Em Ruby, isso geralmente é resolvido com uma versão iterativa. Em Haskell, podemos resolver da seguinte forma:
fib n = fibs !! n
where
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)Antes de explicar a expressão, é necessário explicar o que zipWith faz. Essencialmente, zipWith pega duas listas e aplica a função às mesmas, elemento por elemento, resultando em uma única lista final. Por exemplo:
*Main> zipWith (*) [1, 2] [3, 4]
[3, 8]O uso de (*) tem a ver com outro conceito interessante chamado currying que veremos em um artigo futuro.
Essencialmente, então, o que a definição de fib está dizendo é:
Para o argumento
n,fibdené o elementonde uma lista chamadafibs. O operador!!é o equivalente Haskell do indexador[]em outras linguagens.A lista
fibsé definida como a concatenação de 0, 1 e do resultado da concatenação de si mesma com sua cauda com a aplicaçâo de (+). Essa última parte pode soar estranha, mas é exatamente isso o que está acontecendo. Essencialmente, o que você tem aqui é uma lista infinita. Digamos que você queira calcular então o quinto termo da série de Fibonacci. Nesse caso, você teria a seguinte execução:
0 : 1 : zipWith (+) (0 : 1 : ...) (1 : ...)
0 : 1 : (0 + 1) : zipWith (+) (1 : 1 : ...) (1 : ...)
0 : 1 : (0 + 1) : (1 + 1) : zipWith (+) (1 : 2 : ...) (2 : ...)
0 : 1 : (0 + 1) : (1 + 1) : (1 + 2) : zipWith (+) (2 : 3 : ...) (3 : ...)O retorno final seria três, que é o quinto item da lista. Se você está curioso, a própria função zipWith pode ser definida como:
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []
Em outras palavras, zipWith de uma lista cujo primeiro elemento é x e cujo restante é xs e de uma lista cujo primeiro elemento é y e cujo restante é ys para uma função f é f de x e y concatenado a zipWith de xs e ys sobre f. A segunda linha diz que em qualquer outro caso, o retorno é uma lista vazia. A definição recursiva pode ser vista facilmente na chamada em fibs.
Note que a lista sempre é expressa como uma lista sem término, ou seja, infinita. Para retornar um valor específico, basta pegar o elemento em questão. O cálculo necessário é feito somente até aquele ponto e não mais. O resto da lista continua sendo expresso internamente por uma representação que permite obter o próximo valor sem mais do que uma simples continuação do processamento. A função é bem eficiente e não sofre das penalidades recursivas da versão original.
A beleza da função acima, entretanto, não está em evitar recursão explícita (esse é outro conceito que exploraremos futuramente) ou usar uma lista infinita. Antes, está no fato de que o cálculo, além de somente ser executado quanto necessário, não é repetido. Ou seja, seu eu pegar o décimo primeiro elemento e depois pegar o quinto, a lista não é recalculada. E quando eu precisar do vigésimo elemento, só serão necessárias mais nove passagens na lista. O cálculo todo acontece sob demanda.
Um outro exemplo interessante disso é o cálculo do Crivo de Eratóstenes em Haskell:
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]Essencialmente, a função tira todos múltiplos de dois de uma lista infinita de números naturais maiores ou iguais a dois, depois tira todos múltiplos de três, depois todos de cinco, e assim por diante, com cada novo primo descoberto.
Ao contrário da função fib, essa é extremamente ineficiente, o que mostra que o uso de lazy evaluation não é uma panacéia e que também depende de bons algoritmos.
O que isso tudo significa
Em linguagens com suporte direto a lazy evaluation, o uso da mesma pode facilitar a implementação e aumentar muito a performance de um programa.
Em linguagens que não suportam lazy evaluation, uma simulação da técnica pode ser bem útil para gerar resultados com maior performance. É um troca, na verdade, já que geralmente isso envolve um consumo maior de memória, mas pode ser bem útil se o cálculo é tão intensivo que exige uma forma melhor de ser tratado.
Uma forma de fazer algo parecido em Ruby é usando a classe Fiber, disponível a partir da versão 1.9. Você teria algo assim:
require "fiber"
fib = Fiber.new do
x, y = 0, 1
loop do
Fiber.yield y
x, y = y, x + y
end
endEssa computação é infinita, já que não há uma condição de saída, e você pode obter valores chamando o método resume na classe retornada:
20.times { puts fib.resume }O problema com a chamada acima é que se eu quisesse recalcular uma número de Fibonacci qualquer, eu teria que criar uma nova Fiber. Isso pode ser resolvido com algo um pouco mais complexo:
require "fiber"
class LazyList
def initialize(&block)
@memo = []
@fiber = Fiber.new(&block)
end
def [](value)
@memo << @fiber.resume while @memo.size <= value
@memo[value]
end
end
def fib(n)
(class << self; self; end).instance_eval do
((@global_lazy_dict ||= {})[:fib] ||= LazyList.new {
x, y = 0, 1
loop do
Fiber.yield y
x, y = y, x + y
end
})[n]
end
end
[12, 10, 17].each { |i| puts fib(i) }O código acima usa uma forma bem básica de memoização para manter a lista em memória mas a idéia é essa. Se você rodar o código, verá que a lista somente é calculada até onde necessário e que valores anteriores são retornados do cache.
Uma aplicação interessante desse tipo de técnica seria executar cálculos pesados em uma thread separada e retornar somente o necessário para a exibição. Se está fosse feita em páginas, por exemplo, você poderia requisitar somente os valores daquela página enquanto os das demais páginas estão sendo calculados. Para quem, inclusive, quer experimentar com isso em Ruby, há justamente uma biblioteca chamada lazy.rb para auxiliar. Veja o método future.
Conclusão
Espero que isso tenha ajudado a entender um pouco o que é lazy evaluation. Qualquer dúvida posterior, coloque nos comentários aqui. Da mesma forma, sugestões e críticas são bem-vindas. Na próxima sexta-feira, continuaremos com mais um artigo.
Êêê! Olha minha série de conceitos de programação =D
Valeu! Vou ler com muita atenção e mal posso esperar pelos próximos! Principalmente sobre sort()… O BozoSort/BogoSort é a melhor técnica =D
Bem, espero que você e o resto dos leitores gostem. Vamos ver como eu me saio para explicar essas coisas.
Olá,
Acompanho teu blog há algum tempo. Gosto muito do que escreves! Achei bastante interessante o início desta série de artigos sobre Conceitos de Programação, uma área que me interessa muito também (apesar de ainda estar apenas engatinhando nisso).
Apenas uma sugestão: acho que poderias usar algum exemplo melhor sobre curto-circuito. Um bom exemplo é o if com ao menos um and: se a primeira condição é falsa, as demais já nem são avaliadas e vai-se para o else, caso haja um. Ou então o caso do or, bastante similar: se a primeira condição é verdadeira, as demais não são avaliadas e o código da condição é executado.
Muito obrigado pelas palavras e pela audiência. Sobre os exemplos, o uso de *and* e *or* é realmente uma boa. Mas pensando bem, fiquei contente com a contribuição e acho que esse modelo é bem interessante. Se eu deixar passar alguma coisa, os leitores certamente vão me corrigir.
Um ótimo artigo, e tomara que a seção continue no mesmo nível. Artigos desse tipo são ótimos para programadores que se preocupam em entender o que estão fazendo, e não apenas ‘pilotarem’ ides.
Bem, eu espero conseguir continuar no mesmo nível. Vamos ver o que acontece.
Ótimo artigo! Espero que continue!
Obrigado pelas palavras. O próximo chega na sexta-feira.
Uma observação: aquele *não* é o crivo de Eratóstenes.
http://www.haskell.org/pipermail/haskell-cafe/2007-February/022666.html
Além disso, apesar daquele link, lazy /= memoizado!
=)
Obrigado pelo comentário, Felipe. Boa dica, por sinal. Esse é um dos algoritmos mais usados para representar Haskell e cita incontáveis vezes como exemplo do crivo.
Sobre lazy versus memoizado, o meu texto não sugere que haja alguma equivalência. Antes, como eu deixo claro logo no início da parte em questão, a forma demonstrada é uma simulação para obter efeitos similares.
Ótimo artigo!