В Scheme, как вы используете lambda для создания рекурсивной функции?

(lambda (x) (xx)) – это функция, которая называет аргумент x на себе.

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

 (((lambda (x) (xx)) (lambda (fact-gen) (lambda (n) (if (zero? n) 1 (* n ((fact-gen fact-gen) (sub1 n))))))) 5) 

Это вызывает его с 5 и возвращает 120.

Самый простой способ подумать об этом на высоком уровне состоит в том, что первая функция (lambda (x) (xx)) дает х ссылку на себя, так что теперь х может ссылаться на себя и, следовательно, рекурсивно.

Выражение (lambda (x) (xx)) создает функцию, которая при оценке одним аргументом (которая должна быть функцией) применяет эту функцию к себе как к аргументу.

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

 (let ((factorial ((lambda (x) (xx)) (lambda (fact-gen) (lambda (n) (if (zero? n) 1 (* n ((fact-gen fact-gen) (sub1 n))))))))) (display (factorial 5))) 

В вашем примере есть несколько уровней, стоит поэтапно работать и внимательно изучать, что каждый делает.

(lambda (x) (xx)) принимает объект функции, а затем вызывает этот объект с использованием одного аргумента, самого объекта функции.

Затем он вызывается с другой функцией, которая принимает этот объект функции под именем параметра fact-gen . Он возвращает лямбду, которая принимает фактический аргумент, n . Вот как работает ((fact-gen fact-gen) (sub1 n)) .

Вы должны прочитать образец главы (Глава 9) от The Little Schemer, если вы можете следовать ей. В нем обсуждается, как создавать функции этого типа и, в конечном счете, извлекать этот шаблон в комбинатор Y (который может использоваться для обеспечения рекурсии вообще).

Вы определяете его так:

 (let ((fact #f)) (set! fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1)))))) (fact 5)) 

так как letrec действительно работает. См. LiSP от Christian Queinnec.

В примере, о котором вы спрашиваете, комбинатор самоприложений называется « U combinator» ,

 (let ((U (lambda (x) (xx))) (h (lambda (g) (lambda (n) (if (zero? n) 1 (* n ((gg) (sub1 n)))))))) ((U h) 5)) 

Тонкость здесь заключается в том, что из-за правил '' '' '' '' '' '' '' scoping '', lambda-выражения не могут ссылаться на определяемые имена.

Когда вызывается ((U h) 5) , оно сводится к ((hh) 5) применению, внутри frameworks среды, созданной формой let .

Теперь приложение h в h создает новый фрейм среды, в котором g указывает на h в окружении над ним:

 (let ((U (lambda (x) (xx))) (h (lambda (g) (lambda (n) (if (zero? n) 1 (* n ((gg) (sub1 n)))))))) ( (let ((gh)) (lambda (n) (if (zero? n) 1 (* n ((gg) (sub1 n)))))) 5)) 

Выражение (lambda (n) ...) здесь возвращается изнутри фрейма среды, в котором g указывает на h над ним - в качестве объекта замыкания . Т.е. функция одного аргумента n , которая также запоминает привязки для g , h и U

Поэтому, когда это замыкание вызывается, n получает 5 , и форма if вводится:

 (let ((U (lambda (x) (xx))) (h (lambda (g) (lambda (n) (if (zero? n) 1 (* n ((gg) (sub1 n)))))))) (let ((gh)) (let ((n 5)) (if (zero? n) 1 (* n ((gg) (sub1 n))))))) 

Приложение (gg) получает сокращение в (hh) приложение, потому что g указывает на h определенный в фрейме среды над средой, в которой был создан объект закрытия. То есть наверху, в верхней форме. Но мы уже видели сокращение вызова (hh) , которое создало замыкание, т. Е. Функцию одного аргумента n , служащую нашей factorial функцией, которая на следующей итерации будет вызываться с 4 , затем 3 и т. Д.

Будет ли использоваться новый объект закрытия или тот же объект закрытия, будет использоваться повторно, зависит от компилятора. Это может повлиять на производительность, но не на семантику рекурсии.

Мне нравится этот вопрос. «Язык программирования схемы» – хорошая книга. Моя идея из главы 2 этой книги.

Во-первых, мы это знаем:

 (letrec ((fact (lambda (n) (if (= n 1) 1 (* (fact (- n 1)) n))))) (fact 5)) 

С letrec мы можем выполнять функции рекурсивно. И мы видим, когда мы называем (fact 5) , fact уже связан с функцией. Если у нас есть другая функция, мы можем назвать ее таким образом (another fact 5) , а теперь another называется двоичной функцией (мой английский не хорош, извините). Мы можем определить another как это:

 (let ((another (lambda (fx) .... (fx) ...))) (another fact 5)) 

Почему бы нам так не определить этот fact ?

 (let ((fact (lambda (fn) (if (= n 1) 1 (* n (ff (- n 1))))))) (fact fact 5)) 

Если fact является бинарной функцией, то он может быть вызван функцией f и целым числом n , и в этом случае функция f оказывается fact .

Если вы получили все вышеперечисленное, вы можете написать комбинатор Y теперь, заменив let lambda .

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

Я сам прошел эти шаги для лучшего понимания.
https://gist.github.com/z5h/238891

Если вам не нравится то, что я написал, просто выполните некоторые действия для Y Combinator (функция).

Мне было любопытно писать рекурсивную функцию без использования define. Основная проблема, конечно, в том, что вы не можете вызвать функцию внутри себя, если у нее нет имени.

Немного не по теме, но, видя приведенные выше утверждения, я просто хотел сообщить вам, что «без использования define» не означает «не имеет имени». Можно дать что-то имя и использовать его рекурсивно в Схеме без определения.

 (letrec ((fact (lambda (n) (if (zero? n) 1 (* n (fact (sub1 n))))))) (fact 5)) 

Было бы более ясно, если ваш вопрос конкретно говорит «анонимная recursion».