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

[thedeemon]

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

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

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

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

Comments

[mr-aleph.livejournal.com]

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

[thesz.livejournal.com]

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

Это если они об этом помнят. И база кода небольшая. И народу работает мало.

Нарушь хоть одно из условий, и всё.

[soonts.livejournal.com]

Как только эти ненужные вычисления начнут отнимать существенное время, сразу засветятся в vTune или любом другом используемом профайлере. Это произойдёт даже если много народу работают над большой базой кода и никто ничего не помнит. После этого, если есть какие-то требования к производительности (например это real-time игра, или серверное приложение), алгоритм будет оптимизирован.

[soonts.livejournal.com]

Читаю журнальчег.

Бодрячком, чо.

Интересно, они ещё будут проводить подобные конкурсы, с более-менее реалистичной задачей и без обязательного требования использовать ФП-инструменты? Я бы поучаствовал, наверное.

[zhacka (from livejournal.com)]

> и без обязательного требования использовать ФП-инструменты

А его и не было. Среди решений были и на Visual Basic, C#, Python.

[thedeemon.livejournal.com]

Надеюсь, что будут.

[potan.livejournal.com]

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

[valyagolev.net (from livejournal.com)]

После таких пунктов должно стоять "А на самом деле..."

[awson.livejournal.com]

Статью не читал и не буду, процитированный кусок действительно плох. Однако, в какой-то мере выступлю за авторов:

1. Как уже отметили выше, чтобы не вычислять лишнего на неленивых языках нужно прилагать *специальные усилия*.

2. В таком духе можно говорить о чем угодно. Речь же идет о выразительности. Кстати, из теории следует, что non-strict порядок вычислений *строго* выразительнее strict порядка.

3. Теоретически да. Но практически (не говорю об игрушечных языках) существует единственный чистый и единственный ленивый и это один и тот же язык - Haskell. В нем, если на минуту забыть об unsafe конструкциях, нет *неконтролируемых* побочных эффектов в духе любого типичного императивного языка и нет проблемы reasoning о порядке вычислений. Для нечистых же языков вообще нет никакой теории, которая хотя бы позволила дать для них определение non-strict семантики. Поэтому непонятно в каком контексте тут можно "думать о порядке вычислений гораздо больше обычного". При этом в таком (почти) строгом языке, как C/C++, порядок вычислений не прост и не понятен - загляните, например, в уложение о sequence points.

[thesz.livejournal.com]

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

LazyML

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

[usovalx.livejournal.com]

А Clean и Miranda чем не угодили?

[thedeemon.livejournal.com]

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

2. Да, выразительность в ленивом языке выше. Да, теоретически можно выполнять более широкий класс программ. Об этом и надо писать, а не о бесконечных последоветельностях.

3. Я проблемы в Хаскелле и имел в виду - сколько раз начинающие программисты попадали в засаду с монадой ЙО, когда файл вдруг закрывался до начала чтения или операции с сетью откладывались до конца сессии. Эти проблемы реальны и регулярно случаются. И именно из-за смеси ленивости и сайд эффектов.

[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. "Ок, идем от противного. От необходимости следить за порядком вычислений избавляет чистота, но не ленивость. Следовательно, ленивость требует строгого порядка вычислений? " Эту импликацию поподробнее, пожалуйста.

[zevlg.livejournal.com]

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

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

[juan-gandhi.livejournal.com]

1. Это не так. К примеру, есть конструктор множества, которому или нужно подавать размер, или не нужно (сам сосчитает). Если объявить размер ленивым, то эти два конструктора получаются практически идентичными. (И, кстати, множествам размер не нужен... но это другой вопрос.)

2. Бесконечные программы бывают. Это такие программы, которые работают над потенциально бесконечным потоком. Они не знают, сколько этих данных будет.

С пунктом 3 согласен.

[thedeemon.livejournal.com]

1. В данном примере ленивость позволит сэкономить несколько строчек исходника, но не добавит производительности, о которой речь в первом пункте.

2. Такие программы обычно отлично делают на циклах. Сделать то же на ленивом списке, например, да так, чтобы не текла память, уже заметно сложнее.

[maxim-moiseev.livejournal.com]

Так как я тоже имею отношение к статье, не могу воздержаться от комментария.

Тут собрались все умные люди, готовые прямо сказать нам(авторам) статьи на то что написан бред. (Не стану отрицать. Может быть и бред. Лично я ленивость понимаю настолько насколько она описана в 12 главе Programming in Haskell). Кроме того, автор утверждает, что точно такой же бред написан и в википедии.

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

Предложите свой вариант и мы вставим его в статью, или напишите "линивость для чайников" и мы сошлёмся.

[thedeemon.livejournal.com]

Если бы я хотел что-то прямо скзать авторам, я бы писал в обсуждении статьи. Здесь же у меня не адресованные никому конкретно мысли вслух.

Править википедию я не считаю себя вправе, да и вряд ли имею возможность (множество фанатов хаскеля быстро отменят подобную правку).

Извиняюсь за неконструктивную критику. Вы правы, конструктивная была бы лучше. До выхода номера статью не смотрел, т.к. был занят своей.

[dsorokin.blogspot.com (from livejournal.com)]

Если считать seq примером ленивых вычислений, то все три описанные в статье преимущества имеют место быть, если использовать seq. Лично я считаю, что seq достаточно ленив, поскольку он вычисляет значения по требованию. Более того, на основе seq легко построить поток (через LazyList). Думаю, что те строки были написаны под сильным впечатлением seq. Другое дело, что к этому списку можно действительно добавить такой же или больший список недостатков ленивых вычислений, но об этом речи не было.

[thedeemon.livejournal.com]

Да, про seq соглашусь. Мой rant касается haskell-style ленивых вычислений.

[beroal.livejournal.com]

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

В том и разница, что в языке с ленивой семантикой бесконечный и конечный список имеют один и тот же тип, что удобно. То есть:

• lazy выразительнее strict при чуть меньшей производительности;
• lazy кушает меньше памяти, чем strict, при равной выразительности (это для данных большого объёма, которые можно обрабатывать потоково, но strict их загружает в память целиком).

В общем, вы цепляетесь к словам. :)

[thedeemon.livejournal.com]

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

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