В Схеме, как вы используете лямбда для создания рекурсивной функции?
Я в классе Scheme, и мне было интересно написать рекурсивную функцию без использования define. Основная проблема, конечно, в том, что вы не можете вызывать функцию внутри себя, если у нее нет имени.
Я нашел этот пример: это факторный генератор, использующий только лямбду.
((lambda (x) (x x))
(lambda (fact-gen)
(lambda (n)
(if (zero? n)
1
(* n ((fact-gen fact-gen) (sub1 n)))))))
Но я даже не могу понять смысл первого вызова (лямбда (х) (хх)): что именно это делает? И где вы вводите значение, которое вы хотите получить факториал?
Это не для класса, это просто из любопытства.
9 ответов
(lambda (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)), дает х ссылку на себя, так что теперь х может ссылаться на себя и, следовательно, рекурсивно.
Выражение (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)))
В вашем примере есть несколько слоев, стоит пройтись по шагам и внимательно изучить, что делает каждый.
По сути, у вас есть форма, похожая на Y комбинатор. Если вы реорганизовали специфичный для факториала код, чтобы можно было реализовать любую рекурсивную функцию, тогда оставшийся код будет Y-комбинатором.
Я сам прошел через эти шаги для лучшего понимания.
https://gist.github.com/z5h/238891
Если вам не нравится то, что я написал, просто поищите в Google Combinator (функция).
Вы определяете это так:
(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 и т.п.
Будет ли это новый объект замыкания или тот же самый объект замыкания будет использоваться повторно, зависит от компилятора. Это может повлиять на производительность, но не на семантику рекурсии.
(lambda (x) (x x)) принимает объект функции, затем вызывает этот объект, используя один аргумент, сам объект функции.
Затем вызывается с другой функцией, которая принимает этот объект функции под именем параметра fact-gen, Он возвращает лямбду, которая принимает фактический аргумент, n, Вот как ((fact-gen fact-gen) (sub1 n)) работает.
Вы должны прочитать пример главы (Глава 9) из The Little Schemer, если можете следовать ей. В нем обсуждается, как создавать функции этого типа и, в конечном итоге, извлекать этот шаблон в Y-комбинатор (который можно использовать для обеспечения рекурсии в целом).
Мне нравится этот вопрос. "Язык программирования схем" - хорошая книга. Моя идея из второй главы этой книги.
Во-первых, мы знаем это:
(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,
С одной лямбдой это невозможно. Но возможно использование двух или более лямбда-выражений. Поскольку все остальные решения используют три лямбда-выражения или let/letrec, я объясню метод, используя два лямбда-выражения:
((lambda (f x)
(f f x))
(lambda (self n)
(if (= n 0)
1
(* n (self self (- n 1)))))
5)
А на выходе 120.
Здесь,
-
(lambda (f x) (f f x))создает лямбду, которая принимает два аргумента, первый из которых является лямбдой (назовем его), а второй — параметром (назовем его). Обратите внимание, в своем теле он вызывает предоставленную лямбду с помощью иx. - Теперь лямбда
f(из пункта 1) т.е. это то, что мы хотим рекурсивно. Видите, при рекурсивном вызове мы также передаемselfв качестве первого аргумента и(- n 1)в качестве второго аргумента.
Мне было любопытно написать рекурсивную функцию без использования define. Основная проблема, конечно, в том, что вы не можете вызывать функцию внутри себя, если у нее нет имени.
Немного не по теме, но, увидев вышеприведенные утверждения, я просто хотел сообщить, что "без использования определения" не означает "не имеет имени". Можно дать что-то имя и использовать его в Scheme без определения.
(letrec
((fact
(lambda (n)
(if (zero? n)
1
(* n (fact (sub1 n)))))))
(fact 5))
Было бы более понятно, если бы в вашем вопросе было указано "анонимная рекурсия".
Я нашел этот вопрос, потому что мне нужна была рекурсивная вспомогательная функция внутри макроса, где нельзя использовать определение.
Хочется понять (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-комбинатор, если такого кода достаточно. Схема, подобно Хаскеллу и Млечному Пути, таит в центре массивную черную дыру. Многие бывшие продуктивные программисты очарованы математической красотой этих черных дыр, и их больше никогда не увидишь.