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

Question

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

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

А также с чем Постоянные применения формы находятся:

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

Это просто не имеет смысла для меня! Не ((+) 4) Так же, как «по -настоящему постоянно», как 12? Кафе звучат как значения для моего простого ума.

Answer 1

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

---

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

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

---

Постоянные применения формы что -то еще полностью. Они немного более тонкие, и у них есть несколько случаев. Способ думать о них является аспектом реализации компилятора без отдельного семантического значения, но с потенциально глубоким влиянием на производительность выполнения. Следующее может быть не идеальным описанием кафе, но он попытается передать мою интуицию того, что такое, так как я не видел В самом деле Хорошее описание где -нибудь еще для меня, чтобы покинуть. А Чистое «авторитетное» описание в комментарии GHC Wiki читает следующее:

Постоянные прикладные формы, или 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

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

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

Answer 2

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

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

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

Этот последний пример эквивалентен на абстракцию ETA \ x -> (+) 4 x который не кафе.

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