Ленивые вычисления
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 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 09:11 pm (UTC)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:57 pm (UTC)В системе типов LazyML не было разделения на чистые выражения и выражения с побочным эффектом.
Ну, и в примерах видно, как делалось IO. И насколько всё это было хрупким. ;)
no subject
Date: 2010-05-23 04:18 am (UTC)2. Да, выразительность в ленивом языке выше. Да, теоретически можно выполнять более широкий класс программ. Об этом и надо писать, а не о бесконечных последоветельностях.
3. Я проблемы в Хаскелле и имел в виду - сколько раз начинающие программисты попадали в засаду с монадой ЙО, когда файл вдруг закрывался до начала чтения или операции с сетью откладывались до конца сессии. Эти проблемы реальны и регулярно случаются. И именно из-за смеси ленивости и сайд эффектов.
no subject
Date: 2010-05-23 06:31 am (UTC)no subject
Date: 2010-05-23 05:32 pm (UTC):)
no subject
Date: 2010-05-30 07:50 pm (UTC)Они делали hGetContents и hClose?
no subject
Date: 2010-05-31 05:46 am (UTC)no subject
Date: 2010-05-31 08:45 am (UTC)