Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Функциями высших порядков или функционалами называются функции, которые используют другие функции в качестве аргументов или вырабатывают их как результат. Правильность выражений, включающих такие функциями, требует корректной подстановки параметров и учета функционального типа основной функции и параметров, которые определяют возможность манипулирования функциональными значениями.
Хорошим примером является известная в программировании функция высшего порядка - свёртка (обычно обозначается как folding, reduce, accumulate), которая производит преобразование структуры данных к единственному атомарному значению при помощи заданной функции. Операция свёртки часто используется в функциональном программировании при обработке списков.
Функция свёртки обычно принимает три аргумента: комбинирующую двухместную функцию f, начальное значение start и структуру данных seq. Иногда функция свёртки не принимает начальное значение, но требует непустого списка.
Пусть список seq является следующим: (e1 e2 ... en). Свертка называется левоассоциативной, если вычисляет значение по правилу:
(f ... (f (f start e1) e2) ... en)
и правоассоциативной, если вычисляет значение по правилу:
(f e1 (f e2 ... (f en start) ... ))
Пример.Функция правоассоциативной свертки.
foldl(f,x,())=x
foldl(f,x, y:z)=f(y, foldl(f, x, z))
Другой известной функцией высшего порядка является функция map, Первым ее аргументом является функция (скалярного аргумента), а вторым - список скалярных значений. Результатом является список, каждый элемент которого получается применением функции к соответствующему элементу исходного списка.
Пример.Функция map.
map(f,x)= foldl(g(f),() ,x),
где g(f)(x,y)=f(x):y
Последняя запись означает, что g – функция высшего порядка от одного аргумента, вырабатывает в качестве значения функцию двух аргументов, результат применения которой к паре аргументов (x,y) описан в определении.
Приведенные примеры иллюстрируют функции высших порядков, которые используют другие функции в качестве входных параметров. В общем случае функция высшего порядка может также вырабатывать функцию в качестве значения результата. Полученная функция может быть использована как функция в дальнейших вычислениях. Для реализации таких функций в языке необходимо предусмотреть средства описания функциональных констант или безымянных значений функционального типа. В функциональных языках программирования для этой цели используются l–формы.
Пример.Способы определения функции map с использованием l–формы.
1. map(f,x)= foldl(g(f),() ,x), где g(f) = lxy.f(x):y
2. map(f,x)= foldl(g(f),() ,x), где g = lfxy.f(x):y
3. map(f,x)= foldl(lxy.f(x):y,() ,x).
Одним из направлений применения таких функций является метапрограммирование, т.е. разработка программ, которые в ходе выполнения в качестве результата вырабатывают другие программы.
Исчисление функциональных типов
Под типом (сортом) в математике принято понимать относительно устойчивую и независимую совокупность элементов, которую можно выделить во всем рассматриваемом множестве (предметной области). В программировании тип определяет множество значений, которые может принимать данная переменная.
Система типов формируется следующим образом.
1.Задается множество базисных типов (обозначим их символами d1 , d2,... и т. д.).
2.Т.к. тип – это множество, то для него выполнимы все операции, известные в теории множеств (объединение diÈ dj, пересечение diÇ dj, прямое произведение diÄ dj и т.д.), кроме того, между типами определено отношение Í, определяющее частичный порядок на множестве типов, т.е. множество типов является частично упорядоченным.
3.Если A и B считаются типами, то функция, определенная на множестве A и принимающая значения из множества B также считается типом, который обозначается A→B.
4.Будем обозначать a:A отношение «a имеет тип A». Т.к. множество типов является частично упорядоченным, то переменная может иметь несколько типов, более точно запись a:A следует понимать как «a может быть отнесено к типу A».
5.Основное правило исчисления заключается в следующем: если f:X ®Y, x:X, то f(x):Y, в противном случае запись f(x) не имеет смысла.
Примеры.
Функция f(x)=2*x удвоения числа имеет тип f:R ®R
Функция f(x,y)=x+y сложения чисел имеет тип f:RÄ R ®R
здесь R – множество чисел.
Пусть теперь A-алфавит, из которого оставляются строки, A*-множество строк над алфавитом A.
Функция f(x,y)=xy конкатенация символьных строк имеет тип f:A*ÄA*®A*.
Функция f(x)=y взятия головного символа строки имеет тип f:A*®A.
Функция f(x, y)= xy присоединения головного символа к строке имеет тип f: AÄA*®A*.
Параметрический тип и полиморфизм
Полиморфизм предполагает описание функций, выполняющих одинаковые действия для различных типов данных. Например, функция сортировки одинакова для данных любого типа, если функция сравнения данных задана отдельно. Функция сравнения для многих языков программирования работает одинаково, например, для числовых и символьных аргументов.
Пример.
Если имеются функции сравнения, например, < с различными типами одна типа <:R® R, другая - типа <: A*®A* (см. предыдущий пример), то на их основе можно определить программу сортировки, которая будет полиморфной и иметь параметризованный тип sort:X*®X*, где X-параметр, принимающий значения R или A*. При этом X*-может обозначать массив числовой или массив строк символов алфавита A.
Пример.Автоаппликация.
Рассмотрим функцию высшего порядка, рассмотренную выше и известную в программировании под именем map. Ее тип map: (X ®Y)Ä X*®Y*. Если эту функцию преобразовать так, чтобы ее можно было применить только к первому ее аргументу, то ее тип преобразуется в следующий map1:(X®Y)®(X*®Y*). Функция map1 преобразует скалярную функцию, доопределяя ее для векторных (списковых) аргументов.
Аргумент функции map1 имеет тип (X®Y) для различных значений параметров X и Y. Интересно, что сама функция map1 является функцией того же типа map1: X®Y, где X= X ®Y, Y= X*®Y*.
В связи с этим функция map1 применима к самой себе. Такое явление называется самоприменимостью или автоаппликацией.
Какой же тип будет у результата map1(map1). По правилам исчисления функциональных типов map1: (X ®Y) ®(X*®Y*), в то же время map1: X®Y. Значит map1(map1):(X*®Y*), но в данном случае X=X®Y и Y=X*®Y*. Значит, тип результата будет map1(map1):(X®Y)*®(X*®Y*)*. Итак, результатом будет функция, на вход которой подается список скалярных функций, а на выходе получается список аналогичных функций, доопределенных для векторных (списковых) аргументов.
3.5. Карринг
Под каррингом понимается применение функции к неполному списку аргументов. Результатом такого применения является функция от остальных аргументов. Например, если функция add определена как
add x y = x+y,
то можно определить функцию inc, увеличивающую свой аргумент на 1 следующим образом:
inc = add 1
Бинарные инфиксные операции являются функциями двух переменных и, следовательно, для них также допустим карринг. Например, если операция «+» двухместная и имеет тип +:RÄ R ®R, то функция «1+»- одноместная, прибавляет 1 к своему аргументу и имеет тип 1+:R®R
Карринг в узком смысле – это применение функции только к одному, самому первому своему аргументу. Это практически означает, что всякая функция нескольких переменных, имеющая тип f: X1Ä X2Ä...Ä XN®Y, преобразуется к типу f: X1® (X2®...® (XN®Y)...), т. е. всякая функция является функцией только одного аргумента, а результатом может являться другая функция.
Пример.
Функция map1 определена как функции одного аргумента. Тогда
map1(*2) – функция, умножающая все элементы списка на 2.
map1(^2) – функция, возводящая все элементы списка в квадрат. Т. е. map1(*2)(1 2 3)=(2 4 6), map1(^2)= (1 4 9). Кроме того,
map1(map1)((*2 ^2))(1 2 3)=((2 4 6)(1 4 9))
В языке HASKELL карринг в узком смысле реализован в полном объеме, т. е. все функции определены как функции одного аргумента. Инфиксные бинарные операторы здесь также можно применять лишь к части своих аргументов (для бинарных операторов эта часть состоит из одного аргумента). Бинарная операция, примененная к одному аргументу, называется секцией.
В LISP'е карринг ни в узком, ни, тем более, в широком смысле не поддерживается на уровне языка, однако программист может определять функции с подходящим типом, допускающие карринг в узком смысле, например:
(defun v (a) (list 'lambda '(b) (list '+ a 'b))) или
(defun v (a) (function (lambda (b) (+ a b))))
с помощью этой функции можно определять другие функции, такие как inc.
(putd 'inc1 (v 1))
(putd 'inc2 (v 2))
Функция inc1 прибавляет к своему аргументу 1, inc2 - 2.
3.6. λ-исчисления и алгебра комбинаторов
Основной объект изучения в λ–исчислении – это λ–термы – прообразы λ–форм в языках программирования и их преобразования (конверсии).
Начиная изучать λ–исчисление можно опираться на проведенную параллель, фиксирующую различие между школьной алгеброй и арифметикой. В алгебре мы отвлекаемся от конкретных числовых значений, которые мы должны сложить или вычесть, поэтому центр тяжести переносится на изучение самих алгебраических операций. Аналогично в λ–исчислении мы отвлекаемся от конкретных функций и концентрируемся на изучении операций создания функций и приложения их к аргументам.
3.6.1. λ–термы
Определение.
(1) λ–термы определяются как строки над алфавитом:
x, y, z - переменные,
λ– абстрактор,
(, ) – скобки.
(2) Пусть x –произвольная переменная. Множество Λ λ–термов определяется следующим образом:
a) xÎΛ;
b) MÎΛ=>(λx.M)ÎΛ;
c) M,NÎΛ=> (MN)ÎΛ.
Соглашение.(о скобках)
(1) внешние скобки не пишутся;
(2) запись N1N2…Nk означает (…(N1N2)…Nk );
(3) запись λx 1x 2…x k.M означает λx 1(λx 2…(λx k.M)…).
Определение. Множество свободных переменных терма M (FV(M)) определяется следующим образом:
(1) FV(x)={x};
(2) FV(λx.M)=FV(M)\{x};
(3) FV(MN)=FV(M)ÈFV(N).
Неформально говоря, если имеется выражение, в которое в качестве подвыражения входит λх.е, то все вхождения переменной х в выражении ебудут связанными. Если переменная не является связанной в некотором выражении, то она в нем будет свободной.
3.6.2. Подстановки
Определение. Результат подстановки терма N вместо всех свободных вхождений переменной x в терм M (обозначается M[x:=N]) определяется следующим образом:
(1) x[x:=N]≡N;
(2) y[x:=N]≡y, если x≠y;
(3) (λy.M)[x:=N]≡(λy.M[x:=N]), если x≠y и yÏFV(N);
(4) KM[x:=N]≡(K[x:=N])(M[x:=N]).
3.6.3. Конверсии
Определение.Отношение конвертируемости λ–термов .M и N.(M=N) определяется следующим образом:
(1) λx.M=λy.M[x:= y], если x≠y и yÏFV(M) (a-конверсия);
(2) (λx.M)N=M[x:=N] (b-конверсия);
(3) аксиомы эквивалентности:
a) M=M рефлексивность;
b) M=N => N=M симметричность;
c) M=N, N=L => M=L транзитивность;
(4) аксиомы λ–исчисления:
a) M=N => MZ=NZ;
b) M=N => ZM=ZN;
c) M=N => λx.M= λx.N (правило x)
Эти аксиомы определяют классическое λ–исчисление. На его основе могут строиться различные теории, путем добавления дополнительных аксиом. Наиболее известными являются:
(1) Mx=Nx => M=N (ext - аксиома экстенсиональности);
(2) λx.Mx=M (h-конверсия)/
3.6.4. Неподвижная точка
Определение.Неподвижной точкой λ–терма F называется λ–терм X такой, что FX=X.
Утверждение. (теорема о неподвижной точке)λ–терм X=WW, где W= λx.F(xx) является неподвижной точкой λ–терма F.
Доказательство:X= WW= (λx.F(xx))W=F(WW)= F(X) ч.т.д.
Пример.Рассмотрим функцию конкатенации списков (см. п.3.2).
C((),y)=y
C(x:z,y)=R(x,y, C(z, y)),
где R(x, y, z)= x:z.
или то же самое с использованием функций car, cdr, cons и if/
C(x,y)=if (x=()), y, cons(car(x), C(cdr(x), y))) или
C= λxy.if (x=()), y, cons(car(x), C(cdr(x), y))) или
C=(λfxy.if (x=()), y, cons(car(x), f(cdr(x), y))))C или C=FC, где
F=(λfxy.if (x=()), y, cons(car(x), f(cdr(x), y)))), т. е. функция конкатенации списков является неподвижной точкой λ–терма F.
3.6.5. Редукции
Определение.Отношение редуцируемости λ–термов .M и N .(M®N) определяется аналогично отношению конвертируемости с той лишь разницей, что отсутствует аксиома симметричности и знак конвертируемости (=) замене на знак редуцируемости (®).
Редуцируемость, в отличие от конвертируемости, является несимметричным отношением между λ–термами и это соответствует действительности, например, (λх.х2+1)3=10можно интерпретировать как «10 — результат вычисления выражения (λх.х2+1)3», но не наоборот. Более правильной была бы запись (λх.х2+1)3®10,которая читается следующим образом: «(λх.х2+1)3 редуцируется (или сводится) к 10». Редукции тесно связаны с конверсиями. Согласно теореме Чёрча — Россера, два терма взаимно конвертируемы тогда и только тогда когда они оба редуцируются к одному и тому же терму.
Мы ввели четыре способа преобразования выражений в лямбда-исчислении.
(1) переименованием переменных или a-преобразование. a-преобразование заключающееся в замене в выражении lх.епеременной хна любую другую с одновременной заменой всех свободных вхождений этой переменной в выражение е, возможно, если только новая переменная уже не входит свободно в выражение е, а также, если при этом свободное вхождение переменной не окажется связанным. Так, например, в выражении lх.lf.fxуможно заменить переменную х, например, на переменную z. В результате получится выражение lz.lf.fzу,которое эквивалентно исходному и имеет тот же смысл. Однако, в том же выражении переменную хнельзя заменить на у, поскольку переменная у входит в тело λ–выражения свободно, так что получившееся после замены выражение ly.lf.fyyуже будет иметь другой смысл - в нем оба вхождения переменной у оказываются связанными. Нельзя также произвести и замену хна f, поскольку это приведет к тому, что в теле λ–выражения свободное вхождение переменной хпревратится в связанное вхождение переменной f, и получившееся выражение lf.lf.ff утакже будет иметь уже другой смысл.
(2) d-редукция, соответствующая применению константы-функции к константам-аргументам. Так, например, если константа + представляет функцию арифметического сложения целых, а константа or - функцию логического «или», то в результате d-редукции выражение +14 может быть преобразовано к выражению 5, а выражение or true false - к выражению true.
(3) b-редукция, соответствующая применению функции, представленной λ–выражением, к аргументу. Если исходное выражение имело вид (lх.е)а, то в результате применения b-редукции оно будет преобразовано в е[х:=а]-выражение е, в котором все свободные вхождения переменной хзаменены на выражение а. Например, выражение (lх.+хх)5 в результате применения b-редукции будет преобразовано в (+55), которое, в свою очередь, может быть преобразовано в 10 с помощью d-редукции.
(4) h-преобразование, выражает тот факт, что функции, которые при применении к одному и тому же аргументу дают один и тот же результат, эквивалентны (равенство функций определяется по их внешнему поведению, а не по внутреннему устройству). Исходное выражение lх.Ехможет быть заменено на Е.
Пример.Применение a-преобразования
Исходное выражение: (lу.(lу.+2у)(+1у))1. Формальные аргументы обеих функций представлены переменной у. Во избежание ошибки целесообразно переименовать одну из связанных переменных. Получим (lу.(lz.+2z)(+1у))1. Далее (lz.+2z)(+11) ® +2(+11) ® +22® 4.
Пример.Применение a-преобразования.
Исходное выражение (lх.lу.+ху)у. Попытка применить b-редукцию без предварительного проведения a-преобразования приведет к ошибке: мы получим выражение lу.+уу, в котором свободное вхождение переменной у попало в позицию, где переменная у связана.
Упражнение.Убедиться, что полученное выражение не эквивалентно исходному.
Продолжение примера.Верное преобразование основано на переименовании связанной переменной у. В этом случае получим (lх.lz.+хz)у ® lz.+уz.
Если в некоторое выражение входит подвыражение, к которому можно применить одну из редукций, то такое подвыражение называется редексом (от redex - reducible expression). Таким образом, процесс преобразования сводится к применению редукций к редексам, содержащимся в исходном выражении.
Пример Применение b-редукции.
Рассмотрим выражение: (lх.+х((lх.*хх)3))5. В нем имеются два подвыражения-редекса. Первый - это само выражение, второй – подвыражение (lх.*хх)3. Если применить b-редукцию к первому из этих редексов - внешнему, - то получится выражение +5((lх.*хх)3). Свободное вхождение переменной х было заменено константой 5, а связанные вхождения остались неизменными. Если применить b-редукцию к внутреннему редексу, то получим (lх +х(*33))5.
3.6.6. Нормальная форма λ-термов
Редукции можно применять до тех пор, пока в выражении имеется хотя бы один редекс. Если ни одного редекса в выражении нет, то говорят, что выражение находится в нормальной форме.
Как мы уже видели, в одном и том же выражении может содержаться несколько редексов, а значит, процесс преобразования выражения к нормальной форме - это не однозначный процесс.
Пример. Приведение к нормальной форме.
Исходное выражение (lх.+х((lх.*хх)3))5 может быть преобразовано двумя разными способами либо к +5((lх.*хх)3), либо к(lх+х(*33))5. В любом случае получившееся выражение еще не находится в нормальной форме, и может быть преобразовано далее. В первом случае, применяя b-редукция, а потом два раза d-редукция. Получим +5(*33), затем +59 и, наконец, 45. Во втором случае опять имеем два редекса в выражении - d-редекс *33 и все выражение, представляющее собой b-редекс. Последовательно преобразуя это выражение применением d- и b-редукций, получим сначала (lх +х9)5, потом +59 и, наконец 45. Несмотря на разные способы преобразования результат - нормальная форма - получился одним и тем же.
Справедлив и более общий факт: если у некоторого выражения существует нормальная форма, то она единственна, то есть какими бы способами ни выполнять преобразования, результат всегда будет одним и тем же, если только вообще он будет достигнут. Нормальная форма существует не всегда, так же как не любая программа обязана завершиться выдачей результата. Кроме того, если нормальная форма существует, не любыми способами к ней можно прийти.
Пример. Выражение, не имеющее нормальной формы.
Рассмотрим выражение (lх.хх)(lх.хх). Само это выражение не является нормальной формой, поскольку к нему можно применить b-редукцию. Однако, при подстановке аргумента (lх.хх) вместо переменной х в тело λ–выражения хх, мы получим опять то же самое выражение (lх.хх)(lх.хх).
Выражение, подобное только что рассмотренному, иллюстрирует важнейшие феномены аппликативных систем, а именно, автоапплиацию (самоприменимость), авторепликацию (воспроизведение себе подобного) и, кроме того, является простейшей формой «зацикливающейся» программы.
Пример.К нормальной форме можно прийти не любым способом.
Рассмотрим выражение (lх.(lу.у))((lх.хх)(lх.хх)). Его можно привести к нормальной форме, если выполнить b-редукцию, считая все выражение редексом. Действительно, выражение представляет собой применение функции (lх.(lу.у)) к некоторому аргументу. Однако, аргумент х не используется в теле функции - lу.у, так что независимо от того, что представляет собой этот аргумент, результатом такой b-редукции будет выражение lу.у. С другой стороны, в исходном выражении есть и еще один редекс - выражение (lх.хх)(lх.хх). Если применять b-редукцию к нему, то преобразования никогда не закончатся.
Назовем редекс самым внешним, если он не содержится ни в каком другом из редексов в рассматриваемом выражении. Так, в рассматриваемом выражении (lх.(lу.у))((lх.хх)(lх.хх)) редекс, представляющий собой все выражение, является самым внешним. Назовем редекс самым внутренним, если внутри него не содержится редексов. Второй из рассматриваемых в нашем выражении редексов - аргумент вызова - является самым внутренним. Конечно, может оказаться, что в выражении есть несколько самых внутренних и несколько самых внешних редексов, причем одни и те же редексы могут быть как самыми внешними, так и самыми внутренними
Дата: 2016-10-02, просмотров: 257.