Ленивые вычисления
May. 23rd, 2010 12:33 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonЧитаю статью про F# в очередном номере ПФП, а там стандартный набор бреда про сабж:
В противоположность жадному подходу существует стратегия ленивых вычислений, которая позволяет вычислять значение выражения только тогда, когда оно становится необходимо. Преимуществами такого подхода являются:
• производительность, поскольку неиспользуемые значения просто не вычисляются;
• возможность работать с бесконечными или очень большими последовательностями, так как они никогда не загружаются в память полностью;
• декларативность кода. Использование ленивых вычислений избавляет программиста от необходимости следить за порядком вычислений, что делает код проще.
По пунктам:
1.
а) Что-то я не припомню, чтобы программисты на неленивых языках стали бы вычислять какие-то значения, которые потом не используют. Обычно все-таки люди достаточно разумны, чтобы их программы вычисляли ровно столько, сколько нужно.
б) Ленивость создает накладные расходы, причем существенные. Если две программы делают одно и то же, ленивый вариант никак не будет производительнее энергичного. Почему-то большинство проблем с производительностью программ на Хаскеле решают именно расстановкой всяких ! и $!, убирающих ленивость. И оптимизатор тем же занимается.
2.
С бесконечными структурами ни ленивые, ни энергичные программы работать не могут, они всегда работают с конечной их частью. Насчет больших последовательностей - в неленивых языках они доступны в виде итераторов, энуменаторов и т.п., но это несколько другая вещь, т.к. значения обрабатываются по очереди и не хранятся в памяти, в отличие от ленивых списков и структур. Если же что-то в памяти хранить, то из-за накладных расходов на ленивость ленивые языки принципиально могут хранить меньше данных в тех же объемах памяти, чем неленивые.
3.
От необходимости следить за порядком вычислений избавляет исключительно чистота, а не ленивость. Если код не весь чист (содержит побочные эффекты), то ровно наоборот - ленивость заставляет думать о порядке вычислений гораздо больше обычного, т.к. программа ведет себя не так, как обычно подсказывает интуиция. В строгих же языках порядок вычислений настолько прост и понятен, что задумываться не заставляет.
В противоположность жадному подходу существует стратегия ленивых вычислений, которая позволяет вычислять значение выражения только тогда, когда оно становится необходимо. Преимуществами такого подхода являются:
• производительность, поскольку неиспользуемые значения просто не вычисляются;
• возможность работать с бесконечными или очень большими последовательностями, так как они никогда не загружаются в память полностью;
• декларативность кода. Использование ленивых вычислений избавляет программиста от необходимости следить за порядком вычислений, что делает код проще.
По пунктам:
1.
а) Что-то я не припомню, чтобы программисты на неленивых языках стали бы вычислять какие-то значения, которые потом не используют. Обычно все-таки люди достаточно разумны, чтобы их программы вычисляли ровно столько, сколько нужно.
б) Ленивость создает накладные расходы, причем существенные. Если две программы делают одно и то же, ленивый вариант никак не будет производительнее энергичного. Почему-то большинство проблем с производительностью программ на Хаскеле решают именно расстановкой всяких ! и $!, убирающих ленивость. И оптимизатор тем же занимается.
2.
С бесконечными структурами ни ленивые, ни энергичные программы работать не могут, они всегда работают с конечной их частью. Насчет больших последовательностей - в неленивых языках они доступны в виде итераторов, энуменаторов и т.п., но это несколько другая вещь, т.к. значения обрабатываются по очереди и не хранятся в памяти, в отличие от ленивых списков и структур. Если же что-то в памяти хранить, то из-за накладных расходов на ленивость ленивые языки принципиально могут хранить меньше данных в тех же объемах памяти, чем неленивые.
3.
От необходимости следить за порядком вычислений избавляет исключительно чистота, а не ленивость. Если код не весь чист (содержит побочные эффекты), то ровно наоборот - ленивость заставляет думать о порядке вычислений гораздо больше обычного, т.к. программа ведет себя не так, как обычно подсказывает интуиция. В строгих же языках порядок вычислений настолько прост и понятен, что задумываться не заставляет.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-05-22 05:38 pm (UTC)no subject
Date: 2010-05-22 06:12 pm (UTC)Это если они об этом помнят. И база кода небольшая. И народу работает мало.
Нарушь хоть одно из условий, и всё.
no subject
Date: 2010-05-22 06:13 pm (UTC)Бодрячком, чо.
Интересно, они ещё будут проводить подобные конкурсы, с более-менее реалистичной задачей и без обязательного требования использовать ФП-инструменты? Я бы поучаствовал, наверное.
no subject
Date: 2010-05-22 06:18 pm (UTC)no subject
Date: 2010-05-22 06:19 pm (UTC)А его и не было. Среди решений были и на Visual Basic, C#, Python.
no subject
Date: 2010-05-22 06:21 pm (UTC)no subject
Date: 2010-05-22 06:59 pm (UTC)Мой любимый пример: одну и ту же штуку под названием CollisionEnvironment, что получалась в результате выборки по миру, требовали несколько систем, причём одна из них - в нескольких местах, и не всегда в каждом из них. Я как-то справился, получив пятикратное ускорение, но на этом примере я люблю демонстрировать пользу ленивых вычислений - вместо "if (ce == null) ce = вычисление" можно было бы просто создать выборку "ce=вычисление", которая бы выполнилась только тогда, когда надо. И не более одного раза.
До этого считалось, что в физике с AI особых проблем с производительностью нет. ;)
no subject
Date: 2010-05-22 07:02 pm (UTC)no subject
Date: 2010-05-22 07:11 pm (UTC)no subject
Date: 2010-05-22 07:14 pm (UTC)1. Как уже отметили выше, чтобы не вычислять лишнего на неленивых языках нужно прилагать *специальные усилия*.
2. В таком духе можно говорить о чем угодно. Речь же идет о выразительности. Кстати, из теории следует, что non-strict порядок вычислений *строго* выразительнее strict порядка.
3. Теоретически да. Но практически (не говорю об игрушечных языках) существует единственный чистый и единственный ленивый и это один и тот же язык - Haskell. В нем, если на минуту забыть об unsafe конструкциях, нет *неконтролируемых* побочных эффектов в духе любого типичного императивного языка и нет проблемы reasoning о порядке вычислений. Для нечистых же языков вообще нет никакой теории, которая хотя бы позволила дать для них определение non-strict семантики. Поэтому непонятно в каком контексте тут можно "думать о порядке вычислений гораздо больше обычного". При этом в таком (почти) строгом языке, как C/C++, порядок вычислений не прост и не понятен - загляните, например, в уложение о sequence points.
no subject
Date: 2010-05-22 08:10 pm (UTC)LazyML
Вот уж его авторы покрутились, чтобы сделать ему нормальный ввод-вывод.
no subject
Date: 2010-05-22 08:39 pm (UTC)Во первых, статья рассчитана не на матерых функциональщиков, написавших на хаскеле много разного и сталкивавшихся с утечками памяти из-за болтающихся в памяти санков. Статья рассчитана на широкую аудиторию и призвана ликвидировать пробел в русскоязычной литературе на эту тему. Между прочим, название статьи начинается со слова "Введение" не просто так :D
а) Что-то я не припомню, чтобы программисты на языках без сборки мусора не освобождали за собой память. Обычно все-таки люди достаточно разумны, чтобы их программы удаляли ненужные объекты до того, как приложение прибьет OOM killer.
б) Сборка мусора создает накладные расходы, причем существенные. Если две программы делают одно и то же, GC вариант никак не будет производительнее варианта с ручным управлением памятью. Почему-то большинство проблем с производительностью программ на C# решают именно оптимизацией управления памятью. И сборщик мусора тем же занимается.
В статье кстати сказано о возможных проблемах с производительностью, вскользь, но сказано.
Черт возьми, а я думал что программа на F# сможет обработать бесконечный список полностью, вот почитал статьи по ФП и сложилось именно такое впечатление. xD
Вообще, seq в F# - это и есть аналог Enumerable или итератора, как вам будет угодно, просто вычислительное выражение избавляет от необходимости делать все "ручками".
Ок, идем от противного. От необходимости следить за порядком вычислений избавляет чистота, но не ленивость. Следовательно, ленивость требует строгого порядка вычислений? Тоесть Haskell - это такой сплошной содом и гоморра, ребята сами себе делают хорошо пытаясь уследить за тем, в каком порядке будут выполняться отложенные вычисления?
Я придерживаюсь следующего мнения, строгий порядок вычислений необходим достаточно редко, думаю вы со мной согласитесь в этом. Обычно где-то нужен частичный порядок, а где-то строгий. Отложенные вычисления, вполне могут использоваться для организации частичного порядка вычислений. Опять же, цели глубоко осветить тему ленивости в функциональном программировании мы перед собой не ставили.
no subject
Date: 2010-05-22 08:55 pm (UTC)no subject
Date: 2010-05-22 09:08 pm (UTC)Но смысл все равно один: в природе не существует работающих нечистых ленивых языков. Вот, правда, выше thesz указал на LazyML, для меня сюрприз, что он нечистый, я всегда был уверен, что LML это HBC, то есть Хаскелл.
no subject
Date: 2010-05-22 09:11 pm (UTC)no subject
Date: 2010-05-22 09:22 pm (UTC)no subject
Date: 2010-05-22 09:41 pm (UTC)no subject
Date: 2010-05-22 09:53 pm (UTC)nice try.
no subject
Date: 2010-05-22 09:57 pm (UTC)В системе типов LazyML не было разделения на чистые выражения и выражения с побочным эффектом.
Ну, и в примерах видно, как делалось IO. И насколько всё это было хрупким. ;)
no subject
Date: 2010-05-23 01:24 am (UTC)Проблема "как мотивировать людей участвовать" имеет очень отдалённое отношение к техническим проблемам, это в чистом виде PR.
Я например до вчерашнего дня не подозревал о конкурсе и о журнале.
Лично у меня появилось желание поучаствовать, когда я прочитал что какой-то сраный функциональный lisp, на котором ныписаны 2.5 приложения, в разы выиграл по производительности у нормальных языков вроде С# и C++. Мне нравится участвовать в holywars, защищая mainstream технологии продвигаемые microsoft. По-моему результат говорит о недостаточной квалификации учасников, выбравших нормальные языки. AFAIK лисп неплох для очень узкого круга задач, экономя много времени разработки, но производительность?
no subject
Date: 2010-05-23 03:59 am (UTC)no subject
Date: 2010-05-23 04:07 am (UTC)Решения на C# и VB действительно не самые оптимальные по скорости, но, вообще говоря, в условиях конкурса скорость работы не ставилась основной целью, даже наоборот просили не увлекаться оптимизациями.
no subject
Date: 2010-05-23 04:18 am (UTC)2. Да, выразительность в ленивом языке выше. Да, теоретически можно выполнять более широкий класс программ. Об этом и надо писать, а не о бесконечных последоветельностях.
3. Я проблемы в Хаскелле и имел в виду - сколько раз начинающие программисты попадали в засаду с монадой ЙО, когда файл вдруг закрывался до начала чтения или операции с сетью откладывались до конца сессии. Эти проблемы реальны и регулярно случаются. И именно из-за смеси ленивости и сайд эффектов.
no subject
Date: 2010-05-23 04:43 am (UTC)1. Аналогия со сборщиком мусора интересна (хотя про скорость лажа написана), но как она доказывает, что ленивость добавляет производительности?
2. Про seq в курсе, только к ленивым вычислениям он мало отношения имеет, потому и доступен в неленивых языках в виде того же IEnumerable и yield return.
3. "Ок, идем от противного. От необходимости следить за порядком вычислений избавляет чистота, но не ленивость. Следовательно, ленивость требует строгого порядка вычислений? " Эту импликацию поподробнее, пожалуйста.
no subject
Date: 2010-05-23 05:09 am (UTC)2. Бесконечные программы бывают. Это такие программы, которые работают над потенциально бесконечным потоком. Они не знают, сколько этих данных будет.
С пунктом 3 согласен.