Avaliação preguiçosa - Lazy evaluation

Na teoria da linguagem de programação , a avaliação preguiçosa , ou chamada por necessidade , é uma estratégia de avaliação que atrasa a avaliação de uma expressão até que seu valor seja necessário ( avaliação não estrita ) e que também evita avaliações repetidas ( compartilhamento ). O compartilhamento pode reduzir o tempo de execução de certas funções por um fator exponencial em relação a outras estratégias de avaliação não rígidas, como chamada por nome , que avalia repetidamente a mesma função, às cegas, independentemente de a função poder ser memoizada .

Os benefícios da avaliação preguiçosa incluem:

  • A capacidade de definir o fluxo de controle (estruturas) como abstrações em vez de primitivas.
  • A capacidade de definir estruturas de dados potencialmente infinitas . Isso permite uma implementação mais direta de alguns algoritmos.
  • O desempenho aumenta, evitando cálculos desnecessários e evitando condições de erro ao avaliar expressões compostas.

A avaliação preguiçosa costuma ser combinada com a memoização , conforme descrito em Jon Bentley 's Writing Efficient Programs . Depois que o valor de uma função é calculado para esse parâmetro ou conjunto de parâmetros, o resultado é armazenado em uma tabela de pesquisa que é indexada pelos valores desses parâmetros; na próxima vez que a função for chamada, a tabela será consultada para determinar se o resultado para aquela combinação de valores de parâmetro já está disponível. Nesse caso, o resultado armazenado é simplesmente retornado. Caso contrário, a função é avaliada e outra entrada é adicionada à tabela de pesquisa para reutilização.

A avaliação lenta pode levar à redução do consumo de memória, uma vez que os valores são criados quando necessário. No entanto, a avaliação preguiçosa é difícil de combinar com recursos imperativos, como tratamento de exceções e entrada / saída , porque a ordem das operações torna-se indeterminada. A avaliação lenta pode apresentar vazamentos de memória .

O oposto da avaliação preguiçosa é a avaliação ansiosa , às vezes conhecida como avaliação rigorosa. A avaliação rápida é a estratégia de avaliação empregada na maioria das linguagens de programação .

História

A avaliação preguiçosa foi introduzida para cálculo lambda por Christopher Wadsworth e empregada pelo Plessey System 250 como uma parte crítica de uma Meta-Máquina Lambda-Calculus, reduzindo a sobrecarga de resolução para acesso a objetos em um espaço de endereço de capacidade limitada. Para linguagens de programação, foi introduzido independentemente por Peter Henderson e James H. Morris e por Daniel P. Friedman e David S. Wise.

Formulários

A avaliação atrasada é usada principalmente em linguagens de programação funcionais . Ao usar a avaliação atrasada, uma expressão não é avaliada assim que é associada a uma variável, mas quando o avaliador é forçado a produzir o valor da expressão. Ou seja, uma declaração como x = expression;(ou seja, a atribuição do resultado de uma expressão a uma variável) claramente exige que a expressão seja avaliada e o resultado colocado x, mas o que realmente está xé irrelevante até que haja a necessidade de seu valor por meio de uma referência a xem alguma expressão posterior cuja avaliação poderia ser adiada, embora, eventualmente, a árvore de dependências de crescimento rápido fosse podada para produzir algum símbolo em vez de outro para o mundo exterior ver.

A avaliação atrasada tem a vantagem de ser capaz de criar listas infinitas calculáveis ​​sem loops infinitos ou questões de tamanho interferindo na computação. Por exemplo, pode-se criar uma função que cria uma lista infinita (geralmente chamada de fluxo ) de números de Fibonacci . O cálculo do n- ésimo número de Fibonacci seria meramente a extração daquele elemento da lista infinita, forçando a avaliação apenas dos primeiros n membros da lista.

