23


5

非決定的プログラミング言語

プロローグでは次のようなことができることを知っています

someFunction(List) :-
    someOtherFunction(X, List)
    doSomethingWith(X)
    % and so on

これは、リスト内のすべての要素を反復処理するわけではありません。代わりに、異なる「マシン」に分岐します_(複数のスレッドを使用する、単一のスレッドでバックトラッキングする、並列ユニバースを作成するなど)_、「someOtherFunction(X 、List) `がtrueを返します! +(これがどのように行われるかわかりませんが、それは質問にとって重要ではありません)

私の質問は次のとおりです。他の非決定論的プログラミング言語はどこにありますか? before-*なぜこの手法がより一般的ではないのですか?

8 回答


16


プロローグは実際には決定論的です。評価の順序は規定されており、順序が重要です。

_ なぜ非決定論がより一般的ではないのですか? _

非決定性は、プログラムの結果について推論するのを難しくし、真に非決定的な_executions_(セマンティクスとは対照的に)の実装が難しいため、人気がありません。

私が知っている唯一の非決定論的言語は

  • ダイクストラの保護されたコマンドの計算、彼は決してなりたくなかった 実装済み

  • 同時ML。通信を同期できます 非決定論的に

  • モデルの言語であるジェラルド・ホルツマンのプロメラ言語 チェッカーSPIN

SPINは実際に非決定性を使用し、可能な場合は状態空間全体を探索します。

もちろん、スレッドが同期されていない場合、マルチスレッド言語は非決定的に動作しますが、それはまさに推論するのが難しい種類のことであり、効率的で正しいロックフリーのデータ構造を実装するのが難しいのです。

ちなみに、並列処理を実現しようとしている場合、Haskellのような純粋な関数型言語の単純な `map`関数で同じことを実現できます。 Google MapReduceが関数型言語に基づいているのには理由があります。


6


Wikipedia articleは、スキームであるhttp://mitpress.mit.edu/sicp/full-text/sicp/book/node88.html[Amb]を指します。 -非決定的プログラミングの能力を持つ派生物。

私が理解している限り、プログラミング言語がそうしない主な理由は、(すべての既存のコンピューターと同様に)決定論的マシンで非決定論的プログラムを実行することは本質的に高価だからです。 基本的に、非決定性チューリングマシンは、多項式時間の複雑な問題を解決できます。決定論的チューリングマシンの多項式アルゴリズムは知られていません。 言い換えれば、非決定性プログラミングは、既存のコンピューターのコンテキストでアルゴリズムの本質を捉えることに失敗します。

同じ問題がPrologに影響します。 効率的、または少なくとも非効率的ではないPrologアプリケーションは、「カット」演算子を使用して、指数関数的な数のパスの探索を回避する必要があります。 その演算子は、プログラマーがPrologインタープリターが可能なパスを決定論的かつ非常に手続き的な方法でどのように探索するかについての精神的な見方を持っている場合にのみ機能します。 非常に手続き的なものは、関数型プログラミングとうまく混ざり合いません。後者は、ほとんど手続き型で考えない努力であるためです。

補足として、決定論的チューリングマシンと非決定論的チューリングマシンの間には、「量子コンピューティング」モデルがあります。 量子コンピューターは、存在すると仮定して、非決定的チューリングマシンが実行できるすべてを実行するわけではありませんが、決定論的チューリングマシン以上のことを実行できます。 現在、量子コンピューター用のプログラミング言語を設計している人がいます(最終的には量子コンピューターが構築されると仮定しています)。 これらの新しい言語の一部は機能的です。 このhttp://en.wikipedia.org/wiki/Quantum_programming[Wikipedia page]には、便利なリンクが多数あります。 どうやら、機能的であるかどうかにかかわらず、量子プログラミング言語を設計し、それを使用することは容易ではなく、確かに「単純」ではありません。


4


非決定論的な言語の一例は、http://en.wikipedia.org/wiki/Communicating_sequential_processes [CSP]理論に基づくhttp://en.wikipedia.org/wiki/Occam_%28programming_language%29[Occam]です。 「PAR」と「ALT」のコンストラクトの組み合わせにより、マルチプロセッサシステムで非決定的な動作が発生し、http://en.wikipedia.org/wiki/Parallel_computing#Fine-grained.2C_coarse-grained.2C_and_embarrassing_parallelism [fine粒並列]プログラム。

ソフトチャネルを使用する場合、つまり 同じプロセッサ上のプロセス間のチャネルでは、「ALT」の実装により動作が決定論に近くなります、ハードチャネル(物理的なプロセッサ外通信リンク)の使用を開始するとすぐに、決定論の幻想が消えます。 異なるリモートプロセッサは、いかなる方法でも同期されることは期待されておらず、同じコアまたはクロック速度を持たない場合もあります。

〜「ALT」コンストラクトは「PRI ALT」で実装されることが多いため、フェアにする必要がある場合はフェアに明示的にコーディングする必要があります。

'' '' '

非決定論は、プログラムについて推論し、正しいことを証明することになると不利に見えますが、多くの点でそれを受け入れれば、決定論が推論に強制する多くの制約から解放されます。

コミュニケーションの順序付けがhttp://en.wikipedia.org/wiki/Deadlock[deadlock]につながらない限り、これはCSPテクニックを適用することで実行でき、物事が実行される正確な順序は重要ですless_は、時間内に必要な結果を得るかどうかよりも小さい。

おそらく、この決定性の欠如が、http://en.wikipediaによって支配されている軍事プロジェクトでのOccamおよびhttp://en.wikipedia.org/wiki/Transputer[Transputer]システムの採用を妨げる主要な要因でした。 org / wiki / Ada_%28programming_language%29 [Ada]当時、CPUが各クロックサイクルで何をしていたかを正確に知ることは、システムを正しく証明するために不可欠であると考えられていました。 この制約がなければ、Occamとそれが実行されたTransputerシステム(正式に実績のあるIEEE浮動小数点実装を持つ当時の唯一のCPU)は、小規模で高レベルの処理機能を必要とするハードリアルタイムの軍事システムに最適です。スペース。


4


Prologでは、非決定性と並行性の両方を持つことができます。 非決定論は、サンプルコードに関する質問で説明したものです。 Prolog句には、暗黙的なhttp://www.randomhacks.net/2005/10/11/amb-operator/[amb]ステートメントがたくさんあることが想像できます。 並行性がロジックプログラミングによってもサポートされていることはあまり知られていません。

歴史は言う:

_ 最初の並行論理プログラミング言語は、クラークとグレゴリーのリレーショナル言語であり、IC-Prologの派生物でした。 コンカレントロジックプログラミングの最新バージョンには、ShapiroのConcurrent PrologとUedaのGuarded Horn Clause言語GHCが含まれます。 https://en.wikipedia.org/wiki/Concurrent_logic_programming _

しかし、今日はロジックプログラミングの内部に踏み込むだけかもしれません。 https://stackoverflow.com/questions/7647758/prolog-findall-implementation/38152802#38152802 [こちら]は、スレッドを介してfindallを実装する例です。 これは、コレクションであらゆる種類のタスクを実行するように変更したり、分散人工知能に向けたエージェントネットワークを作成することもできます。


1


Haskellには、非決定的なマシンを構築する機能があると思います。 Haskellは最初は実用的では難しすぎて抽象的に見えるかもしれませんが、実際には非常に強力です。


1


注:リンクをクリックして失望する前:これはhttp://en.wikipedia.org/wiki/Esoteric_programming_language#Nondeterministic_language[esoteric]言語であり、並列処理とは関係ありません。


1


「制御ネットワークプログラミング」と呼ばれる非決定的な問題のためのプログラミング言語があります。 詳細については、http://controlnetworkprogramming.comにアクセスしてください。 このサイトはまだ進行中ですが、それに関する情報を読むことができます。


1


IBM Researchで開発中のhttp://soft.vub.ac.be/~smarr/2011/08/sly-and-the-roarvm-exploring-the-manycore-future-of-programming/[Sly]プログラミング言語特定のタイプのアルゴリズムの実行にマルチスレッド実行に固有の非決定論を含める試みです。 しかし、非常に進行中の作業のようです。