В теории языков программирования ленивое вычисление или вызов по необходимости [1] — это стратегия вычисления , которая откладывает вычисление выражения до тех пор, пока не потребуется его значение ( нестрогое вычисление ), а также позволяет избежать повторных вычислений (путем использования обмена ) . [2] [3]
Преимущества ленивых вычислений включают в себя:
Ленивая оценка часто сочетается с запоминанием , как описано в книге Джона Бентли «Эффективное написание программ» . [4] После того, как значение функции вычислено для этого параметра или набора параметров, результат сохраняется в справочной таблице , которая индексируется значениями этих параметров; при следующем вызове функции таблица проверяется, чтобы определить, доступен ли уже результат для этой комбинации значений параметров. Если да, то сохраненный результат просто возвращается. Если нет, функция оценивается, и в таблицу поиска добавляется еще одна запись для повторного использования.
Ленивую оценку сложно сочетать с императивными функциями, такими как обработка исключений и ввод/вывод , поскольку порядок операций становится неопределенным.
Противоположностью ленивой оценки является нетерпеливая оценка , иногда известная как строгая оценка. Стремительная оценка — это стратегия оценки, используемая в большинстве [ количественных ] языков программирования .
Ленивое вычисление было введено для лямбда-исчисления Кристофером Уодсвортом [5] и использовано системой Plessey 250 в качестве критической части метамашины лямбда-исчисления, уменьшающей накладные расходы на разрешение для доступа к объектам в адресном пространстве с ограниченными возможностями . [6] Что касается языков программирования, его независимо представили Питер Хендерсон и Джеймс Х. Моррис [7] , а также Дэниел П. Фридман и Дэвид С. Уайз. [8] [9]
Отложенная оценка используется, в частности, в функциональных языках программирования. При использовании отложенной оценки выражение оценивается не сразу после привязки к переменной, а тогда, когда оценщик вынужден выдать значение выражения. То есть такой оператор, как x = expression;(т. е. присвоение результата выражения переменной), явно требует вычисления выражения и помещения результата в , xно то, что на самом деле находится в, xне имеет значения до тех пор, пока не возникнет необходимость в его значении. через ссылку на xв каком-то более позднем выражении, вычисление которого само по себе может быть отложено, хотя в конечном итоге быстро растущее дерево зависимостей будет сокращено, чтобы создать один символ, а не другой, который сможет увидеть внешний мир. [10]
Отложенное вычисление позволяет определять структуры управления обычным образом, а не как примитивы или методы времени компиляции. Например, можно определить операторы if-then-else и сокращенные операторы вычисления : [11] [12]
ifThenElse True b c = b ifThenElse False b c = c -- или Истина || б = Правда Ложь || б = б -- и True && b = b False && b = False Они имеют обычную семантику, т. е. оценивают (a), тогда если и только если (a) оценивается как true, он оценивает (b), в противном случае он оценивает (c). То есть будет оцениваться ровно одно из (b) или (c). Аналогично , если простая часть выдает True, можно избежать большого количества рабочих выражений. Наконец, если при оценке SafeToTry имеет значение false , попытка оценки Expression не будет предпринята .ifThenElse a b cEasilyComputed || LotsOfWorkSafeToTry && Expression
И наоборот, на энергичном языке приведенное выше определение будет оценивать (a), (b) и (c) независимо от значения (a). Это нежелательное поведение, поскольку (b) или (c) могут иметь побочные эффекты , занимать много времени для вычислений или вызывать ошибки. Обычно в энергичных языках можно вводить определяемые пользователем структуры отложенного управления в виде функций, хотя они могут отличаться от синтаксиса языка для быстрого вычисления: часто задействованные тела кода необходимо обернуть значением функции, чтобы они выполнялись только когда звонят.ifThenElse a b c
Преимущество отложенной оценки состоит в том, что она позволяет создавать вычисляемые бесконечные списки без бесконечных циклов или вопросов размера, мешающих вычислениям. Фактические значения вычисляются только при необходимости. Например, можно создать функцию, которая создает бесконечный список (часто называемый потоком ) чисел Фибоначчи . Вычисление n -го числа Фибоначчи будет просто извлечением этого элемента из бесконечного списка, что потребует оценки только первых n членов списка. [13] [14]
Возьмем, к примеру, эту тривиальную программу на Haskell :
NumberFromInfiniteList :: Int -> Int numberFromInfiniteList n = бесконечность !! n - 1 , где бесконечность = [ 1 .. ] main = print $ numberFromInfiniteList 4 В функции numberFromInfiniteList значение бесконечности представляет собой бесконечный диапазон, но до тех пор, пока не потребуется фактическое значение (или, точнее, конкретное значение по определенному индексу), список не оценивается, и даже тогда он оценивается только как необходимо (то есть до тех пор, пока не будет достигнут желаемый индекс). При условии осторожности программиста программа завершается нормально. Однако некоторые вычисления могут привести к тому, что программа попытается оценить бесконечное количество элементов; например, запрос длины списка или попытка суммировать элементы списка с помощью операции сгиба приведет к тому, что программа либо не сможет завершить работу, либо ей не хватит памяти .
В качестве другого примера, список всех чисел Фибоначчи можно записать на языке программирования Haskell следующим образом: [14]
fibs = 0 : 1 : zipWith ( + ) fibs ( хвостовые фибы ) В синтаксисе Haskell " :" добавляет элемент к списку, tailвозвращает список без первого элемента и zipWithиспользует указанную функцию (в данном случае сложение) для объединения соответствующих элементов двух списков для создания третьего. [13]
В компьютерных оконных системах отображение информации на экране управляется событиями раскрытия , которые запускают код отображения в последний возможный момент. Поступая таким образом, оконные системы избегают вычисления ненужных обновлений отображаемого содержимого. [15]
Другим примером лени в современных компьютерных системах является выделение страниц при копировании при записи или подкачка по требованию , когда память выделяется только тогда, когда значение, хранящееся в этой памяти, изменяется. [15]
Ленивость может быть полезна для сценариев с высокой производительностью. Примером может служить функция Unix mmap , которая обеспечивает загрузку страниц с диска по требованию , так что в память загружаются только те страницы, которые действительно были затронуты, а ненужная память не выделяется.
MATLAB реализует копирование при редактировании , где фактическое хранилище массивов, которые копируются, реплицируется только тогда, когда их содержимое изменяется, что может привести к ошибке нехватки памяти при последующем обновлении элемента, а не во время операции копирования. [16]
Число бета-сокращений для сокращения лямбда-члена с вызовом по необходимости не превышает количество, необходимое для сокращения вызова по значению или по имени . [17] [18] А в некоторых программах количество шагов может быть намного меньше, например, определенное семейство лямбда-термов, использующих цифры Чёрча, выполняет бесконечное количество шагов с вызовом по значению (т. е. никогда не завершается), экспоненциальное количество шагов при вызове по имени, а только полиномиальное число при вызове по необходимости. Вызов по необходимости включает в себя две оптимизации: никогда не повторять работу (аналогично вызову по значению) и никогда не выполнять ненужную работу (аналогично вызову по имени). [19] Отложенное вычисление также может привести к уменьшению объема памяти , поскольку значения создаются при необходимости. [20]
На практике ленивая оценка может вызвать значительные проблемы с производительностью по сравнению с нетерпеливой оценкой. Например, в современных компьютерных архитектурах отложить вычисление и выполнить его позже происходит медленнее, чем немедленное выполнение. Эту проблему можно облегчить с помощью анализа строгости . [19] Отложенное вычисление также может привести к утечкам памяти из-за невычисленных выражений. [21] [22]
Некоторые языки программирования по умолчанию задерживают вычисление выражений, а некоторые другие предоставляют функции или специальный синтаксис для задержки вычисления. В Miranda и Haskell вычисление аргументов функции по умолчанию задерживается. Во многих других языках вычисление может быть отложено путем явной приостановки вычислений с использованием специального синтаксиса (как в случае с " " и " " в Scheme и " " и " " в OCaml ) или, в более общем смысле, путем заключения выражения в thunk . Объект, представляющий такую явно отложенную оценку, называется ленивым будущим . Raku использует ленивую оценку списков, поэтому можно присваивать бесконечные списки переменным и использовать их в качестве аргументов функций, но в отличие от Haskell и Miranda, Raku по умолчанию не использует ленивую оценку арифметических операторов и функций. [10]delayforcelazyLazy.force
В ленивых языках программирования, таких как Haskell, хотя по умолчанию выражения вычисляются только тогда, когда они требуются, в некоторых случаях можно сделать код более «активным» — или, наоборот, снова сделать его более ленивым после того, как он стал более «торопливым». Это можно сделать, явно закодировав что-то, что требует выполнения вычислений (что может сделать код более «торопливым») или избежать такого кода (что может сделать код более ленивым). Строгая оценка обычно подразумевает рвение, но технически это разные понятия.
Однако в некоторых компиляторах реализована оптимизация, называемая анализом строгости , которая в некоторых случаях позволяет компилятору сделать вывод, что значение будет использоваться всегда. В таких случаях это может сделать выбор программиста относительно того, задавать это конкретное значение или нет, неуместным, поскольку анализ строгости приведет к строгой оценке .
В Haskell пометка полей конструктора как строгая означает, что их значения всегда будут запрашиваться немедленно. Функцию seqтакже можно использовать для немедленного запроса значения и последующей его передачи, что полезно, если поле конструктора обычно должно быть ленивым. Однако ни один из этих методов не реализует рекурсивную строгость — для этого была изобретена функция deepSeq.
Кроме того, сопоставление с образцом в Haskell 98 по умолчанию является строгим, поэтому ~необходимо использовать квалификатор, чтобы сделать его ленивым. [23]
В Java ленивая оценка может выполняться с использованием объектов, у которых есть метод для их оценки, когда значение необходимо. Тело этого метода должно содержать код, необходимый для выполнения этой оценки. С момента появления лямбда-выражений в Java SE8 Java поддерживает для них компактную нотацию. Следующий пример универсального интерфейса обеспечивает основу для отложенных вычислений: [24] [25]
интерфейс Lazy < T > { T eval (); } Интерфейс Lazyсо своим eval()методом эквивалентен интерфейсу Supplierсо своим get()методом в java.util.functionбиблиотеке. [26] [27] : 200
Каждый класс, реализующий Lazyинтерфейс, должен предоставлять evalметод, а экземпляры класса могут содержать любые значения, необходимые методу для выполнения отложенной оценки. Например, рассмотрим следующий код для ленивого вычисления и печати 2 10 :
Lazy < Integer > a = () -> 1 ; for ( int я знак равно 0 ; я < 10 ; я ++ ) { Lazy < Integer > b = a ; а = () -> б . оценка () + б . оценка (); } Система . вне . println ( "a =" + a.eval ( ) ); В приведенном выше примере переменная a изначально относится к ленивому целочисленному объекту, созданному с помощью лямбда-выражения . Оценка этого лямбда-выражения аналогична [a] созданию нового экземпляра анонимного класса , который реализуется с помощью метода eval , возвращающего 1 .() -> 1Lazy<Integer>
Каждая итерация цикла связывает a с новым объектом, созданным путем вычисления лямбда-выражения внутри цикла. Каждый из этих объектов содержит ссылку на другой ленивый объект b и имеет метод eval , который вызывается дважды и возвращает сумму. Переменная b необходима здесь для удовлетворения требования Java о том, чтобы переменные, на которые ссылаются внутри лямбда-выражения, были фактически окончательными.b.eval()
Это неэффективная программа, поскольку эта реализация ленивых целых чисел не запоминает результат предыдущих вызовов eval . Это также включает в себя значительную часть автоупаковки и распаковки . Что может быть неочевидно, так это то, что в конце цикла программа создала связанный список из 11 объектов и что все фактические добавления, участвующие в вычислении результата, выполняются в ответ на вызов в последней строке код. Этот вызов рекурсивно просматривает список для выполнения необходимых дополнений.a.eval()
Мы можем создать класс Java, который запоминает ленивый объект, следующим образом: [24] [25]
класс Memo <T> реализует Lazy <T> { private Lazy <T> lazy ; _ _ _ _ _ _ // ленивое выражение, eval устанавливает для него нулевое значение Private T memo ; // меморандум о предыдущем значении общественная памятка ( ленивый <T> ленивый ) { this . _ _ ленивый = ленивый ; } public T eval () { if ( lazy != null ) { memo = lazy . оценка (); ленивый = ноль ; } вернуть заметку ; } } Это позволяет переписать предыдущий пример и сделать его гораздо более эффективным. Если оригинал работал за время, экспоненциальное от количества итераций, мемоизированная версия работает за линейное время :
Lazy < Integer > a = () -> 1 ; for ( int я знак равно 0 ; я < 10 ; я ++ ) { Lazy < Integer > b = a ; a = new Memo < Integer > (() -> b . eval () + b . eval ()); } Система . вне . println ( "a =" + a.eval ( ) ); Лямбда-выражения Java — это всего лишь синтаксический сахар . Все, что можно записать с помощью лямбда-выражения, можно переписать как вызов создания экземпляра анонимного внутреннего класса , реализующего интерфейс, [a] и любое использование анонимного внутреннего класса можно переписать с использованием именованного внутреннего класса и любого именованный внутренний класс можно переместить на самый внешний уровень вложенности.
В JavaScript ленивые вычисления можно моделировать с помощью генератора . Например, поток всех чисел Фибоначчи можно записать с помощью мемоизации как:
/** * Функции-генераторы возвращают объекты-генераторы, которые реализуют отложенное вычисление. * @return {!Generator<bigint>} Ненулевой генератор целых чисел. */ function * fibonacciNumbers () { let memo = [ 1n , - 1n ]; // создаем начальное состояние (например, вектор чисел «негафибоначчи») while ( true ) { // повторяем бесконечно memo = [ memo [ 0 ] + memo [ 1 ], memo [ 0 ]]; // обновляем состояние каждого меморандума о выходе оценки [ 0 ]; // получаем следующее значение и приостанавливаем выполнение до возобновления } } пусть поток = fibonacciNumbers (); // создаем ленивый вычисляемый поток чисел let first10 = Array . from ( новый массив ( 10 ), () => поток . следующий (). значение ); // оцениваем только первые 10 чисел console . журнал ( первый10 ); // вывод: [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n] В Python 2.x range()функция [28] вычисляет список целых чисел. Весь список сохраняется в памяти при вычислении первого оператора присваивания, поэтому это пример нетерпеливого или немедленного вычисления:
>>> r = диапазон ( 10 ) >>> напечатайте r [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> напечатайте r [ 3 ] 3В Python 3.x range()функция [29] возвращает генератор , который вычисляет элементы списка по требованию. Элементы генерируются только тогда, когда они необходимы (например, когда print(r[3])вычисляется в следующем примере), поэтому это пример ленивой или отложенной оценки:
>>> r = диапазон ( 10 ) >>> print ( r ) range(0, 10) >>> print ( r [ 3 ]) 3В Python 2.x можно использовать функцию xrange(), которая возвращает объект, генерирующий числа в диапазоне по запросу. Преимущество в xrangeтом, что сгенерированный объект всегда будет занимать один и тот же объем памяти.
>>> r = xrange ( 10 ) >>> print ( r ) xrange(10) >>> lst = [ x для x в r ] >>> print ( lst ) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]Начиная с версии 2.2, Python реализует ленивые вычисления, реализуя итераторы (ленивые последовательности), в отличие от последовательностей кортежей или списков. Например (Python 2):
>>> числа = диапазон ( 10 ) >>> итератор = итератор ( числа ) >>> напечатать числа [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> напечатать итератор < объект listiterator по адресу 0xf7e8dd4c> >>> print iterator . следующий () 0В среде .NET можно выполнять ленивые вычисления с помощью класса . [30] Этот класс можно легко использовать в F# с помощью ключевого слова, в то время как метод будет принудительно выполнять вычисление. Существуют также специализированные коллекции, подобные этой, обеспечивающие встроенную поддержку отложенных вычислений. System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq
пусть Фибоначчи = Seq . развернуть ( fun ( x , y ) -> Some ( x , ( y , x + y ))) ( 0I , 1I ) Фибоначчи |> Seq . энное 1000 В C# и VB.NET этот класс используется напрямую. System.Lazy<T>
public int Sum () { int a = 0 ; интервал б = 0 ; Lazy < int > x = new Lazy < int > (() => a + b ); а = 3 ; б = 5 ; вернуть х . Ценить ; // возвращает 8 } Или более практичный пример:
// рекурсивный расчет n-го числа Фибоначчи public int Fib ( int n ) { return ( n == 1 ) ? 1 : ( п == 2 ) ? 1 : Фибо ( n - 1 ) + Фибо ( n - 2 ); } общественная недействительность Main () { Console . WriteLine ( "Какое число Фибоначчи вы хотите вычислить?" ); интервал n = Int32 . Разбор ( Console.ReadLine ( )) ; Lazy < int > fib = new Lazy < int > (() => Fib ( n )); // функция подготовлена, но не выполнена boolexecute ; если ( n > 100 ) { Console . WriteLine ( "Это может занять некоторое время. Вы действительно хотите вычислить такое большое число? [да/нет]" ); выполнить = ( Console . ReadLine () == "y" ); } Еще выполнить = правда ; if ( выполнить ) Console . WriteLine ( фиб . Значение ); // число вычисляется только при необходимости } Другой способ — использовать yieldключевое слово:
// нетерпеливая оценка public IEnumerable < int > Fibonacci ( int x ) { IList < int > fibs = new List < int > (); интервал предыдущая = - 1 ; ИНТ следующий = 1 ; for ( int я знак равно 0 ; я < x ; я ++ ) { int sum = предыдущая + следующая ; предыдущая = следующая ; следующий = сумма ; выдумки . Добавить ( сумма ); } вернуть фибы ; } // ленивая оценка public IEnumerable < int > LazyFibonacci ( int x ) { int prev = - 1 ; ИНТ следующий = 1 ; for ( int я знак равно 0 ; я < x ; я ++ ) { int sum = предыдущая + следующая ; предыдущая = следующая ; следующий = сумма ; сумма возврата дохода ; } }