9

関数自体を本体で呼び出さずに再帰関数を定義することは可能でしょうか。代わりに、どういうわけかcall / ccを使用しますか？ありがとう。

4

3 に答える 3

14

こちら で説明されているようcall/ccに、を使用して Y コンビネータを実装できます。(このきちんとした投稿に言及してくれた John Cowan に感謝します!) その投稿を引用すると、Oleg の実装は次のようになります。

系 1. Y コンビネータ via 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)))

観測的に同等です。

于 2012-03-30T03:23:14.930 に答える
6

あなたの質問は少し曖昧です。特に、call / ccを使用して、再帰呼び出しを直接行わずに再帰呼び出しをモデル化するシステムが必要なようです。ただし、再帰呼び出しを行わずに、またcall / ccを使用せずに、再帰呼び出しをモデル化できることがわかりました。例えば：

#lang racket

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

(factorial factorial 3)

それは浮気のように見えるかもしれませんが、それはYコンビネータの基盤です。おそらく、あなたはあなたが考えている一連の制限を厳しくすることができますか？

PS：これが宿題なら、私を引用してください！

于 2012-03-29T16:04:06.117 に答える
2

これとcall/ccはあまり関係がないのではないかと思います。再帰関数を定義するには、実際には 2 つの方法しかありません。

  • あなたの言語が再帰関数の定義を許可しているとします。つまり、関数本体は囲んでいる関数を参照できます。または、関数本体は、本体が を参照する関数をf参照できます。この場合は、まあ、通常の方法で書くだけです。gf
  • 言語でこれらの両方が禁止されていても、それでもファーストクラスの関数とラムダがある場合は、Y コンビネーターのような固定小数点コンビネーターを使用できます。再帰的なステップを表すことを意図した関数を追加の引数として受け取るように関数を記述します。再帰するすべての場所で、代わりにその引数を呼び出します。

の場合はfactorial、次のように記述します。

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

Y コンビネータの魔法は、recurseに供給される関数を構築することfactorial-stepです。

于 2012-03-29T21:49:52.833 に答える