Ответ 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)!