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

Question

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

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

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

Но я даже не могу понять смысл первого вызова (лямбда (x) (xx)): Что именно это делает?И где вы вводите значение, которое вы хотите получить факториал?

Это не для класса, это просто из любопытства.

Answer 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)), дает x ссылку на себя, так что теперь x может ссылаться на себя и, следовательно, возвращаться.

Answer 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)))

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

Answer 3

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

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

, вот как на самом деле работает letrec.См. LiSP , Кристиан Квиннек.

---

В примере, о котором вы спрашиваете, комбинатор самоприменения называется " U комбинатор" ,

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

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

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

Теперь приложение от h до 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 и т. Д.

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

Answer 4

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

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

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

Answer 5

Мне нравится этот вопрос.«Язык программирования схем» - хорошая книга.Моя идея взята из главы 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.

Answer 6

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

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

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