Ленивая оценка

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

Преимущества ленивых вычислений включают в себя:

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

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

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

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

История

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

Приложения

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

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

Отложенное вычисление позволяет определять структуры управления обычным образом, а не как примитивы или методы времени компиляции. Например, можно определить операторы if-then-else и сокращенные операторы оценки :

ifThenElse True b c = b
ifThenElse False b c = c

-- or
True || b = True
False || b = b

-- and
True && b = b
False && b = False

Они имеют обычную семантику, т.е. ifThenElse a b c вычисляет (a), тогда если и только если (a) оценивается как true, он оценивает (b), в противном случае он оценивает (c). То есть будет оцениваться ровно одно из (b) или (c). Аналогично, для EasilyComputed || LotsOfWork, если простая часть дает True, можно избежать большого количества рабочих выражений. Наконец, при оценке SafeToTry && Expression, если SafeToTry имеет значение false, попытка вычислить выражение не будет предпринята .

И наоборот, на энергичном языке приведенное выше определение для ifThenElse a b c будет оценивать (a), (b) и (c) независимо от значения (a). Это нежелательное поведение, поскольку (b) или (c) могут иметь побочные эффекты , занимать много времени для вычислений или вызывать ошибки. Обычно в нетерпеливых языках можно вводить определяемые пользователем структуры ленивого управления в виде функций, хотя они могут отличаться от синтаксиса языка для нетерпеливого вычисления: часто задействованные тела кода необходимо обернуть в значение функции, чтобы они выполнялись только когда звонят.

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

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

Возьмем, к примеру, эту тривиальную программу на Haskell :

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

main = print $ numberFromInfiniteList 4

В функции NumberFromInfiniteList , значение бесконечность — это бесконечный диапазон, но до тех пор, пока не потребуется фактическое значение (или, точнее, конкретное значение по определенному индексу), список не оценивается, и даже тогда он оценивается только по мере необходимости (то есть до тех пор, пока не будет достигнуто желаемое значение). index.) При условии, что программист будет внимателен, программа завершится нормально. Однако некоторые вычисления могут привести к тому, что программа попытается оценить бесконечное количество элементов; например, запрос длины списка или попытка суммировать элементы списка с помощью операции свертывания приведет к тому, что программа либо не сможет завершить работу, либо ей не хватит памяти .

Другой пример: список всех чисел Фибоначчи можно записать на языке программирования Haskell следующим образом:

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

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

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

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

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

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

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

Производительность

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

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

Выполнение

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

Лень и рвение

Управление рвением в ленивых языках

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

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

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

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

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

Ява

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

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

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

Каждый класс, реализующий Lazy интерфейс должен обеспечивать eval метод, а экземпляры класса могут содержать любые значения, необходимые методу для выполнения отложенной оценки. Например, рассмотрите следующий код для ленивого вычисления и печати 2 ¹⁰ :

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

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

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

Это неэффективная программа, поскольку такая реализация ленивых целых чисел не запоминает результат предыдущих вызовов. оценка . Это также включает в себя значительную часть автоупаковки и распаковки . Что может быть неочевидно, так это то, что в конце цикла программа создала связанный список из 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; // the memorandum of the previous value

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

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

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

Lazy<Integer> a = () -> 1;
for (int i = 0; i < 10; i++) {
    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 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 можно выполнять отложенную оценку с помощью класса System.Lazy<T>. Этот класс можно легко использовать в F# с помощью lazy ключевое слово, в то время как force метод приведет к принудительной оценке. Есть также специализированные коллекции, такие как Microsoft.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;
    }
}

Основная статья: Танк

См. также

• Комбинаторная логика
• каррирование
• Поток данных
• Стремительная оценка
• Функциональное программирование
• Фьючерсы и обещания
• Генератор (компьютерное программирование)
• Сокращение графа
• Инкрементальные вычисления – родственная концепция, согласно которой вычисления повторяются только в том случае, если их входные данные изменяются. Может сочетаться с ленивой оценкой.
• Лямбда-исчисление
• Ленивая инициализация
• смотреть вперед
• Нестрогий язык программирования
• Обычная оценка заказа
• Оценка короткого замыкания (минимальная)

Источники

• Фридман, Д.П .; Мудрый, Дэвид С. (1976). С. Майклсон; Р. Милнер (ред.). «Противники не должны оценивать свои аргументы» (PDF) . Языки автоматов и программирование Третий международный коллоквиум . Издательство Эдинбургского университета.
• Хендерсон, Питер; Моррис, Джеймс Х. (1976). «ленивый оценщик». Материалы 3-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '76 . стр. 95–103. дои : 10.1145/800168.811543 . S2CID   1228296 .
• Худак, Пол (сентябрь 1989 г.). «Концепция, эволюция и применение языков функционального программирования». Обзоры вычислительной техники ACM . 21 (3): 383–385. дои : 10.1145/72551.72554 . S2CID   207637854 .
• Лаунбери, Джон (1993). «Естественная семантика для ленивых вычислений». Материалы 20-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '93 . стр. 144–154. дои : 10.1145/158511.158618 . ISBN  0897915607 . S2CID   14945994 .
• Рейнольдс, Джон К. (1998). Теории языков программирования . Издательство Кембриджского университета . ISBN  9780521594141 . Проверено 23 февраля 2016 г.
• Уодсворт, Кристофер П. (1971). Семантика и прагматика лямбда-исчисления (кандидатская диссертация). Оксфордский университет.

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

• Макросы ленивых вычислений в Nemerle
• Лямбда-исчисление в библиотеках Boost на C++ языке
• Ленивая оценка в ANSI C++ путем написания кода в стиле, использующем классы для реализации замыканий функций .