Ленивая оценка - Lazy evaluation

Стратегии оценки

В программировании теории языка , ленивые вычисления , или вызов по необходимости , является стратегия оценки , которая задерживает оценку того или иного выражения , пока его значение не требуется ( нестрогое оценки ) и которая также позволяет избежать повторных оценок ( обмена ). Совместное использование может сократить время работы некоторых функций экспоненциально по сравнению с другими стратегиями нестрогого вычисления, такими как вызов по имени , которые многократно оценивают одну и ту же функцию вслепую, независимо от того, можно ли запоминать функцию .

К преимуществам ленивого оценивания относятся:

  • Возможность определять поток управления (структуры) как абстракции, а не примитивы.
  • Возможность определять потенциально бесконечные структуры данных . Это позволяет упростить реализацию некоторых алгоритмов.
  • Производительность увеличивается за счет исключения ненужных вычислений и ошибок при вычислении составных выражений.

Ленивое оценивание часто сочетается с запоминанием , как описано в книге Джона Бентли « Написание эффективных программ» . После того, как значение функции вычислено для этого параметра или набора параметров, результат сохраняется в таблице поиска, которая индексируется значениями этих параметров; при следующем вызове функции выполняется консультация с таблицей, чтобы определить, доступен ли уже результат для этой комбинации значений параметров. Если да, то просто возвращается сохраненный результат. Если нет, функция оценивается, и в таблицу поиска добавляется еще одна запись для повторного использования.

Ленивое вычисление может привести к сокращению объема памяти, поскольку значения создаются при необходимости. Однако ленивое вычисление трудно сочетать с императивными функциями, такими как обработка исключений и ввод / вывод , потому что порядок операций становится неопределенным. Ленивое вычисление может привести к утечке памяти .

Противоположность ленивому оцениванию - это активное оценивание , иногда известное как строгое вычисление. Активная оценка - это стратегия оценки, используемая в большинстве языков программирования .

История

Ленивое вычисление было введено для лямбда-исчисления Кристофером Уодсвортом и использовано системой Plessey System 250 как критическая часть мета-машины лямбда-исчисления, уменьшая накладные расходы на разрешение для доступа к объектам в адресном пространстве с ограниченными возможностями. Для языков программирования он был независимо представлен Питером Хендерсоном и Джеймсом Х. Моррисом, а также Дэниелом П. Фридманом и Дэвидом С. Уайзом.

Приложения

Отсроченная оценка используется, в частности, в функциональных языках программирования . При использовании отложенного вычисления выражение оценивается не сразу после его привязки к переменной, а тогда, когда оценщик вынужден произвести значение выражения. То есть, такой оператор, как x = expression;(то есть присвоение результата выражения переменной) явно требует, чтобы выражение было оценено и результат помещен в x, но то, что на самом деле есть, не xимеет значения, пока не возникнет потребность в его значении. через ссылку на xв каком-то более позднем выражении, вычисление которого само может быть отложено, хотя в конечном итоге быстрорастущее дерево зависимостей будет обрезано, чтобы создать какой-то символ, а не другой, чтобы его мог увидеть внешний мир.

Отложенная оценка имеет преимущество в том, что она позволяет создавать вычисляемые бесконечные списки без бесконечных циклов или вопросов размера, влияющих на вычисления. Например, можно создать функцию, которая создает бесконечный список (часто называемый потоком ) чисел Фибоначчи . Вычисление n-го числа Фибоначчи было бы просто извлечением этого элемента из бесконечного списка, заставляя вычислять только первые n членов списка.

Например, в языке программирования Haskell список всех чисел Фибоначчи можно записать как: 

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

В синтаксисе Haskell " :" добавляет элемент к списку, tailвозвращает список без его первого элемента и zipWithиспользует указанную функцию (в данном случае сложение) для объединения соответствующих элементов двух списков для создания третьего.

Если программист проявляет осторожность, оцениваются только те значения, которые необходимы для получения определенного результата. Однако некоторые вычисления могут привести к тому, что программа попытается оценить бесконечное количество элементов; например, запрос длины списка или попытка суммирования элементов списка с помощью операции сворачивания приведет к тому, что программа либо не завершится, либо будет исчерпана память .

Структуры управления

Практически во всех распространенных «нетерпеливых» языках операторы if вычисляются лениво. 

if a then b else c

оценивает (a), тогда, если и только если (a) оценивается как true, он оценивает (b), в противном случае он оценивает (c). То есть ни (b), ни (c) не будут оцениваться. И наоборот, на нетерпеливом языке ожидаемое поведение таково, что 

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

будет по-прежнему оценивать (e) при вычислении значения f (d, e), даже если (e) не используется в функции f. Однако определяемые пользователем управляющие структуры зависят от точного синтаксиса, поэтому, например, 

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

(i) и (j) оба будут оцениваться на нетерпеливом языке. Пока на ленивом языке, 

l' = if h then i else j

(i) или (j) будут оцениваться, но никогда оба.

