私は Scheme クラスにいて、define を使わずに再帰関数を書くことに興味がありました。もちろん、主な問題は、関数に名前がない場合、その関数を呼び出すことができないことです。
私はこの例を見つけました:これは、ラムダのみを使用する階乗ジェネレーターです。
((lambda (x) (x x))
(lambda (fact-gen)
(lambda (n)
(if (zero? n)
1
(* n ((fact-gen fact-gen) (sub1 n)))))))
しかし、最初の呼び出し (lambda (x) (xx)) の意味さえ理解できません。そして、階乗を取得したい値をどこに入力しますか?
これは授業用ではありません。ただの好奇心からです。
(lambda (x) (x x))は、それ自体で引数xを呼び出す関数です。
投稿したコードのブロック全体が、1 つの引数の関数になります。次のように呼び出すことができます。
(((lambda (x) (x x))
(lambda (fact-gen)
(lambda (n)
(if (zero? n)
1
(* n ((fact-gen fact-gen) (sub1 n)))))))
5)
これは 5 で呼び出し、120 を返します。
これを大まかに考える最も簡単な方法は、最初の関数がxに自分自身への参照を(lambda (x) (x x))与えているため、 xが自分自身を参照できるようになり、したがって再帰できるということです。
この式(lambda (x) (x x))は、1 つの引数 (関数である必要があります) で評価されると、それ自体を引数としてその関数を適用する関数を作成します。
指定された式は、1 つの数値引数を取り、その引数の階乗を返す関数に評価されます。それを試すには：
(let ((factorial ((lambda (x) (x x))
(lambda (fact-gen)
(lambda (n)
(if (zero? n)
1
(* n ((fact-gen fact-gen) (sub1 n)))))))))
(display (factorial 5)))
あなたの例にはいくつかのレイヤーがあります。ステップバイステップで作業し、それぞれが何をするかを注意深く調べることは価値があります。
基本的に、あなたが持っているのは Y コンビネータに似たフォームです。再帰関数を実装できるように階乗固有のコードをリファクタリングした場合、残りのコードは Y コンビネーターになります。
理解を深めるために、これらの手順を自分で実行しました。
https://gist.github.com/z5h/238891
私が書いたものが気に入らない場合は、Y Combinator (関数) についてググってみてください。
次のように定義します。
(let ((fact #f))
(set! fact
(lambda (n) (if (< n 2) 1
(* n (fact (- n 1))))))
(fact 5))
これがletrec実際に機能する方法です。Christian Queinnec によるLiSPを参照してください。
あなたが尋ねている例では、自己適用コンビネーターは「Uコンビネーター」と呼ばれ、
(let ((U (lambda (x) (x x)))
(h (lambda (g)
(lambda (n)
(if (zero? n)
1
(* n ((g g) (sub1 n))))))))
((U h) 5))
ここでの微妙な点は、letのスコープ規則により、ラムダ式は定義されている名前を参照できないことです。
が呼び出されると、フォームによって作成された環境フレーム内のアプリケーションに((U h) 5)縮小されます。((h h) 5)let
htoのアプリケーションは、その上の環境で を指すh新しい環境フレームを作成します。gh
(let ((U (lambda (x) (x x)))
(h (lambda (g)
(lambda (n)
(if (zero? n)
1
(* n ((g g) (sub1 n))))))))
( (let ((g h))
(lambda (n)
(if (zero? n)
1
(* n ((g g) (sub1 n))))))
5))
ここでの式は、その上を指す(lambda (n) ...)環境フレーム内から、クロージャーオブジェクトとして返されます。つまり、 、、およびのバインディングも記憶する1 つの引数の関数。ghnghU
したがって、このクロージャーが呼び出されると、nが割り当てられ5、ifフォームが入力されます。
(let ((U (lambda (x) (x x)))
(h (lambda (g)
(lambda (n)
(if (zero? n)
1
(* n ((g g) (sub1 n))))))))
(let ((g h))
(let ((n 5))
(if (zero? n)
1
(* n ((g g) (sub1 n)))))))
クロージャオブジェクトが作成された環境の上の環境フレームで定義されたを指すため、アプリケーション(g g)はアプリケーションに縮小されます。つまり、そこまで、最高の形で。しかし、呼び出しの削減についてはすでに見てきました。これにより、クロージャ、つまり 1 つの引数の関数が作成され、関数として機能し、次の反復でなどで呼び出されます。(h h)ghlet(h h)nfactorial43
新しいクロージャ オブジェクトになるか、同じクロージャ オブジェクトを再利用するかは、コンパイラに依存します。これはパフォーマンスに影響を与える可能性がありますが、再帰のセマンティクスには影響しません。
(lambda (x) (x x))関数オブジェクトを受け取り、1 つの引数 (関数オブジェクト自体) を使用してそのオブジェクトを呼び出します。
これは、別の関数で呼び出され、その関数オブジェクトをパラメーター name の下で受け取りますfact-gen。実際の引数を取るラムダを返しますn. これが仕組み((fact-gen fact-gen) (sub1 n))です。
理解できる場合は、 The Little Schemerのサンプルの章 (Chapter 9) を読む必要があります。このタイプの関数を構築する方法と、最終的にこのパターンをY コンビネーター (一般に再帰を提供するために使用できる) に抽出する方法について説明します。
私はこの質問が好きです。「スキームプログラミング言語」は良書です。私のアイデアは、その本の第 2 章からのものです。
まず、次のことがわかっています。
(letrec ((fact (lambda (n) (if (= n 1) 1 (* (fact (- n 1)) n))))) (fact 5))
を使用letrecすると、関数を再帰的に作成できます。そして、 を呼び出すと(fact 5)、 factがすでに関数にバインドされていることがわかります。別の関数がある場合は、このように呼び出すことができ(another fact 5)、現在は二項another関数と呼ばれています (私の英語は苦手です。申し訳ありません)。次のように定義できます。another
(let ((another (lambda (f x) .... (f x) ...))) (another fact 5))
なぜfactこのように定義しないのでしょうか?
(let ((fact (lambda (f n) (if (= n 1) 1 (* n (f f (- n 1))))))) (fact fact 5))
factが2 項関数の場合、関数fと整数nを指定して呼び出すことができます。この場合、関数fはたまたまfactそれ自体になります。
上記のすべてを取得した場合、Yletコンビネーターを記述して、 with を置き換えlambdaます。
define を使わずに再帰関数を書くことに興味がありました。もちろん、主な問題は、関数に名前がない場合、その関数を呼び出すことができないことです。
少し話が逸れますが、上記のステートメントを見て、「define を使用しない」ということは「名前がない」という意味ではないことをお伝えしたかっただけです。何かに名前を付けて、定義せずにSchemeで再帰的に使用することができます。
(letrec
((fact
(lambda (n)
(if (zero? n)
1
(* n (fact (sub1 n)))))))
(fact 5))
あなたの質問が「匿名の再帰」と具体的に言っていると、より明確になります。