Рассмотрим две крайние стратегии применения редукций:
(1) пусть редукция всегда применяется к самому левому из самых внутреннихредексов. При этом может оказаться, что в некоторый момент выражение окажется в нормальной форме. Может оказаться и так, что этот процесс никогда не будет закончен. В выражении (lх.(lу.у))((lх.хх)(lх.хх)) самым внутренним является редекс (lх.хх)(lх.хх), поэтому данная стратегия не сможет привести выражение к нормальной форме. Этот описанный порядок редукций называется аппликативным, сокращенно - АПР (аппликативный порядок редукций).
(2) пусть редукция всегда применяется к самому левому из самых внешнихредексов. Этот порядок редукций называется нормальным или сокращенно НПР (нормальный порядок редукций).
Если обращение к аргументу в теле функции происходит несколько раз, то при применении НПР его преобразование будет происходить столько раз, сколько имеется таких обращений. Приведенный пример показывает, что при применении НПР для приведения выражения к нормальной форме может потребоваться больше шагов, чем при АПР, однако, НПР более «надежен», так как он позволяет получить нормальную форму всегда, если только она существует.
Аппликативному порядку редукций соответствует энергичный способ вычисления значения функций в функциональном программировании, при котором в каждом вызове функции сначала вычисляются значения аргументов, а затем происходит их подстановка в тело вызываемой функции.
Нормальному порядку редукций соответствуют «ленивые» вычислений, при котором подстановка аргументов в тело функции происходит до начала вычислений самих аргументов.
3.6.8. Алгебра комбинаторов
l-терм, не содержащий свободных переменных называется замкнутым l-термом или комбинатором. Определим следующие l-термы - комбинаторы:
I=lх.х – комбинатор тождества;
K=lху.х – комбинатор выбора;
S=lхуz.хz(уz) – комбинатор соединения.
Комбинаторы работают следующим образом:
Ix = x;
Kxy = x;
Sxyz = xz(yz).
Утверждение.Посредством комбинаторов I,K и S, используя операцию аппликации, можно выразить любой замкнутый l-терм.
Более сильное утверждение.Любой замкнутый l-терм можно выразить, используя только комбинаторы K и S.
Чтобы доказать последнее, достаточно выразить комбинатор I через K и S. Таким образом, комбинаторы I,K и S (и даже только комбинаторы K и S) составляют комбинаторный базис на множестве замкнутых l-термов. Используем при доказательстве определения комбинаторов и a, b-конверсии.
Вспомогательное утверждение.Комбинатор I выражается через комбинаторы K и S с помощью операции аппликации.
Доказательство.
SKK=(lхуz.хz(уz))KK=lz..Kz(Kz)=lz..(lху.х)z(Kz)=lz..z=lх.х=I
Докажем еще две простые формулы.
Утверждение.Верна следующая формула:
lх.M=KM, при условии, если хÏFV(M.)
Доказательство: KM=(lху.х)M=(lх.(lу.х))M=
-здесь b- конверсию можно применить только, если уÏFV(M), иначе свободная переменная у, входящая в M, превращается в связанную переменную. В данной ситуации мы имеем возможность переименования связанной переменной, поэтому считаем, что уÏFV(M) -
=lу.M=lх.M.
– использовать a- конверсию можно только, если хÏFV(M) по той же причине. Здесь мы не имеем возможности переименования, поэтому условие хÏFV(M) является существенным.Равенство доказано.
Утверждение.Верна следующая формула:
lх.MN=S(lх.M)(lх.N).
Доказательство:S(lх.M)(lх.N)=(lхуz.хz(уz))(lх.M)(lх.N)=
lz..(lх.M)z((lх.N)z)=lz..(M[х:=z])(N[х:=z])=lх.MN.
Равенство доказано. При доказательстве использованы b-конверсия и определение комбинатора S.
Пример.Выразить замкнутый l-терм lху.ух через базисные комбинаторы I, K и S.
Используем доказанные формулы.
lху.ух=lх.(lу.ух)=lх.(S(lу.у)(lу.х))=lх.(SI(Kх))=
= S(lх.SI)(lх.Kх)= S(K(SI))(S(lх.K)(lх.х))= S(K(SI))(S(KK)I).
Алгебра комбинаторов обладает возможностью моделировать процесс реализации программного обеспечения на языке функционального программирования, причем данный подход предполагает программирование без переменных на основе алгебры программ.
Кроме того, алгебра комбинаторов позволяет прозрачно формализовать процедуру приписывания типов объектам языка. Например, базисным комбинаторам могут быть приписаны параметризованные типы следующим образом:
I:A®A,
K:A®(B®A),
Упражнение. Проверить правильность приписывания типов комбинаторам I и K.
Утверждение.Пусть A, B, C – некоторые произвольные типы. Тогда тип комбинатора S выражается следующим образом:
S:((A®(B®C))®((A®B)®(A®C))
Доказательство: Пусть х:A®(B®C), у:A®B, z:A. Тогда
Sх: (A®B)®(A®C) ÞSху:(A®C) Þ Sхуz:C.
С другой стороны, используя определение комбинатора Sxyz = xz(yz); получим.
х:A®(B®C), z:A Þ xz:B®C;
у:A®B, z:AÞ yz:B;
xz: B®C, yz:BÞ xz(yz):CÞ Sхуz:C.
3.7. Функциональный язык Бэкуса
Данный язык положил начало направлению, которое и получило название «функциональное программирование». Он был опубликован в статье [21] в 1979 году. В этой статье была определена система функционального программирования (FP), которую мы и рассмотрим далее.
Для сравнения запишем определение программы вычисления скалярного произведения векторов в фон Неймановском стиле и отметим особенности стиля.
c.:=0
for i:=I step 1 until n do
c:=c + a[i]*b[i]
a) ее операторы воздействуют на невидимое «состояние» в соответствии с достаточно сложными правилами;
b) она не является иерархической. За исключением правой части оператора присваивания, в ней не строятся более сложные конструкции из более простых;
c) она является динамической и циклической. Чтобы понять ее, необходимо мысленно ее выполнить;
d) она вычисляет повторением (присваивания) и модификацией (переменной i);
e) часть данных, n, находится внутри программы; таким образом, ограничивается общность (работает только для векторов длины n);
f) она именует свои аргументы; т.е. может использоваться только для a и b(имеется в виду данный текст как фрагмент программы). Для достижения общности, требуется описание процедуры, что вовлекает нас в сложные вопросы (вызова по имени или вызова по значению);
g) «вспомогательные» действия представлены символами в рассеянных местах (в for операторе и в индексах присваивания). Это лишает возможности объединить вспомогательные операции в единственном операторе, пригодном для универсального применения.
Аналогичная функция, вычисляющая скалярное произведение в функциональном стиле будет выглядеть следующим образом.
Def IP - (/+)o(@*)oTrans.
Смысл используемых обозначений может быть легко понят из приведенного ниже порядка выполнения этого определения и подробно разъясняется ниже. Определим порядок выполнения функционального выражения следующего вида IP:<< 1,2,3>, <6,5,4>> для вычисления скалярного произведения двух векторов. Выполнение представляет собой последовательность шагов, на каждом из которых используется некоторое общее свойство функционального языка или свойство отдельных функций, производится преобразование, получается новое выражения, равносильное предыдущему.
IP:<< 1,2,3>, <6,5,4>> =
-используется определение функции IP Þ
=(/+)o(@x)oTrans: << 1,2,3>, <6,5,4>>=
-используется свойство операции композиция (o) Þ
=(/+):((@x):(Trans:<<1,2,3>, <6,5,4>>))=
-используется свойство операции транспонирования (Trans) Þ
=(/+):((@x): <<1,6>, <2,5>, <3,4>>)=
-используется свойство операции @. Применение умножения (x) ко всем элементам списка Þ
=(/+): <x: <1,6>, x: <2,5>, x: <3,4>>=
-выполнение умножений (x)Þ
=(/+): <6,10,12>=
-используется свойство функционала «/»Þ
=+: <6, +: <1O,12>>=
-сложение (+)Þ =+: <6,22>=
-снова сложение (+) и окончательный результат Þ =28.
3.7.1. Состав системы FP
Определим систему функционального программирования FP. Она включает следующее:
l) множество O объектов;
2) множество F функций f, которые преобразуютобъекты в объекты;
3) операция (:) аппликации (application)-применения функции к аргументу;
4) множество F функциональных форм; они используются для комбинирования имеющихся функций или объектов для формирования новых функций в F;
5) множество D определений, которые описывают функцию в F и присваивает ей имя..
Объекты. Объект xлибо атом (atom) aлибо список (sequence) <x1,...., xn>, элементы которогоxiесть объекты или ^ (неопределенность). Будем рассматривать множество непустых строк, букв, цифр и специальных символов. Некоторые из строк будем называть числами. Атом Æ обозначает пустую последовательность и является единственным объектом, являющимся одновременно атомом и последовательностью. Атомы T и F обозначают «true» и «false». Имеется важное ограничение в конструкции объектов: если x последовательность с, содержащая элемент ^, то x = ^.
Примеры объектов
^; 1.5; ¢p; AB3; <AB, 1, 2.3>; <.4, <<B>, C>, D>; <,4, ^> = ^.
Аппликация. FP система имеет единственную операцию – аппликация. Если f– функция и x объект, то f:x аппликация, обозначающая объект, являющийся результатом применения функции f к аргументу x .
Примеры аппликаций
+:<1,2> = 3;
tI:<.A,B,C> = <B,C>;
I:<A,B,C> = A;
2:<A,B,C> = B.
3.7.2. Функции FP
Функции. Все функции отображают объекты в объекты и являются ^-сохраняющими, т.е.f: ^ = ^.
Функции делятся на примитивные, определяемые и функциональные формы.
Примеры примитивных функций
Для описания функций будем использовать условные выражения вида: pl ® el; ... ;pn ® en; en+1. Выражение обозначает, что если выполняется условие pl , то в качестве значения выбираетсяel, если оно не выполняется, то последовательно рассматриваем пары pi ® ei до тех пор, пока условие pi не выполнится. Если не выполнится ни одно из условий, в качестве результата берется en+1.
Функции выбора (selectors).Применение целого числа к списку дает в качестве результата элемент списка с соответствующим номером.
1: x º x =< x 1, ..., x n> ® x 1; ^
и для любого целого положительного s
s: x º x =< x 1..., x n>&n³s® xs; ^
т.е., 3:<A,B,C> = C; 2:<A> = ^.
Хвост (tail).Вычисляется хвост списка в обычном понимании этого термина.
tl:x º x=<x1> ® Æ; x =< x 1, ..., x n>&n³2 ®< x 2, ..., x n>; ^
Пустая функция (Identity).Функция выдает свой аргумент в качестве результата.
id:x º x.
Проверка на атом (Atom).Функция вырабатывает значение T или F в зависимости от того, является ли аргумент атомом.
atom:x º x атом ® T; x¹^®F; ^
Сравнение (Equals)
eq:x º x=<y,z> & y=z®T; x=<y,z> & y¹z®F; ^
Проверка на пустоту (Null)
null:x º x=Æ® T; x¹^®F; ^
Обращение списка (Reverse)
reverse:x º x=Æ® Æ; x =< x 1, ..., x n>®< x n, ..., x 1>; ^
Распределение левое и правое (Distribute from left; distribute from right)
distl:x º x=<y,Æ> ® Æ; x =<.y,<z1,...,zn>> ® << y,z1>,...,< y,zn>>;^
distr:x º x=<Æ,y> ® Æ; x =<.<z1,...,zn>,y> ® <<z1 ,y>,...,< z n ,y >>;^
Вычисление длины (Length)
length:x º x=<x 1, ..., x n> ® n; x=Æ® 0;^
Арифметическе операции (Add, subtract, multiply, divide)
+:x º x=<y,z> &y,z числа ® y+z;^
-:x º x=<y,z> & y,z числа ® y-z;^,
*:x º x=<y,z> & y,z числа ® y*z;^
¸:x º x=<y,z> & y,z числа ® y¸z;^(where y+0 =^)
Транспонирование (Transpose)
trans:x -- x=<Æ,...,Æ'>® Æ; x =< x 1,...,x n>®<y1,..., ym >;^
(where xi =< x i1, ..., x im> and yj=< x 1j,...,x nj >, l£i£n, l£j£m
Логические операции (And, or, not)
and::x º x=<y,z> &y,z логические ® y and z;^
or::x º x=<y,z> &y,z логические ® y or z;^
not::x º x логическое ® not x;^
Присоединение слева и справа (Append left; append right)
apndl:x º x=<y, Æ> ® <y>; x =<.y,<z1,...,zn>> ® < y,z1,...,zn>;^
apndr:x º x=<Æ,y> ® <y>; x =<.<z1,...,zn>,y> ® <z1,...,z n ,y>;^
Выбор справа (Right selectors; Right tail)
lr:x º x =< x 1,...,x n>® x n; ^
2r:x º x =< x 1,...,x n>& n³2® x n-1; ^
s: x º x =< x 1..., x n>&n³s® x n-s+1; ^
tlr:x º x=<x1> ® Æ; x =< x 1, ..., x n>&n³2 ®< x 1, ..., x n-1>; ^
Циклическая перестановка влево и вправо(Rotate left; rotate right)
rotl:x º x=Æ® Æ; x =< x 1>®<x 1>; x=<x 1,...,x n>®<x 2,...,x n,x1>;^
rotr:x º x=Æ®Æ; x =< x 1>®<x 1>; x =<x 1,...,x n>®<x n,x 1,...,xn>;^
3.7.3. Функциональные формы
Функциональные формы – это способ соединения функций для получения новых функций.
Примеры функциональных форм
Композиция (Composition) (fog).
(fog):x º f : (g : x)
Конструирование (Construction) [fi . . . . . fn].
[fi . . . . . fn]:x º < fi :x,..., fn:x >
Условное выражение (Condition) (p®f, g).
(p®f, g):x º (p:x)=T® f:x; (p:x)=F® g:x;^
Константа (Constant) 
(x некоторый объект, например, число).
:y º y=^® ^; x
Свертка (Insert) /f .(см. также раздел «Функции высшего порядка»)
/f:xºx=<x 1>®x 1;x=<x 1,...,x n>&n³2® f:<x 1, /f:<x 2,...,x n>>;^
Если двухместная функция fимеет единственную правую единицу uf,то можно расширить вышеприведенное определение: /f: Æ = uf. Таким образом,
/+:<4,5,6> = +:<4, +:<5,/+:<6>>> = +:<4, +:<5,6>> = 15
/+:Æ=0
/+:<6>= +:<6,/+: Æ>=+:<6, 0>=6
Роль единицы для функции сложения выполняет 0. Для умножения эту роль выполняет 1. Т.е.
/*:<4,5,6> =*:<4,*:<5,/*:<6>>> = *:<4, *:<5,6>> = 120
/*:Æ=1
/*:<6>=*:<6,/*: Æ>=*:<6, 1>=6
Применить ко всем (Apply to all) @f.
@f:x º x=Æ®Æ; x =< x 1, ..., x n>®< f:x 1,..., f:x n>;^
Карринг. Преобразование бинарной функции в унарную (Binary to unary) (bu f x) (x некоторый объект, например, число)
(bu f x) :y º f:<x,y>
Например, (bu + l):x = l+x
Цикл (While) (while p f).
(while p f): x º p: x= T ® (while p f):(f: x);p:x=F® x;^
Дата: 2016-10-02, просмотров: 331.
