Оптимизации Карри. 
Функциональное программирование

Наша программа преобразования выражений в комбинаторную форму дает правильный результат, по применять ее на практике затруднительно, поскольку результат преобразования часто оказывается слишком сложным. Хотелось бы добиться того, чтобы результаты получались в максимально простом виде. Это можно сделать двумя способами: во-первых, ввести дополнительные правила преобразований, которые в некоторых частных случаях позволят получать более короткие результаты; во-вторых, ввести дополнительные комбинаторы, позволяющие представлять аппликативные выражения в более компактном виде. Рассмотрим оба этих способа.

Хаскелл Карри предложил использовать во время преобразований некоторые правила, которые позволяют записывать некоторые сложные выражения в более коротком виде. Рассмотрим следующие два правила. В записи этих правил мы используем символ ««» в смысле «функционально эквивалентно»:

S (К еД (К е₂) * К (е_х е₂) (1).

S (К еj) I «е₂ (2).

Легко проверить, что эти правила действительно справедливы. Действительно, функциональная эквивалентность выражений означает, что если применить эти выражения к одному и тому же аргументу, то получатся одинаковые результаты. По определению комбинаторов S, К и I получаем для правила (1).

S (К еД (К е₂) х = К е_х х (К е₂ х) = е, е₂ = К (е_г е₂) х и для правила (2).

S (К е_г) I х = К е_г х (I х) = е_г х что и доказывает возможность применения первого и второго из оптимизационных правил Карри.

Когда мы получили выражение S (S (К +) (К 1)) I в качестве комбинаторной формы для выражения (Ах.+ 1 х), то написали, что с помощью чисто формальных преобразований упростить это выражение не удается. Однако это так только в смысле невозможности применения определений основных комбинаторов. Сразу становится понятно, что подвыражение S (К +) (К 1) имеет вид, пригодный для применения первого оптимизационного правила Карри, и может быть преобразовано в К (+ 1). Теперь все выражение приобрело вид S (К (+ 1)) I, и к нему можно применить второе правило. Выражение привелось к «естественному» простейшему виду + 1.

К сожалению, довольно трудно применять правила Карри к, возможно, весьма сложному выражению, полученному применением функции comb. Проще применять эти правила непосредственно в процессе преобразования выражений, получая при этом тот же результат. Изменим нашу программу преобразования выражений, добавив оптимизационные правила Карри в правила для функции абстрагирования от переменной. Теперь, перед тем, как формировать результат, получаемый абстрагированием от переменной в выражении вида [х] el е2, функция будет анализировать, можно ли получить более простое выражение, чем S ([х]е1) ([х] е2). Функция приобретает следующий вид:

abstr: String -> Expression -> Expression abstr _ c@ (Constant _) = Application k c.

abstr _ f@ (Function _) = Application k f.

abstr x v0 (Variable у) I x == у = i.

I otherwise = Application k v abstr x (Application el e2) = abstr' al a2.

where al = abstr x el a2 = abstr x e2.

abstr' (Application (Function «K») e) (Function «I») = e abstr' (Application (Function «K») el).

(Application (Function «K») e2) =.

Application k (Application el e2) abstr' al a2 = Application (Application s al) a2.

Модифицированная программа выдает заметно более компактные аппликативные выражения. Так, если исходная программа для выражения (Хх.Ху.+ х у) выдавала в качестве результата (с точностью до расстановки скобок).

(S (S (К S)) (S (S (К S) (S (К К) (К +))) (S (К К) I))) (К I).

то модифицированная программа выдает в качестве результата выражение.

II м Второй способ сделать получаемые нами аппликативные выражения более компактными — это ввести дополнительные комбинаторы и определить для них 8-правила. Введем два дополнительных комбинатора. Комбинатор В, называемый композитором, представляет функцию образования композиции двух заданных функций. 8-правило для него выглядит следующим образом:

В f g х = f (g х) Второй комбинатор, называемый перестановщиком, обозначается буквой С и имеет следующее 8-правило:

Cfxy = fyx.

Нетрудно понять, что композитор соответствует широко используемой в Haskell функции композиции (.), а перестановщик выражается в Haskell посредством стандартной функции flip.

Для того чтобы ввести новые комбинаторы в результат преобразования выражений в комбинаторную форму, можно использовать третье и четвертое оптимизационные правила Карри:

S (К е_х) е₂ * В е_х е₂ (3).

S е₂ (К е₂) * С е_х е₂ (4).

Корректность этих новых правил также легко проверить:

S (К е_х) е₂ х = (К е_х х) (е₂ х) = е_х (е₂ х) = В е_г е₂ х.

S е_х (К е₂) х = е₁ х (К е₂ х) = е₂ х е₂ = С e_L е₂ х Заметим, что эти правила будут применяться только тогда, когда неприменимо ни одно из первых двух правил.

Введем новые правила в программу преобразования выражений. Новые комбинаторы получают в программе обозначения b и с:

b = Function «В» с = Function «С».

а функция абстрагирования будет выглядеть так, как показано в листинге 15.2.

Листинг 15.2. Модифицированная функция абстрагирования

abstr:: String -> Expression -> Expression abstr _ c@ (Constant _) = Application k c.

abstr _ f0 (Function _) = Application k f.

abstr x v0 (Variable у) | x == у = i.

I otherwise = Application k v abstr x (Application el e2) = abstr' al a2.

where al = abstr x el a2 = abstr x e2.

abstr' (Application (Function «K») e) (Function «I») = e abstr' (Application (Function «K») el).

(Application (Function «K») e2) =.

Application k (Application el e2) abstr' (Application (Function «K») el) e2 =.

Application (Application b el) e2 abstr' el (Application (Function «K») e2) =.

Application (Application c el) e2 abstr' al a2 = Application (Application s al) a2.

В качестве примера рассмотрим функцию, которая использовалась нами в чистом лямбда-исчислении в качестве функции сложения двух натуральных чисел:

PLUS = Xm.An.m SUCC n.

где функция следования SUCC имела вид.

SUCC = An.Af.Ax.f (n f х) Создадим соответствующие этим функциям значения типа Expression: >> let pureSucc = Lambda «n» (Lambda «f» (Lambda «x» (Application (Variable «f») (Application (Application (Variable «n») (Variable «f»)) (Variable «x»))))).

" let purePlus = Lambda «m» (Lambda «n» (Application (Application (Variable «m») pureSucc) (Variable «n»))).

Если преобразовать функцию PLUS в комбинаторную форму с помощью формальных преобразований без оптимизаций программой, представленной в листинге 15.1, то получившийся результат будет содержать 721 вхождение комбинаторов S, К и I. Если использовать первые два оптимизационных правила Карри, то результат уже будет выглядеть вполне пригодным для практических целей:

" comb purePlus ((S I) (К (S ((S (К S)) К)))).

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

" comb purePlus ((С I) (S В)).