Что на самом деле делает seq в Haskell?

Question

Из Real World Haskell я читал

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

где я подчеркнул тогда, потому что для меня это означает порядок, в котором происходят две вещи.

Из Hackage я читал

Значение равно дну, если оно дно, и в противном случае равно. Другими словами, он оценивает первый аргумент нормальной формы слабой головы (WHNF). seq обычно вводится для повышения производительности, избегая ненужной лени.

Примечание о порядке оценки: выражение seq a bне гарантирует, что будет оцениваться раньше. Единственная гарантия, которую дает, заключается в том, что оба и будут оцениваться перед возвратом значения. В частности, это означает, что b может быть оценено до a. […]

Кроме того, если я нажму на # Source ссылку оттуда, страница не существует, поэтому я не вижу код.

Это похоже на комментарий под этим ответом :

[…] Не может быть определен в обычном Haskell

С другой стороны (или на самом деле с той же стороны) другой комментарий гласит:

Реальность' seq определено в GHC.Prim как seq :: a -> b -> b; seq = let x = x in x. Это всего лишь фиктивное определение. В основном seq - это особый синтаксис, обрабатываемый компилятором.

Кто-нибудь может пролить свет на эту тему?

Answer 1

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

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

      foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc [] = acc
foldl' f acc (x : xs)
  = acc' `seq` foldl' f acc' xs
  where
    acc' = f acc x

Конечно, мы заботимся о том, чтобы нас оценили перед рекурсивным вызовом. Если это не так, вся цель потеряна! Так почему бы не использовать здесь? И действительно ли все это полезно?

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

Понимание и строгость

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

1. считается строгим по обоим своим аргументам. То есть в таком определении функции, как

           f a b c = (a `seq` b) + c
   

   будет считаться строгим по всем трем аргументам.

2. точно так же, но считается строгим только в первом аргументе, а не во втором. Это означает, что в определении функции вроде

           g a b c = (a `pseq` b) + c
   

   будет считаться строгим в и, но не .

Что это значит? Что ж, давайте сначала определим, что значит для функции «быть строгой в одном из своих аргументов». Идея состоит в том, что если функция является строгой в одном из своих аргументов, то вызов этой функции гарантированно оценит этот аргумент. Это имеет несколько последствий:

• Предположим, у нас есть функция это строго по своим аргументам, и предположим, что у нас есть вызов, который выглядит так:

          foo (x + y)
  

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

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

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

Имея это в виду, вернемся к нашим примерам и выше. Давайте подумаем, какой строгости мы интуитивно ожидаем от этих функций:

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

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

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

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

   Однако, что примечательно, это не та строгость, которую предполагает GHC. GHC считает строгим in and, но не, хотя по нашему определению строгости выше, очевидно, является строгим in: должен быть оценен для получения результата! Как мы увидим, именно это несоответствие делает так глубоко волшебным, и почему это вообще плохая идея.

Последствия строгости

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

      f a (b + 1) c

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

На первый взгляд может показаться, что все хорошо, но подождите: а что, если это преобразователь? Несмотря на то, что он также является строгим, это всего лишь простая переменная - возможно, она была передана в качестве аргумента откуда-то еще - и у GHC нет никаких оснований для принудительного применения здесь, если он собирается принудить ее сам. Единственная причина, по которой мы форсируем, - это избавить новый преобразователь от создания, но мы ничего не сохраняем, кроме принудительного создания уже созданного на сайте вызова. Это означает, что на самом деле это может быть принято как неоцененный преобразователь.

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

Конечно, именно поэтому второй аргумент считается ленивым, хотя на самом деле это не так. Если мы заменим на , то GHC послушно выделит новый преобразователь для и передать его в кучу, убедившись, что он не оценивается слишком рано. Это, конечно, означает большее выделение кучи, отсутствие распаковки и (что хуже всего) отсутствие распространения информации о строгости дальше по цепочке вызовов, создавая потенциально каскадные пессимизации. Но послушайте, это то, о чем мы просили: любой ценой не оценивать слишком рано!

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

