Основы функционального программирования

Неподвижная точка и самоприменимость функций


Возможность использования безымянных определений функций не вполне очевидна для вспомогательных рекурсивных функций, так как их имена нужны в их собственных определениях. Но при необходимости и определение рекурсивной функции можно привести к форме, не зависящей от ее имени. Такие имена формально работают как связанные переменные, т.е. их смысл не зависит от имени — нечто вроде местоимения. Это позволяет выполнять систематическую замену названия функции на другие символы или выражения.

Пример (предложен В.А.Потапенко).

Преобразуем определение факториала в самоприменимую безымянную форму.

Для этого нужно:

  • преобразовать исходное определение в самоприменимую форму;
  • избавиться от собственного имени функции.

Традиционное определение факториала:

(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, связано с реализационным различием структурного представления данных и представляемых ими функций.


Содержание раздела