Conceitos de Programação: Lazy Evaluation

January 25th, 2008 § 11 comments

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
end

Em 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 Function

O 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)
end

Essa é 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 é:

  1. Para o argumento n, fib de n é o elemento n de uma lista chamada fibs. O operador !! é o equivalente Haskell do indexador [] em outras linguagens.

  2. 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
end

Essa 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.

§ 11 Responses to Conceitos de Programação: Lazy Evaluation"

  • Êêê! 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

  • Ronaldo says:

    Bem, espero que você e o resto dos leitores gostem. Vamos ver como eu me saio para explicar essas coisas. :-)

  • Cesar Silveira says:

    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.

  • Ronaldo says:

    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. :-)

  • Elomar says:

    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.

  • Ronaldo says:

    Bem, eu espero conseguir continuar no mesmo nível. Vamos ver o que acontece. :-)

  • tiago says:

    Ótimo artigo! Espero que continue!

  • Ronaldo says:

    Obrigado pelas palavras. O próximo chega na sexta-feira.

  • Felipe says:

    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!

    =)

  • Ronaldo says:

    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.

Leave a Reply

Your email address will not be published. Required fields are marked *

What's this?

You are currently reading Conceitos de Programação: Lazy Evaluation at Superfície Reflexiva.

meta