 |
Функции более высокого порядка
|
|
|
|
Функционалы
Функциональный аргумент. Основываясь на едином представлении данных и программ (идущем из ламбда-исчисления), функции в качестве аргумента можно указать и функцию, или, другими словами, определение функции, либо представляющий функцию символ. Аргумент, значением которого является функция, называют в функциональном программировании функциональным аргументом, а функцию, имеющую функциональный аргумент, - функционалом.
Различие между понятиями “данные” и “функция” определяется не на основе их структуры, а в зависимости от их использования. Если аргумент используется в функции лишь как объект, участвующий в вычислениях, то мы имеем дело с обыкновенным аргументом, представляющим данные. Если же он используется как средство, определяющее вычисления, т. е. играет в вычислениях, например, роль ламбда-выражения, которое применяется к другим аргументам, то мы имеем дело с функцией.
Одно и то же выражение может в связи с различными аспектами выступать, с одной стороны, как обыкновенный аргумент, а с другой стороны, как функциональный. Роль в интерпретации выражения зависит от его синтаксической позиции. Приведем пример:
(first ‘(lambda (x) (list x))) ==> lambda
((lambda (x) (list x)) ‘first) ==> (first)
Сравните с позициями ламбда-выражений в операции аппликации.
Далее мы будем использовать понятия функции, вызова функции и значения функции в следующем смысле:
1) функция сама есть изображение вычислений или определение;
2) вызов функции есть применение этого изображения;
3) з начение функции есть результат такого применения.
Функция является функционалом, если в качестве её аргумента используется лисповский объект типа (1), который интерпретируется как функция (2) в теле функционала. Таким функциональным объектом может быть:
|
|
|
· символьное имя, представляющее определение функции (системная функция или функция, определенная пользователем);
· безымянное ламбда-выражение;
· так называемое замыкание (рассматриваемое позже).
Функциональное значение функции. Функция может быть и результатом функции. Такие функции (или функционалы), говорят, имеют функциональное значение.
В Коммон Лиспе предполагается, что в вызове функции на месте имени функции находится символ, определенный с помощью DEFUN как имя функции. Переданный в качестве параметра функциональный объект можно использовать лишь через явный вызов применяющих функционалов (FUNCALL, APPLY).
Способы композиции функций
Функции первого порядка:
· обыкновенный вызов
(defun f... (g...)...)
· рекурсивный вызов
(defun f... (f...)...)
· вложенный рекурсивный вызов
(defun f... (f... (f...)...)...)
Функции более высокого порядка:
· функциональный аргумент
(defun f (... g...)... (apply g...)...)
· рекурсивный функциональный аргумент
(defun f (... g...)...(apply g... g...)...)
Получающий себя в качестве аргумента функционал называют применяемым к самому себе или автоаппликативной (самоприменяемой) функцией. Соответственно функцию, возвращающую саму себя, называют авторепликативной (самовоспроизводящей) функцией.
Автоаппликативные и авторепликативные функции образуют класс автофункций.
Применяющие функционалы позволяют применять функциональный аргумент к другим параметрам. Применяющие функционалы дают возможность интерпретировать и преобразовывать данные в программу и применять ее в вычислениях.
APPLY применяет функцию к списку аргументов
(APPLY fn список) <==> (fn ‘x1 ‘ x2... ‘xn)
где список = (x1 x2... xn)
Функция fn не должна быть встроенной функцией or или and.
|
|
|
(apply ‘+ ‘(2 3)) ==> 5
(setq f ‘+)
(apply f ‘(2 3)) ===> 5
(apply ‘eval ‘(+ 2 3)) ==> 5
(apply ‘apply ‘(+ (2 3))) ==> 5
(apply ‘(lambda (x y) (+ x y)) ‘(2 3)) ==>5
Использование APPLY дает большую гибкость по сравнению с прямым вызовом функции: с помощью одной и той же функции APPLY можно в зависимости от функционального аргумента осуществлять различные вычисления.
FUNCALL вызывает функцию с аргументами
Аргументы для вызываемой функции funcall принимает не списком, а по отдельности.
(funcall fn x1 x2... xn) <==> (fn x1 x2... xn)
Функция fn не должна быть встроенной функцией or или and.
(funcall ‘list ‘apply ‘‘+ ‘‘(2 3)) ==> (apply (quote +) (quote (2 3)))
(defun do (x f1 f2)
(funcall (if (< x 0) f1 f2) x))
(do -1 ’- ’(lambda (x) (* x x x))) ==> 1
(do 4 ’- ’(lambda (x) (* x x x))) ==> 64
Отображающие функционалы повторяют применение функции: отображают список в новый список.
Mapcar - применяет функцию к последовательным элементам списка
Синтаксис: (mapcar <fcn> <list1> <list2>...)
Применяет функцию к последовательным элементам списков:
<fcn> - функция или функциональное имя,
<listn> - список для каждого аргумента функции.
Возвращает список значений функции.
(mapcar ‘1+ ‘(1 2 3)) ==> (2 3 4)
(mapcar ‘(lambda (x) (* 2 (1+ x))) ‘(1 2 3)) ==> (4 6 8)
(mapcar ‘+ ‘(1 2 3) ‘(5 6 7)) ==> (6 8 10)
(mapcar ‘list ‘(+ + +) ‘(1 2 3) ‘(a b c)) ==> ((+ 1 a) (+ 2 b) (+ 3 c))
(mapcar ’evenp ‘(1 2 3 4)) ==> (nil t nil t)
(mapcar ’equal ‘(1 2 3) ‘(1 4 9 16)) ==> (t nil nil)
(mapcar ’max ‘(1 2 3 4) ‘(1 4 9 16) ‘(11 1 2 10)) ==> (11 4 9 16)
Функционал mapcar с одноместной функцией в качестве функционального аргумента можно определить так:
(defun map (f x)
(if (null x) nil
(cons (funcall f (first x)) (map f (rest x)))
)
)
MAPLIST повторяет вычисления на хвостовых частях списка; действует подобно mapcar, но действия осуществляет не над элементами списка, а над последовательностью хвостов этого списка (начиная с самого исходного списка):
(maplist ‘(lambda (x) x) ‘(a b c)) ==> ((a b c) (b c) (c))
(maplist ‘reverse ‘(a b c)) ==> ((c b a) (c b) (c))
"Универсальный" функционал reduce
(defun reduce (g x a)
(if (null x) a
(funcall g (first x) (reduce g (rest x) a))
)
)
Пусть x - список, состоящий из элементов (x1 x2 x3 x4... xn), тогда значение функции (reduce g x a) есть результат вычисления выражения
g (x1, g (x2,... g (xn, a)...))
; примеры вызова:
; (reduce '* '(6 4 3) 1)
; (reduce 'max '(6 4 8) 0)
; (reduce 'list '(a b c) nil) => (A (B (C NIL)))
; (reduce ‘(lambda (x y) (list x '+ y)) '(a b c) 'd)
|
|
|
; =>(A + (B + (C + D)))
(defun sumpr (s)
(list (reduce ’+ s 0)
(reduce ’* s 1)))
Замыкания
Чтобы на этапе вызова функционала можно было отличить функциональный аргумент от обычного, функциональный аргумент помечают с помощью предотвращающей вычисления формы FUNCTION:
(function функция)
Примеры:
(function (lambda (x) (list x y)))
(function first)
Форму function называют функциональной блокировкой. Краткое обозначение:
#’ f <===> (function f)
Если нужно передать функции данные в том виде, как они записаны, то используется обычная форма QUOTE. Формы QUOTE достаточно и для передачи имени функции или ламбда-выражения, если в нем не используются свободные переменные. В системных функциях свободных переменных нет, поэтому все следующие формы имеют одинаковое значение:
(+ 2 3)
(funcall ‘+ 2 3)
(funcall (function +) 2 3)
(funcall #’+ 2 3)
((lambda (x y) (+ x y)) 2 3)
(funcall (function (lambda (x y) (+ x y))) 2 3)
Замыкание - это функция и контекст ее определения. Часто бывает полезным и необходимым, чтобы функция для продолжения вычислений могла запомнить связи и состояние более раннего контекста. Это достигается с помощью замыкания - функционального объекта, в котором вместе с самим описанием вычислений сохраняется контекст момента определения функции, защищенный от более позднего контекста вызова. В Коммон Лиспе замыкание создается формой FUNCTION, например,
(function (lambda (x) (+ x y)))
В замыкание из контекста определения функции включаются лишь связи свободных переменных функции (в приведенном примере глобальное значение y). Если в замыкаемой функции нет свободных переменных, то форма FUNCTION ничем не отличается от формы QUOTE.
Пример:
; результат вызова функции inc - снова функция
(defun inc (n) #’(lambda (z) (+ z n)))
(defun inc3 (z) (funcall (inc 3) z))
(funcall (inc 4) 5) => 9
Абстрактный подход
Абстракция отображения (отображение данных) основана на параметризации ламбда-выражений. Можно с помощью механизма параметризации абстрагировать сами функции, т. е. параметризация касается первого элемента вызова функции - это называется абстракцией вычислений.
Обобщение функций, имеющих одинаковый вид. Рассмотрим обобщение с помощью функционалов функций, определения которых с точки зрения абстракции вычислений сходны по строению, но которые довольно различны с точки зрения производимых действий.
|
|
|
Функция последовательного объединения двух списков.
(defun append1 (x y)
(if (null x) y
(cons (first x) (append1 (rest x) y))))
Функция слияния двух упорядоченных списков в один упорядоченный.
(defun merge (x y)
(if (null x) y
(insert (first x) (merge (rest x) y))))
(defun insert (a s)
(cond ((null s) (list a))
((< a (first s)) (cons a s))
(t (cons (first s) (insert a (rest s)))))
)
Добавим новый функциональный аргумент в reduce.
(defun reduce2 (g f x a)
(if (null x) a
(funcall g (funcall f (first x)) (reduce2 g f (rest x) a))
)
)
Вместо двух рекурсивных функций append1 и merge применяем обобщающий функционал reduce2
(defun append2 (x y) (reduce2 #’cons #’(lambda (z) z) x y))
(defun merge1 (x y) (reduce2 #’insert #’(lambda (z) z) x y))
Определим функциональный предикат (forall p s), который истинен т. и т.т., когда p(x) истинна для всех элементов списка s.
(defun forall (p s)
(reduce #’and (mapcar p s) t))
В этом примере нужно использовать не встроенную функцию and, а определить ее самостоятельно, например, так:
(defun and (x y)
(if x y nil))
Определим функциональный предикат (forsome p s), который истинен т. и т.т., когда p(x) истинна для некоторого элемента x списка s.
(defun forsome (p s)
(reduce #’or (mapcar p s) nil))
В этом примере также нужно использовать не встроенную функцию or, а определить ее самостоятельно, например, так:
(defun or (x y)
(if x t y))
Функционал reduce2 можно использовать для образных вычислений.
(defun member (x s)
(reduce2 #’or #’(lambda (y) (equal y x)) s nil))
; число вхождений элемента в список
(defun count (x s)
(reduce2 #’+ #’ (lambda (y) (if (eql x y) 1 0)) s 0)
(defun map (f x)
(reduce2 #’cons f x nil))
Абстрагирование вычислений с помощью функций с функциональными значениями. Композицию двух функций можно определить так:
(defun comp (f g)
#’(lambda (x) (funcall f (funcall g x)))
)
В результате конкретного вызова функции comp возвращается одноместная функция (в Лиспе она трактуется как замыкание). Мы можем теперь строить пирамиды новых функционалов. Например, определим функцию twice:
(defun twice (f) (comp f f))
Примеры вызовов:
(funcall (twice #’ (lambda (x) (* x x x))) 2) => 512
(defun inc3 (x) (+ x 3))
(funcall (twice 'inc3) 10) => 16
( funcall (twice (twice ‘1+)) 1) ==> 5
Определим n-ую степень функции fn <==> f(f(f(f(...f(x))))
(f применяется n раз).
(defun n-comp (f n)
(if (zerop n) #’(lambda (x) x)
(comp f (n-comp f (1- n)))))
(funcall (n-comp #’1+ 10) 20) ==> 30
Примеры использования функции n-comp:
сложение двух натуральных чисел
(defun summa (n m)
(funcall (n-comp #’1+ n) m))
(summa 4 9) ==>13
умножение двух натуральных чисел
(defun mult (n m)
(funcall (n-comp #’(lambda (x) (summa x n)) m) 0))
(mult 5 6) ==> 30
возведение натурального числа в натуральную степень
(defun power (n m)
|
|
|
(funcall (n-comp #’(lambda (x) (mult x n)) m) 1))
(power 2 10) ==> 1024
Автофункции
В функциональном программировании рассматриваются автоаппликативные и авторепликативные функционалы как функции, которые получают или возвращают в качестве результата самих себя или, точнее, копии самих себя. Конечно, не очевидно, что такие функции вообще существуют. Однако никаких принципиальных препятствий для их существования и определения не существует. В Лиспе их можно определить и использовать довольно просто.
Для начала рассмотрим автоаппликативный вариант факториала:
(defun factorial (f n)
(if (zerop n) 1 (* n (funcall f f (1- n)))))
Для вычисления 10! необходимо функционалу factorial в его вызове в качестве функционального аргумента передать его собственное определение.
> (factorial 'factorial 10)
3628800
Соответственно тому, как мы можем через функциональный аргумент определить автоаппликативную рекурсивную функцию, мы можем определить и возвращающую себя рекурсивно функцию с функциональным значением.
Возьмем в качестве примера простейшую возможную функцию, которая возвращает себя в качестве результата. Это лямбда-выражение, примененное к такому же лямбда-выражению с формой QUOTE, т. е. это лямбда-вызов:
((lambda (x) (list x (list ‘quote x))) ‘(lambda (x) (list x (list ‘quote x))))
Форма является одновременно автоаппликативной! Она содержит изображение самой себя, но не целиком, поскольку такое изображение было бы бесконечно длинным. Изображение получается ограниченным благодаря механизму блокировки и лямбда-механизму, а также благодаря автоаппликации.
Для проверки присвоим форму переменной self:
(setq self
‘((lambda (x) (list x (list ‘quote x))) ‘(lambda (x) (list x (list ‘quote x)))))
> (eval self)
((lambda (x) (list x (list ‘quote x))) ‘(lambda (x) (list x (list ‘quote x))))
Форму можно вычислять вновь и вновь, и все равно получается тот же результат: само определение функции (его копия). Кроме того, значение функции совпадает со значением аргумента ее вызова. Такое значение называется неподвижной точкой функции.
Форма self аналогична известному комбинатору (lx. x x) (lx. x x):
b -редукция терма (lx. x x) (lx. x x) приводит к бесконечному циклу
(lx. x x) (lx. x x) ® (lx. x x) (lx. x x) ® ….
Автоаппликация как форма рекурсии с теоретической точки зрения очень интересна, но в практическом программировании не находит особого применения. С нею связаны теоретические вопросы и проблемы, которые во многом еще не изучены. В формализмах и постановке проблем, которые основаны на похожих на автоаппликацию ссылках на себя (self-reference), очень легко приходят к логическим парадоксам, подобным известному из учебников по теории множеств парадоксу Рассела. Их разрешение предполагает учет типов объектов и кратности ссылок.
Однако автоаппликация может открыть новый подход к программированию. Возможными применениями могли бы быть, например, системы, сохраняющие неизменными определенные свойства, хотя какие-то их части изменяются. Такими свойствами могли бы быть наряду с применимостью и репродуцируемостью, например, способность к самоизменениям (self-modification), таким как приспособляемость, согласованность и обучаемость, самосознание и сознательность и т. д. Самосознание предполагает существование модели мира внутри такой системы, включая саму систему в эту модель.
Автофункции - это новый класс функций, которые отличаются от обыкновенных рекурсивных функций так же, как рекурсивные функции отличаются от нерекурсивных. Чтобы их можно было использовать в программировании столь же удобно, как и рекурсию, нужно использовать механизмы, которые при программировании учитывают инвариантные свойства вычислений таким же образом, как механизмы определения, вызова и вычисления функций учитывают рекурсию.
[ГАсГ1]
|
|
|
