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

Question

私はPrologであなたが次のようなことをすることができることを知っています

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

これは、リスト内のすべての要素を反復処理するわけではありません。代わりに、異なる「マシン」に分岐し（複数のスレッドを使用する、単一のスレッドでバックトラックする、パラレルユニバースを作成するなど）、Xの可能な値ごとに個別に実行してsomeOtherFunction(X, List)trueを返します。
（私はそれがこれをどのように行うのか分かりませんが、それは質問にとって重要ではありません）

私の質問は、 他にどのような非決定論的プログラミング言語が出回っているのかということです。 非決定論は、不変の変数を持つ言語でマルチスレッドを実装するための最も簡単で論理的な方法のようですが、これが行われるのを見たことがありません-なぜこの手法がより一般的ではないのですか？

score 21 · Accepted Answer

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

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

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

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

Dijkstra の保護されたコマンドの微積分 (彼は決して実装されたくないもの)
通信が非決定論的に同期される可能性がある同時 ML
モデルチェッカー SPIN の言語である Gerard Holzmann の Promela 言語

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

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

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

score 5 · Accepted Answer

ウィキペディアの記事は、非決定論的プログラミングの能力を持つスキーム派生物であるAmbを指しています。

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

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

ちなみに、決定論的チューリングマシンと非決定論的チューリングマシンの間には、「量子コンピューティング」モデルがあります。量子コンピューターは、存在すると仮定すると、非決定論的チューリングマシンが実行できるすべてのことを行うわけではありませんが、決定論的チューリングマシン以上のことを実行できます。現在、量子コンピューター用のプログラミング言語を設計している人がいます (最終的に量子コンピューターが構築されることを前提として)。それらの新しい言語のいくつかは機能的です。このウィキペディアのページには、便利なリンクがたくさんあります。どうやら、機能的であろうとなかろうと、量子プログラミング言語を設計し、それを使用することは簡単ではなく、確かに「単純」ではありません。

score 5 · Accepted Answer

非決定論的言語の一例は、CSP理論に基づくOccamです。およびコンストラクトを組み合わせると、マルチプロセッサシステムで非決定論的な動作が発生し、細粒度の並列プログラムが実装される可能性があります。PARALT

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

^†_{コンストラクトはで実装されることが多い}_{ため、公正にする必要がある場合は、明示的に公平にコーディングする必要があります。ALTPRI ALT}

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

通信の順序付けがデッドロックにつながらない限り(これは CSP 手法を適用することで実現できます)、物事が行われる正確な順序は、必要な結果が時間内に得られるかどうかよりもはるかに重要ではありません。

間違いなく、この決定論の欠如が、軍事プロジェクトでのオッカムおよびトランスピューターシステムの採用を妨げる主な要因であり、当時エイダが支配していました。そこでは、すべてのクロックサイクルで CPU が何をしているかを正確に知ることが、システム正しい。この制約がなければ、Occam とそれが実行された Transputer システム (公式に証明された IEEE 浮動小数点実装を備えた当時唯一の CPU) は、小規模で高レベルの処理機能を必要とするハードリアルタイムミリタリーシステムに完全に適合していたでしょう。スペース。

score 1 · Accepted Answer

Java 2K

注: リンクをクリックしてがっかりする前に: これは難解な言語であり、並列処理とは何の関係もありません。

score 1 · Accepted Answer

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

IBM Research で開発中のSlyプログラミング言語は、特定のタイプのアルゴリズムの実行において、マルチスレッド実行に固有の非決定性を組み込む試みです。しかし、非常に進行中の作業のように見えます。

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

8 に答える 8

Related

Reference