K.Maebashi's BBS

はじめまして、「プログラミング言語を作る」楽しく読ませていただいています。 crowbarには再帰呼び出しのための名前付きのクロージャがありますが、名前のないクロージャでも、不動点演算子を使えば再帰呼び出しは可能です。 # 不動点演算子(2引数関数用) function fp_op2(f) { return closure(p) { return p(p); }(closure(x) { return closure(g, h) { return f(x(x))(g, h); }; }); } # 使用例。コードは(ぱ)さんの本にあったクイックソートをそのまま使わせていただきました function quick_sort(data, less) { fp_op2(closure(quick_sort_sub) { return closure(left, right) { pivot = data[(left + right) / 2]; left_index = left; right_index = right; while (left_index <= right_index) { for (; less(data[left_index], pivot); left_index++) {} for (; less(pivot, data[right_index]); right_index--) {} if (left_index <= right_index) { temp = data[left_index]; data[left_index] = data[right_index]; data[right_index] = temp; left_index++; right_index--; } } if (left_index < right) { quick_sort_sub(left_index, right); } if (left < right_index) { quick_sort_sub(left, right_index); } }; })(0, data.size() - 1); return data; } print("" + quick_sort({ 5,6,3,2,1,9,8,0,7,5,3,2,4,3 }, closure(lhs, rhs) { return lhs < rhs; }) + "\n"); # => (0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9) 名前付きクロージャを使った方が簡単でわかりやすいですが(ついでに効率もいいです)、こういうのもありますよ、ということで投稿しました。 ＃ 既にご存じでしたら申し訳ありません

>はじめまして、「プログラミング言語を作る」楽しく読ませていただいています。 どうも。はじめまして。最近停滞しておりましてすみません。 >crowbarには再帰呼び出しのための名前付きのクロージャがありますが、 >名前のないクロージャでも、不動点演算子を使えば再帰呼び出しは可能です。 知らなかったので、「不動点演算子」をGoogleしてみました。 …頭から煙が出そうになったので、サンプルのソースを読もうとしてみました。 …すみません、今の眠い頭ではちょっと追えそうにないので、後日再挑戦してみます。 興味深いネタの提供ありがとうございました。 # 勉強不足を痛感いたしますです。

> …頭から煙が出そうになったので、サンプルのソースを読もうとしてみました。 サンプルをそのまま追うと多分死にます。 簡略化してから追うと fp_op2(closure(f) { return closure(x, y) { ... f(a, b) ... }; }) ⇒ Z Z(c, d) ⇒ closure(f) { return closure(x, y) { ... f(a, b) ... }; }(Z)(c, d) ⇒ closure(x, y) { ... Z(a, b) ... }(c, d) こんな感じです。 参考ページ http://lecture.ecc.u-tokyo.ac.jp/~kawai/pub/is/isis2-note.html http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/fix.html ＃ 「不動点演算子」じゃなかなか見付からないですね。orz ＃ どうやって見付けたんだろう。 == 私も(crowbarを基に)プログラミング言語を作ろうと思っていますが、 そのときは名前付きのクロージャは入れないで、 Schemeの拡張シンタックスのような機能を付けようと思っています。 んで、 named_closure tag (x, y, ...) { ... } と書けば closure(tag) { tag = closure(x, y, ...) { ... }; return tag; }(null) と展開されるようなものをプログラマが自分で作れるようにしたいな、と(不動点演算子はどこへ行った) ＃ で、ライブラリに入れておく

ええと、まず目的として、クイックソートなんだから当然再帰を使いたい、 ってのがあって、つまりいかにしてquick_sort_sub()を呼び出すかが 問題なわけですが、 以下の箇所で定義されているふたつのクロージャを、それぞれ c1, c2とすると、 fp_op2(closure(quick_sort_sub) { ←c1 return closure(left, right) { ←c2 c2が、通常のクイックソートの実行部ですが、その中では、 その外周のクロージャであるc1の引数である、quick_sort_sub()が 参照できるわけですね。 c1は、引数としてクロージャを受け取り、戻り値としてc2を返すわけですが、 c1の引数にc2を渡して実行できれば万事解決である、と。 で、これを実現しているのがfp_op2()であるわけですが、 これは以下のように書き換えることが可能で、 function fp_op2(f) { c3 = closure(p) { return p(p); }; c4 = closure(x) { c5 = closure(g, h) { return f(x(x))(g, h); }; return c5; }; return c3(c4); } 最後のreturnでc3が実行されていますが、 c3というのは、クロージャを受け取り、そのクロージャにそれ自身を 渡して実行して返す関数なわけで、で、c3のpに実際に渡されているのは c4なので、つまりこのタイミングでc4が実行される。 c4は引数としてxを受け取りますが、c3の定義からして、 xにはc4自身が格納されている。 そして、c4は、戻り値としてc5を返す。 この戻り値は、c3の戻り値でありすなわちfp_op2()の戻り値でもある。 呼び出し元のquick_sort()関数のほうでは、fp_op2()の戻り値に 引数ふたつ与えて評価して、それがクイックソートの実行となる。 で、そのc5ですが、「f(x(x))」のfはつまりc1であり、 その引数の「x(x)」におけるxはc4なので、fの引数には c4の戻り値が渡されることになる。 c4の戻り値であるc5はつまり、引数をふたつとってc1の戻り値 すなわちc2を実行して返す、という、c2のラッパーなので、 当初の目的である 「c1の引数にc2を渡して実行できれば万事解決である」 というのが実現できている… うーん、ぶすぶす… (頭から煙が出ている音) Paul Grahamの「簡潔さは力なり」の中で、 http://www.shiro.dreamhost.com/scheme/trans/power-j.html 数式を散文で書くと量が増える、なんてことが書いてありますが、 数式の力を持ち合わせていない私が書くとこうなってしまうわけで、 やっぱり勉強不足ですね。