On Lisp「22章 非決定性」をRubyで試してみる:TKMR.blog.show
"On Lisp―Advanced Techniques for Common Lisp" (Paul Graham) を読んだ。 ・Lispの基礎から、マクロ、遅延評価、Schemeと継続、継続をCommonLispで実装して、継続を使った非決定的アルゴリズムの実装、Prolog 初めて関数型プログラミング、というかLispを勉強した身にとっては全編興味深い、特に22章の「非決定性」が面白かった。 On Lisp - 非決定性 非決定的アルゴリズムはある意味では超自然的な予見に基づいて動作するものだ．超能力を持ったコンピュータに触れることのない私達に，どうしてそんなものが必要なのだろうか？\ それは非決定的アルゴリズムを決定的アルゴリズムでシミュレートできるからだ．純粋に関数的なプログラム ---すなわち副作用の一切ないもの--- では，非決定性は特に直截的になる．純粋に関数的なプログラ
独習 Scheme 三週間 Teach Yourself Scheme in Fixnum Days
非決定性 McCarthy の非決定性オペレータ amb [cite{jmc:amb}, cite{wc:amb}, cite{zmc:amb}] は Lisp 自身と同じくらい古いものですが、Lisp にはありません。amb は ０個あるいはそれ以上の式を引数としてとり、それらの、非決定的な (あるいは「あいまいな」)な選択を作ります。プログラムを意味のあるものに 収束させるこれらの選択を好んでつかいます。ここで、 曖昧選択の深さ優先選択をつかい、他の選択肢を探索するための バックトラックに Scheme の制御オペレータ call/cc を使う amb の Scheme への埋め込みについて検討しましょう。 結果は、拡張言語にたよることなく、Scheme で直接書けるような 探索問題の分野で使用できるエレガントなバックトラッキング戦略が できあがります。この埋め込みは Prolog 流
Scheme 入門 18. 非決定性
1. 初めに 非決定性は問題を記述するだけで答えが得られるようにするアルゴリズムです。 プログラムは選択肢の中から条件に合うものを自動的に選び出します。 この手法を使うと論理プログラムを容易に書くことができます。 例えば、 > (let ((i (amb 4 6 7)) (j (amb 5 8 11))) (if (prime? (+ i j)) (list i j) (amb))) (6 5) のようにすると '(4 6 7) と '(5 8 11) のうちから二つの数の和が素数になる組の１つを返します。 (amb 4 6 7) は、式が値を返すように 4, 6, 7 の中から適切に値を選び、同様に、 (amb 5 8 11) は、式が値を返すように 5, 8, 11 の中から適切に値を選びます。 (amb) は選ぶべき値が無いので失敗を表します。 実際は、amb は深さ優先の探索をして
On Lisp --- 非決定性
プログラミング言語を使うことで，膨大な量の詳細に飲み込まれないで済んでいる． Lispがよいプログラミング言語なのは，それ自身が多くの詳細を扱ってくれて， プログラマが耐えられる複雑さの限界を有効に使わせてくれている． この章ではマクロでLispにさらに別の種類の詳細を扱わせる方法を示す． 非決定的なアルゴリズムを決定的なものに変換することの詳細だ． この章は5つの部分に分けられる． まず，非決定性とは何かを説明する． 次に，非決定的なchooseとfailを継続を使ってSchemeで実装する． 3番目では，第20章の継続渡しマクロを基礎にCommon Lispで実装したchooseとfailを示す． 4番目では，オペレータcutをPrologとは独立に理解する方法を示す． 最後に，非決定的オペレータの改良について考察する． この章で定義される非決定的な選択オペレータは， 第23章のATN
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
