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

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

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

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

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

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

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

История

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

Приложения

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

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

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

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

 -- или 
 True   ||    б   =   Правда 
 Ложь   ||    b   =   b 

 -- и 
 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   =    бесконечность   !!    n   -   1 
     где   бесконечность   =   [  1  ..  ] 

 main   =   print   $   numberFromInfiniteList   4 

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

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

 fibs   =   0   :   1   :   zipWith   (  +  )   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 поддерживает для них компактную нотацию. Следующий пример универсального интерфейса предоставляет основу для отложенных вычислений:

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

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

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

Lazy  <  Integer  >   a   =   ()   ->   1  ; 
  for   (  int   я   знак равно   0  ;   я   <   10  ;   я  ++  )   { 
     Lazy  <  Integer  >   b   =   a  ; 
      а   =   ()   ->   б  .   оценка  ()   +   б  .   оценка  (); 
  } 
 Система  .   вне  .   println  (  "a ="   a.eval   (  +  )  ); 

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

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

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

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

класс   Memo  <T>  <T>  реализует   ;   Lazy ​ ​ ​   { 
     private   Lazy  <T> ​ ​   lazy ​     // ленивое выражение, eval устанавливает для него нулевое значение 
     Private   T   memo  ;    // меморандум о 

     public   Memo  (  Lazy  <T>  lazy  значении   )  {   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 — это всего лишь синтаксический сахар . Все, что можно записать с помощью лямбда-выражения, можно переписать как вызов создания экземпляра анонимного внутреннего класса , реализующего интерфейс. и любое использование анонимного внутреннего класса может быть переписано с использованием именованного внутреннего класса, и любой именованный внутренний класс может быть перемещен на самый внешний уровень вложенности.

JavaScript

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

/** 
 * Функции-генераторы возвращают объекты-генераторы, которые реализуют отложенное вычисление. 
  * @return {!Generator<bigint>} Ненулевой генератор целых чисел. 
  */ 
 function  *   fibonacciNumbers  ()   { 
     let   memo   =   [  1n  ,   -  1n  ];    // создаем начальное состояние (например, вектор чисел «негафибоначчи») 
     while   (  true  )   {   // повторяем бесконечно 
         memo   =   [  memo  [  0  ]   +   memo  [  1  ],   memo  [  0  ]];    // обновляем состояние каждого 
         о выходе   меморандума  оценки [  0  ];    // получаем следующее значение и приостанавливаем выполнение до возобновления 
     } 
 } 

 letstream   fibonacciNumbers   =   (  );    // создаем ленивый вычисляемый поток чисел 
 let   first10   =   Array  .   from  (  новый   массив  (  10  ),   ()   =>   поток  .  следующий  ().  значение  );    // оцениваем только первые 10 чисел 
 console  .   журнал  (  первый10  );    // вывод: [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n] 

Питон

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

>>>  r   =   диапазон  (  10  ) 
 >>>  напечатайте   r 
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
 >>>  напечатайте   r  [  3  ] 
 3 

В Python 3.x range() функция возвращает генератор , который вычисляет элементы списка по требованию. Элементы генерируются только тогда, когда они необходимы (например, когда 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 

В приведенном выше примере показано, что списки оцениваются при вызове, но в случае итератора первый элемент «0» печатается при возникновении необходимости.

.NET

В среде .NET можно выполнять отложенную оценку с помощью класса System.Lazy<T>. Этот класс можно легко использовать в F# с помощью lazy ключевое слово, в то время как forceметод приведет к принудительной оценке. Есть также специализированные коллекции, такие как Microsoft.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   =   предыдущая   +   следующая  ; 
          предыдущая   =   следующая  ; 
          следующий   =   сумма  ; 
         дохода   возврата    сумма  ; 
      } 
 } 

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

См. также

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

Источники

• Фридман, Д.П .; Мудрый, Дэвид С. (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++ путем написания кода в стиле, использующем классы для реализации замыканий функций .