Можно ли использовать call / cc для реализации рекурсии?

Question

Интересно, можно ли определить рекурсивную функцию, не вызывая саму функцию в ее теле, но каким-то образом используя call / cc вместо этого? Спасибо.

Answer 1

Вы можете реализовать Y комбинатор, используя call/cc, , как описано здесь . (Большое спасибо Джону Коуэну за упоминание этого аккуратного поста!) Цитируя этот пост, вот реализация Олега:

Следствие 1. Y комбинатор через call/cc - Y комбинатор без явного самостоятельного применения.

(define (Y f)
  ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n)))))
   (call/cc (call/cc (lambda (x) x)))))

Здесь мы использовали тот факт, что

((lambda (u) (u p)) (call/cc call/cc))

и

((lambda (u) (u p)) (lambda (x) (x x)))

обсервационно эквивалентны.

Answer 2

Ваш вопрос немного расплывчатый. В частности, это звучит так, будто вам нужна система, которая моделирует рекурсивные вызовы без непосредственного выполнения рекурсивных вызовов, используя call / cc. Однако оказывается, что вы можете моделировать рекурсивные вызовы без выполнения рекурсивных вызовов, а также без использования call / cc. Например:

#lang racket

(define (factorial f n)
  (if (= n 0) 1 (* n (f f (- n 1)))))

(factorial factorial 3)

Это может показаться обманом, но это основа Y комбинатора. Возможно, вы можете ужесточить набор ограничений, о которых вы думаете?

P.S .: если это домашнее задание, пожалуйста, процитируйте меня!

Answer 3

Боюсь, call/cc на самом деле не имеет к этому никакого отношения.На самом деле существует только два способа определения рекурсивной функции:

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

Итак, для factorial вы пишете это так:

(define (factorial-step recurse n)
  (if (zero? n)
      1
      (* n (recurse (- n 1)))))

Магия комбинатора Y заключается вчто она создает функцию recurse, которая будет передана в factorial-step.