Почему концепция ленивой оценки полезна?

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

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

29 голосов | спросил z_axis 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 01:55:43 +0400 2012, 01:55:43

8 ответов


60

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

Классический аргумент изложен в цитированной статье «Почему функциональный «Вопросы программирования» (PDF-ссылка) Джона Хьюза. Ключевым примером в этой статье (раздел 5) является воспроизведение Tic-Tac-Toe с использованием алгоритма альфа-бета-поиска. Ключевым моментом является (стр. 9):

  

[Lazy evaluation] делает практичным модуляцию программы как генератора, который создает большое количество возможных ответов, и селектор, который выбирает соответствующий.

Программа Tic-Tac-Toe может быть записана как функция, которая генерирует все игровое дерево, начинающееся с заданной позиции, и отдельную функцию, которая его потребляет. Во время выполнения это внутренне не генерирует целое игровое дерево, а только те подчасти, которые действительно нужны потребителю. Мы можем изменить порядок и комбинацию, в которой альтернативы производятся путем изменения потребителя; не нужно вообще менять генератор.

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

  1. Объединение генерации и потребления в одну и ту же функцию;
  2. Написание производителя, который работает оптимально только для определенных потребителей;
  3. Реализация собственной версии лень.
ответил sacundim 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 05:02:29 +0400 2012, 05:02:29
31
  

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

Когда выражение является свободным от побочных эффектов, порядок, в котором эти выражения оцениваются, не влияет на их значение, поэтому на поведение программы не влияет порядок. Поэтому поведение вполне предсказуемо.

Теперь побочные эффекты - это другое дело. Если побочные эффекты могут возникать в любом порядке, поведение программы действительно было бы непредсказуемым. Но на самом деле это не так. Ленивые языки, такие как Haskell, делают его ориентированным на прозрачность, т. Е. Гарантируя, что порядок, в котором выражения оцениваются, никогда не повлияет на их результат. В Haskell это достигается за счет того, что все операции с видимыми пользователем побочными эффектами происходят внутри монады IO. Это гарантирует, что все побочные эффекты происходят точно в том порядке, в котором вы ожидаете.

ответил sepp2k 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 02:42:51 +0400 2012, 02:42:51
22

Если вы знакомы с базами данных, очень простой способ обработки данных:

  • Задайте вопрос, например select * from foobar
  • Пока есть больше данных, выполните следующие действия: получите следующую строку результатов и обработайте ее.

Вы не контролируете, как генерируется результат и каким образом (индексы? Полная таблица сканирует?) или когда (все ли данные должны генерироваться сразу или постепенно при запросе?). Все, что вы знаете: if , есть больше данных, вы получите их, когда попросите его.

Ленивая оценка довольно близка к одной и той же вещи. Скажем, у вас есть бесконечный список, определенный как ie. последовательность Фибоначчи - если вам нужно пять чисел, вы вычисляете пять чисел; если вам нужно 1000, вы получите 1000. Трюк в том, что среда выполнения знает, что обеспечить где и когда. Это очень, очень удобно.

(Java-программисты могут эмулировать это поведение с помощью итераторов - другие языки могут иметь что-то подобное)

ответил 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 02:42:10 +0400 2012, 02:42:10
14

Подумайте о том, чтобы спросить свою базу данных о списке первых 2000 пользователей, чьи имена начинаются с «Ab» и старше 20 лет. Также они должны быть мужчинами.

Вот небольшая диаграмма.

You                                            Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
                         --------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
                         --------------------- NOW I'll get them...
WAIT! Make sure they're  ---------->---------- Good idea Boss!
over 20!
                         --------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!

No that is all. :(       ---------->---------- FINE! Getting records!

                         --------------------- Here you go. 
Thanks Postgres, you're  ---------->----------  ...
my only friend.

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

В отличие от получения первых пользователей 2000, возвращающих их, фильтрации их для «Ab», их возврата, фильтрации их более 20, возврата их и фильтрации для мужчин и, наконец, их возврата.

Ленивая загрузка в двух словах.

ответил sergserg 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 02:58:14 +0400 2012, 02:58:14
9
  

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

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

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

ответил Caleb 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 02:58:24 +0400 2012, 02:58:24
5

Есть несколько аргументов для ленивой оценки, которые я считаю убедительными

  1. Модульность С ленивой оценкой вы можете разбить код на части. Например, предположим, что у вас есть проблема «найти первые десять обратных элементов в списке списка, так что обратные меньше 1». В чем-то вроде Haskell вы можете написать

    take 10 . filter (<1) . map (1/)
    

    , но это просто неверно на строгом языке, так как если вы дадите ему [2,3,4,5,6,7,8,9,10,11,12,0], вы разделите его на ноль. См. Ответ сасундима о том, почему это на практике ужасно.

  2. Работает больше вещей Строго (каламбур) больше программ заканчивается с нечеткой оценкой, чем со строгой оценкой. Если ваша программа завершается с «нетерпеливой» стратегией оценки, она прекратится с «ленивым», но oposite не соответствует действительности. В качестве конкретных примеров этого явления вы получаете такие вещи, как бесконечные структуры данных (которые на самом деле являются только интересными). Больше программ работают на ленивых языках.

  3. Оптимальность Оценка по требованию асимптотически оптимальна по времени. Хотя основные ленивые языки (которые по существу являются Haskell и Haskell) не обещают позывные, вы можете более или менее ожидать оптимальной модели затрат. Анализаторы строгости (и спекулятивная оценка) сохраняют накладные расходы на практике. Пространство - более сложный вопрос.

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

ответил Philip JF 25 72012vEurope/Moscow11bEurope/MoscowSun, 25 Nov 2012 10:12:49 +0400 2012, 10:12:49
2

Предположим, что у вас есть много дорогостоящих расчетов, но не знаете, какие из них действительно понадобятся или в каком порядке. Вы можете добавить сложный протокол mother-may-i заставить потребителя выяснить, что доступно, и инициировать расчеты, которые еще не выполнены. Или вы можете просто предоставить интерфейс, который действует так, как если бы расчеты были все сделано.

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

ответил ddyer 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 02:23:27 +0400 2012, 02:23:27
1

с ленивой оценкой вы не теряете контроль над выполнением кода, она по-прежнему абсолютно детерминирована. Однако с этим трудно привыкнуть.

ленивая оценка полезна, потому что это способ сокращения лямбда-термина, который прекратится в некоторых случаях, когда нетерпеливая оценка потерпит неудачу, но не наоборот. Это включает 1), когда вам нужно связать результаты вычислений, прежде чем выполнять вычисления, например, когда вы создаете структуру циклического графа, но хотите сделать это в функциональном стиле 2), когда вы определяете бесконечную структуру данных, но управляете этим корнем структуры, чтобы использовать только часть структуры данных.

ответил permeakra 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 07 Sep 2012 13:49:52 +0400 2012, 13:49:52

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132