Введение

Техника оптимизации программного обеспечения

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

История

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

Приложения

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

Выступление

Количество бета-уменьшений для приведения лямбда-терма с использованием стратегии "вызов по необходимости" не превышает количество уменьшений, необходимых при стратегиях "вызов по значению" или "вызов по имени". И для определенных программ число шагов может быть значительно меньше: например, для конкретного семейства лямбда-термов, использующих числа Черча, требуется бесконечное число шагов при стратегии "вызов по значению" (то есть вычисление никогда не завершается), экспоненциальное число шагов при стратегии "вызов по имени", но лишь полиномиальное число шагов при стратегии "вызов по необходимости". Стратегия "вызов по необходимости" сочетает в себе две оптимизации: она не повторяет вычисления (как при "вызове по значению") и не выполняет ненужные вычисления (как при "вызове по имени"). Ленивые вычисления также могут привести к уменьшению объема используемой памяти, поскольку значения создаются только при необходимости. Однако на практике ленивые вычисления могут вызывать значительные проблемы с производительностью по сравнению с нетерпеливыми вычислениями. Например, на современных компьютерных архитектурах отложенное вычисление и его последующее выполнение обычно медленнее, чем немедленное выполнение. Эту проблему можно смягчить с помощью анализа строгости.

Реализация

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