Каковы пункты строгости Haskell?

Question

Мы все знаем (или должны знать), что Haskell по умолчанию ленив.Ничто не оценивается, пока оно не должно быть оценено.Так когда же нужно что-то оценивать?Есть моменты, где Haskell должен быть строгим.Я называю эти «точками строгости», хотя этот конкретный термин не так широко распространен, как я думал.По моему мнению:

Сокращение (или оценка) в Haskell только происходит в точках строгости.

Так что вопрос: что, точно , это точки строгости Haskell? Моя интуиция говорит, что шаблоны main, seq / bang, сопоставление с образцом и любые действия IO, выполняемые с помощью main, являются основной строгостьюбаллов, но я не знаю, почему я это знаю.

(Кроме того, если они не называются «точками строгости», что они называют «1019» ?)

Полагаю, что хороший ответ будет включать в себя обсуждение WHNF и так далее.Я также думаю, что это может коснуться лямбда-исчисления.

---

Редактировать: дополнительные мысли по этому вопросу.

Поскольку я размышлял над этим вопросом, я думаю,было бы яснее добавить что-то к определению точки строгости.Точки строгости могут иметь различную контексту и различную глубину (или строгость).Возвращаясь к моему определению, что «сокращение в Haskell происходит только в точках строгости», давайте добавим к этому определению следующее условие: «точка строгости срабатывает только тогда, когда ее окружающий контекст оценивается или уменьшается».

ИтакПозвольте мне начать с того ответа, который я хочу.main - точка строгости.Он специально обозначен в качестве основного пункта строгости его контекста: программы.Когда программа (контекст main) оценивается, активируется точка строгости main.Глубина Main максимальна: она должна быть полностью оценена.Main обычно состоит из действий ввода-вывода, которые также являются точками строгости, контекст которых main.

Теперь попробуйте: обсудите seq и сопоставление с образцом в этих терминах.Объясните нюансы применения функции: насколько она строгая?Как это не так?А как насчет deepseq?let и case заявления?unsafePerformIO?Debug.Trace?Определения верхнего уровня?Строгие типы данных?Шаблоны взрыва?И т. Д. Сколько из этих элементов можно описать в терминах просто seq или сопоставления с образцом?

Answer 1

Хорошее место для начала - понимание этой статьи: Естественная семантика для ленивой оценки (Launchbury).Это скажет вам, когда выражения оцениваются для небольшого языка, похожего на ядро ​​GHC.Тогда оставшийся вопрос заключается в том, как отобразить полный Haskell на Core, и большая часть этого перевода дается самим отчетом Haskell.В GHC мы называем этот процесс «десагерингом», потому что он удаляет синтаксический сахар.

Ну, это не вся история, потому что GHC включает в себя целый ряд оптимизаций между десагерингом и генерацией кода, и многие из этих преобразований будутпереставьте Ядро так, чтобы вещи оценивались в разное время (в частности, анализ строгости приведет к тому, что вещи будут оцениваться раньше).Таким образом, чтобы действительно понять, как ваша программа будет оцениваться, вам нужно взглянуть на ядро, созданное GHC.

Возможно, этот ответ кажется вам несколько абстрактным (я не упомянул конкретноbang pattern или seq), но вы попросили что-то точное , и это лучшее из того, что мы можем сделать.

Answer 2

Я бы, вероятно, переформулировал этот вопрос следующим образом: При каких обстоятельствах Хаскелл оценит выражение? (Возможно, отметьте «нормальная форма слабой головы».)

В первом приближении, мы можем указать это следующим образом:

• Выполнение действий ввода-вывода оценит любые выражения, которые им «нужны». (Таким образом, вам нужно знать, выполняется ли действие ввода-вывода, например, его имя является основным, илион вызывается из main И вам нужно знать, что нужно для действия.)
• Выражение, которое оценивается (эй, это рекурсивное определение!), оценит любые выражения, в которых оно нуждается.

Из вашего интуитивного списка основные и IO-действия попадают в первую категорию, а seq и сопоставление с образцом попадают во вторую категорию.Но я думаю, что первая категория в большей степени соответствует вашей идее «точки строгости», потому что именно так мы заставляем оценку в Haskell стать наблюдаемыми эффектами для пользователей.

