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

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

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

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

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

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

(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».

  • Функциональное программирование: что такое «неправильный список»?
  • Сгладить список, используя только формы в «The Little Schemer»
  • В чем разница между eq ?, eqv ?, equal ?, и = в схеме?
  • Как показать схему таблицы в базе данных MySQL?
  • Рекурсивный диапазон в Lisp добавляет период?
  • В чем разница между цитатой и списком?
  • Как сгенерировать диаграммы UML (особенно диаграммы последовательности) из кода Java?
  • Как разработать таблицу продуктов для многих видов продуктов, где каждый продукт имеет множество параметров
  • Почему foldl определенно задан в Racket?
  • Какова наилучшая схема базы данных для поддержки значений, которые подходят только для определенных строк?
  • conda, condi, conde, condu
  • Interesting Posts

    Excel 2013 – объединение условного форматирования

    Контролировать учетные записи пользователей linux ubuntu

    Помогите с пониманием функционального объекта или функтора в Java

    Лучший язык для анализа чрезвычайно больших файлов Excel 2007

    Таймауты с длительным запуском ASP.NET MVC Core Controller Метод HTTPPost

    Штрих-код на скорости 4

    Как ядра в модуле AMD Bulldozer сравниваются с виртуальными ядрами Intel HTT и двумя отдельными ядрами с точки зрения производительности многозадачности?

    Есть ли у java какой-либо механизм для виртуальной машины для отслеживания вызовов методов на себе, без использования javaagent и т. Д.?

    WinXP – размещение пользовательских каталогов на вторичном разделе?

    как изменить имя процесса приложения Java?

    C #: Как получить полный путь выполнения процесса?

    Как программно заблокировать / разблокировать экран?

    Как бинарные файлы POST с помощью AngularJS (с загрузкой DEMO)

    Как я перемещаю элементы в списке и удаляю их?

    Windows XP INSTALL BSOD

    Давайте будем гением компьютера.