Полная ленивость
Cтраница 1
Полная ленивость сохраняется, если никакое частичное применение f не становится разделяемым. Иначе возможно, что подвыражение внутри тела комбинатора будет вычисляться каждый раз при применении разделяемого частичного применения. Компилятор может определить, будет ли / применяться частично, и если да, то будет ли это частичное применение разделяемым. Если разделение не имеет места, соответствующий комбинатор можно оставить без изменения, не боясь потерять полную ленивость. Если же он может стать разделяемым, то мсв-удаление должно применяться в таком виде, как описано в разд. При этом появляется по крайней мере один новый комбинатор. [1]
Использование улучшенных суперкомбинаторов дает нам меньшее число комбинаторов и сохраняет полную ленивость. [2]
Простое Я-удаление абстрагирует свободные переменные из Я-тел; при этом теряется полная ленивость. [3]
А сейчас давайте вернемся к функции element и посмотрим, как суперкомбинаторный подход сохраняет полную ленивость. [4]
При трансляции в суперкомбинаторную форму из Я-тел абстрагируются максимальные свободные выражения ( мсв), что гарантирует полную ленивость. [5]
Общее Я-удаление абстрагирует свободные переменные из вложенных А-абстракций, давая в результате меньше комбинаторов, однако при этом полная ленивость снова не гарантируется. [6]
 |
Проблема свободных переменных в редукции графов. [7] |
Существуют также более сложные методы, например использование суперкомбинаторов [46], и мы рассмотрим подходы, основанные на использовании комбинаторов, с целью найти эффективные реализации редукции графов в следующих двух главах. Дополнительная выгода решения проблемы свободных переменных этим путем заключается в устранении ненужного копирования и дублирования редукций, что придает реализации свойство так называемой полной ленивости. [8]
Простейшее преобразование данного типа называется Я-уда-лением и заключается в удалении свободных переменных из каждого Я-тела, в результате чего получается один новый комбинатор. Однако такое решение не дает максимально возможной эффективности, поскольку число применений в результирующих выражениях ( и, следовательно, число редукций графов, требуемых в процессе вычисления этих выражений) можно уменьшить, а размер структурных элементов комбинаторов - увеличить. Еще более серьезный недостаток состоит в том, что полная ленивость может быть утрачена, и при этом возникает вероятность, что в процессе вычисления выражения одно и то же подвыражение будет вычислено более одного раза. [9]
Хотя этот метод является достаточно элегантным и увеличивает размер структурного элемента, но для комбинатора а он, конечно, не оптимален. Ясно, что поскольку новые комбинаторы р и у эквивалентны, нет необходимости генерировать V-Менее очевидно то, что р также не нужно было определять из-за его схожести с а; эти комбинаторы отличаются только порядком параметров. Гораздо менее ясно, что метод простого Я-удаления может привести к дублированию редукций постоянных подвыражений, при этом полная ленивость теряется. [10]
Полная ленивость сохраняется, если никакое частичное применение f не становится разделяемым. Иначе возможно, что подвыражение внутри тела комбинатора будет вычисляться каждый раз при применении разделяемого частичного применения. Компилятор может определить, будет ли / применяться частично, и если да, то будет ли это частичное применение разделяемым. Если разделение не имеет места, соответствующий комбинатор можно оставить без изменения, не боясь потерять полную ленивость. Если же он может стать разделяемым, то мсв-удаление должно применяться в таком виде, как описано в разд. При этом появляется по крайней мере один новый комбинатор. [11]
Как мы видели в предыдущем разделе, при использовании Я-удаления для преобразования - выражения в КАФ свободные переменные аппликативных Х - тел представляются с помощью параметров вновь сгенерированных комбинаторов. Эти изолированные свободные переменные являются минимальными непостоянными cb А-тел, поскольку они не содержат подвыражений. В противоположность этому мы могли бы определить новые комбинаторы, параметры которых представляют непостоянные максимальные ев ( аббревиатура - мсв) соответствующих Х - тел. Комбинаторы, полученные таким путем, называются суперкомбинаторами, и были первоначально введены [46] с целью преодоления некоторых трудностей, связанных с простым Х - удалением, рассмотренным выше. В частности, при таком подходе сохраняется полная ленивость, поскольку она теряется, только когда свободная переменная, входящая в ев большего размера, удаляется из Х - тела. [12]
Простейшее преобразование данного типа называется Я-уда-лением и заключается в удалении свободных переменных из каждого Я-тела, в результате чего получается один новый комбинатор. Однако такое решение не дает максимально возможной эффективности, поскольку число применений в результирующих выражениях ( и, следовательно, число редукций графов, требуемых в процессе вычисления этих выражений) можно уменьшить, а размер структурных элементов комбинаторов - увеличить. Еще более серьезный недостаток состоит в том, что полная ленивость может быть утрачена, и при этом возникает вероятность, что в процессе вычисления выражения одно и то же подвыражение будет вычислено более одного раза. При этом подходе удаляются целые подвыражения, содержащие свободные переменные, а не сами свободные переменные, и сохраняется полная ленивость. Более того, увеличивается сложность суперкомбинаторов, что в конечном счете ведет к уменьшению числа требуемых применений функций. Предложения по дальнейшей оптимизации суперкомбинаторной реализации даны в разд. [13]
Это свойство сохранения аппликативных подвыражений, для которого требуется только первое правило оптимизации из предыдущего раздела и не требуются дополнительные комбинаторы В и С. В неоптимизированном представлении с использованием S, К, / это свойство отсутствует. Компоненты постоянного подвыражения 12 распределяются по этому КЛ-выражению. Однако при применении первого правила оптимизации, приведенного выше, результирующее КЛ-выражение принимает вид К ( 12), оставляя подвыражение 12 без изменений. Сохранение постоянных подвыражений особенно важно в случае постоянных ре-дексов, и именно оно способствует их разделению в процессе вычисления выражения. В результате становится возможным избежать повторного вычисления таких редексов. Это способствует полной ленивости; данный термин иногда используют для обозначения того, что никакое вычисление не выполняется больше одного раза при выполнении функциональной программы. [14]
Страницы: 1