Ленивое вычисление позволяет определять управляющие структуры обычным образом, а не как примитивы или методы времени компиляции. Если (i) или (j) имеют побочные эффекты или вносят ошибки времени выполнения, тонкие различия между (l) и (l ') могут быть сложными. Обычно можно ввести определяемые пользователем структуры отложенного управления в энергичных языках в качестве функций, хотя они могут отклоняться от синтаксиса языка для энергичной оценки: часто задействованные тела кода (например, (i) и (j)) должны быть заключены в значение функции, поэтому они выполняются только при вызове.

Вычисление короткого замыкания логических управляющих структур иногда называют ленивым .

Работа с бесконечными структурами данных

Многие языки предлагают понятие бесконечных структур данных . Это позволяет давать определения данных в терминах бесконечных диапазонов или бесконечной рекурсии, но фактические значения вычисляются только при необходимости. Возьмем, к примеру, эту тривиальную программу на Haskell: 

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

main = print $ numberFromInfiniteList 4

В функции numberFromInfiniteList значение бесконечности представляет собой бесконечный диапазон, но до тех пор, пока не потребуется фактическое значение (или, более конкретно, конкретное значение по определенному индексу), список не оценивается, и даже тогда он оценивается только по мере необходимости. (то есть до желаемого индекса.)

Шаблон списка успехов

Избегайте чрезмерных усилий

Составное выражение может быть в форме EasilyComputed или LotsOfWork, так что, если простая часть дает истинное значение, можно избежать большой работы. Например, предположим, что нужно проверить большое число N, чтобы определить, является ли оно простым числом, и доступна ли функция IsPrime (N), но, увы, для ее оценки может потребоваться много вычислений. Возможно, N = 2 или [Mod (N, 2) ≠ 0 и IsPrime (N)] помогут, если будет много вычислений с произвольными значениями для N.

Предотвращение ошибок

Составное выражение может быть в форме SafeToTry и Expression, посредством чего, если SafeToTry имеет значение false, не должно быть попыток оценить выражение, чтобы не выдать сигнал об ошибке времени выполнения, такой как деление на ноль или выход индекса за пределы, и т.д. Например, следующий псевдокод определяет местонахождение последнего ненулевого элемента массива: 

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

Если все элементы массива равны нулю, цикл будет работать до L = 0, и в этом случае цикл должен быть завершен без попытки ссылаться на нулевой элемент массива, которого не существует.

Другое использование

В компьютерных оконных системах отображение информации на экране управляется событиями раскрытия, которые запускают код дисплея в последний возможный момент. Делая это, оконные системы избегают вычисления ненужных обновлений отображаемого содержимого.

Другой пример лени в современных компьютерных системах - распределение страниц с копированием при записи или подкачка по запросу , когда память выделяется только при изменении значения, хранящегося в этой памяти.

Лень может быть полезна в сценариях с высокой производительностью. Пример является Unix - ММАП функции, которая обеспечивает спрос загрузку страниц с диска, так что только те страницы , на самом деле коснулись загружаются в память, а ненужная память не выделяются.

MATLAB реализует копирование при редактировании , где массивы, которые копируются, имеют свое фактическое хранилище в памяти, реплицируемое только при изменении их содержимого, что может привести к ошибке нехватки памяти при последующем обновлении элемента, а не во время операции копирования.

Реализация

Некоторые языки программирования по умолчанию откладывают вычисление выражений, а некоторые другие предоставляют функции или специальный синтаксис для отсрочки вычисления. В Miranda и Haskell оценка аргументов функции по умолчанию откладывается. Во многих других языках оценка может быть отложена путем явной приостановки вычислений с использованием специального синтаксиса (как в схемах « delay» и « force» и OCaml « lazy» и « Lazy.force») или, в более общем смысле, путем помещения выражения в преобразователь . Объект, представляющий такую ​​явно отложенную оценку, называется ленивым будущим . Raku использует ленивое вычисление списков, поэтому можно назначать бесконечные списки переменным и использовать их в качестве аргументов для функций, но в отличие от Haskell и Miranda, Raku по умолчанию не использует ленивое вычисление арифметических операторов и функций.

Лень и рвение

Сдерживание рвения на ленивых языках

В ленивых языках программирования, таких как Haskell, хотя по умолчанию выражения оцениваются только тогда, когда они требуются, в некоторых случаях можно сделать код более активным или, наоборот, снова сделать его более ленивым после того, как он стал более активным. Это может быть сделано путем явного кодирования чего-то, что требует оценки (что может сделать код более активным) или избегания такого кода (что может сделать код более ленивым). Строгая оценка обычно подразумевает рвение, но это технически разные концепции.

Однако в некоторых компиляторах реализована оптимизация, называемая анализом строгости , которая в некоторых случаях позволяет компилятору сделать вывод о том, что значение будет использоваться всегда. В таких случаях это может сделать выбор программиста, принудительно ли использовать это конкретное значение или нет, неуместным, потому что анализ строгости требует строгой оценки.

В Haskell маркировка полей конструктора строгими означает, что их значения всегда будут запрашиваться немедленно. seqФункция также может быть использована немедленно требовать значения , а затем передать его, что полезно , если поле конструктора обычно должно быть ленивым. Однако ни один из этих методов не реализует рекурсивную строгость - для этого deepSeqбыла изобретена вызываемая функция .

Кроме того, сопоставление с образцом в Haskell 98 по умолчанию строгое, поэтому ~нужно использовать квалификатор, чтобы сделать его ленивым.

Имитация лени в нетерпеливых языках

Джава

В Java ленивая оценка может выполняться с помощью объектов, у которых есть метод для их оценки, когда значение необходимо. Тело этого метода должно содержать код, необходимый для выполнения этой оценки. С момента появления лямбда-выражений в Java SE8 Java поддерживает для этого компактную нотацию. В следующем примере универсального интерфейса представлена ​​структура для ленивой оценки: 

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

LazyИнтерфейс с его eval()метода эквивалентен Supplierинтерфейсу с его get()методом в java.util.functionбиблиотеке.

Каждый класс, реализующий Lazyинтерфейс, должен предоставлять evalметод, а экземпляры класса могут нести любые значения, необходимые методу для выполнения ленивой оценки. Например, рассмотрим следующий код для ленивого вычисления и вывода 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() );