Подробное описание всех деталей является большой задачей, поскольку Haskell - это большой язык.Это также довольно тонко, потому что Concurrent Haskell может оценивать вещи спекулятивно, даже если мы в конечном итоге не используем результат в конце: это третье поколение вещей, которые вызывают оценку.Вторая категория довольно хорошо изучена: вы хотите взглянуть на строгость задействованных функций.Первая категория также может рассматриваться как своего рода «строгость», хотя это немного хитроумно, потому что evaluate x и seq x $ return () на самом деле разные вещи!Вы можете обращаться с этим должным образом, если вы дадите какую-то семантику монаде ввода-вывода (явно передавая токен RealWorld#, работающий для простых случаев), но я не знаю, есть ли название для такого вида стратифицированного анализа строгости в целом.

Answer 3

C имеет концепцию точек последовательности , которые гарантируют для определенных операций, что один операнд будет оценен перед другим. Я думаю, что это наиболее близкая существующая концепция, но по существу эквивалентный термин точка строгости (или, возможно, точка силы ) больше соответствует мышлению Хаскелла.

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

& hellip;

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

$! определяется как seq.

- Ленивый против нестрогого .

Так что ваше мышление о ! / $! и seq по существу правильно, но сопоставление с образцом подчиняется более тонким правилам. Конечно, вы всегда можете использовать ~ для принудительного сопоставления с образцом. Интересный момент из той же статьи:

Анализатор строгости также ищет случаи, когда подвыражения всегда требуются внешним выражением, и преобразует их в нетерпеливую оценку. Это может быть сделано, потому что семантика (в терминах «дна») не меняется.

Давайте продолжим по кроличьей норе и посмотрим на документы для оптимизации, выполненной GHC:

Анализ строгости - это процесс, с помощью которого GHC пытается во время компиляции определить, какие данные определенно «всегда будут необходимы». Затем GHC может создать код для простого вычисления таких данных, а не обычный процесс (с большими накладными расходами) для сохранения вычисления и его последующего выполнения.

- Оптимизация GHC: анализ строгости .

Другими словами, строгий код может быть сгенерирован в любом месте в качестве оптимизации, потому что создание блоков неоправданно дорого, когда данные всегда будут нужны (и / или могут использоваться только один раз).

& hellip; больше оценки невозможно выполнить для значения; говорят, что он находится в нормальной форме . Если мы находимся на каком-либо из промежуточных этапов, чтобы выполнить хотя бы некоторую оценку значения, оно находится в нормальной форме слабой головы (WHNF). (Существует также «нормальная форма головы», но она не используется в Haskell.) Полная оценка чего-либо в WHNF сводит его к чему-то в нормальной форме & hellip;

& mdash; Wikibooks Haskell: Лень

(Термин в нормальной форме головы , если в положении головы нет бета-переопределения ¹ . Редекс - это пересмотр головы, если он предшествуют только лямбда-абстракционеры не переопределения ² .) Поэтому, когда вы начинаете форсаж, вы работаете в WHNF; когда не осталось громов, чтобы быть в силе, вы в нормальной форме. Еще один интересный момент:

& hellip; если в какой-то момент нам потребуется, скажем, распечатать z для пользователя, нам потребуется полностью оценить его & hellip;

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

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

Answer 4

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

Хороший источник для модели "ленивости" в haskell можно найти здесь: http://en.wikibooks.org/wiki/Haskell/Laziness

В принципе, важно понимать разницу между thunk и слабым заголовком нормальной формы WHNF.

Насколько я понимаю, haskell тянет вычисления назад по сравнению с императивными языками. Это означает, что в отсутствие шаблонов "seq" и "взрыва" в конечном итоге это будет своего рода побочным эффектом, который заставляет оценивать тук, что может в свою очередь вызывать предварительные оценки (истинная лень).

Поскольку это может привести к ужасной утечке пространства, компилятор затем выясняет, как и когда нужно заранее оценить thunks для экономии места. Затем программист может поддержать этот процесс, предоставив аннотации строгости (en.wikibooks.org/wiki/Haskell/Strictness, www.haskell.org/haskellwiki/Performance/Strictness), чтобы дополнительно сократить использование пространства в виде вложенных групп.

Я не эксперт по операционной семантике haskell, поэтому я просто оставлю ссылку в качестве ресурса.

Еще несколько ресурсов:

http://www.haskell.org/haskellwiki/Performance/Laziness

http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation

Answer 5

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

Для начинающих основное правило: let ленив, case менее ленив.

Answer 6

Это не полный ответ, нацеленный на карму, а всего лишь часть головоломки - в той степени, в которой речь идет о семантике, имейте в виду, что существует несколько стратегий оценки, которые обеспечивают одинаковую семантика. Одним хорошим примером здесь - и проект также говорит о том, как мы обычно думаем о семантике Haskell - был проект Eager Haskell, который радикально изменил стратегии оценки, в то время как поддерживал ту же семантику: http://csg.csail.mit.edu/pubs/haskell.html

Answer 7

Компилятор Glasgow Haskell переводит ваш код в язык, похожий на лямбда-исчисление, называемый core . На этом языке что-то будет оцениваться, когда вы сопоставляете его с шаблоном case. Таким образом, если вызывается функция, будет вычислен внешний конструктор и только он (если нет обязательных полей). Все остальное консервируется в толпе. (Thunks вводятся let привязками).

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

Если вы попытаетесь оценить функцию вручную, вы можете подумать:

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