Por exemplo, na linguagem de programação Haskell , a lista de todos os números de Fibonacci pode ser escrita como:

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Na sintaxe Haskell, " :" adiciona um elemento a uma lista, tailretorna uma lista sem seu primeiro elemento e zipWithusa uma função especificada (neste caso, além) para combinar os elementos correspondentes de duas listas para produzir uma terceira.

Desde que o programador seja cuidadoso, apenas os valores necessários para produzir um determinado resultado são avaliados. No entanto, certos cálculos podem resultar na tentativa do programa de avaliar um número infinito de elementos; por exemplo, solicitar o comprimento da lista ou tentar somar os elementos da lista com uma operação de dobra resultaria na falha do programa em encerrar ou em falta de memória .

Estruturas de controle

Em quase todas as linguagens "ansiosas" comuns, as declarações if são avaliadas de maneira preguiçosa.

if a then b else c

avalia (a), então se e somente se (a) for avaliado como verdadeiro, ele avalia (b); caso contrário, avalia (c). Ou seja, (b) ou (c) não serão avaliados. Por outro lado, em uma linguagem ansiosa, o comportamento esperado é que

define f(x, y) = 2 * x
set k = f(d, e)

ainda avaliará (e) ao calcular o valor de f (d, e) mesmo que (e) não seja usado na função f. No entanto, as estruturas de controle definidas pelo usuário dependem da sintaxe exata, então, por exemplo

define g(a, b, c) = if a then b else c
l = g(h, i, j)

(i) e (j) seriam avaliados em uma linguagem ambiciosa. Enquanto em uma linguagem preguiçosa,

l' = if h then i else j

(i) ou (j) seriam avaliados, mas nunca ambos.

