Ранжирование функций
Применение функций высших порядков естественным образом завершает освоение функционального программирования как логической системы, допускающей конструирование функциональных объектов при решении задач регулярной обработки формализованной информации. Подобные задачи возникают при реализации и настройке сложных информационных систем, таких как операционные системы, системы программирования, текстовые и графические процессоры, системы управления базами данных, поддержки проектов и т.п.
Функции высших порядков используют другие функции в качестве аргументов или вырабатывают их как результат.
(defun mul-N (N) #'(lambda (x) (* x N))) ; конструктор семейства функций, множащих ; аргумент на N (funcall (mul-N 25) 7) ; применение частной функции, умножающей на 25
Правильность выражений с такими функциями требует корректной подстановки параметров и учета ранга функции, определяющего возможность манипулирования функциональными значениями. Функции можно ранжировать на основе так называемых типовых выражений, представляющих области определения и значения функций. Например,
x+1 : Number -> Number
x+y : (Number Number) -> Number
Отсутствие таких средств в языке можно компенсировать соответствующими комментариями [3].
Суперпозицию функций можно характеризовать следующими типовыми выражениями:
S(h,g) = { при h: X -> Y, g: Y -> Z строит f=g(h) — суперпозиция } : (X->Y Y->Z) -> (X->Z)
(defun super (f g) #'(lambda (x) (funcall f (funcall g x)) )) ; конструктор суперпозиции функций
(funcall (super #'car #'cdr) '(1 2 3)) ; применение суперпозиции CAR и CDR
Двойное применение функции можно определить независимо или через суперпозицию — типовое выражение от этого не зависит, но оно представляет собой параметризованное выражение.
W f = ((lambda x)(f (f x))) = S (f,f) { дважды применяется функция } : (Number->Number) -> (Number->Number)
или более точно:
: (X->X) -> (X->X),
где X — произвольный тип значения. Типовое выражение представляет зависимость от этого типа — параметризованный тип значения.
(defun duble (f) #'(lambda (x) (funcall f(funcall f x)) )) ; конструктор двойного применения функции
(funcall (duble #'car) '(((1) 2) 3)) ;= (1)
(defun duble (f) (funcall #'super f f)) ; двойное применение функции через суперпозицию
(funcall (duble #'car) '(((A B) B) C)) ; = (A B)
Можно ввести обозначения:
Atom — атомы, Number — число, List (X) — NIL или списки из элементов типа X Bool — NIL или T,` Some — любой объект.
Соответственно пишутся типовые выражения для элементарных функций:
cons : (X List (X)) -> List (X) car : List (X) -> X cdr : List (X) -> List (X) eq : (Atom Atom) -> Bool atom : Some -> Bool : (Atom -> T) & (List (X) -> NIL) null : Some -> Bool : (NIL -> T) & (Atom \=NIL -> NIL) & (List(X)\=NIL -> NIL)
Таким же образом можно специфицировать и универсальную функцию:
eval [e, al]:(Some List( (Atom . Some ) )) -> Some | | | List( (Atom . Some) ) Some{ могут попасть и неправильные выражения }
apply [fn, (a1 a2 …), al]:(List( Some ) -> Some List( Some ) List((Atom . Some) )) | | | -> Some | | List((Atom . Some)) | List(Some) (List(Some) -> Some
Отображающий функционал также может характеризоваться типовым выражением:
map [x, f] :( List(X) (X->Y) ) -> List(Y)
(defun map (x f) (cond (x (cons (funcall f (car x)) (map (cdr x) f ))))) (map '((1) (2) (3)) #'car )
Можно построить функцию, непосредственно преобразующую свой функциональный аргумент в новую функцию.
mapf [f] : List(X->Y) ->( List(X) -> List(Y))
(defun mapf (f) #'(lambda (x) (cond (x (cons (funcall f (car x)) (funcall (mapf f ) (cdr x)) ))) )) (funcall (mapf #'car ) '((1) (2) (3)) )
Аргумент может быть списком функций, результаты которых следует собрать в общий список.
manyfun [lf] : List(X->Y) -> (X -> List(Y)) | | |_____список | | результатов функций | |_____тип аргумента | отдельной функции |____________________список функций (defun manyfun (lf) #'(lambda (x) (cond (lf (cons (funcall (car lf) x) (funcall (manyfun (cdr lf)) x) ))) )) (funcall (manyfun '(car cdr length)) '(1 f (2 T) (3 D e)) )
Таким образом можно как бы «просачивать» определения функций над простыми данными, распределять их по структурам данных и тем самым распространять простые функции на сложные данные подобно матричной арифметике. Такой стиль работы характерен для теории комбинаторов и языка FORTH.
Похожие построения предлагаются Бэкусом в его программной статье о функциональном стиле программирования [20] и в языке APL, ориентированном на обработку матриц.
Существует ряд языков функционального программирования, требующих или допускающих спецификацию объектов, что, кроме дисциплины программирования, дает средства для корректной работы с пакетами, сопряжения с модулями на других языках, оптимизирующих преобразований, распараллеливания и верификации программ (Sisal, ML и др.).
