Ленивые вычисления

[thedeemon]

Читаю статью про F# в очередном номере ПФП, а там стандартный набор бреда про сабж:
В противоположность жадному подходу существует стратегия ленивых вычислений, которая позволяет вычислять значение выражения только тогда, когда оно становится необходимо. Преимуществами такого подхода являются:
• производительность, поскольку неиспользуемые значения просто не вычисляются;
• возможность работать с бесконечными или очень большими последовательностями, так как они никогда не загружаются в память полностью;
• декларативность кода. Использование ленивых вычислений избавляет программиста от необходимости следить за порядком вычислений, что делает код проще.

По пунктам:
1.
а) Что-то я не припомню, чтобы программисты на неленивых языках стали бы вычислять какие-то значения, которые потом не используют. Обычно все-таки люди достаточно разумны, чтобы их программы вычисляли ровно столько, сколько нужно.
б) Ленивость создает накладные расходы, причем существенные. Если две программы делают одно и то же, ленивый вариант никак не будет производительнее энергичного. Почему-то большинство проблем с производительностью программ на Хаскеле решают именно расстановкой всяких ! и $!, убирающих ленивость. И оптимизатор тем же занимается.

2.
С бесконечными структурами ни ленивые, ни энергичные программы работать не могут, они всегда работают с конечной их частью. Насчет больших последовательностей - в неленивых языках они доступны в виде итераторов, энуменаторов и т.п., но это несколько другая вещь, т.к. значения обрабатываются по очереди и не хранятся в памяти, в отличие от ленивых списков и структур. Если же что-то в памяти хранить, то из-за накладных расходов на ленивость ленивые языки принципиально могут хранить меньше данных в тех же объемах памяти, чем неленивые.

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

Comments

[thedeemon.livejournal.com]

1. Да, выразительнее.
http://thedeemon.livejournal.com/16444.html?thread=164924#t164924

2. Если у нас есть
let xs = большой ленивый список
res = f xs in ...
то xs все равно целиком окажется в памяти, нет?

[beroal.livejournal.com]

Я думаю, что нет.

[thedeemon.livejournal.com]

main = putStrLn $ show $ sum xs
 where
  xs = map f [1..10000000]
  f x = x*x `mod` 10

C ключом -02 работает в constant space. Без оного съедает кучу памяти и падает. Т.е. сами по себе ленивые вычисления не экономят память, только в сочетании с хорошим оптимизатором, который в сложных случаях может не справиться.

[beroal.livejournal.com]

Попробуйте так:

import Data.List
main = let
	xs = map f [1..200000]
	f x = x*x `mod` 10
	in putStrLn (show (foldl' (+) 0 xs))

Дело не в списке, а в том, что (+) не запускается сразу, а заносится в замыкание. Поэтому создаётся цепочка замыканий, длина которой равна длине списка. Думаю, strictness analyzer это пресекает.

[thedeemon.livejournal.com]

Да, точно, дело в foldl, через который определена sum. И лечится добавлением строгости. Вот видите, на ровном месте ленивость подкидывает проблем! Пока от нее не избавились, памяти потребляется даже больше, чем в чисто строгом случае с созданием списка.

[beroal.livejournal.com]

Все проблемы с хвостовой рекурсией и ленивостью описаны в Wiki.

[beroal.livejournal.com]

Sorry, Performance/Strictness.

[beroal.livejournal.com]

Если STG-machine выполнит ваш let, она создаст два замыкания. До списков она вообще касаться не будет.

[thedeemon.livejournal.com]

А можно подробнее? Какие именно замыкания?
Насколько я помню про STG, по мере потребления списка каждый его элемент будет появляться сперва в виде thunk'a, потом в санке вызов вычисления будет заменяться возвратом значения, но сам вычисленный thunk никуда не исчезнет, пока его сборщик мусора не уберет. А если у нас кто-то еще ссылается на начало списка (xs), то весь список и будет в памяти.

[beroal.livejournal.com]

Подробнее нельзя, потому что вам кусок программы слишком короткий.

Ленивый список не присутствует в памяти полностью именно потому, что его ненужный префикс убирает сборщик мусора. Вы намекаете, что в статье этого не написали?

[mr-aleph.livejournal.com]

если ленивость выражена явно в виде потока/итератора в неленивом языке --- то оставить в памяти ссылку на префикс практически невозможно...

в отличие от ленивого языка, где надо специально следить, как бы что-нибудь где-нибудь не зацепилось случайно.

[beroal.livejournal.com]

Итераторы по сути есть новый специализированный язык программирования. Конечно, специализированный язык программирования лучше языка общего назначения. Это справедливо даже для Haskell. :) Вы намекаете, что это должны были написать в статье?

[thedeemon.livejournal.com]

Не написали, вроде.

Интересно, что мешает сборщику мусора здесь:
http://thedeemon.livejournal.com/16444.html?thread=173628#t173628
(в режиме без -О2)