ラムダ計算、コンビネータ論理、関数型プログラミングの本で説明されているように、階乗ラムダ式を実装しようとしています。
そこに記述されている方法は次のとおりです。
fact = (Y)λf.λn.(((is-zero)n)one)((multiply)n)(f)(predecessor)n
Y = λy.(λx.(y)(x)x)λx.(y)(x)x
どこ
(x)y is equivalent to (x y) and
(x)(y)z is equivalent to (x (y x)) and
λx.x is equivalent to (fn [x] x)
およびis-zero、、、およびはone、標準のチャーチ数に対して定義されています。ここでの実際の定義。multiplypredecessor
私はそれを次のように翻訳しました
(defn Y-mine [y] ; (defn Y-rosetta [y]
((fn [x] (y (x x))) ; ((fn [f] (f f))
(fn [x] ; (fn [f]
(y ; (y (fn [& args]
(x x))))) ; (apply (f f) args))))))
と
(def fac-mine ; (def fac-rosetta
(fn [f] ; (fn [f]
(fn [n] ; (fn [n]
(is-zero n ; (if (zero? n)
one ; 1
(multiply n (f (predecessor n))))))) ; (* n (f (dec n)))))))
コメントアウトされたバージョンは、Rosettaコードの同等のfac関数とY関数です。
質問1：
他の場所を読んで、Y-rosettaβ-がに還元されることを理解していY-mineます。その場合、なぜそれを他のものよりも使用することが好ましいのですか？
質問2：
使ってもY-rosetta。試してみるとStackOverflowErrorが発生します
((Y-rosetta fac-mine) two)
その間
((Y-rosetta fac-rosetta) 2)
正常に動作します。
無防備な再帰はどこで起こっていますか？
ifフォームがclojureでどのように機能するかと関係があるのではないかと思いますが、これは私のis-zero実装と完全には同等ではありません。しかし、私は自分でエラーを見つけることができませんでした。
ありがとう。
アップデート：
@amalloyの答えを考慮して、私はfac-mine怠惰な議論をするように少し変更しました。私はclojureにあまり詳しくないので、これはおそらく正しい方法ではありません。しかし、基本的に、私はis-zero匿名のゼロ引数関数を取り、それが返すものは何でも評価するようにしました。
(def lazy-one (fn [] one))
(defn lazy-next-term [n f]
(fn []
(multiply n (f (predecessor n)))))
(def fac-mine
(fn [f]
(fn [n]
((is-zero n
lazy-one
(lazy-next-term n f))))))
次のようなエラーが発生します。
=> ((Y-rosetta fac-mine) two)
ArityException Wrong number of args (1) passed to: core$lazy-next-term$fn clojure.lang.AFn.throwArity (AFn.java:437)
lazy-next-termそれが常にとと呼ばれてnいることを考えると、これは本当に奇妙に思えますf