Что такое суперкомбинаторы и постоянные аппликативные формы?

Я борюсь с тем, что Суперкомбинаторы:

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

А также с тем, что Constant Applicative Forms:

Любой суперкомбинатор, который не является абстракцией лямбда. Это включает в себя по-настоящему постоянные выражения, такие как 12, ((+) 1 2), [1,2,3], а также частично применяемые функции, такие как ((+) 4). Обратите внимание, что этот последний пример эквивалентен в eta абстракции \x → (+) 4 x, который не является CAF.

Это просто не имеет никакого смысла для меня! Разве не ((+) 4) так же, как "по-настоящему постоянный", как 12? CAFs звучат как ценности для моего простого ума.

Ответ 1

Эти страницы Wiki, которые вы ссылаетесь, являются старыми, и я думаю, к сожалению, написано. Особенно печально, что они смешивают CAF и суперкомбинаторы. Суперкомбинаторы интересны, но не связаны с GHC. CAFs по-прежнему являются частью GHC и могут быть поняты без ссылки на суперкомбинаторы.

Итак, начнем с суперкомбинаторов. Комбинаторы проистекают из комбинаторной логики, а в использовании здесь состоят из функций, которые применяют только значения, переданные друг другу в ту или иную сторону форма - т.е. они объединяют свои аргументы. Самый известный набор комбинаторов S, K и I, которые вместе взяты, являются завершающими. В этом контексте суперкомбинаторы представляют собой функции, построенные только из значений, передаваемых в комбинаторах, и других суперкомбинаторах. Следовательно, любой суперкомбинатор можно разложить путем замены на простой старый комбинатор.

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

Постоянная аппликативная форма - это нечто иное. Они немного более тонкие и имеют несколько ошибок. Способ думать о них является аспектом реализации компилятора без отдельного смыслового значения, но с потенциально глубоким воздействием на производительность выполнения. Следующее не может быть идеальным описанием CAF, но оно попытается передать мою интуицию тому, что есть, так как я не видел действительно хорошего описания где-либо еще для меня, чтобы вырваться из. чистое "авторитетное" описание в Wiki Wiki Wiki выглядит следующим образом:

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

Это хорошее начало. Чистые, функциональные, ленивые языки можно рассматривать в некотором смысле как машину для уменьшения графа. В первый раз, когда вы требуете значения node, это заставляет его оценивать, что, в свою очередь, может потребовать значения поднодов и т.д. Оценивается один из node, результирующее значение прилипает (хотя оно не должно придерживаться - так как это чистый язык, мы всегда можем поддерживать субноды вживую и пересчитывать без семантического эффекта). CAF действительно просто ценность. Но в контексте особый вид ценности - тот, который может определить компилятор, имеет значение, полностью зависящее от его поднодов. То есть:

foo x = ...
  where thisIsACaf = [1..10::Int]

        thisIsNotACaf = [1..x::Int]
        thisIsAlsoNotACaf :: Num a => [a]
        thisIsAlsoNotACaf = [1..10] -- oops, polymorphic! the "num" dictionary is implicitly a parameter.

        thisCouldBeACaf = const [1..10::Int] x -- requires a sufficiently smart compiler
        thisAlsoCouldBeACaf _ = [1..10::Int] -- also requires a sufficiently smart compiler

Итак, почему нам все равно, являются ли CAF? В основном потому, что иногда мы действительно не хотим что-то перепрограммировать (например, memotable!) И поэтому хотим удостовериться, что они правильно распределены. В других случаях мы действительно хотим что-то перепрограммировать (например, огромный скучный легко генерируемый список - например, натуралы, которые мы просто перешагиваем), и не иметь его навсегда. Комбинация именования вещей и привязка их к датам или их встраиванию и т.д. Обычно позволяет нам конкретизировать эти вещи естественным, интуитивно понятным способом. Иногда, однако, компилятор умнее или глубже, чем мы ожидаем, и то, что мы думаем, должно вычисляться только один раз, всегда пересчитывается, или что-то, что мы не хотим висеть, чтобы быть снятым как CAF. Тогда нам нужно подумать об этом более тщательно. См. Это обсуждение, чтобы получить представление о некоторой сложности: Хороший способ избежать "совместного использования" и"

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

Ответ 2

Мэтт прав в том, что это определение сбивает с толку. Это даже противоречиво. CAF определяется как:

Любой суперкомбинатор, который не является абстракцией лямбда. Это включает действительно постоянные выражения, такие как 12, ((+) 1 2), [1,2,3] как а также частично применяемые функции, такие как ((+) 4).

Следовательно, ((+) 4) рассматривается как CAF. Но в самом следующем предложении нам говорят, что это эквивалентно тому, что не является CAF:

этот последний пример эквивалентен в eta абстракции до \ x -> (+) 4 x, который не является CAF.

Было бы проще исключить частично примененные функции на том основании, что они эквивалентны абстрактам лямбда.