Лень боятьсяСергей Зефиров |
Аннотация: Интересующиеся функциональным программированием часто встречают прилагательное «ленивый» в связи с такими существительными, как «язык» и «порядок вычислений». Встретив же, идут в интернет и находят что-то наподобие «ленивый порядок вычислений, иначе называемый вызов-по-необходимости, строго нормализующий порядок вычислений, удовлетворяющий условиям алмазной леммы Чёрча-Россера», после чего ближайшее знакомство с функциональными языками откладывается на потом.Небольшой опус, введение к которому вы читаете, представляет собой попытку неформально объяснить, что же такое «ленивые вычисления». Они часто встречаются в повседневной жизни программиста и, на мой взгляд, по своей сути не сложнее новой платформы или компьютерной архитектуры.
1 Обязательное условие
Ни один язык программирования не обходится без условных конструкций. В большинстве языков они являются неотъемлемой частью синтаксиса и семантики (смысла конструкций языка) и поэтому воспринимаются как нечто, данное свыше. Соответственно, их редко рассматривают в подробностях, хотя они весьма интересны, ведь именно здесь программист впервые встречается с ленивыми вычислениями.
На Си и его спутниках самая распространенная условная конструкция — оператор ветвления if
:
При рассуждении о программе с условием мы делаем, фактически, подстановку действий: сначала из action1, а потом из action2. При её выполнении процессор и в самом деле выполняет подстановку — по крайней мере, результат выполнения программы с условными переходами на глаз неотличим от результата выполнения программы с условной подстановкой.
Умозрительная и физическая подстановки действий грубо соответствуют одному из порядков вычисления функциональных программ — порядку под названием call-by-name (передача-по-имени). Вкратце его можно описать так: ничего не вычисляй сразу, результаты вычислений могут не понадобиться, запоминай вычисления. В императивных языках считается, что вычисления внутри одной из ветвей понадобятся сразу, как только станет возможным вычислить условие.
Обычная реализация передачи-по-имени сводится к построению структур в памяти: вместо вычисления x+y создаётся узел дерева +(x,y), вместо тяжёлого вызова f(x) создаётся узел call(f,x). Когда же требуется значение вычисления, вызывается интерпретатор структур.
Более привычный порядок вычислений называется call-by-value (передача-по-значению). В нём всё честно: всё надо вычислять всегда. Увидев вычисление, надо немедленно его произвести, сохранить результат в переменную, подставить как аргумент или вернуть как результат выполнения функции. Большинство языков программирования так себя и ведут большую часть времени, пока не дойдут до условного оператора. Такая смесь двух способов вычислений с преобладанием call-by-value называется энергичным порядком вычислений [2].
Передача-по-значению приводит к необходимости защиты от излишних вычислений, как в примере из Таблицы 1. Сначала результат сложного и дорогого вычисления требовался в обеих ветвях условия. Потом у нас изменились требования, он стал требоваться только в одной ветви, и, по-хорошему, нам надо перенести вычисления внутрь условия.
Если бы мы использовали порядок вычисления call-by-name, то можно было бы остановиться на втором варианте, сэкономив время на рефакторинг. При выполнении в x положат не результат, а запрос на вычисления, переменная a также будет работать с запросом, и он будет вычислен, только когда (и если!) понадобится.
Прямое использование call-by-name с её практически текстовыми подстановками само по себе не очень эффективно. Возьмем простую последовательность: x=z+1; y=x×x. В y попадёт запрос на вычисление ×(+(z,1), +(z,1)). Значение z будет вычислено два раза, два раза будет выполнено сложение. Пустая трата ресурсов.
Поэтому был изобретён ещё один способ вычислений — call-by-need. Это подстановка с запоминанием. Последовательность x=z+1; y=x×x так и останется этой последовательностью. Если нам потребуется y, то мы вычислим левый аргумент выражения x, и далее по цепочке, и запомним, что x чему-то равен. Когда мы приступим к вычислению правого аргумента умножения, мы просто возьмём уже вычисленное значение. Вуаля! Вычисление z требуется всего один раз, и сложение срабатывает тоже один раз.
Метод call-by-need называется «ленивым порядком вычислений».
Таким образом, мы имеем дело с тремя методами вычислений:
- call-by-value
- Известен как «энергичный порядок вычислений» или «строгий порядок вычислений». Встречается чаще всего. Вычислит всё, до чего дотянется, если не контролировать каждый шаг. Для полноценной работы1 требует call-by-name в заметных дозах. Проще всего реализуется, поэтому столь распространён.
- call-by-name
- Простая подстановка структуры вычислений. Вычислит только нужное, но может вычислять некоторые части нужного большее количество раз, чем требуется. В языках программирования встречается в малых объёмах из-за низкой эффективности реализации. Основной прием в рассуждениях о программах, как императивных, так и функциональных.
- call-by-need
- Ленивый порядок вычислений. Со стороны выглядит как предыдущий, только работает быстрее. Считается, что встречается редко и только в специально отведённых местах. Тем не менее, он часто встречается в обычных программах (вычисление по требованию с запоминанием) и используется при оптимизации программ для устранения повторных вычислений.
Только один известный язык программирования — Algol-60 — использовал семантику call-by-name в промышленных масштабах. Остальные либо подходят к делу не столь радикально и применяют её только по месту, либо делают гораздо более широкий шаг и сразу берутся за полностью ленивые вычисления.
Главное — то, что некоторая ленивость присутствует практически в любом языке программирования. Без неё никуда, всего же на свете не вычислишь.
2 Сравнение с лучшим образцом
Одним из немногих языков, использующих ленивый порядок вычислений, является Haskell. Вот пример небольшой функции на нём:
Это определение оператора &&
путём сравнения с образцом. Всё достаточно прозрачно: если False
хотя бы слева, то что бы ни было справа, ответом будет False
, поэтому переменная x игнорируется. Если же слева True
, то результатом будет значение справа.
Результатом False
&&
error
будет False — до "unreachable!"
error
дело не дойдёт. А результатом 10/0 == 10 &&
True
будет деление на ноль.
Для выбора одного из клозов &&
нам надо вычислить левый аргумент. Если его значение равно False
, то правый аргумент вообще не понадобится!
Внимательный читатель наверняка уже сопоставил эти правила с правилами вычисления логических связок в языке Си и его спутниках, где логические связки также вычисляются до понимания результата и не дальше. В условии if
(
i
>=0 &&
i
<10 &&
arr
[
i
] !=
EOF
) ...
до проверки arr
[
i
]
дело может не дойти (как выше не запустился error
)."unreachable!"
В стандартном Паскале, где нет закорачивания вычислений логических связок (short circuit evaluation [5]), все выражения в приведенном выше условии будут вычислены. В результате мы получим ошибку выхода за границы массива, несмотря на то, что проверили все условия.
В C++ нас ожидает другой сюрприз: если мы попытаемся переопределить оператор &&
для нового типа данных, мы с удивлением обнаружим, что &&
вычисляет оба аргумента.
Ниже я приведу ещё один пример на Хаскеле, на этот раз для логического типа со значением «Unknown
»:
Только в случае, когда мы не уверены в левом аргументе, мы вынуждены вычислять правый. Поэтому ошибку обращения вне границ массива, как в примере тремя абзацами выше, мы получим, только если мы не сможем чётко понять, больше ли i нуля и меньше ли i десяти. Но в этом случае мы эту ошибку заслужили, по-моему.
При реализации на C++ типа enum
{
False
,
True
,
Unknown
}
оператор &&
для него будет вести себя одинаково плохо вне зависимости от степени нашей уверенности в результатах сравнения — он всегда будет вычислять оба операнда. Нам придётся придумывать что-то ещё, например, применять указатели. Чего мы не заслужили — то, что может быть автоматизировано,
должно быть автоматизировано.
Логические связки — это второе и последнее место в привычных языках программирования, где дела могут идти ленивым порядком. Остальное реализуется с помощью обычного программного кода, более или менее независимого от языка программирования, о чём будет следующая часть.
3 Ленивый код
Выборка данных по SQL запросу часто осуществляется чем-то вроде строящегося в процессе работы итератора. Мы создаём структуру данных с двумя функциями: получить голову и получить хвост. Голова будет очередной строкой выборки, а хвост будет вычислением, позволяющим получить последующие строки (если они есть), по одной строке с хвостом за раз. Это и есть итератор, только потенциально бесконечный.
И тут мы подходим к причине, по которой ленивые языки трудно использовать.
Мы создали запрос к БД и даже что-то из неё выбрали. В процессе мы решили, что в БД чего-то не хватает, и добавили туда информацию, которая может влиять на содержимое нашего SQL запроса. Совсем плохо, если это решили и добавили не мы.
Получается, что мы можем получить данные, в которых, допустим, нарушен порядок сортировки строк. Или можем не получить актуальные данные.
Иными словами, работая лениво, мы не можем вести простые рассуждения о последовательности действий. А раз не можем рассуждать о последовательности, то не можем просто предсказать время работы.
Это приводит к необходимости чётко разграничивать участки программы, где последовательность действий надо контролировать, и остальные, где такой контроль не нужен2.
В этом есть и плюсы, и минусы. С одной стороны, добавляется работы по разделению программы на разные участки — это минус. С другой стороны, как показывает практика, количество кода, где неважно, что за чем будет вычисляться, больше в разы, если не на порядки.
Получается, что мы экономим свой труд, поскольку в большем количестве мест дополнительная работа не требуется. Экономия состоит и в отсутствии необходимости рефакторинга, и в простоте самого рефакторинга: в коде, где нет зависимости от порядка вычислений, порядок определений не важен. Последовательности определений «x=f(z); y=g(x);» и «y=g(x); x=f(z);» имеют один и тот же смысл. Мы упрощаем для себя рассуждения о программе, поскольку можем проводить простую текстовую подстановку без оглядок на состояние мира или переменных. Мы, наконец, можем заглядывать глубоко в структуры данных и использовать их части напрямую, без боязни, что кто-то их поменяет.
4 Размышления
Уже достаточно долго меня мучает вопрос: почему ленивые вычисления так тяжело воспринимаются даже весьма умными людьми? Что их останавливает?
Более или менее приемлемый ответ пришёл ко мне после знакомства с различными параллельными архитектурами вычислительных систем. Если быть кратким, то обычный процессор умеет делать scatter (писать в любое место памяти) и gather (читать из любого места памяти). Трудности синхронизации двух параллельно выполняющихся процессов разбрасывания и собирания данных велики, поэтому их как-то ограничивают: отдавая предпочтение одному из них при реализации, разделяя их во времени3 или действуя иначе. Например, процессоры GPU умеют только gather (причем, в ограниченном объёме), машины динамического потока данных — scatter (и тоже в ограниченном объёме). Труден и анализ произвольной рекурсии, поэтому от неё тоже избавляются (GPU).
Например, на GPU делать обработку изображений просто, а анализ — тяжело; с задачей «получить N координат максимальных4 результатов обработки изображения» мы не смогли справиться за пару недель. На GPU нельзя сделать сортировку слиянием или быструю сортировку, надо делать bitonic sort, при этом управление сортировкой внешнее (рекурсии-то нет, как и локальных массивов); в цикле вычисляются параметры очередного прохода и запускается шаг параллельного алгоритма. Для программ типа компиляторов GPU вообще не применимо — в компиляторах используются практически неограниченные структуры, не ложащиеся на массивы.
Изучение программирования GPU имеет вполне определённую цель — ускорить выполнение программ. Но это подходит не для любых программ — компиляторы от использования GPU только проиграют, на данный момент. Поэтому создатели компиляторов на GPGPU5 не смотрят.
Применение ленивых вычислений может сократить код логики программы, тех вычислений, что можно записать в нём с выгодой. Но они не помогут, когда большую часть времени занимает ввод-вывод или когда требуется удовлетворить неким временным условиям.
По-моему, в этом GPU и ленивые вычисления схожи: они подходят не для всех задач, надо с ними разбираться, чтобы понимать, могут ли они пригодиться в конкретных задачах. Многих это и останавливает, поскольку «известный путь самый короткий». Но наблюдения показывают, что области применения как GPU, так и ленивых вычислений расширяются: в GPU не так давно добавили практически произвольную рекурсию, а ленивые вычисления помогают лучше структурировать анализ при обработке в условиях временных ограничений6.
Уподобление ленивых вычислений компьютерной архитектуре позволяет провести ещё одну интересную параллель. Языки программирования с ленивым порядком вычислений можно представить как автокод немного непривычного компьютера или виртуальной машины. Ну, ещё одна архитектура, сколько их в карьере программиста. А автокоды бывают очень пристойными: «Советская Ада» Эль-76 Эльбруса, Java для JavaVM, C# для .Net. В свое время на автокоде МИР (Машины для Инженерных Расчётов) [7] решали весьма серьёзные задачи, к которым было трудно подступиться на машинах побольше.
5 Чистый параллелизм
Раз речь зашла о параллельных архитектурах, нельзя не упомянуть и о том, как распараллеливание связано с разбиением на чистый код (без побочных эффектов) и остальной.
Если в двух внешне независимых участках кода есть вызов функции с неизвестным побочным эффектом (допустим, отладочная печать), то выполнять эти участки кода параллельно нельзя, поскольку порядок вызова этих внешних функций может измениться.
Чистый же код можно переставлять, как угодно [1] — зависимости в нем выражены исключительно явным образом. Это не означает лёгкости анализа для автоматического распараллеливания, но упрощает ручное распараллеливание. Практика показывает, что это действительно так: изменения в двух строках одного многопроходного оптимизатора нашего проекта ускорили процесс оптимизации на 10% на двух ядрах по сравнению с одним. Код оптимизатора занимает порядка 800 строк, то есть, мы получили 10% ускорения за счёт 0.3% изменений кода. Получается, что ленивый порядок вычислений, заставивший нас трудиться над разбиением кода на отдельные части, подготовил код для параллельного выполнения.
Более того, в чистом коде без побочных эффектов проще проверять всякого рода условия, например, что мы не зациклимся, или что не будет ошибок обращений к массивам [6].
6 Заключение
Приведу немного статистики. В gcc 4.2.2, большом проекте на C, есть файл bitmap.c. Он довольно средний по размерам: 1500 строк, 40 функций. Он содержит 132 оператора if
и один тернарный оператор ?:
. Таким образом, на функцию приходится более трех операторов if
, по одному условному оператору на каждые 12 строк. Получается, что мы, обычные программисты, используем грубый аналог call-by-name примерно 5—6 раз за рабочий день7.
Можно оценить и количество использования ленивых вычислений в gcc. Поиск «grep -E -i recog_memoiz *.c» дал 13 файлов из 299 (33 использования) всё того же gcc 4.2.2. Везде используется call-by-need — производится вычисление и запоминается промежуточный результат. Немного, но используется.
Если интересно, поищите у себя в коде что-либо наподобие установки в конструкторе некоего поля в NULL, и чтобы рядом где-нибудь был getter вида:
Наверняка найдётся нечто похожее, что означает наличие ленивых вычислений.
Не стоит бояться ленивых вычислений. Они встречаются даже чаще, чем я думал, и гораздо привычней, чем принято считать. Они позволяют структурировать программу так, что в ней открываются новые возможности для экономии времени программиста и увеличения скорости работы на современных системах. И уж тем более не стоит бояться ленивых языков программирования: они не страшней автокода многих существующих, или существовавших ранее, машин.
Список литературы
- [1]
- Data dependencies. Ссылка в Wikipedia, http://en.wikipedia.org/wiki/Data_dependencies. О зависимости по данным и их влиянии на параллелизм. В этой статье говорится только про параллелизм уровня инструкций, но если поставить части массивов или других структур данных на место переменных, то получим всё то же самое, только для параллелизма большего объёма.
- [2]
- Evaluation strategy. Статья в Wikipedia, http://en.wikipedia.org/wiki/Evaluation_strategy. Описываются все известные порядки вычислений.
- [3]
- General-purpose computation on graphics processing units. http://gpgpu.org/. Об использовании GPU в гражданских целях.
- [4]
- General-purpose computing on graphics processing units. Ссылка в Wikipedia, http://en.wikipedia.org/wiki/GPGPU. О технике использования графического процессора видеокарты для общих вычислений.
- [5]
- Short circuit evaluation. Статья в Wikipedia, http://en.wikipedia.org/wiki/Short_circuit_evaluation. Логические операторы в разных языках программирования.
- [6]
- Single Assignment C. http://www.sac-home.org/. Чего можно добиться, отказавшись от разрушающего присваивания.
- [7]
- Машина для Инженерных Расчётов. Ссылка в Wikipedia, http://ru.wikipedia.org/wiki/МИР_(компьютер). Об одной из первых в мире персональной ЭВМ, созданной в 1965 году Институтом кибернетики Академии наук Украины. МИР выпускалась серийно и предназначалась для использования в учебных заведениях, инженерных бюро и научных организациях.
- [8]
- Bingsheng He, Naga K. Govindaraju, Qiong Luo, and Burton Smith. Efficient gather and scatter operations on graphics processors. 2008. О реализации произвольного доступа к памяти на GPU.
- [9]
- Oleg Kiselyov. Incremental multi-level input processing with left-fold enumerator: predictable, high-performance, safe, and elegant. О безопасном применении ленивых итераторов. Предназначено для сильных духом, поскольку содержит магию типов Haskell высшего уровня., 2008.
- [10]
- Neil Mitchell. Catch: Case Totality Checker for Haskell. Проверка полноты разбора по образцу. По сравнению с тестами экономит время; отыскивает ошибки, которые тесты отловить не в состоянии.
- 1
- Call-by-name и call-by-need Тьюринг-полны, в то время как основная для большинства языков семантика сall-by-value не является Тьюринг-полной. Условные конструкции с семантикой сall-by-name обеспечивают таким языкам Тьюринг-полноту.
- 2
- В современных функциональных языках такое разграничение поддерживается системой типов.
- 3
- Что может сказаться на производительности.
- 4
- Максимальных по какому-то критерию, например, по величине результатов алгоритма определения подходящих для отслеживания точек — чем выше «яркость», тем лучше отслеживать.
- 5
- Техника использования графического процессора видеокарты для общих вычислений, см. [4].
- 6
- Приём очень простой: создаётся (практически бесконечный) генератор итераций анализа. Управляющая часть программы выбирает из потока итераций до тех пор, пока не кончится время на реакцию или не будет найдено удовлетворительное решение. Таким образом, анализ не знает о временных ограничениях, а управляющая часть — об алгоритме.
- 7
- ≈17000 отлаженных строк кода в год для программистов вне США. 68 строк кода в день.
Этот документ был получен из LATEX при помощи HEVEA