Zコンビネータの符号別値を用いた終了

Question

私は自分のλ-計算通訳を作りようとしています。これまでのところ、それは、値と正常な順序の両方をサポートします。

私は今固定ポイントを介して再帰を試してみましょう。 $ Y $ コンビネータは、教員関数 $$ \ text {fac}=lambda fでテストされた通常の順序で動作します。 。\ Lambda n。\ text {iszero} \、n \、1（\ text {mul} \、n \、（f（\ text {pred}、n）））\ text {、} $$ たとえば、私のインタプリタは $ y \、\ text {fac} \、3 \ stackrel {\ text {no}} 6 $ です。 （私は10進数として行動的に同等の教会数字を書く）

呼入副value="x" $ z $ コンビネータを必要とする限り、代わりに

$$ z=lambda f。 （\ LAMBDA X.F（\ LAMBDA x x x x x。f（\ Lambda x。f（\ Lambda x.f.）\ text {、} $$

$ Y $ として、即時の無限回帰を引き起こします。

問題は、 $ z \、\ text {fac} \、0 $ をどれほど理解しません。それはまた私のインタプリタで終わらないが、私はそれを手動で理解したいのです。

いくつかの手順の後、値は以下のとおりに到着する必要があります。 $$ z \、\ text {fac} \、0 \\=lambda f。 （\ LAMBDA X.F（\ Lambda x x x x x。f（\ Lambda x。f（\ Lambda x x x y））\、{fac} \、0 \\\ stackrel {\ text {cbv}} {\ resplary}（\ Lambda x. \ text {fac}（\ Lambda}）（\ Lambda x. \ text {fac}（\ Lambda}） ）\、0 \\\ stackrel {\ text {cbv}}} {\ ritarrow} \ text {fac}（\ Lambda}（\ Lambda y。（\ Lambda}（\ Lambda x））（\ Lambda x） 。\ text {fac}（\ Lambda y。xx y '））y）\、0 \\\ stackrel {\ text {cbv}} {\ rightarrow} \ text {fac} \、f \、0 \ stackrel {\ text {cbv}} {\ resplary} \ text {iszero} \、0 \、1 \、a \ text {、} $$ < / SPAN>

ここで省略された用語

$$ A=text {mul} \、0 \、（f \、（\ text {pred} \,,0））$$ / P>

$$ f=lambda y。（\ Lambda x. \ text {fac}（\ Lambda y '\ text）））（\ text {fac }（\ Lambday'.xxy '））\、y $$ 。

今、 $ \ text {iszero} \、0 \ stackrel {\ text {cbv}} \ Lambda T. \ Lambda FT $ st

$$ \ text {iszero} \、0 \、1 \、a \ stackrel {\ text {cbv}} {\ lightarrow}（\ Lambda T. \ Lambda FT ）\、1 \、\ stackrel {\ text {cbv}} {\ lightarrow}（\ Lambda f.1）\、\ text {。} $$

私たちの言語が $ a $ ブランチを無視する分岐構造を持っていた場合、私たちは私たちが行われますが、値を評価する必要があります< span class="math-container"> $ A $ 値、つまり抽象化。

$ A=text {mul} \、0 \、（f \、（\ text {pred} \、0））$ と $ \ text {mul} \、0 $ は、次に $ f \、（\ text {preg）を減らさなければなりません。 \、0）$ 。

$ \ text {pread} \、0 \ stackrel {\ text {cbv}} {\ ritarrow} 0 $ 、 $ f \、0 $ 。

$$ f \、0=（\ Lambda y。（\ Lambda x。}（\ Lambda y '}）（\ Lambda x）。 \ text {fac}（\ Lambday'.xxy '））\、y）\、0 \ stackrel {\ text {cbv}} {\ lambda x. \ text {fac}（\ Lambday'） .xxy '））（\ Lambda x。\ text {fac}（\ Lambday'.xxy'））\、0 \ stackrel {\ text {cbv}} {\ ritarrow} \ text {fac} \、f \ 、0 $$

そして今、私たちは正方形のものに戻ってきました。私は間違ったことをしていますか？

Answer 1

私はあなたが間違って縮小しているとは思わないが、問題はzコンビネータではありません。問題は $ \ text {iszero} $ です。all-by-valueでの分岐構造は、テストにかかわらず、両方のブランチが評価されるため、呼び出しごと（または類似の）の引数として各ブランチの直接的な用語を取得できません。これは再帰とは明らかに不十分に相互作用しますが、一般的には望ましくありません。

代わりに、call-by-value内の分岐構造は、明示的に遅延引数を取ります。そのため： $$ \ text {iszero} \n\（λ\ _.1）（λ\ _。\ text {mul} \n\（f \ text{PRED} \ n））$$ このように再帰的評価は、実際に必要な場合を除き、再帰的評価を回避することができます。もちろん、 $ \ text {iszero}のままにすることができます。$ のように、常にこの方法でそれを使用し、あなた自身の余分な引数を提供しますが、通常は遅延引数を期待するように定義されます。