9
  • 固定小数点コンビネータは、再帰を導入するための非常に便利なツールです。
  • Continuation-Passing スタイルは、関数が決して返らないラムダ計算のスタイルです。代わりに、プログラムの残りの部分をラムダ引数として関数に渡し、それらを続行します。これにより、実行フローをより適切に制御し、さまざまなフロー変更構造 (ループ、コルーチンなど) をより簡単に定義できます。

しかし、ひとつひとつを表現できるかどうかは疑問です。私が見たすべての CPS スタイルの言語には、FIX再帰を定義するための明示的な構造があります。

  • なしでは、プレーンな CPS で固定小数点コンビネータ (または類似のもの) を定義できないためFIXですか? もしそうなら、あなたはそのようなことの証拠を知っていますか?
  • それともタイピングの問題だけですか？
  • それとも可能かもしれませんが、何らかの理由で非現実的ですか？
  • それとも、そこにある解決策が見つからなかっただけですか...？

Y コンビネータのような CPS 関数が次のように機能することを期待しCPSYます。Y 対応の CPS 関数を定義すると、次のようになります。

function Yready(this, return) = 
    return (lambda <args> . <body using 'this' as recursion>);

次に、それを入れて、CPSYそれ自体に再帰する関数を生成します。

function CPSY(F, return) = ?????

CPSY(Yready,
    lambda rec . <body where 'rec' names 'lambda <args>' from above, but with the loop closed>
)

はCPSY、再帰に依存しない単純な継続渡しスタイルの関数である必要があります。Y コンビネータは、組み込みの再帰を使用せずに、単純なラムダ計算でこのような方法で定義できます。なんらかの形で CPS にも存在できますか?

明確にするために繰り返します：私はコンビネータのような関数CPSYを探しています：

  • CPS 関数の再帰を有効にします
  • it の定義は再帰に依存しません
  • it の定義は、継続渡しスタイルで与えられます (の本体内のどこにもラムダを返しませんCPSY) 。
4

4 に答える 4

3

TL;DR : 同じ適用順序Yは、継続カリー化スタイルで記述された CPS 関数に対して機能します。

組み合わせスタイルでは、 Yを使用した階乗の通常の定義は、もちろん、

_Y (\r -> \n -> { n==0 -> 1 ; n * r (n-1) })     , where
                               ___^______
_Y = \g -> (\x-> x x) (\x-> g (\n-> x x n))  -- for applicative and normal order

CPS 階乗定義は

fact = \n k -> equals n 0         -- a conditional must expect two contingencies
                 (\True -> k 1) 
                 (\False -> decr n 
                                 (\n1-> fact n1          -- *** recursive reference
                                             (\f1-> mult n f1 k)))

CPS -Yは、追加の偶発性引数のために拡張されます (真の継続から明確にするために「偶発性」と言っています)。スキームでは、

(define (mult a b k)     (k (* a b)))
(define (decr c   k)     (k (- c 1)))
(define (equals d e s f) (if (= d e) (s 1) (f 0)))

(((lambda (g) 
     ( (lambda (x) (x x))
       (lambda (x) (g (lambda (n k) ((x x) n k))))))

  (lambda (fact)
    (lambda (n k)
      (equals n 0 (lambda (_) (k 1))
                  (lambda (_) (decr n 
                                (lambda (n1) (fact n1
                                               (lambda (f1) (mult n f1 k))))))))))

  5 (lambda (x) (display x)) )

これは 120 を返します。

もちろん、自動カリー化遅延言語 (ただし型なし!) では、上記の CPS-Y は eta 短縮により、通常の Y 自体とまったく同じです。

しかし、再帰関数に 2 つの実際のパラメーターと継続 ⁄ 偶発性 (3 つ目) がある場合はどうなるでしょうか? では、Scheme のような言語では、(lambda (n1 n2 k) ((x x) n1 n2 k))内側に別の Y が必要でしょうか?

常に contingency 引数firstを持つように切り替え、常にカリー化された方法でコーディングできます (各関数には正確に 1 つの引数があり、おそらく別のそのような関数を生成するか、すべてが適用された後に最終結果が生成されます)。そして、それも機能します：

(define (mult   k)   (lambda (x y) (k (* x y))))
(define (decr   k)   (lambda (x)   (k (- x 1))))
(define (equals s f) (lambda (x y) (if (= x y) (s) (f))))

((((lambda (g)                                ; THE regular,
     ( (lambda (x) (x x))                        ; applicative-order
       (lambda (x) (g (lambda (k) ((x x) k))))))   ; Y-combinator

   (lambda (fact)
    (lambda (k)
      (lambda (n)
        ((equals  (lambda () (k 1))
                  (lambda () ((decr (lambda (n1) 
                                        ((fact 
                                            (lambda (f1) ((mult k) n f1)))
                                         n1)))
                               n)))
          n 0)))))

   (lambda (x) (display x))) 
  5)

あなたの言語が入力されている場合、そのようなものを入力する方法もあります。または、型付けされていない言語では、おそらくすべての引数をリストにパックできます。

于 2016-03-11T01:14:57.430 に答える
1

これは「自明な解決策」であり、OP が望んでいた非再帰的な解決策ではありません。比較のために残しておきます。

再帰バインディングを提供する言語がある場合は、fixCPS 関数を定義できます (ここでは Haskell を使用):

Prelude> let fixC f = \c -> f (fixC f c) c
Prelude> :t fixC
fixC :: (t -> t1 -> t) -> t1 -> t
Prelude> let facC' = \rec c n -> if n == 0 then c 1 else c (n * rec (n-1))
Prelude> let facC = fixC facC'
Prelude> take 10 $ map (facC id) [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]

ただし、プリミティブとして提供することfixCはパフォーマンスに影響を与える可能性があります (単にクロージャーとしてではなく継続を表す場合)、または「従来の」ラムダ計算には再帰的に使用できる関数の名前がないためです。

(おそらく、 に類似したより効率的なバリアントもありますfix f = let x = f x in x。)

于 2016-03-10T19:11:01.317 に答える