При каких обстоятельствах общий отказ от подэкспрессии влияет на лень программы Haskell?

От wiki.haskell.org:

Во-первых, исключение общего подвыражения (CSE) означает, что если выражение появляется в нескольких местах, код перестраивается, так что значение этого выражения вычисляется только один раз. Например:
foo x = (bar x) * (bar x)
может быть преобразовано в
foo x = let x' = bar x in x' * x'
таким образом, функция бара вызывается только один раз. (И если бар является особенно дорогостоящей функцией, это может сэкономить немало работы.) GHC фактически не выполняет CSE так часто, как вы могли ожидать. Проблема в том, что выполнение CSE может повлиять на строгость/лень программы. Таким образом, GHC выполняет CSE, но только в определенных обстоятельствах - см. Руководство GHC. (Раздел??)

Короче говоря: "Если вы заботитесь о CSE, сделайте это вручную".

Мне интересно, при каких обстоятельствах CSE "влияет" на строгость/лень программы и какой эффект может быть.

Ответ 1

Наивное правило CSE было бы

e'[e, e]  ~>  let x = e in e'[x, x].

То есть всякий раз, когда подвыражение e встречается дважды в выражении e', мы используем let-binding для вычисления e один раз. Это, однако, приводит к некоторым тривиальным утечкам пространства. Например

sum [1..n] + prod [1..n]

как правило, O(1) использование пространства в ленивом функциональном языке программирования, таком как Haskell (поскольку sum и prod будут хедж-рекурсией и бла-бла-бла), но станут O(n) когда будет принято наивное правило CSE. Это может быть ужасно для программ, когда n высоко!

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

Два вхождения e могут быть далеко друг от друга на e', что приводит к длительному времени жизни для связывания let x = e.
Связи let-binding всегда должны выделять замыкание, где раньше, возможно, не было такого.
Это может создать несвязанное количество замыканий.
Бывают случаи, когда закрытие может никогда не освободиться.

Что-то лучше

let x = e in e'[e]  ~>  let x = e in e'[x]

Это более консервативное правило, но гораздо безопаснее. Здесь мы понимаем, что e появляется дважды, но первое вхождение синтаксически доминирует над вторым выражением, а это означает, что программист уже ввел let-binding. Мы можем просто повторить использование let-binding и заменить второе вхождение e на x. Никаких новых закрытий не выделяется.

Другой пример синтаксического доминирования:

case e of { x -> e'[e] }  ~> case e of { x -> e'[x] }

И еще одно:

case e of {
   Constructor x0 x1 ... xn ->
     e'[e]
}

~>

case e of {
   Constructor x0 x1 ... xn ->
     e'[Constructor x0 x1 ... xn]
}

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

Смотрите также

Для полного обсуждения CSE в ленивом FPL читайте статью Читиля (очень доступную) 1997 года. Для полного изучения того, как CSE работает в производственном компиляторе, см. Модуль GHC CSE.hs, который очень хорошо документирован благодаря традиции GHC для написания длинных сносок. Коэффициент комментария к коду в этом модуле отсутствует в диаграммах. Также обратите внимание, сколько лет этот файл (1993)!