В приведенном выше примере переменная a изначально относится к ленивому целочисленному объекту, созданному лямбда-выражением ()->1. Оценка этого лямбда-выражения эквивалентна созданию нового экземпляра анонимного класса, который реализуется Lazy<Integer>с помощью метода eval, возвращающего 1 .

Каждая итерация цикла связывает a с новым объектом, созданным путем вычисления лямбда-выражения внутри цикла. Каждый из этих объектов содержит ссылку на другой ленивый объект, b , и имеет метод eval, который вызывается b.eval()дважды и возвращает сумму. Переменная b здесь необходима, чтобы удовлетворить требование Java, чтобы переменные, на которые ссылается лямбда-выражение, были окончательными.

Это неэффективная программа, потому что эта реализация ленивых целых чисел не запоминает результат предыдущих вызовов eval . Это также включает в себя значительную часть автобокса и распаковки . Что может быть неочевидным, так это то, что в конце цикла программа создала связанный список из 11 объектов и что все фактические добавления, участвующие в вычислении результата, выполняются в ответ на вызов a.eval()в последней строке код. Этот вызов рекурсивно просматривает список для выполнения необходимых дополнений.

Мы можем создать класс Java, который запоминает ленивые объекты следующим образом: 

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;
    }
}

Это позволяет переписать предыдущий пример, сделав его более эффективным. Если исходная версия выполнялась с экспоненциальной скоростью по количеству итераций, то мемоизированная версия работает с линейным временем: 

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() );

Обратите внимание, что лямбда-выражения Java - это просто синтаксический сахар . Все, что вы можете написать с помощью лямбда-выражения, можно переписать как вызов для создания экземпляра анонимного внутреннего класса, реализующего интерфейс, и любое использование анонимного внутреннего класса может быть переписано с использованием именованного внутреннего класса, а любой именованный внутренний класс может быть перемещенным на самый внешний уровень вложенности.

JavaScript

В JavaScript ленивую оценку можно смоделировать с помощью генератора . Например, поток всех чисел Фибоначчи можно записать, используя мемоизацию , как: 

/**
 * 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]

Python

В Python 2.x range()функция вычисляет список целых чисел. При оценке первого оператора присваивания весь список сохраняется в памяти, так что это пример активной или немедленной оценки: 

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

В Python 3.x range()функция возвращает специальный объект диапазона, который вычисляет элементы списка по запросу. Элементы объекта диапазона генерируются только тогда, когда они необходимы (например, когда print(r[3])оценивается в следующем примере), так что это пример ленивой или отложенной оценки: 

>>> r = range(10)
>>> print(r)
range(0, 10)
>>> print(r[3])
3
Это изменение на ленивую оценку экономит время выполнения для больших диапазонов, которые могут никогда не использоваться полностью, и использование памяти для больших диапазонов, где в любой момент требуется только один или несколько элементов.

В Python 2.x можно использовать вызываемую функцию, xrange()которая возвращает объект, генерирующий числа в диапазоне по запросу. Преимущество xrangeзаключается в том, что сгенерированный объект всегда будет занимать один и тот же объем памяти. 

>>> 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]

Начиная с версии 2.2 Python демонстрирует ленивую оценку, реализуя итераторы (ленивые последовательности), в отличие от последовательностей кортежей или списков. Например (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
В приведенном выше примере показано, что списки оцениваются при вызове, но в случае итератора первый элемент «0» печатается, когда возникает необходимость.

.NET Framework

В .NET Framework с помощью класса можно выполнять ленивую оценку . Класс может быть легко использован в F # с помощью ключевого слова, в то время как метод будет принудительно выполнять оценку. Существуют также специализированные коллекции, которые предоставляют встроенную поддержку ленивых вычислений. 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

В C # и VB.NET класс используется напрямую. 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
}

Или с более практичным примером: 

// 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
}

Другой способ - использовать yieldключевое слово: 

// 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;
    }
}
Основная статья: Thunk

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки