31

WAM とほぼ同時期に発明された代替案が他に少なくとも 2 つあるという記事を読んだことがあります。ポインタはありますか？

4

3 に答える 3

23

WAM の前に、Clocksin の ZIP がありました。そのデザインは今でも非常に興味深いものです。SWI-Prolog はそれを使用します。また、B-Prolog は WAM 設計から ZIP へとゆっくりと移行しています。もちろん、その過程で多くの新しいイノベーションが開発されました。もう 1 つの選択肢は VAM です。

1993 年時点での比較は次のとおりです。

http://www.complang.tuwien.ac.at/ulrich/papers/PDF/binwam-nov93.pdf

それまでの間、最も興味深いアーキテクチャの開発は B-Prolog に関連しています。

WAM 対 ZIP

WAM と ZIP の主な違いは、述語の引数の正確なインターフェイスです。WAM では、引数はすべてレジスタを介して渡されます。つまり、実際のレジスタまたは少なくともメモリ内の固定位置のいずれかです。ZIP はスタックを介してすべての引数を渡します。

最小限の例を考えてみましょう:

p(R1,R2,R3,L1,L2,L3) :-  % WAM                % ZIP
                         % store L1..L3       % nothing
                         % nothing            % push R1..R3
                         % init X1..X3        % push X1..X3
   q(R1,R2,R3,X1,X2,X3),
                         % put unsafe X1..X3  % push X1..X3
                         % load       L1..L3  % push L1..L3
   r(X1,X2,X3,L1,L2,L3).

電話する前にq：

WAM は、まったく同じ位置で最初のゴールに渡される引数に対してアクションを実行する必要はありません ( R1..R3)。これは、2 項節 (つまり、最後に 1 つの規則的なゴールがある節) の場合に特に興味深いものです。ここでWAMが優れています。

他の引数L1..L3はローカルに保存する必要があります。したがって、これらの引数については、レジスタ インターフェイスは何の役にも立ちませんでした。

一方、ZIP は引数を保存する必要はありません。引数は既にスタックに保存されています。これは、複数の目標を持つ句だけでなく、制約や割り込みなどの他の割り込み目標にも適しています。

欠点として、ZIP をもう一度押す必要がありR1..R3ます。

どちらも初期化X1..X3してスタックに保存する必要があります。

呼び出しq:

を呼び出すとき、WAM は6 つのセルにスタック スペースを割り当てる必要がありますが、ZIPqは. したがって、ここでは、WAM の方がスペース効率が優れています。また、WAM では、ZIP ではほぼ不可能な環境のトリミング (より複雑な状況の場合) が可能です。X1..X3L1..L3R1..R3,L1..L3,X1..X3

電話する前にr：

これrは最後の呼び出しであり、選択ポイントが存在しない場合、システムはこの句のスペースを解放しようとします。

WAM の場合、存在する変数がまだインスタンス化されていないローカル変数 ( ) でX1..X3 あることを確認put_unsafeする必要があり、それらがヒープに移動される場合は、コストがかかりますが、めったに発生しません。L1..L3ロードされるだけです。以上で、WAM は安全にローカル フレームの割り当てを解除できるようになりました。したがって、最後の呼び出しの最適化は非常に安価です。

ZIP の場合、通常どおりすべてをプッシュする必要があります。その後、追加のスキャンでスタック上のすべての値を調べ、それに応じてそれらを移動する必要があります。それはかなり高価です。いくつかの最適化は可能ですが、それでも WAM の機能をはるかに超えています。((可能な改善は、逆の順序で引数をプッシュすることです。その後、変数L1..L3はその場所に残される可能性があります。したがって、これらの変数は処理を必要としません。そのような実装は (まだ) 見たことがありません。))

于 2010-12-21T21:57:40.977 に答える
8

「抽象Prolog命令セット」というタイトルのテクニカルノートでは、Warrenは、Bowen、Byrd、およびClocksinによる別のコンパイラも参照しています。しかし、彼は、2つのアーキテクチャには多くの共通点があると言っているので、そのコンパイラが本当に代替として考えられるかどうかはわかりません。

于 2010-12-18T19:29:06.047 に答える
5

これがあなたの言いたいことかどうかはわかりませんが、最初の 2 つの Prolog 実装は、Colmerauer らによって Fortran で書かれたインタープリターでした。Warren らによる DEC PDP-10 ネイティブ コンパイラ。

ウォーレンは、Ait-Kaci のWAMのチュートリアルの再構築の序文でこれらについて言及しています。これが意図したものでない場合は、そのドキュメントまたはその参照に記載されている可能性があります。

于 2010-12-18T16:40:13.143 に答える