Комбинаторная редукция на графах

В результате изучения материала главы 16 студент должен:

знать

• • способы редукции на графах, представляющих выражения, записанные в комбинаторной форме;
• • каковы преимущества комбинаторного представления выражений при выполнении преобразований на графах;

уметь

• представлять рекурсивные и нерекурсивные выражения в виде графов в комбинаторной форме;

владеть

• техникой выполнения редукций на графах комбинаторных выражений.

Правила преобразования графов для основных комбинаторов

Редукция выражений на графах, введенная в гл. 14, позволила нам адекватно представлять разделение переменных в процессе редукций, поскольку замена ссылок на переменные в процессе p-редукции ссылками на фактический аргумент функции не приводит к копированию этих аргументов. Зато копированию в процессе той же p-редукции подвергается тело лямбда-выражения, что снижает эффективность работы. Кроме того, если в графе имеются циклические ссылки, то копирование тел лямбдавыражений вообще становится крайне затруднительным. Именно поэтому мы до сих пор не рассматривали выражений, содержащих рекурсию — такие выражения приводят к появлению в графе циклических ссылок.

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

Напомним, как выглядят 5-правила для всех введенных нами комбинаторов:

S f g x =.

f X (g x).

К x у = x I x = x В f g x = f (g x).

Cfxy = fyx.

В графическом виде эти правила можно представить так, как показано на рис. 16.1.

Рис. 16.1. 5-редукции для основных комбинаторов.

Посмотрим, как эти правила работают на примере выражения, представленного графически на рис. 14.6. Выражение, которое мы представляли графически, было записано нами как twice (+1) 3, где функция twice.

определялась выражением Af. Ах. f (f х). Прежде всего, воспользуемся функцией comb, представленной в листинге 15.1 с модифицированной функцией абстрагирования листинга 15.2:

>> let twice = Lambda «f» (Lambda «x» (Application.

• (Variable «f»)(Application (Variable «f»)(Variable «x»)))) «twice
• (f. (x. (f (f x))))

>> let expr = Application (Application twice (Application.

(Function «+»)(Constant 1)))(Constant 3).

" expr.

(((f. (x. (f (f x)))) (+ 1)) 3).

>> comb expr.

((((S B) I) (+ 1)) 3).

Если удалить лишние скобки из результата применения функции comb, то получившееся после преобразования выражение будет иметь вид S В I (+ 1) 3. В представлении в виде графа это выражение будет выглядеть так, как показано на рис. 16.2.

Рис. 16.2. Пример представления выражения (S В I (+ 1) 3) в виде графа.

Применение распределителя S и последующее использование композитора В преобразует этот граф последовательно в графы, представленные на рис. 16.3, а и б.

В полученном на рис. 16.3, 6 выражении самым левым из самых внешних редексов является 5-редекс применения примитивной функции сложения. Для того чтобы выполнить редукцию, нужно сначала привести аргументы к нормальной форме. Первый аргумент представлен константой 1, так что он уже находится в нормальной форме. Второй аргумент преобразуется к нормальной форме за два шага. Первый шаг состоит в применении тождественного комбинатора, и в результате граф будет преобразован к графу, показанному на рис. 16.4, а. Второй шаг — выполнение сложения, в котором уже оба операнда находятся в нормальной форме, так что в результате получается константа 4. Результирующий граф показан на рис. 16.4, 6. Наконец, последний шаг преобразования — применение функции сложения к двум константам приведет к окончательному результату 5 (рис. 16.4, в).

Рис. 16.3. Первые два шага преобразования аппликативного выражения.

Рис. 16.4. Последующие шаги преобразования аппликативного выражения.