Ранжирование функций
Применение функций высших порядков (ФВП) характерно при решении задач регулярной обработки формализованной информации. Подобные задачи возникают при реализации и настройке сложных информационных систем, таких как операционные системы, системы программирования, текстовые и графические процессоры, системы управления базами данных, поддержки проектов и т.п. Рассмотрим технику применения ФВП на примере функционалов языка Лисп.
Функции высших порядков используют другие функции в качестве аргументов или вырабатывают в качестве результатов.
(defun mul-N (N) #'(lambda (x) (* x N))) ; конструктор семейства функций, множащих аргумент на N
(funcall (mul-N 25) 7) ; применение частной функции, умножающей на 25
Правильность выражений с такими функциями требует корректной подстановки параметров и учета ранга функции, определяющего возможность манипулирования функциональными значениями. Функции можно ранжировать на основе так называемых типовых выражений, представляющих области определения и значения функций. Задание типов данных может требоваться языком программирования или быть представимо в виде комментария. Методы таких представлений рассмотрены в курсе [[23],[8]].
Например, можно ввести обозначения:
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 at : Some -> Bool : (Atom -> T) & (List (X) -> NIL) nl : Some -> Bool : (NIL -> T) & (Atom \=NIL -> NIL) & (List (X)\=NIL -> NIL)
Таким же образом можно специфицировать интерпретатор:
eval : (Some List( (Atom . Some ) )) -> Some |__ могут попасть неправильные выражения
apply : (List(Some ) -> Some List(Some ) List((Atom . Some)) ) -> Some
Отображающий функционал также может характеризоваться типовым выражением:
map- : ( 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 : 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 : 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 [[3]]. Похожие построения предлагаются Бэкусом в его программной статье о функциональном стиле программирования и в языке APL, ориентированном на обработку матриц [[16]].
Существует ряд языков функционального программирования, требующих или допускающих спецификацию объектов, что, кроме дисциплины программирования, дает средства для корректной работы с пакетами, сопряжения с модулями на других языках, оптимизирующих преобразований, распараллеливания и верификации программ (Sisal, ML и др.) [[84]].
