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

[thedeemon]

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

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

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

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

Comments

[evgeny-lazin.blogspot.com (from livejournal.com)]

Итак, поскольку стандартный набор бреда про сабж написал я, то мне за это и отвечать :)
Во первых, статья рассчитана не на матерых функциональщиков, написавших на хаскеле много разного и сталкивавшихся с утечками памяти из-за болтающихся в памяти санков. Статья рассчитана на широкую аудиторию и призвана ликвидировать пробел в русскоязычной литературе на эту тему. Между прочим, название статьи начинается со слова "Введение" не просто так :D

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

а) Что-то я не припомню, чтобы программисты на языках без сборки мусора не освобождали за собой память. Обычно все-таки люди достаточно разумны, чтобы их программы удаляли ненужные объекты до того, как приложение прибьет OOM killer.
б) Сборка мусора создает накладные расходы, причем существенные. Если две программы делают одно и то же, GC вариант никак не будет производительнее варианта с ручным управлением памятью. Почему-то большинство проблем с производительностью программ на C# решают именно оптимизацией управления памятью. И сборщик мусора тем же занимается.

В статье кстати сказано о возможных проблемах с производительностью, вскользь, но сказано.

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

Черт возьми, а я думал что программа на F# сможет обработать бесконечный список полностью, вот почитал статьи по ФП и сложилось именно такое впечатление. xD
Вообще, seq в F# - это и есть аналог Enumerable или итератора, как вам будет угодно, просто вычислительное выражение избавляет от необходимости делать все "ручками".

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

Ок, идем от противного. От необходимости следить за порядком вычислений избавляет чистота, но не ленивость. Следовательно, ленивость требует строгого порядка вычислений? Тоесть Haskell - это такой сплошной содом и гоморра, ребята сами себе делают хорошо пытаясь уследить за тем, в каком порядке будут выполняться отложенные вычисления?
Я придерживаюсь следующего мнения, строгий порядок вычислений необходим достаточно редко, думаю вы со мной согласитесь в этом. Обычно где-то нужен частичный порядок, а где-то строгий. Отложенные вычисления, вполне могут использоваться для организации частичного порядка вычислений. Опять же, цели глубоко осветить тему ленивости в функциональном программировании мы перед собой не ставили.

[mr-aleph.livejournal.com]

вы решили защитить свой бред выдав на гора еще бреда? правильный подход, одобряю!

[109.livejournal.com]

опровержение путём написания бреда, по форме отдалённо похожего на опровергаемое, но не имеющего смысла?

nice try.

[thedeemon.livejournal.com]

Я Вас не виню, бред назван стандартным, потому что встречается даже в педивикии.

1. Аналогия со сборщиком мусора интересна (хотя про скорость лажа написана), но как она доказывает, что ленивость добавляет производительности?

2. Про seq в курсе, только к ленивым вычислениям он мало отношения имеет, потому и доступен в неленивых языках в виде того же IEnumerable и yield return.

3. "Ок, идем от противного. От необходимости следить за порядком вычислений избавляет чистота, но не ленивость. Следовательно, ленивость требует строгого порядка вычислений? " Эту импликацию поподробнее, пожалуйста.

[evgeny-lazin.blogspot.com (from livejournal.com)]

кажется я вчера палку перегнул с сарказомом :)

1. Аналогия со сборщиком мусора интересна (хотя про скорость лажа написана), но как она доказывает, что ленивость добавляет производительности?

Про скорость лажа написана для того, что-бы от оригинальной цитаты далеко не уходить :D
Ленивость, на мой взгляд, может добавить производительности в сложной системе, в которой сложно или невозможно следить за тем, что нужно вычислять, а что нет и было-ли оно уже вычислено ранее.

2. Про seq в курсе, только к ленивым вычислениям он мало отношения имеет, потому и доступен в неленивых языках в виде того же IEnumerable и yield return.

Мне все же кажется что имеет, если это не так, то я даже не знаю, как можно дать определение ленивости.

Эту импликацию поподробнее, пожалуйста.

Пожалуй не буду, кажется я тут вообще что-то не то написал :D

[thedeemon.livejournal.com]

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

Это очень гипотетическая ситуация. Пока нет практических примеров и подтверждений, говорить о том, что ленивость улучшает производительность преждевременно. Если бы в исходной фразе было добавлено "гипотетически, в некоторых случаях", у меня бы не было возражений.

[zevlg.livejournal.com]

> б) Сборка мусора создает накладные расходы, причем существенные. Если две программы делают одно и то же, GC вариант никак не будет производительнее варианта с ручным управлением памятью.

это неправда! современные gc намного эфективнее работают с памятью нежели программист. Сходно с тем, что компилятры пишут более быстрый код на ассемблере нежели человек.

[mr-aleph.livejournal.com]

если повезёт. иногда не везет =)

[thedeemon.livejournal.com]

Человек пояснил потом:
"Про скорость лажа написана для того, что-бы от оригинальной цитаты далеко не уходить :D"

[zevlg.livejournal.com]

точно, у меня скрыт был этот коммент. тогда извиняюсь за баламутство