Как рекурсивно вызывать функцию с функцией как параметр

Question

Из вопроса How do I pass a function as a parameter to in elisp? Я знаю, как передать функцию в качестве параметра функции. Нонам нужно идти глубже ...

Lame фильма цитирует в стороне, я хочу иметь функцию, которая принимает функцию в качестве параметра и в состоянии назвать себя [снова передавая функцию, которую она приняла как параметр]. Рассмотрим следующий фрагмент:

(defun dummy() 
    (message "Dummy")) 

(defun func1 (func) 
    (funcall func)) 

(defun func2 (func arg) 
    (message "arg = %s" arg) 
    (funcall func) 
    (func2 'func (- arg 1))) 

Calling (func1 'dummy) дает ожидаемый результат:

Dummy  
"Dummy" 

Calling (func2 'dummy 4) результаты в сообщении об ошибке:

arg = 4 
Dummy 
arg = 3 
funcall: Symbol's function definition is void: func 

я ожидал четырех вызовов фиктивный, однако вторая итерация func2, похоже, потеряла знание функции, переданной первой итерации (и переданной оттуда). Любая помощь высоко ценится!

Answer 1

Это потому, что вы пытаетесь вызвать функцию func, а не функцию dummy.

(Следовательно, ошибка "определение функции Symbol является недействительным: FUNC".)

Вы хотите:

(func2 func (- arg 1))) 

нет:

(func2 'func (- arg 1))) 

Answer 2

1. Вам не нужно цитировать func в func2 звонок
2. Вы a повторно отсутствует условие завершения рекурсии в func2

Вот что работает для меня:

(defun func2 (func arg) 
    (message "arg = %s" arg) 
    (funcall func) 
    (when (plusp arg) 
    (func2 func (- arg 1)))) 

Answer 3

Там, вероятно, лучший способ сделать это с помощью лексической области видимости. Это более или менее перевод с Rosetta Код:

(defun closure (y) 
    `(lambda (&rest args) (apply (funcall ',y ',y) args))) 

(defun Y (f) 
    ((lambda (x) (funcall x x)) 
    `(lambda (y) (funcall ',f (closure y))))) 

(defun factorial (f) 
    `(lambda (n) 
    (if (zerop n) 1 
     (* n (funcall ,f (1- n)))))) 

(funcall (Y 'factorial) 5) ;; 120 

Вот ссылка на Rosetta код: http://rosettacode.org/wiki/Y_combinator с кучей других языков immplementing то же самое. Y-комбинатор представляет собой конструкцию из семейства fixed-point combinator с. Грубо говоря, идея состоит в том, чтобы устранить необходимость в реализации рекурсивных функций (рекурсивные функции требуют большей сложности, когда вы думаете о том, как их компилировать/внедрять в виртуальной машине). Y-combinator решает это, позволяя механически переводить все функции в нерекурсивную форму, сохраняя при этом рекурсию вообще.

Справедливости ради, приведенный выше код не очень хорош, поскольку он будет создавать новые функции на каждом рекурсивном шаге. Это связано с тем, что до недавнего времени у Emacs Lisp не было лексических привязок (вы не могли бы захватить функцию своей лексической средой), другими словами, когда функция Emacs Lisp используется за пределами области действия, которую она объявила, значения связанные переменные будут взяты из текущей области функции.В вышеприведенном случае такие связанные переменные составляют f в функции Y и y в функции closure. К счастью, это всего лишь символы, обозначающие существующую функцию, поэтому можно имитировать это поведение с помощью макросов.

Теперь, что делает Y-комбинатор:

1. Захватывает исходную функцию в переменной f.

2. Возвращает функцию-оболочки одного аргумента, который будет вызывать f, при вызове в своей очереди, используемый Y-комбинатор в

3. Вернется функцией обертки неограниченного числа аргументов, которые будут

4. вызовите исходную функцию, передав ей все аргументы, с которыми она была вызвана.

Эта структура также диктует вам структуру функции для использования с Y-комбинатора: он должен принимать один аргумент, который должен быть функцией (это та же функция снова) и возвращает функцию (любого количества аргументов), который вызывает функцию, унаследованную из внешней области.

Ну, это, как известно, немного ошеломляет :)