На этом шаге мы введем понятия автоаппликации и авторепликации.
Получающий себя в качестве аргумента функционал называют автоаппликативной функцией (применяемой к самой себе). Соответственно функцию, возвращающую саму себя, называют авторепликативной (самовоспроизводящейся) функцией.
Автоаппликативные и авторепликативные функции образуют класс автофункций. Конечно, не очевидно, что такие функции вообще существуют. Однако, никаких принципиальных препятствий для их существования и определения не существует. В языке LISP их можно определить и использовать довольно просто.
Пример. Возьмем в качестве примера простейшую возможную функцию, которая возвращает себя в качестве результата:
$ ((LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X))) (QUOTE (LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X)))) )Результат:
(QUOTE (LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X))))
Функция является одновременно и автоаппликативной! Для проверки присвоим ее атому
SAMO:
$ (SETQ SAMO (QUOTE ((LAMBDA (X) (LIST X (LIST (QUOTE
QUOTE) X))) (QUOTE (LAMBDA (X) (LIST X (LIST (QUOTE
QUOTE) X)))))))
Результат:
$ (EVAL (EVAL (EVAL SAMO)))
((LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X))) (QUOTE
(LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X)))))
Значение функции можно вычислять вновь и вновь, и все равно получается тот же результат: само определение функции (его копия). Кроме того, значение функции совпадает со значением аргумента ее вызова. Такое значение называется неподвижной точкой функции.
Автоаппликация как форма рекурсии с теоретической точки зрения очень интересна, но в практическом программировании, во всяком случае до настоящего времени, не находит особого применения. С нею связаны теоретические вопросы и проблемы, которые во многом еще не изучены.
Однако, автоаппликация может открыть новый подход к программированию. Возможными применениями могли бы быть, например, системы, сохраняющие неизменными определенные свойства, хотя какие-то их части изменяются.
Автофункции - это новый класс функций, которые отличаются от обыкновенных рекурсивных функций
так же, как рекурсивные функции отличаются от нерекурсивных.
На следующем шаге мы предложим выполнить несколько заданий на использование рекурсии.
