stringtranslate.com

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

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

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

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

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

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

История

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

Приложения

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

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

Ленивая оценка позволяет определять структуры управления нормально, а не как примитивы или методы времени компиляции. Например, можно определить операторы if-then-else и short-circuit оценки : [11] [12]

еслиТогдаЕльсе Истина b c = b еслиТогдаЕльсе Ложь b c = c          -- или Истина || b = Истина Ложь || b = b        -- и Истина && b = b Ложь && b = Ложь

Они имеют обычную семантику, т. е. оценивает (a), тогда, если и только если (a) оценивается как true, он оценивает (b), в противном случае он оценивает (c). То есть, будет оценено ровно одно из (b) или (c). Аналогично, для , если легкая часть дает True , выражения с большим объемом работы можно было бы избежать. Наконец, при оценке , если SafeToTry ложно , не будет попытки оценить 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 ( хвост fibs )

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

Модель списка успехов

Другие применения

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

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

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

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

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

Число бета-сокращений для сокращения лямбда-терма с вызовом по необходимости не больше числа, необходимого для сокращения вызова по значению или вызова по имени . [17] [18] А в некоторых программах число шагов может быть намного меньше, например, определенное семейство лямбда-термов, использующих числительные Чёрча, выполняет бесконечное количество шагов с вызовом по значению (т. е. никогда не завершается), экспоненциальное количество шагов с вызовом по имени, но только полиномиальное число с вызовом по необходимости. Вызов по необходимости воплощает две оптимизации — никогда не повторять работу (аналогично вызову по значению) и никогда не выполнять ненужную работу (аналогично вызову по имени). [19] Ленивые вычисления также могут привести к сокращению занимаемой памяти , поскольку значения создаются по мере необходимости. [20]

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

Выполнение

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

Лень и рвение

Контроль рвения в ленивых языках

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

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

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

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

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

Ява

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

интерфейс  Ленивый < T > { T eval (); }

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

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

Ленивый < Целое число > a = () -> 1 ; for ( int i = 0 ; i < 10 ; i ++ ) { Ленивый < Целое число > b = a ; a = () -> b .eval ( ) + b .eval ( ); } System .out .println ( "a = " + a .eval ( ) ) ;

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

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

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

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

