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

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

Вы определяете его следующим образом:

(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) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
  ((U h) 5))

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

Мне нравится этот вопрос. "Язык программирования схемы" - хорошая книга. Моя идея из главы 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 (f x) .... (f x) ...))) (another fact 5))

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

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

Если fact - двоичная функция, то ее можно вызвать с помощью функции f и целого n, и в этом случае функция f оказывается самой fact.

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

Ответ 7

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

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

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

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

Ответ 8

Я нашел этот вопрос, потому что мне нужна была рекурсивная вспомогательная функция внутри макроса, где нельзя использовать define.

Кто-то хочет понять (lambda (x) (xx)) и Y-комбинатор, но по имени let выполняет работу, не отпугивая туристов:

 ((lambda (n)
   (let sub ((i n) (z 1))
     (if (zero? i)
         z
         (sub (- i 1) (* z i)) )))
 5 )

Можно также отложить понимание (lambda (x) (xx)) и Y-комбинатор, если такого кода достаточно. Схема, подобно Хаскелу и Млечному Пути, таит в центре массивную черную дыру. Многие бывшие продуктивные программисты очарованы математической красотой этих черных дыр, и их больше никогда не увидишь.