Неподвижная точка и самоприменимость функций
Возможность использования безымянных определений функций не вполне очевидна для вспомогательных рекурсивных функций, так как их имена нужны в их собственных определениях. Но при необходимости и определение рекурсивной функции можно привести к форме, не зависящей от ее имени. Такие имена формально работают как связанные переменные, т.е. их смысл не зависит от имени — нечто вроде местоимения. Это позволяет выполнять систематическую замену названия функции на другие символы или выражения.
Пример (предложен В.А.Потапенко).
Преобразуем определение факториала в самоприменимую безымянную форму.
Для этого нужно:
- преобразовать исходное определение в самоприменимую форму;
- избавиться от собственного имени функции.
Традиционное определение факториала:
(defun N! (n) (cond ((eq n 0) 1) (T (* n (N! (- n 1)))) ; Факториал
; Выход из рекурсии
; Рекурсивный виток с редукцией аргумента ) ) ; и умножением на результат предыдущего витка
Строим самоприменимое определение факториала:
(defun N!_self (f n) ; Обобщенная функция, ; равносильная факториалу при f = N!_self (cond ((eq n 0)1) (T (* n (apply f (list f (- n 1))))) ; применение функции f ; к списку из уменьшенного аргумента ) )
Использовать это определение можно следующим образом:
(N!_self #'N!_self 3) ; = 6 =
или
(apply 'N!_self '(N!_self 4)) ; = 24 =
При таких аргументах оно эквивалентно исходному определению факториала. Теперь избавимся от названия функции:
((lambda (f n ) ; безымянная функция, равносильная факториалу ; при f = N!_self
(cond ((eq n 0)1) (t (* n ( f (list f (- n 1))))) ))
Использовать это определение можно в следующей форме:
((lambda (f n ) (cond ((eq n 0)1) (t (* n (apply f (list f (- n 1))))) )) ; функция
(lambda (f n ) (cond ((eq n 0)1) (t (* n (apply f (list f (- n 1))))) )) ;первый аргумент — f 5 ; второй аргумент — n ) ; = 120
или
(apply
#'(lambda (f n ) (cond ((eq n 0)1)(t (* n (apply f (list f (- n 1))))) ) ) ; функция '((lambda (f n ) (cond ((eq n 0)1) (t (* n (apply f (list f (- n 1))))) )) 6 ) ; список аргументов )) ; = 720
Можно записать этот текст программы (код) без дублирования определения функции:
(lambda (n) ( (lambda (f) (apply f f n)) #'(lambda (f n ) (cond ((eq n 0)1) (t (* n (apply f (list f (- n 1)))) ) ) ; внутренняя функция f ) ))
И использовать полученное определение следующим образом:
((lambda (n) ((lambda (f) (apply f (list f n))) #'(lambda (f n ) (cond ((eq n 0)1) (t (* n (apply f (list f (- n 1))))) ) ) )) 6 ) ; = 120 )
Сокращаем совпадающие подфункции и получаем форму, в которой основные содержательные компоненты локализованы:
((lambda (n) (flet ((afl (f n) (apply f (list f n)) ))
((lambda (f) (afl f n)) #'(lambda (f n ) (cond ((eq n 0)1) (t (* n (afl f (- n 1)))) ))))) 6 ) ; = 720 )
Таким образом, определение рекурсивной функции можно преобразовать к безымянной форме. Техника эквивалентных преобразований позволяет поддерживать целостность системы функций втягиванием безымянных вспомогательных функций внутрь тела основного определения. Верно и обратное: любую конструкцию из лямбда-выражений можно преобразовать в систему отдельных функций.
Такое, пусть не самое понятное, определение позволяет получить больше, чем просто скорость исполнения кода и его переносимость. Техника функциональных определений и их преобразований позволяет рассматривать решение задачи с той точки зрения, с какой это удобно при постановке задачи, с естественной степенью подробности, гибкости и мобильности.
специальная функция function (#') обеспечивает доступ к функциональному объекту, связанному с атомом, а функция funcall обеспечивает применение функции к произвольному числу ее аргументов.
(funcall f a1 a2 ... ) = (apply f (list a1 a2 ...))
Разрастание числа функций, манипулирующих функциями в Clisp, связано с реализационным различием структурного представления данных и представляемых ими функций.
