[解決済み] 論理プログラミングに関して、PrologとminiKanrenの主な技術的な違いは何でしょうか？[クローズド］。

質問

ロジックプログラミングについて調べたいとき、私はいつも2つの主な方法につまずきます。

• ミニカンレン で紹介したミニ言語 推論型スキーマ で紹介され、現在では コア・ロジック .
• プロログ 最初の大きな論理プログラミング言語です。

今興味があるのは 両者の主な技術的な違いは何でしょうか。アプローチや実装が非常に似ているのか、それとも論理プログラミングに対して全く異なるアプローチを取っているのか。また、その理論的基礎はどのようなものなのでしょうか。

どのように解決するのですか？

まず最初に、あなたの素晴らしい pw0n1e アイコンを褒め称えましょう。

miniKanrenとPrologは本当に言語の家族であり、その特徴や、実際にどのように使われるかを比較するのは困難です。 もし、私がPrologは深さ優先探索を使うと言ったら、多くのProlog実装は他の探索戦略をサポートし、他の探索戦略もメタインタプリタのレベルでコード化できることを認識しておいてください。 それでも、miniKanrenとPrologには異なる設計哲学があり、異なるトレードオフを行います。

Prologは記号的な人工知能プログラミングのための2つの古典的な言語のうちの1つです（もう1つの古典的な言語はLispです）。 Prologは、宣言的知識が一階論理で符号化された、記号的ルールベースのシステムの実装に優れています。 Prologはこのようなアプリケーションのために表現力と効率を最適化し、時には論理的な純度を犠牲にしています。 例えば、Prologはデフォルトでは、単一化において"occurate check"を使用しません。 数学/論理の立場からは、このバージョンの単一化は不正確です。 しかし、occurチェッ クは高価であり、ほとんどの場合、occurチェックがないことは問題ではありま せん。 これは、Prologの深さ優先探索の使用と同様に、非常に実用的な設計上の決定で、 カット( ! ) を使ってバックトラックを制御しているのと同じです。 これらの決定は、1970年代のハードウェア上で実行されたときに絶対に必要であったと確信していますし、今日、大きな問題に取り組むとき、そして巨大な（しばしば無限！）探索空間を扱うときに非常に有用です。

Prologはカットを含む多くのquot;extra-logical" またはquot;non-logical" 機能をサポートしています。 assert そして retract を使用した算術演算のための変数の投影。 is などがあります。 これらの機能の多くは、複雑な制御フローを表現し、Prologのグローバルな事実のデータベースを操作することを容易にします。 Prologの非常に興味深い特徴は、Prologのコード自体が事実のグローバルな データベースに格納され、実行時に問い合わせることができることです。 これにより、解釈中のPrologコードの動作を変更するメタインタプリタ を書くことが容易になります。 例えば、探索順序を変更するメタインタプリタを用いて、Prologで幅優先探索をエンコードすることが可能です。 これは、Prologの世界以外ではあまり知られていない、非常に強力な技法です。 The Art of Prolog'には、このテクニックが詳しく説明されています。

Prologの実装を改善するために多大な努力が払われてきましたが、そのほとんどはWarren Abstract Machine (WAM)をベースにしています。 WAMは、論理変数に破壊的に値が割り当てられ、バックトラックでこれらの副作用が元に戻るという副作用モデルを使用します。 WAMの命令を拡張することにより、Prologに多くの機能を追加することができます。 この方法の欠点は、Prologの実装論文は、WAMをしっかり理解しないと読めな いということです。 一方、Prologの実装者は、実装上の問題を議論するための共通のモデルを持っています。 並列Prologでは、1990年代のAndorra Prologを頂点とする多くの研究が行なわれてきました。 少なくとも、これらのアイデアのいくつかは、Ciao Prologの中で生きています。 (Ciao Prologは興味深いアイディアに満ちており、その多くはPrologの標準をはるかに超えています)。

Prologは美しい単一化ベースのquot;パターンマッチングスタイルの構文を持っており、非常に簡潔なプログラムになっています。 Prologユーザーは、Lispユーザーがs式を好きなように、その構文を愛しています。 Prologはまた、標準的な述語の大きなライブラリを持っています。 WAMを高速にするために行われたすべてのエンジニアリングのため、非常に有能で成熟したPrologの実装があります。 その結果、多くの大規模な知識ベース・システムは、完全にPrologで書かれています。

miniKanrenは、小さく、簡単に理解でき、簡単にハックできる実装を持つ最小限の論理プログラミング言語として設計されました。 miniKanrenはもともとSchemeに組み込まれていましたが、過去10年間で何十もの他のホスト言語に移植されてきました。 最も人気のあるminiKanrenの実装はClojureの「core.logic」で、今では多くのProlog風の拡張と多くの最適化を行っています。 最近、miniKanrenの実装のコアはさらに単純化され、microKanrenと呼ばれる小さなカーネルになりました。 microKanren や miniKanren を新しいホスト言語に移植することは、miniKanren を学ぶプログラマにとって標準的な作業になっています。 その結果、ほとんどの一般的な高級言語には、少なくとも1つのminiKanrenまたはmicroKanrenの実装があります。

miniKanren と microKanren の標準的な実装には、突然変異やその他の副作用はありません。ただし、miniKanren のいくつかのバージョンでは、論理変数の比較にポインタの等価性が使用されています。 多くの実装では、カウンタを渡すことでこの効果さえも回避していますが、私はこれを「良性の効果」と考えています。 miniKanrenの実装思想は関数型プログラミングに触発されたもので、突然変異や効果は避けるべきで、すべての言語構成は語彙的スコープを尊重すべきです。 実装を注意深く見れば、いくつかのモナドを見つけることができるかもしれません。 検索の実装は、遅延ストリームの結合と操作に基づいており、ここでも変異を用いない。 これらの実装の選択は、Prologとは非常に異なったトレードオフをもたらします。 Prologでは、変数探索は一定時間ですが、バックトラックは副作用を元に戻す必要があります。 miniKanrenでは、変数のルックアップはより高価ですが、バックトラックは無料です。

miniKanren の実装の 1 つの興味深い側面は、コードが本質的にスレッドセーフで、少なくとも理論的には自明な並列化可能であることです。 もちろん、コードを並列化する際に より遅く というのも、各スレッドまたはプロセスには、並列化のオーバーヘッドを補うのに十分な仕事が与えられる必要があるからです。 それでも、これは miniKanren の実装の領域であり、もっと注目され、実験されることを望みます。

miniKanren は単一化のための発生チェックを使用し、深さ優先探索の代わりに完全なインターリーブ探索を使用します。 インターリーブ検索は深さ優先の検索よりも多くのメモリを使用しますが、深さ優先の検索が永遠に発散/ループするようないくつかのケースで答えを見つけることができます。 はします。 は、いくつかの特別な論理演算子をサポートしています。 conda , condu そして project のように、例えば conda と condu はPrologのカットをシミュレートするために使用することができます。 project は論理変数に関連付けられた値を得るために使われることができます。

の存在は conda , condu そして project ---といった検索方法を簡単に変更できるため、プログラマはminiKanrenをPrologのような組み込み言語として使用することができます。 これは特にClojureの'core.logic'のユーザーに当てはまり、多くのPrologのような拡張を含んでいます。 この実用的な使い方が、産業界におけるminiKanrenの使用の大部分を占めているようです。 ClojureやPython、JavaScriptで書かれた既存のアプリケーションに、知識ベースの推論システムを追加したいプログラマーは、一般的に、Prologでアプリケーション全体を書き直すことに興味がありません。 ClojureやPythonに小さな論理プログラミング言語を埋め込むことの方が、ずっと魅力的です。 組み込みのProlog実装は、おそらく、この目的のために、同様にうまくいくでしょう。 私は、miniKanrenが組み込み論理言語として人気が出たのは、小さくて純粋なコア実装と、「The Reasoned Schemer」が出版されて以来出てきた講演、ブログ記事、チュートリアル、その他の教育資料のためだと考えています。

Prologに似た実用的な組み込み型論理プログラミング言語としての使用に加え、miniKanrenはquot;relationalプログラミングの研究にも使用されています。 つまり、数学的な関数ではなく、数学的な関係として振る舞うプログラムを書くということです。 たとえば、Schemeでは append 関数は2つのリストを足し合わせて新しいリストを返すことができます: 関数呼び出し (append '(a b c) '(d e)) はリストを返します。 (a b c d e) . しかし append を2引数の関数としてではなく、3つの場所の関係として扱うこともできます。 この場合 (appendo '(a b c) '(d e) Z) を呼び出すと、論理変数 Z とリスト (a b c d e) . もちろん、ロジック変数を他の位置に配置すると、もっと面白いことになります。 例えば (appendo X '(d e) '(a b c d e)) は X と (a b c) という呼び出しがある一方で (appendo X Y '(a b c d e)) が関連付けられます。 X と Y と等しいリストのペアで、追加されると (a b c d e) . 例えば X = (a b) そして Y = (c d e) はそのような値の組の1つです。 また、次のように書くこともできます。 (appendo X Y Z) と書くこともできますが、これは無限にリストのトリプルを生成します。 X , Y そして Z を追加することで X に Y が生み出す Z .

このリレーショナル版の append はPrologで簡単に表現でき、実際、多くのPrologチュートリアルで紹介されています。 実際には、より複雑なPrologプログラムは、少なくともcutのような余分な論理的機能を使用する傾向があり、結果として得られるプログラムを関係として扱う能力を阻害しています。 対照的に、miniKanrenはこのような関係プログラミングのスタイルをサポートするように 明確に設計されています。 最近のminiKanrenでは、記号的な制約解法( symbolo , numbero , absento や不平等制約、名目論理プログラミングなど）により、非自明なプログラムを関係として書きやすくしています。 実際には、私はminiKanrenの非論理的な機能を使うことはなく、miniKanrenのプログラムはすべて関係として書いています。 関係プログラムとして最も興味深いのは、Schemeのサブセットに対する関係インタプリタです。 このインタプリタには面白い機能がたくさんあって、例えば、リスト (I love you) と評価されるSchemeプログラムを100万個生成したり、 クワイン(自分自身に評価されるプログラム)を自明な形で生成したりと、 多くの興味深い能力を持っています。

miniKanrenはこのリレーショナルスタイルのプログラミングを可能にするために、Prologが行うトレードオフとは全く異なる、多くのトレードオフを行っています。 時間の経過とともに、miniKanrenはより多くの記号的制約を追加し、実際に記号指向の制約論理プログラミング言語となりました。 多くの場合、これらの記号制約により、以下のような余計な論理演算子を 使わずにすむようになりました。 condu そして project . また、このような記号的な制約では不十分な場合もあります。 記号制約をよりよくサポートすることは、より大規模で複雑なプログラムをいかに関係として書くかという広い問題とともに、miniKanrenの研究の活発な分野の一つである。

要するに、miniKanrenとPrologは両方とも興味深い機能、実装、用途を持っており、両方の言語からアイデアを学ぶ価値があると思います。 他にもMercury、Curry、Gödelなど非常に興味深い論理プログラミング言語があり、それぞれが論理プログラミングに独自のアプローチを持っています。

最後に、ミニ観蓮のリソースをいくつか紹介します。

miniKanrenのメインサイトです。 http://minikanren.org/

リレーショナルプログラミングとminiKanrenについて、Prologとの比較も含めて行ったインタビューです。 http://www.infoq.com/interviews/byrd-relational-programming-minikanren

乾杯

--ウィル