Por que o conceito de avaliação preguiçosa é útil?

Parece que a avaliação preguiçosa de expressões pode fazer com que um programador perca o controle sobre a ordem em que seu código é executado. Estou tendo problemas para entender por que isso seria aceitável ou desejado por um programador.

Como esse paradigma pode ser usado para criar software previsível que funcione conforme o esperado, quando não temos garantia de quando e onde uma expressão será avaliada?

Muitas respostas estão relacionadas a listas infinitas e ganhos de desempenho em partes não avaliadas da computação, mas isso está perdendo a maior motivação para a preguiça: a modularidade .

O argumento clássico é apresentado no citado artigo "Por que a programação funcional é importante" (link em PDF), de John Hughes. O exemplo principal desse artigo (Seção 5) é jogar Tic-Tac-Toe usando o algoritmo de busca alfa-beta. O ponto principal é (p. 9):

[Avaliação preguiçosa] torna prático modularizar um programa como um gerador que constrói um grande número de respostas possíveis e um seletor que escolhe o apropriado.

O programa Tic-Tac-Toe pode ser escrito como uma função que gera toda a árvore do jogo iniciando em uma determinada posição e como uma função separada que a consome. No tempo de execução, isso não gera intrinsecamente toda a árvore do jogo, apenas as subpartes de que o consumidor realmente precisa. Podemos mudar a ordem e a combinação na qual as alternativas são produzidas mudando o consumidor; não é necessário trocar o gerador.

Em um idioma ansioso, você não pode escrever dessa maneira, porque provavelmente gastaria muito tempo e memória gerando a árvore. Então você acaba:

1. Combinando geração e consumo na mesma função;
2. Escrever um produtor que funcione de maneira ideal apenas para determinados consumidores;
3. Implementando sua própria versão da preguiça.

Como esse paradigma pode ser usado para criar software previsível que funcione conforme o esperado, quando não temos garantia de quando e onde uma expressão será avaliada?

Quando uma expressão é livre de efeitos colaterais, a ordem na qual as expressões são avaliadas não afeta seu valor, portanto, o comportamento do programa não é afetado pela ordem. Portanto, o comportamento é perfeitamente previsível.

Agora os efeitos colaterais são uma questão diferente. Se os efeitos colaterais pudessem ocorrer em qualquer ordem, o comportamento do programa seria realmente imprevisível. Mas esse não é realmente o caso. Idiomas preguiçosos como Haskell fazem questão de ser referencialmente transparente, ou seja, garantir que a ordem na qual as expressões sejam avaliadas nunca afetem seus resultados. Em Haskell, isso é alcançado forçando todas as operações com efeitos colaterais visíveis ao usuário a ocorrer dentro da mônada de E / S. Isso garante que todos os efeitos colaterais ocorram exatamente na ordem que você esperaria.

Se você conhece os bancos de dados, uma maneira muito frequente de processar dados é:

• Faça uma pergunta como select * from foobar
• Enquanto houver mais dados, faça: obtenha a próxima linha de resultados e processe-a

Você não controla como o resultado é gerado e de que maneira (índices? Varreduras de tabelas completas?) Ou quando (todos os dados devem ser gerados de uma só vez ou incrementalmente quando solicitados?). Tudo o que você sabe é: se houver mais dados, você os obterá quando solicitar.

A avaliação preguiçosa é bem próxima da mesma coisa. Digamos que você tenha uma lista infinita definida como ie. a sequência de Fibonacci - se você precisar de cinco números, obtém cinco números calculados; se você precisar de 1000, recebe 1000. O truque é que o tempo de execução sabe o que fornecer onde e quando. É muito, muito útil.

(Programadores Java podem emular esse comportamento com Iteradores - outras linguagens podem ter algo semelhante)

Considere pedir ao seu banco de dados uma lista dos primeiros 2.000 usuários cujos nomes começam com "Ab" e têm mais de 20 anos. Eles também devem ser do sexo masculino.

Aqui está um pequeno diagrama.

You                                            Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
                         --------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
                         --------------------- NOW I'll get them...
WAIT! Make sure they're  ---------->---------- Good idea Boss!
over 20!
                         --------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!