Выводы

Надеюсь, что приведенное выше объяснение прояснило, как у обоих и есть преимущества и недостатки:

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

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

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

Чтобы развеять ваши страхи, давайте сделаем шаг назад и задумаемся о том, что здесь происходит на самом деле. Обратите внимание, что GHC на самом деле никогда не компилирует само выражение таким образом, что ранее не могло быть оценено. Учитывая такое выражение, как , GHC никогда не будет тайно наносить вам удар в спину и оценивать, прежде чем оценивать . Скорее, то, что он делает, гораздо более тонкое: оно может косвенно вызывать и оцениваться индивидуально, прежде чем оценивать общий выражение, так как анализатор строгости заметит, что общее выражение все еще строгое в обоих и .

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

      acc' `seq` foldl' f acc' xs

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

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

• можно считать строгим, но здесь это совершенно неинтересно, так как является лишь частью одного из аргументов, и эта информация о строгости вообще не влияет на строгость.

Итак, если на самом деле здесь нет никакой разницы, почему бы не использовать? Что ж, предположим, что он встроен некоторое конечное число раз на сайте вызова, поскольку, возможно, форма его второго аргумента частично известна. Информация о строгости, предоставляемая с помощью, может затем вызвать несколько дополнительных оптимизаций на сайте вызова, что приведет к цепочке выгодных оптимизаций. Если бы он использовался, эти оптимизации были бы скрыты, и GHC дал бы худший код.

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

Когда же тогда использовать? Только когда вы действительно заботитесь об очень конкретном порядке оценки, что обычно происходит только по одной из двух причин: вы используете -основанный параллелизм, или вы используете и позаботьтесь о порядке побочных эффектов. Если вы не делаете ничего из этого, не используйте . Если все, что вас волнует, это варианты использования вроде , где вы просто хотите избежать ненужного наращивания преобразователей, используйте .Вот для чего это нужно.

Answer 2

вводит искусственную зависимость данных между двумя преобразователями. Обычно преобразователь вынужден выполнять оценку только тогда, когда этого требует сопоставление с образцом. Если преобразователь содержит выражение case b of { … }, то заставляя также заставлять. Таким образом, между ними существует зависимость: чтобы определить значение, мы должны оценить.

определяет эту связь между любыми двумя произвольными преобразователями. Когда принудительно, принудительно в дополнение к . Обратите внимание, что я не говорю раньше : в соответствии со стандартом, реализация может быть принудительной до или dраньше или даже их смесь. Требуется только, если c не останавливается, тогда seq c dтоже не останавливается. Если вы хотите гарантировать порядок оценки, вы можете использовать pseq.

В его нынешнем виде он должен быть реализован как внутренний, потому что его тип forall a b. a -> b -> b, утверждает, что работает для любых типов a и b, без каких-либо ограничений. Раньше он принадлежал к классу типов, но он был удален и превращен в примитив, потому что версия класса типов считалась плохо эргономичной: добавление, чтобы попытаться исправить проблему производительности в глубоко вложенной цепочке вызовов функций, потребовало бы добавления шаблона Seq aограничение на каждую функцию в цепочке. (Я бы предпочел ясность, но сейчас ее будет сложно изменить.)

Итак, и синтаксический сахар для него, как строгие поля в data типы или BangPatternsв шаблонах - это гарантия того, что что-то оценивается, путем присоединения этого к оценке чего-то еще, что будет оцениваться. Классический пример: foldl'. Здесь seq гарантирует, что при принудительном рекурсивном вызове аккумулятор также принудительно:

      foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc [] = acc
foldl' f acc (x : xs)
  = acc' `seq` foldl' f acc' xs
  where
    acc' = f acc x

Это требует от компилятора, что если f строгий, такой как (+) на строгом типе данных, таком как, то аккумулятор сокращается до Int на каждом этапе, а не выстраивать цепочку преобразователей, оцениваемых только в конце.

Answer 3

Real World Haskell ошибается, и все остальное, что вы цитируете, верны. Если вам важен порядок оценки, используйте pseq вместо.