この文書は、Prologコンパイラとそのオブジェクトを実行する仮想マシン・ インタープリタ(プロセスVM)や、専用プロセッサを作る人は必読の、Warrenの 仮想機械(WAM)のレポートである。
この和訳文書は、竹岡が訳したドラフトをもとに、京都工芸繊維大学コンピュー タ部の有志などとともに、輪講を行い完成させた。輪講のメンバーは、竹岡尚 三、安達彰典、林奉行、湯浅信吾、小宮山敦史、森下耕平である。特に、湯浅 は、WarrenのSB-Prologのソース・コードを読み、本文書の輪講の精度と速度 の向上に貢献した。また、森下は英語の読解力で寄与した。
この文書の原文: http://www.ai.sri.com/pubs/files/641.pdf
SB-Prologソース・コード
ftp://ftp.cs.arizona.edu/sbprolog/v3/
※SB-Prologの仮想機械インタープリタは、ガーベジ・コレクタに問題があ
り、最近のUNIXではトイ・プログラムしか実行できないだろう。
和訳更新履歴
21/OCT/2010 11章のタイトル修正
10/JAN/2010 trust L命令の説明式のtypo修正。プログラム例中のtypo修正。まえがき修正
1. 始めに
このレポートは、ソフトウェア、ファームウェア、ハードウェア実現に適切 な抽象Prolog命令セットについて記述する。この命令セットは、エンコーディ ングの実際の詳細については抽象的であり、また、実現についてはオープンな まま残されている。よって、いくつかの異なった形式で現実化されるだろう。 その形式について、熟考されたものは:
ここで記述されている抽象マシン("new Prolog Engine" (新Prologエンジン)) は、前の文書で述べていた"old Prolog Engine"の大きな改訂である。新しい モデルは、後の節で議論される旧モデルの困難を解消した。 新しいモデルは、旧モデルの変更であると考えることができる。 スタックは、ユーザ定義ゴールの代わりに、環境と呼ばれるコンパイラが定 義(compiler-defined)したゴールを含む。 環境は、節の最後に位置するゴールのいくつかと対応する。 旧モデルは、VAX-730マイクロコードでの実現を一番に気に留めて開発された。 新モデルは、加えて、ハードウェア実現を考えたことに、影響を受けている。 しかし、ソフトウェアやVAXのような機械でのファームウェア実現に、同様に なじむことは残してある。
新モデルは、Warrenによって書かれたDEC-10 Prolog[4]をもとにした抽象マシ ンに非常に近く、末尾再帰最適化[5]を入れるために変更された。 主な変更点は:
このアーキテクチャは、Browen,Byrd,Clocksinの設計による抽象マシン[1]と 多くの共通点がある。
ソフトウェアかファームウェアでアーキテクチャを実現化する一つの本道は、 バイトコード・エミュレータを経由することだ。このアプローチはこのレポー トで強調されている。 バイトコード・エミュレータの設計は、大きな仮想記憶、バイト・アドレシン グ可能な機械を要求し、特にVAXアーキテクチャのようなものに基づいている。 Prologの実行時データ構造は32bitワードの列としてエンコードされている。 Prologプログラムは命令の列として表現され、8bitバイトの列としてエンコー ドされる。各命令は、1バイトのオペレーション・コード(opcode)と、引き続 くアーギュメントの数(通常は1,2,0)から成っている。アーギュメントは、 1,2,4バイトの長さである。
バイトコード・エミュレータは、異なる操作を定義する小さな多数のルーチン でできている。実行は、次の命令のオペコードでのディスパッチによって、1 つのルーチンから、次に進む。いくつかの命令は、2つの異なったモード ("read" モードか"write"モード)で実行される。よって、各モードごとに、別 なルーチンがある、
早期の版のエミュレータ(旧エンジン設計用) は、Progolと呼ばれるPrologベー
スのマクロ言語で実現された。ProgolはVAX機械語版を生成するために使用され
た。Progol実現は、様々な機械への移植と、効率的なソフトウェア実現を
非常に容易にした。このProgolのコードのCへの書換えはすでに実施済みである。
エミュレータのPrologフォームに隠れているのだが、第一番の意志は、
VAX-730や他の適切な機械でのマイクロコード実現のためのモデルを提供する
ことである。
2. データ・オブジェクト
Prologの項(term)は、値(一般的にアドレス) とタグを含んだワードで表現さ れる。(これらのワードの可能な形式は付録Vに与えられる。) 大きなアドレス 空間が想定されていて、その値は32bit程度を占める。タグは項の型を識別し、 最低2bit必要で、可能なら8bitまであるべきだ。主要な型は参照(reference: 対 応するバインド済みやアンバウンドな変数への)、構造体、リスト、定数(アト ムと整数を含む)。アンバウンド変数はそれ自身への参照として表現される。 それは、ハードウェア実現では、分離されたタグによって識別されるだろう。
構造体とリストは非構造体共有(non-structure-sharing) マナーにより表現さ
れる、つまり、それらは、ファンクタ(functor) とアーギュメントが、一連の
メモリのワードとして、明示的にコピーされて生成される。
効率のために、リストは構造体から分離したタグを持つ、よって、ファンクタ
はストアされる必要が無い。
3.データ領域
主要なデータ領域は、命令とプログラムそのものを表現している他のデータを 含んでいるコード領域、それに、スタックとして操作される3つの領域、「(ロー カル)スタック」、「ヒープ(またはグローバル・スタック)」、「トレイル」 である。(また、単一化(unification)に使用される小さなプッシュダウン・リ スト(PDL)がある) スタックは、一般的に、手続き呼び出し毎に拡張し、バッ クトラッキングで縮まる。加えて、末尾再帰最適化は、決定的な手続き (determinate procedure) の中の最後の手続き呼び出しを実行するとき、ロー カル・スタックから情報を取り除き、そして、カット演算子はローカル・スタッ クとトレイルの両方から、バックトラック情報を削除する。
異なる領域は、メモリ上に次のように配置されている。
図1.
low High
|-----------+---+-------+---+------+---+------+------+-----+
| code area |-> | heap |-> |stack |-> |trail |-> <-| PDL |
| | | | | | | | | |
|-----------+---+-------+---+------+---+------+------+-----+
: : : : : :
P HB H B E TR
スタックとヒープを、図の通り並べるというのは重要であろう。(変数-変数バ
インディングを作るとき、宙ぶらりん(dangling)参照ができないように安全な
ために、常に最も低いアドレスに変数のバインディングするという、単純な戦
略であるから)
(+++訳注: なにかを巻き戻すときに現在のポインタより大きいものは回収す
る。ヒープからスタックを指していれば、回収することが即座に判断できる)
ヒープは、単一化と手続き呼び出しで生成された全部の構造体とリストを含ん
でいる。トレイルは、単一化中にバインドされ、また、バックトラックでアン
バインドされなければならない変数への参照を含んでいる。スタックは2種類
のオブジェクトを含んでいる:「環境」と「チョイス・ポイント」(その形式は
付録IVに与えられる)。環境は、いくつかの節のボディ中に現れる変数のため
の値のセルのベクトル(+++訳注:一次元配列)と継続から構成されている。「継
続(continuation)」は別の節のボディへのポインタと、それに関係づいている
環境で、構成されている。結果として、継続は、実行されようとしている(イ
ンスタンシエイトされた)ゴールのリストを表現している。チョイス・ポイン
トは、バックトラックのイベントにおいて、計算の以前の状態を復帰するのに
必要なすべての情報を持っている。手続きに入る時に、その呼び出しにマッチ
する可能性のある1つかそれ以上の節を、手続きが持つ場合にのみ、チョイス・
ポイントは作られる。別な選択肢である節へのポインタ、それに加えて、手続
きに入った時の次のレジスタ(以下を参照) の値が、その情報として格納され
る。格納されるレジスタ: H,TR,B,CP,E, A1からAm ここでmは手続きのアーギュ
メントの数。
4.レジスタと変数の取り扱い
Prolog計算の現在状態は、主要データ領域を指すポインタを含むいくつかの レジスタによって定義できる。主要レジスタは次の通り:
AレジスタとXレジスタは、実のところ、同じものである; 名前が違うのは単 に違う用途であるからである。Aレジスタは手続きへアーギュメントを渡すの に使用される。Xレジスタは節の一時変数の値を保持するのに使用される。
「一時変数(temporary variable)」は、ヘッド中か、構造体中か、最終ゴール の中に最初に現れ、かつ、ボディ中の一つより多いゴール中には現れない(こ こで、その節のヘッドは、最初のゴールの一部分として数える) ような変数で ある。一時変数は節の環境に格納される必要が無い。
(+++訳注:例えば↓こんな感じ p(X,X) :-.. p(X) :- r(1,X),s. +++)
「恒久変数(permanent variable)」は一時変数に分類できないすべての変数であ
る。恒久変数は環境に格納され、環境ポインタからのオフセットでアドレスさ
れる。それらはY1,Y2などとして参照される。特に気をつけたいのは、そのボ
ディに2より少ないゴールしかない節には、恒久変数がまったく存在しないか
ら、よって、そういう節には環境は必要無い。(+++訳注: p(X) :-q(X).は一時変
数のみである) 恒久変数は、それらが必要なくなった時にすぐさま捨てること
ができるように、その環境中に並べられる。この環境の「刈り込み」は、最後
のチョイス・ポイントより新しい環境であるときにだけ、実際の効果がある。
5. 命令セット
PrologプログラムはProlog命令の列としてエンコードされる。一般に、各 Prologシンボルごとに、1つの命令がある。命令は、操作コード(オペコード opcode)といくつかのオペランド(通常、1つだけ) から成っている。オペコー ドは、一般に、Prologシンボルの型と、それが現れる文脈と一緒にエンコード される。それは、1Byte(8bit)より多くの場所は必要としない。オペランドは、 Prologシンボルとして異なった種類を示す、小さな整数、オフセット、アドレ スを含む。エンコードの詳細により、オペランドは、1,2,4バイトを占めるで あろう、または、いくつかのケースでは1バイトより少ないかも知れない。
Prolog命令セットは、get命令、put命令、unify命令、procedural命令、
indexing命令に分類できる。(命令セットの表は付録I。)
「get」命令は節のヘッドのアーギュメントに対応し、 Aレジスタ中に与えられる手続きのアーギュメントに対してマッチングを行う。 主な命令は:
get_variable Yn,Ai get_variable Xn,Ai get_value Yn,Ai get_value Xn,Ai get_constant C,Ai get_nil Ai get_structure F,Ai get_list Ai
ここで(そして、以下の命令の他のクラスの記述でも)、Aiは関係するアーギュ
メント・レジスタを表し、Xn,Yn.C.Fはそれぞれ、一時変数、恒久変数、定数、
ファンクタを表す。「get_variabel」命令は現在、もし変数がまだインスタン
シエイトされていない時に、使用される(つまり、もし節の中の変数でこれが
最初の出現であったら)。そうでなければ、「get_value」命令が使用される。
「put」命令は、節のボディ中のあるゴールのアーギュメントと対応しており、 アーギュメントをAレジスタにロードすることを行う。主な命令は:
put_variable Yn,Ai put_variable Xn,Ai put_value Yn,Ai put_value Xn,Ai put_unsafe_value Yn,Ai put_constant C,Ai put_nil Ai put_structure F,Ai put_list Ai
「put_unsafe_value」命令は、unsafeな変数が出現する最終ゴール中の、
put_value命令の代わりに使用される。(+++訳注:unsafeな変数が出現する最後の
場所に一回だけput_unsafe_value命令が出る。それ以外は、put_value命令を置
く) 「unsafe変数」とは、ヘッド中か構造体の中かに、最初に出現したのではな
い恒久変数であり、すなわち、その変数はput_variable命令で初期化されていな
ければならない。put_unsafe_value命令は、unsafe変数が、現在の環境への参照
ではない何か、ヒープ上の新しい値セルへバインドされた変数(もし必要であれ
ば、変数を「大域化(globalizing)」する) にデリファレンスされることを保証
する。この手段は、後で述べるexecuteかcall命令によって、捨てられる環境の
一部へのダングリング参照が発生するのを、防ぐために必要である。
「unify」命令は、構造体(かリスト)のアーギュメントに対応しており、存在 する構造との単一化(unify)と、新しい構造の構築の両方を行う。主な命令は:
unify_void N unify_variable Yn unify_variable Xn unify_value Yn unify_value Xn unify_local_value Yn unify_local_value Xn unify_constant C unify_nil「unify_void N」命令は一回しか出現しない変数のN個の列を表す; これらの 「void」変数には、一時変数も恒久変数のセルも不要である。 「unify_local_value」命令は、もし、変数がグローバルな値に初期化されて いなければ(例えば、unify_variable命令によって)、「unify_value」命令の 代わりに使用される。
unify命令の列の前には、構造体かリストのgetかput命令が先立って置かれる。 この先立つ命令は、read modeかwrite modeの2つのモードを決定し、引き続く unify命令は、そのモードで実行される。read modeでは、unify命令は、引き 続く、存在する構造体のアーギュメントとの単一化を実行し、Sレジスタを通 してアドレシングされる。write modeでは、unify命令は、引き続くアーギュ メントの新しい構造体を構築し、Hレジスタを通してアドレシングされる。
ネスト(入れ子)になったサブ構造体かサブリストは、次のように取り扱われる。
もしサブ構造体かサブリストがヘッドの中にあれば、それは、unify_variable Xn
命令に変換される。現在のunifyシーケンス(+++訳注:現在のシーケンスとは、
親の構造のこと) の末尾の後ろに、対応するget_structure F,Xn か
get_list Xn命令が続く。もしサブ構造体かサブリストがボディの中にあれば、
それは、unify_value Xn 命令に変換される。現在のunifyシーケンス(+++訳注:
現在のシーケンスとは、親の構造のこと)の始まる前に、対応する
put_structure F,Xn かput_list Xn命令が先立つ。
「procedural」命令はヘッドと節のゴールを組み立てる述語(predicate) に対 応し、制御を移すことを実行し、手続き呼び出しに伴う環境の割り当てを行 う。主な命令は:
proceed allocate execute P deallocate call P,NここでPは述語を、Nは環境中の(使用中の)変数の数を表す。procedural命令は、 ボディ中の0,1,2かもっと多くのゴールを持った節の変換で使用される。
P. get args of P proceed |
P :- Q. get args of P put args of Q execute Q |
P :- Q,R,S. allocate get args of P put args of Q call Q,N put args of R call R,N1 put args of S deallocate execute S (+++訳注:末尾再帰最適化) |
|---|
「indexing」命令は、手続きからなる異なる節を一緒につなぎ(linkし)、与え られた手続き呼び出しと潜在的にマッチするような節の部分集合をフィルタし て洗い出す。このフィルタリング、またはインデキシング、機能は、keyに基 づいたものであり、そのkeyは、(A1レジスタに与えられた)手続きの最初のアー ギュメントの主要な機能である。主な命令は:
try_me_else L try L swicth_on_term Lv,Lc,Ll,Ls retry_me_else L retry L swicth_on_constant N,Table trust_me_else L trust L swicth_on_structure N,TableここでL,Lv,Lc,Ll,Lsは節(または節の集合)のアドレスであり、Tableはサイズ Nのハッシュ・テーブルである。
各節は、try_me_else, retry_me_else, trust_me_else 命令が先にあり、それ
が手続き中の最初, 中間,最後の節であるかどうかに、依存している。これら
の命令は、A1が変数にデリファレンスされる場合のみ実行され、すべての節が
マッチを試行されるべきである。オペランドLは続く節のアドレスである。
「switch_on_term」命令はLv,Lc,Ll,Lsの4つのアドレスのうちの1つにディスパッ
チし、そのディスパッチはA1が変数、定数、リスト、構造体のどれにデリファ
レンスするかに依存する。Lvは、手続きの最初の節に先立つ、try_me_else(ま
たはtrust_me_else)命令のアドレスであろう。Llはそのkeyがリストである単
一の節のアドレスであるか、または、try,retry,trust命令の列で識別される
ような、節の列のアドレスである。
LcとLsは単一の節か、節の列(Llの場合と同様な) のアドレスであるか、また
は、もっと一般的に、各々、switch_on_constantかswitch_on_structure 命令
のアドレスだろう。switch_on_constantかswitch_on_structure 命令は、与え
られたkeyにマッチする節か節たちへのハッシュ・テーブルによるアクセスを
提供する。
6.最適化
アーギュメント・レジスタと一時レジスタは同一であるから、いくつかの命令 はnullオペレーションとなり削除することができる:
get_variable Xi,Ai put_value Xi,Aiコンパイラは悩みながら、このような方法で一時変数をXレジスタに割り当て た、この最適化のためにスコープを最大にして。
注意として、次の命令も、レジスタXiの内容のXjへの単純な転送について、 同じ操作を示している。
get_variable Xj,Ai put_variable Xi,Aj
7. 節のエンコーディングの例
節のエンコーディングの例として、ここでは、concatnateとquick sort 手続 きのコードを示す。
concatenate([],L,L). concatenate([X|L1],L2,[X|L3]) :- concatenate(L1,L2,L3). concatenate/3: switch_on_term C1a,C1,C2,fail Cla: try_me_else C2a % concatenate( C1: get_nil A1 % [] get_value A2,A3 % L,L proceed % ). C2a: trust_me_else fail % concatenate( C2: get_list A1 % [ unify_variable X4 % X| unify_variable A1 % L1], L2, get_list A3 % [ unify_value X4 % X| unify_variable A3 % L3]) :- execute concatenate/3 % concatenate(L1,L2,L3).
qsort([],R,R). qsort([X|L],R0,R) :- split(L,X,L1,L2), qsort(L1,R0,[X|R1]), qsort(L2,R1,R). qsort/3: switch_on_term C1a,C1,C2,fail C1a: try_me_else C2a % qsort( get_nil A1 % [], get_value A2,A3 % R,R proceed % ). C2a: trust_me_else fail % qsort( allocate get_list A1 % [ unify_variable Y6 % X| unify_variable A1 % L], get_variable Y5,A2 % R0, get_variable Y3,A3 % R) :- put_value Y6,A2 % split(L,X, put_variable Y4,A3 % L1, put_variable Y1，A4 % L2 call split/4,6 % ), put_unsafe_value Y4,A1 % qsort(L1, put_value Y5,A2 % R0, put_list A3 % [ unify_value Y6 % X| unify_variable Y2 % R1] call qsort/3,3 % ), put_unsafe_value Y1,A1 % qsort(L2, put_value Y2,A2 % R1, put_value Y3,A3 % R deallocate execute qsort/3 % ).
次の例は恒久変数の扱いをより深く詳説している。
compile(Clause,Instructions):- preprocess(Clause,C1), translate(C1,Symbols), number_variables(Symbols, 0, N,Saga), complete_saga(0,N,Saga), allocate_registers(Saga), generate(Symbols, Instructions). try_me_else fail % compile(Clause, allocate get_variable Y2,A2 % Instructions):- put_variable Y5,A2 % preprocess(Clause,C1 call preprocess/2,5 % ), put_unsafe_value Y5,A1 % translate(C1, put_variable Y1,A2 % Symbols call_translate/2,4 % ), put_value Y1,A1 % number_variables(Symbols, put_constant 0,A2 % 0, put_variable Y4,A3 % N, Put_variable Y3,A4 % Saga call number_variables/4,4 % ), put_constant 0,A1 % complete_saga(0, put_unsafe_value Y4,A2 % N, put_variable Y3,A3 % Saga call complete_saga/3,3 % ), put_unsafe_value Y3,A1 % allocate_registers(Saga call_ allocate_registers/1，2 % ), put_unsafe_value Y1,A1 % generate(Symbols, put_value Y2,A2 % Instructions deallocate execute generate/2 % ).
続く2つの例はネストしたサブ構造体のエンコーディングを示している。
d(U*V,X,(DU*V)+(U*DV)):-d(U,X,DU),d(V,X,DV). try_me_else ... % d( get_structure '*'/2,A1 % *( unify_variable A1 % U, unify_variable Y1 % V), get_variable Y2,A2 % X, get_structure '+'/2,A3 % +( unify_variable X4 % SS1, unify_variable X5 % SS2), get_structure '*'/2,X4 % SS1 = *( unify_variable A3 % DU, unify_value Y1 % V), get_structure '*'/2,X5 % SS2 = *( unify_value A1 % U, unify_variable Y3 % DV)) :- call d/3,3 % d(U,X,DU), put_value Y1,A1 % d(V, put_value Y2,A2 % X, Put_value Y3,A3 % DV, execute d/3 % ).
test :- do(parse(s(np,vp), [birds,fly],[])). trust_me_else fail % test :- put_structure s/2,X2 % do(SS1 = s( unify_constant np % np, unify_constant vp % vp), put_list X4 % SS2 = [ unify_constant fly % fly| unify_nil % []], put_list X3 % SS3 = [ unify_constant birds % birds| unify_value X4 % SS2], put_structure parse/3,A1 % parse( unify_value X2 % SS1, unify_value X3 % SS2, unify_nil % []) execute do/1 ).
続く例はindexing命令の使用を示している。
call(X or Y) :- call(X). call(X or Y) :- call(Y). call(trace) :- trace. call(notrace) :- notrace. call(nl) :- nl. call(X) :- builtin(X). call(X) :- ext(X). call(call(X)) :- call(X). call(repeat). call(repeat) :- call(repeat). call(true). call/1: try_me_else C6a switch_on_type C1a,L1,fail,L2 L1: switch_on_constant 4, $(trace: C3, notrace: C4, fail, nl: C5) L2: switch_on_structure 1, $(or/2: L3) L3: try C1 trust C2 C1a: try_me_else C2a % call( C1: get_structure or/2,A1 % or( unify_variable A1 % X,Y)) :- execute call/1. % call(X). C2a: retry_me_else C3a % call( C2: get_structure or/2,A1 % or( unify_void 1 % X, unify_variable A1 % Y)):- execute call/1 % call(Y). C3a: retry_me_else C4a % call( C3: get_constant trace,A1 % trace) :- execute trace/0 % trace. C4a: retry_me_else C5a % call( C4: get_constant notrace,A1 % notrace) :- execute notrace/0 % notrace. C5a: retry_me_else fail % call( C5: get_constant nl,A1 % nl) :- execute nl/0. % nl. C6a: retry_me_else C7a % call(X) :- execute builtin/1 % builtin(X). C7a: retry_me_else L4 % call(X) :- execute ext/1 % ext(X). L4: trust_me_else fail switch_on_type C8a,L5,fail,L7 L5: switch_on_constant 2,$(repeat: L6, true: C11) L6: try C9 trust C10 L7: switch_on_structure 1,$(call/1: C8) C8a: try_me_else C9a % call( C8: get_structure call/1,A1 % call( unify_variable A1 % X)) :- execute call/1 % call(X). C9a: retry_me_else C10a % call( get_constant repeat,A1 % repeat proceed % ). C10a: retry_me_else C11a % call( get_constant repeat,A1 % repeat) :- put_constant repeat,A1 % call(repeat execute call/1 % ). C11a: trust_me_else fail % call( get_constant true,A1 % true proceed % ).
8. 命令の解説と基本操作
注意: ここに続く記述では、Vnは一般的に、恒久変数Ynか一時変数Xnを示すた
めに使用される。
記述のいくつかには、実行される操作のアルゴリズム的なコードの簡単な場合
を、付けてある。
8.1 制御命令
CE := E E := (CE < B -> B | CE + env_size(CP)) CP(E) := CP CE(E) := CE
CP := CP(E) E := CE(E)
CP := 続くコード P := Proc
P := Proc
P := CP
8.2 Put命令
Ai := Yn := ref_to(Yn)
Ai := Xn := next_term(H) := tag_ref(H)(+++訳注: next_term()が変数の生成。tag_ref()は印をつける)
Ai := Vn
Ai := C
Ai := nil
Ai := tag_struct(H) next_term(H) := F
Ai := tag_list(H)
8.3 Get命令
Vn := Ai
8.4 単一化(unify)命令
In read mode:
S := S + N*word_width
In write mode:
next_term(H) := tag_ref(H)
... {N 回繰り返し}
In read mode:
Vn := next_term(S)
In write mode:
Vn := next_term(H) := tag_ref(H)
In write mode:
next_term(H) := Vn
In write mode:
next_term(H) := C
8.5 indexing 命令
BP(B) := L
B := B(B) HB := H(B)
BP(B) := following code P := L
B := B(B) HB := H(B) P := L
8.6 他の基本的な操作
9. 命令のエンコーディング
命令は様々な方法でエンコード可能である。可能なエンコーディングで、ソ フトウェア・エミュレーションに適したもの、は付録VIに示す。
各オペコードは1バイトを占める。getかput命令の場合、関係するAレジスタの 数を与える別なバイトがこれに引き続く。他のアーギュメントはこれから述 べるように、エンコードされる。
一時か恒久変数の数は1バイトにエンコードされる。定数はフルワード(32bit) の(タグを含んだ)値を与えることによって、エンコードされる。定数の値が符 号拡張付きの16bit値によって得られる場合に、ハーフワード(16bit)表現をサ ポートするための特殊なオペコードが、提供されるだろう。ファンクタは 16bitのファンクタ番号としてエンコードされ、それは、ファンクタのフルワー ド表現を得るためのファンクタ・テーブルへのインデックスとして使用される、 述語と節のアドレスは、アドレス空間の現在の「セグメント」内への16bitオ フセットとして、表現される。つまり、述語か節に対応するフルのアドレスは、 16bitオフセットと、現在の命令のアドレスの上位16bitとをつなぐことによっ て、得られる。セグメント境界を超えるためのなんらかの逃げ道の機構が提供 されなければならない
VAXで許されているように、16bitと32bitのアーギュメントは特に整列させら れている必要は無いことが、想定されている。整列が必要な機械では、正しい 整列を提供するために、コンパイラによって、ダミーの1バイトのスキップ命令 が挿入されてもよい。
命令セットの重要な最適化は、命令を短く(そしてたぶん速く) するために、
数値アーギュメントの小さな値をいくつか作るオペコードを提供することであ
ろう。この最適化の主要な候補は、レジスタAn,Xn,Ynの番号nを与える1バイト
のアーギュメントである、ここでnは小さいとして。
例えば、get_list A3は、新しい命令get_list_3 で置き換えできるだろう。
10. 環境のスタッキング 対 ゴールのスタッキング
現在の設計は「環境スタッキング(environment-stacking)」モデルである。 項が関係している限り非構造共有(non-structure-sharing) な実現であるが、 しかし、構造共有(structure-sharing) はスタック上のゴールを見せるために、 まだ使用されている。
設計の早期の版は、「ゴール・スタッキング(goal-stacking)」モデルを使用 していた。ゴール・スタッキング・モデルは、私の知る限り、実存するすべて のProlog 実現と異なっており、それは、構造共有がまったく無い。構成され た項(構造体)が明示的に表現されているだけではなく、ゴールもそうである。 ゴール・スタックは、実行が残っているゴールのリストの明示的な表現を含ん でいる。 このリストは、まさに、伝統的レゾリューション理論の"resolvent"(解決法) である。これらは、バインディング環境を表現する変数セルへ、ベクタを格納 することを必要としない。
ゴール・スタッキング・モデルの利点は:
しかしながら、ゴール・スタッキングも環境スタッキングに対して、不利なこ ともある:
unsafe変数の取り扱いの問題は、特にシビアである。それが実行時にたくさ んのチェックを要求するからである。環境スタッキング・モデルでは、コンパ イル時の解析が、必要なところにだけ特殊な命令を生成することで、それを大 きく避ける事ができる。この理由から、環境スタッキング・モデルの利点によ り、ゴール・スタッキング・モデルは落ちた。
しかし、環境スタッキング・モデルは早期の設計に強い影響を受けた、 そして、ゴール・スタッキングのソース言語レベルのバリエーションとして見 ることができる。 この視点からすると、環境とは、節の末尾に対応する、コンパイラが生成した ゴールである。ある節:
P :- Q,R,S.は、変換して見ると:
P :-Q,Z1. Z1 :- R,Z2. Z2 :- S.ここでZ1,Z2は環境の引き続く状態に対応している。
11. 非決定的環境でのコピーの長所と短所
今のモデルでは、現在の環境は、スタックのトップにある必要は無い。それ は、引き続くチョイス・ポイントによって"buried"(埋められる)だろう。それ が去って、環境はその元の位置に領域を保存し続け、コピーのオーバヘッドを 避けている。しかし、"埋められた"環境をスタック・トップにコピーすることは いくつかの利点がある:
12. 謝辞
この仕事は、DECの外部研究補助金のサポートを受けた。この研究を可能にし、
励ましてくれた次の方に特別な感謝をする: Peter Jessel, Nils Nilsson,
Michael Poe, Daniel Sgalowicz.
※付録は、
原書 を参照のこと。(英文は無いに等しいので、誰でも読める)
--- EOF