No that is all. :(       ---------->---------- FINE! Getting records!

                         --------------------- Here you go. 
Thanks Postgres, you're  ---------->----------  ...
my only friend.

Como você pode ver por essa terrível interação terrível, o "banco de dados" não está fazendo nada até estar pronto para lidar com todas as condições. É o carregamento lento dos resultados em cada etapa e a aplicação de novas condições a cada vez.

Ao contrário de obter os primeiros 2.000 usuários, devolvê-los, filtrá-los para "Ab", retorná-los, filtrá-los por mais de 20, devolvê-los e filtrar por homens e finalmente devolvê-los.

Carregamento preguiçoso em poucas palavras.

A avaliação lenta das expressões fará com que o designer de um determinado pedaço de código perca o controle sobre a sequência em que o código é executado.

O designer não deve se preocupar com a ordem em que as expressões são avaliadas, desde que o resultado seja o mesmo. Adiando a avaliação, pode ser possível evitar a avaliação completa de algumas expressões, o que economiza tempo.

Você pode ver a mesma ideia em ação em um nível inferior: muitos microprocessadores são capazes de executar instruções fora de ordem, o que lhes permite usar suas várias unidades de execução com mais eficiência. A chave é que eles examinem as dependências entre as instruções e evitem reordenar onde isso mudaria o resultado.

Existem vários argumentos para avaliação preguiçosa que eu acho convincentes

1. Modularidade Com uma avaliação lenta, você pode dividir o código em partes. Por exemplo, suponha que você tenha o problema de "localizar os dez primeiros recíprocos de elementos em uma lista de lista, de modo que os recíprocos sejam menores que 1." Em algo como Haskell, você pode escrever

   take 10 . filter (<1) . map (1/)
   

   mas isso está incorreto em um idioma estrito, pois se você der, [2,3,4,5,6,7,8,9,10,11,12,0]estará dividindo por zero. Veja a resposta de Sacundim para saber por que isso é incrível na prática

2. Mais coisas funcionam Estritamente (trocadilhos) mais programas terminam com uma avaliação não estrita do que com uma avaliação estrita. Se o seu programa terminar com uma estratégia de avaliação "ansiosa", será finalizada com uma estratégia "preguiçosa", mas o contrário não será verdadeiro. Você obtém coisas como estruturas de dados infinitas (que são realmente muito legais) como exemplos específicos desse fenômeno. Mais programas funcionam em idiomas preguiçosos.

3. Ótima avaliação A avaliação por necessidade é assintoticamente ideal em relação ao tempo. Embora as principais linguagens preguiçosas (que são essencialmente Haskell e Haskell) não prometam atender às necessidades, você pode mais ou menos esperar um modelo de custo ideal. Analisadores de rigidez (e avaliação especulativa) mantêm a sobrecarga na prática. O espaço é uma questão mais complicada.

4. A pureza das forças usando a avaliação preguiçosa faz com que lidar com os efeitos colaterais de maneira indisciplinada seja uma dor total, porque, como você diz, o programador perde o controle. Isto é uma coisa boa. A transparência referencial facilita muito a programação, a refatoração e o raciocínio sobre os programas. Linguagens estritas inevitavelmente cedem à pressão de ter bits impuros - algo que Haskell e Clean resistiram lindamente. Isso não quer dizer que os efeitos colaterais sejam sempre ruins, mas controlá-los é tão útil que apenas esse motivo é suficiente para usar linguagens preguiçosas.

Suponha que você tenha muitos cálculos caros em oferta, mas não sabe quais serão realmente necessários ou em que ordem. Você pode adicionar um protocolo complicado de mãe para mãe para forçar o consumidor a descobrir o que está disponível e acionar cálculos que ainda não foram feitos. Ou você pode apenas fornecer uma interface que atue como se todos os cálculos tivessem sido feitos.

Além disso, suponha que você tenha um resultado infinito. O conjunto de todos os números primos, por exemplo. É óbvio que você não pode calcular o conjunto antecipadamente, portanto, qualquer operação no domínio de números primos deve ser preguiçosa.

com uma avaliação lenta, você não perde o controle sobre a execução do código, ainda é absolutamente determinístico. É difícil se acostumar com isso, no entanto.

avaliação preguiçosa é útil porque é uma forma de redução do prazo lambda que terminará em alguns casos, onde a avaliação ansiosa falhará, mas não vice-versa. Isso inclui 1) quando você precisa vincular ao resultado da computação antes de executar a computação, por exemplo, quando constrói a estrutura gráfica cíclica, mas deseja fazê-lo no estilo funcional 2) quando define uma estrutura de dados infinita, mas funciona com esse feed de estrutura para usar apenas parte da estrutura de dados.