Можно ли использовать 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 комбинатора. Возможно, вы можете ужесточить набор ограничений, о которых вы думаете?

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

Answer 3

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

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

Таким образом, для factorial, вы пишете это так:

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

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