A avaliação lenta permite que as estruturas de controle sejam definidas normalmente, e não como primitivas ou técnicas de tempo de compilação. Se (i) ou (j) têm efeitos colaterais ou introduzem erros de tempo de execução, as diferenças sutis entre (l) e (l ') podem ser complexas. Geralmente é possível introduzir estruturas de controle preguiçosas definidas pelo usuário em linguagens ávidas como funções, embora elas possam se afastar da sintaxe da linguagem para uma avaliação rápida: Freqüentemente, os corpos de código envolvidos (como (i) e (j)) precisam ser incluídos um valor de função, para que sejam executados apenas quando chamados.

A avaliação de curto-circuito das estruturas de controle booleanas às vezes é chamada de preguiçosa .

Trabalhar com estruturas de dados infinitas

Muitas linguagens oferecem a noção de estruturas de dados infinitas . Isso permite que as definições dos dados sejam fornecidas em termos de intervalos infinitos ou recursão sem fim, mas os valores reais são calculados apenas quando necessário. Veja, por exemplo, este programa trivial em Haskell:

numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n =  infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4

Na função numberFromInfiniteList , o valor de infinito é um intervalo infinito, mas até que um valor real (ou mais especificamente, um valor específico em um determinado índice) seja necessário, a lista não é avaliada e, mesmo assim, só é avaliada conforme necessário (isto é, até o índice desejado.)

Padrão de lista de sucessos

Evitando esforço excessivo

Uma expressão composta pode estar na forma EasilyComputed ou LotsOfWork, de modo que, se a parte fácil for verdadeira, muito trabalho poderá ser evitado. Por exemplo, suponha que um grande número N deva ser verificado para determinar se é um número primo e uma função IsPrime (N) está disponível, mas, infelizmente, pode exigir muitos cálculos para avaliar. Talvez N = 2 ou [Mod (N, 2) ≠ 0 e IsPrime (N)] ajude se houver muitas avaliações com valores arbitrários para N.

Evitar condições de erro

Uma expressão composta pode estar no formato SafeToExperimente e Expression em que se SafeToExperimente for falso, não deve haver nenhuma tentativa de avaliar a Expressão para que um erro de tempo de execução seja sinalizado, como divisão por zero ou índice fora dos limites, etc. Por exemplo, o seguinte pseudocódigo localiza o último elemento diferente de zero de uma matriz:

 L:=Length(A);
 While L>0 and A(L)=0 do L:=L - 1;

Se todos os elementos do array forem zero, o loop funcionará até L = 0 e, neste caso, o loop deve ser encerrado sem tentar fazer referência ao elemento zero do array, que não existe.

Outros usos

Em sistemas de janelas de computador , a exibição de informações na tela é conduzida por eventos de exposição que conduzem o código de exibição no último momento possível. Ao fazer isso, os sistemas de janelas evitam a computação de atualizações de conteúdo de exibição desnecessárias.

Outro exemplo de preguiça em sistemas de computador modernos é a alocação de página de cópia na gravação ou paginação por demanda , em que a memória é alocada apenas quando um valor armazenado nessa memória é alterado.

A preguiça pode ser útil para cenários de alto desempenho. Um exemplo é a função mmap do Unix , que fornece carregamento orientado por demanda de páginas do disco, de modo que apenas as páginas realmente tocadas sejam carregadas na memória e a memória desnecessária não seja alocada.

O MATLAB implementa cópia na edição , onde os arrays que são copiados têm seu armazenamento de memória real replicado apenas quando seu conteúdo é alterado, possivelmente levando a um erro de falta de memória ao atualizar um elemento posteriormente, em vez de durante a operação de cópia.

Implementação

Algumas linguagens de programação atrasam a avaliação de expressões por padrão, e algumas outras fornecem funções ou sintaxe especial para atrasar a avaliação. Em Miranda e Haskell , a avaliação dos argumentos da função é atrasada por padrão. Em muitas outras linguagens, a avaliação pode ser atrasada suspendendo explicitamente o cálculo usando uma sintaxe especial (como com Scheme " delay" e " force" e OCaml " lazy" e " Lazy.force") ou, mais geralmente, envolvendo a expressão em uma conversão . O objeto que representa tal avaliação explicitamente atrasada é chamado de futuro preguiçoso . Raku usa avaliação preguiçosa de listas, então pode-se atribuir listas infinitas a variáveis ​​e usá-las como argumentos para funções, mas ao contrário de Haskell e Miranda, Raku não usa avaliação preguiçosa de operadores aritméticos e funções por padrão.

Preguiça e ansiedade

Controlando a ansiedade em línguas preguiçosas

Em linguagens de programação preguiçosas como Haskell, embora o padrão seja avaliar expressões apenas quando elas são exigidas, é possível em alguns casos tornar o código mais ansioso - ou, inversamente, torná-lo mais preguiçoso novamente depois de ter sido feito mais ansioso. Isso pode ser feito codificando explicitamente algo que força a avaliação (o que pode tornar o código mais ansioso) ou evitando esse código (o que pode tornar o código mais preguiçoso). A avaliação rigorosa geralmente implica ansiedade, mas são conceitos tecnicamente diferentes.

No entanto, existe uma otimização implementada em alguns compiladores chamada análise de rigidez , que, em alguns casos, permite ao compilador inferir que um valor sempre será usado. Em tais casos, isso pode tornar a escolha do programador de forçar ou não aquele valor específico irrelevante, porque a análise de rigidez forçará uma avaliação rigorosa.

Em Haskell, marcar campos de construtor como estritos significa que seus valores sempre serão exigidos imediatamente. A seqfunção também pode ser usada para exigir um valor imediatamente e, em seguida, passá-lo adiante, o que é útil se um campo de construtor geralmente for lento. No entanto, nenhuma dessas técnicas implementa rigidez recursiva - para isso, uma função chamada deepSeqfoi inventada.

Além disso, a correspondência de padrões no Haskell 98 é estrita por padrão, então o ~qualificador deve ser usado para torná-lo preguiçoso.

Simulando preguiça em línguas ávidas

Java

Em Java , a avaliação preguiçosa pode ser feita usando objetos que possuem um método para avaliá-los quando o valor é necessário. O corpo deste método deve conter o código necessário para realizar esta avaliação. Desde a introdução das expressões lambda no Java SE8, o Java oferece suporte a uma notação compacta para isso. O exemplo de interface genérica a seguir fornece uma estrutura para avaliação preguiçosa:

interface Lazy<T> {
    T eval();
}

A Lazyinterface com seu eval()método é equivalente à Supplierinterface com seu get()método na java.util.functionbiblioteca.

Cada classe que implementa a Lazyinterface deve fornecer um evalmétodo, e as instâncias da classe podem carregar quaisquer valores de que o método precisa para realizar uma avaliação preguiçosa. Por exemplo, considere o seguinte código para calcular e imprimir preguiçosamente 2 10 :

Lazy<Integer> a = ()-> 1;
for (int i = 1; i <= 10; i++) {
    final Lazy<Integer> b = a;
    a = ()-> b.eval() + b.eval();
}
System.out.println( "a = " + a.eval() );

Acima, a variável a inicialmente se refere a um objeto inteiro lento criado pela expressão lambda ()->1. Avaliar essa expressão lambda é equivalente a construir uma nova instância de uma classe anônima que implementa Lazy<Integer>com um método eval que retorna 1 .

Cada iteração do loop vincula a a um novo objeto criado avaliando a expressão lambda dentro do loop. Cada um desses objetos contém uma referência a outro objeto preguiçoso, b , e tem um método eval que chama b.eval()duas vezes e retorna a soma. A variável b é necessária aqui para atender ao requisito de Java de que as variáveis ​​referenciadas em uma expressão lambda sejam finais.

Este é um programa ineficiente porque esta implementação de números inteiros lazy não memoriza o resultado de chamadas anteriores para eval . Também envolve autoboxing e unboxing consideráveis . O que pode não ser óbvio é que, no final do loop, o programa construiu uma lista encadeada de 11 objetos e que todas as adições reais envolvidas no cálculo do resultado são feitas em resposta à chamada de a.eval()na linha final de código. Essa chamada percorre recursivamente a lista para realizar as adições necessárias.

Podemos construir uma classe Java que memoriza objetos preguiçosos da seguinte maneira:

class Memo<T> implements Lazy<T> {
    private Lazy<T> lazy;  // a lazy expression, eval sets it to null
    private T memo = null; // the memorandum of the previous value

    public Memo( Lazy<T> lazy ) { // constructor
        this.lazy = lazy;
    }

    public T eval() {
        if (lazy != null) {
            memo = lazy.eval();
            lazy = null;
        }
        return memo;
    }
}

Isso permite que o exemplo anterior seja reescrito para ser muito mais eficiente. Onde o original é executado no tempo exponencial no número de iterações, a versão memoizada é executada no tempo linear:

Lazy<Integer> a = ()-> 1;
for (int i = 1; i <= 10; i++) {
    final Lazy<Integer> b = a;
    a = new Memo<Integer>( ()-> b.eval() + b.eval() );
}
System.out.println( "a = " + a.eval() );

Observe que as expressões lambda do Java são apenas açúcar sintático . Qualquer coisa que você pode escrever com uma expressão lambda pode ser reescrito como uma chamada para construir uma instância de uma classe interna anônima implementando a interface, e qualquer uso de uma classe interna anônima pode ser reescrito usando uma classe interna nomeada, e qualquer classe interna nomeada pode ser movido para o nível de aninhamento mais externo.

JavaScript

Em JavaScript , a avaliação preguiçosa pode ser simulada usando um gerador . Por exemplo, o fluxo de todos os números de Fibonacci pode ser escrito, usando memoização , como:

/**
 * Generator functions return generator objects, which reify lazy evaluation.
 * @return {!Generator<bigint>} A non-null generator of integers.
 */
function* fibonacciNumbers() {
    let memo = [1n, -1n]; // create the initial state (e.g. a vector of "negafibonacci" numbers)
    while (true) { // repeat indefinitely
        memo = [memo[0] + memo[1], memo[0]]; // update the state on each evaluation
        yield memo[0]; // yield the next value and suspend execution until resumed
    }
}

let stream = fibonacciNumbers(); // create a lazy evaluated stream of numbers
let first10 = Array.from(new Array(10), () => stream.next().value); // evaluate only the first 10 numbers
console.log(first10); // the output is [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n]

Pitão

No Python 2.x, a range()função calcula uma lista de inteiros. Toda a lista é armazenada na memória quando a primeira instrução de atribuição é avaliada, então este é um exemplo de avaliação rápida ou imediata:

>>> r = range(10)
>>> print r
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print r[3]
3

No Python 3.x, a range()função retorna um objeto de intervalo especial que calcula os elementos da lista sob demanda. Os elementos do objeto de intervalo são gerados apenas quando são necessários (por exemplo, quando print(r[3])é avaliado no exemplo a seguir), então este é um exemplo de avaliação preguiçosa ou adiada:

>>> r = range(10)
>>> print(r)
range(0, 10)
>>> print(r[3])
3
Esta mudança para avaliação lenta economiza tempo de execução para grandes intervalos que podem nunca ser totalmente referenciados e uso de memória para grandes intervalos onde apenas um ou alguns elementos são necessários a qualquer momento.

No Python 2.x é possível usar uma função chamada xrange()que retorna um objeto que gera os números na faixa sob demanda. A vantagem de xrangeé que o objeto gerado sempre ocupará a mesma quantidade de memória.

>>> r = xrange(10)
>>> print(r)
xrange(10)
>>> lst = [x for x in r]
>>> print(lst)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Da versão 2.2 em diante, Python manifesta avaliação preguiçosa implementando iteradores (sequências preguiçosas) ao contrário de tupla ou sequências de lista. Por exemplo (Python 2):

>>> numbers = range(10)
>>> iterator = iter(numbers)
>>> print numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print iterator
<listiterator object at 0xf7e8dd4c>
>>> print iterator.next()
0
O exemplo acima mostra que as listas são avaliadas quando chamadas, mas no caso de iterador, o primeiro elemento '0' é impresso quando necessário.

.NET Framework

No .NET Framework , é possível fazer uma avaliação preguiçosa usando a classe . A classe pode ser facilmente explorada em F # usando a palavra - chave, enquanto o método forçará a avaliação. Existem também coleções especializadas como essa que fornecem suporte integrado para avaliação preguiçosa. System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 1000

Em C # e VB.NET, a classe é usada diretamente. System.Lazy<T>

public int Sum()
{
    int a = 0;
    int b = 0; 
    Lazy<int> x = new Lazy<int>(() => a + b);
    a = 3;
    b = 5;
    return x.Value; // returns 8
}

Ou com um exemplo mais prático:

// recursive calculation of the n'th fibonacci number
public int Fib(int n)
{
   return (n == 1)? 1 : (n == 2)? 1 : Fib(n-1) + Fib(n-2);
}

public void Main()
{
    Console.WriteLine("Which Fibonacci number do you want to calculate?");
    int n = Int32.Parse(Console.ReadLine()); 
    Lazy<int> fib = new Lazy<int>(() => Fib(n)); // function is prepared, but not executed
    bool execute; 
    if (n > 100)
    {
        Console.WriteLine("This can take some time. Do you really want to calculate this large number? [y/n]");
        execute = (Console.ReadLine() == "y"); 
    }
    else execute = true;
    
    if (execute) Console.WriteLine(fib.Value); // number is only calculated if needed
}

Outra maneira é usar a yieldpalavra-chave:

// eager evaluation 
public IEnumerable<int> Fibonacci(int x)
{
    IList<int> fibs = new List<int>();

    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        fibs.Add(sum); 
    }
    return fibs;
}

// lazy evaluation 
public IEnumerable<int> LazyFibonacci(int x)
{
    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        yield return sum;
    }
}

Veja também

Referências

Leitura adicional

links externos