class  Memo < T > implements Lazy < T > { private Lazy < T > lazy ; // ленивое выражение, eval устанавливает его в null private T memo ; // меморандум предыдущего значения            публичная заметка ( Ленивый < T > ленивый ) { этот . ленивый = ленивый ; }        public T eval () { if ( lazy != null ) { memo = lazy . eval (); lazy = null ; } return memo ; } }

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

Ленивый < Целое число > a = () -> 1 ; for ( int i = 0 ; i < 10 ; i ++ ) { Ленивый < Целое число > b = a ; a = new Memo < Целое число > (() -> b .eval ( ) + b .eval ( ) ) ; } System .out .println ( " a = " + a .eval () ) ;

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

JavaScript

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

/** * Функции генератора возвращают объекты генератора, которые овеществляют ленивые вычисления. * @return {!Generator<bigint>} Ненулевой генератор целых чисел. */ function * fibonacciNumbers () { let memo = [ 1n , - 1n ]; // создать начальное состояние (например, вектор чисел "отрицательный Фибоначчи") while ( true ) { // повторять бесконечно memo = [ memo [ 0 ] + memo [ 1 ], memo [ 0 ]]; // обновить состояние при каждой оценке yield memo [ 0 ]; // выдать следующее значение и приостановить выполнение до возобновления } }                       let stream = fibonacciNumbers (); // создаем ленивый вычисляемый поток чисел let first10 = Array.from ( new Array ( 10 ), () => stream.next (). value ); // вычисляем только первые 10 чисел console.log ( first10 ); // вывод [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 ) >>> печать ( r ) диапазон(0, 10) >>> печать ( 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> >>> печать  итератора . next () 0
Приведенный выше пример показывает, что списки оцениваются при вызове, но в случае итератора первый элемент «0» выводится при необходимости.

.СЕТЬ

В .NET framework возможно делать ленивые вычисления с использованием класса . [30] Класс может быть легко использован в F# с использованием ключевого слова , в то время как метод будет принудительно выполнять вычисления. Существуют также специализированные коллекции, подобные тем, которые предоставляют встроенную поддержку ленивых вычислений. System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq

пусть фибоначчи = Seq . unfold ( fun ( x , y ) -> Some ( x , ( y , x + y ))) ( 0I , 1I ) фибоначчи |> 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 . Значение ; // возвращает 8 }

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

// рекурсивное вычисление n-го числа Фибоначчи public int Fib ( int n ) { return ( n == 1 ) ? 1 : ( n == 2 ) ? 1 : Fib ( n - 1 ) + Fib ( n - 2 ); }                 public void Main () { Console . WriteLine ( "Какое число Фибоначчи вы хотите вычислить?" ); int n = Int32 . Parse ( Console . ReadLine ()); Lazy < int > fib = new Lazy < int > (() => Fib ( n )); // функция подготовлена, но не выполнена bool execute ; if ( n > 100 ) { Console . WriteLine ( "Это может занять некоторое время. Вы действительно хотите вычислить такое большое число? [y/n]" ); execute = ( Console . ReadLine () == "y" ); } else execute = true ; if ( execute ) Console . WriteLine ( fib . Value ); // число вычисляется только при необходимости }

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

// активное вычисление 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 ; }​                                  // ленивая оценка 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 ; } }

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

Примечания

  1. ^ ab Лямбда-выражения Java не совсем эквивалентны анонимным классам, см. Анонимная функция#Отличия по сравнению с анонимными классами

Ссылки

  1. ^ Худак 1989, стр. 384
  2. ^ Дэвид Энтони Уотт; Уильям Финдли (2004). Концепции проектирования языков программирования. John Wiley and Sons. С. 367–368. ISBN 978-0-470-85320-7. Получено 30 декабря 2010 г.
  3. ^ Рейнольдс 1998, стр. 307
  4. ^ Бентли, Джон Луис. Написание эффективных программ. Prentice-Hall, 1985. ISBN 978-0139702440 
  5. ^ Уодсворт 1971
  6. ^ Хамер-Ходжес, Кеннет (1 января 2020 г.). Цивилизация киберпространства: борьба за цифровую демократию. BOOK WRITING Incorporated. стр. 410. ISBN 978-1-95-163044-7. Получено 29 февраля 2020 г. .
  7. ^ Хендерсон и Моррис 1976
  8. ^ Фридман и Уайз 1976
  9. ^ Рейнольдс 1998, стр. 312
  10. ^ ab Casas, A.; Cabeza, D.; Hermenegildo, MV (2006). "Синтаксический подход к объединению функциональной нотации, ленивой оценки и высшего порядка в системах LP". В Hagiya, M.; Wadler, P. (ред.). Функциональное и логическое программирование, FLOPS 2006. Lecture Notes in Computer Science. Vol. 3945. Springer. p. 149. doi :10.1007/11737414_11. ISBN 978-3-540-33438-5. Получено 14 января 2011 г.
  11. ^ "utility-ht: Data.Bool.HT.Private". hackage.haskell.org . Получено 8 января 2022 г. .
  12. ^ "The Haskell 98 Report: Standard Prelude". www.haskell.org . Булевы функции . Получено 8 января 2022 г. .
  13. ^ ab Wells, JB; Haack, C. (2002). "Типы ветвления". В Le Métayer, Daniel (ред.). Языки программирования и системы, ESOP 2002. Lecture Notes in Computer Science. Vol. 2305. Springer. pp. 129–132. doi : 10.1007/3-540-45927-8_9 . ISBN 978-3-540-43363-7.
  14. ^ ab Maessen, Jan-Willem (2002). "Eager Haskell: resource-bounded execution yields efficient iteration". Труды семинара ACM SIGPLAN Haskell 2002 года (Haskell '02): Питтсбург, Пенсильвания, США; 3 октября 2002 г. Association for Computing Machinery. стр. 38–50 См. стр. 40. doi :10.1145/581690.581694. ISBN 978-1-58113-605-0.
  15. ^ ab Ленивое и спекулятивное исполнение Батлер Лэмпсон Microsoft Research OPODIS, Бордо, Франция 12 декабря 2006 г.
  16. ^ "Недостаточно памяти при присвоении значений существующим массивам?". Ответы MATLAB . MATLAB Central.
  17. ^ Нирен, Иоахим (1996). "Функциональное вычисление как параллельное вычисление" (PDF) . Труды 23-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '96 . стр. 333–343. doi :10.1145/237721.237801. ISBN 0897917693. S2CID  7332050.
  18. ^ Нирен, Иоахим (сентябрь 2000 г.). «Равномерное слияние в параллельных вычислениях». Журнал функционального программирования . 10 (5): 453–499. doi :10.1017/S0956796800003762. S2CID  66013. Получено 7 января 2022 г.
  19. ^ ab Stelle, George Widgery (июль 2019 г.). Shared-Environment Call-by-Need (PhD). Университет Нью-Мексико. стр. 11–12 . Получено 8 января 2022 г.
  20. ↑ Крис Смит (22 октября 2009 г.). Программирование F#. O'Reilly Media, Inc. стр. 79. ISBN 978-0-596-15364-9. Получено 31 декабря 2010 г.
  21. ^ Лончбери 1993.
  22. ^ Эдвард З. Янг. «Зоопарк утечки космоса».
  23. ^ "Ленивый поиск по образцу - HaskellWiki".
  24. ^ ab Grzegorz Piwowarek, Использование лямбда-выражений для ленивых вычислений в Java, 4Comprehension, 25 июля 2018 г.
  25. ^ ab Douglas W. Jones, CS:2820 Notes, осень 2020 г., лекция 25, получено в январе 2021 г.
  26. ^ Interface Suppier<T>, получено в октябре 2020 г.
  27. ^ Блох, Джошуа (2018). «Effective Java: Programming Language Guide» (третье изд.). Addison-Wesley. ISBN 978-0134685991.
  28. ^ "2. Встроенные функции — документация Python 2.7.11".
  29. ^ "2. Встроенные функции — документация Python 3.5.1".
  30. ^ "Класс Lazy(T) (система)". Microsoft.

Источники

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