Pコードマシン
出典: フリー百科事典『ウィキペディア（Wikipedia）』
Pコードマシン（Pseudo-Code Machine）とは、CPUの仕様であり、その機械語がハードウェアではなくソフトウェアで（すなわちインタプリタで）実行されることを目的としたものである。この用語は、そのような仕様一般を指すこともあるが、多くの仕様はそれぞれ個々の名称を持っている（Javaの使用するバイトコードなど）。特にUCSD Pascalの P-Machine を指すことが多い。
このコンセプトは1966年ごろ、BCPLの O-code として実装されたのが最初であるが、Pコードと呼ばれるようになったのは1970年代初期であった。Pコードを生成する初期のコンパイラとしては、1973年、Nori、Ammann、Jensen、Hageli、Jacobi が開発した Pascal-P コンパイラと、ニクラウス・ヴィルトが1975年に開発した Pascal-S コンパイラがある。
Pコードに翻訳されたプログラムは、そのCPU仕様の動作をエミュレートするソフトウェアによって「実行」される。商業的に十分意味があれば、その仕様でハードウェアが実装されることもある（例えば、Pascal MicroEngine）。
目次 |
[編集] 何故 Pコードなのか？
- 移植性を高めるため。コンパイラを他のプラットフォームに移植する際、小さなPコードインタプリタを移植するほうが簡単である。そうすれば、コンパイラ本体は修正なしで移行できる（再コンパイルは必要）。
- コンパイラ開発を早めるため。コンパイラ作成にあたっては、機械語生成部分は最も複雑な部分の1つである。その点で、Pコードを生成する方が簡単である。
- サイズ削減のため。Pコードは理想的な仮想機械に基づいているため、多くの場合、生成されたPコードは実際の機械語に翻訳されたプログラムよりも小さくなる。
- デバッグ性の改善のため。Pコードはインタプリタで実行されるため、インタプリタに各種実行時チェックを入れることで本来の機械語では困難なデバッグが可能となる。
BASICやPascalのいくつかの実装では、Pコードはジャストインタイムコンパイル方式で実際の機械語に翻訳される。ニクラウス・ヴィルトは Pascal の後継である Modula-2 向けの m-code について言及している[1] 。1980年代、イギリスでPコードのプログラムを実行するクロスプラットフォームのオペレーティングシステム Business Operating System (BOS) が開発された。UCSD p-System はPコードを使ったマシン非依存の移植性の高いオペレーティングシステムであった。
[編集] アーキテクチャ
Pコードマシンはスタック指向であり、ほとんどの命令がスタックからオペランドを持ってきて、結果をスタックに戻す。例えば、add 命令はスタックの先頭2要素を取り出し、加算結果をスタックに戻す。一部の命令は即値オペランドを持つ。Pascalと同様、Pコードも型があり、ブーリアン(b)、文字(c)、整数(i)、実数(r)、集合(s)、ポインタ(a)が最初から用意されている。
以下に簡単な命令を示す。命令名、実行前のスタック状態、実行後のスタック状態、解説の順に並んでいる。
- adi: （i1 i2）⇒ (i1+i2）、2つの整数の加算
- adr: （r1 r2）⇒（r1+r2）、2つの実数の加算
- dvi: （i1 i2）⇒（i1/i2）、整数の除算
- inn: （i1 s1）⇒（b1）、メンバーシップを設定。b1 には i1 が s1 のメンバーかどうかが設定される（true/false）。
- idci i1: （）⇒（i1）、整数定数をスタック上にロードする。
- mov: （a1 a2）⇒（）、メモリ間のコピー
- not: （b1）⇒（~b1）、ブーリアンの否定
[編集] 環境
FORTHやJava仮想マシンのような他のスタックベースの環境とは異なり、Pコードマシンはコールスタックとしても使われる1つのスタックしか持たない。マシンの持つ3つのレジスタは、それぞれスタック内の位置を指している。スタックはアドレスの大きくなる方向に成長する。
- SP はスタックのトップを指す。
- MP は現在のスタックフレームの開始位置を指す。
- EP は現在のプロシージャが使っているトップの位置を指す。
他に定数域があり、その下に動的メモリアロケーション域がある。NPレジスタはヒープの先頭（最低位アドレス）を指す。EPがNPより大きくなった場合、マシンのメモリが使い尽くされたことを示す。
PCレジスタはコード領域で現在実行中の命令を指している。
[編集] 呼出規約
スタックフレームは以下のようになっている:
EP ->
ローカルスタック
SP -> ...
ローカル変数
...
引数
...
リターンアドレス（前のPC）
前のEP
動的リンク（前のMP）
静的リンク（外側のプロシージャのMP）
MP -> 関数のリターン値
プロシージャ呼び出しは次のようになる。まず呼び出しは次の命令で開始される。
mst n
ここで、n は入れ子レベルを指定する（Pascalではプロシージャが入れ子になりうることに注意）。この命令はスタックに印をつける。すなわち現在のスタックフレームの上の5要素ぶんを予約し、以前のEP、動的リンク、静的リンクなどを設定する。呼び出し側は必要な引数を計算してプッシュし、次の命令を実行する。
cup n, p
これでユーザープロシージャが呼び出される（n は引数の個数、p はプロシージャのアドレス）。この命令はPCをリターンアドレスとしてスタック上にセーブし、そのプロシージャのアドレスを新たなPCとしてセットする。
ユーザープロシージャは次の2つの命令から開始される。
ent 1, i ent 2, j
1番目の命令はSPを MP + i にする。2番目の命令は EP を SP + j にする。従って、i にはローカル変数用の領域サイズを指定し（引数および余分に5要素分も予約する）、j には命令実行でローカルに必要なスタック領域が指定される。メモリ不足が発生していないかはこの時点でチェックされる。
呼び出し側への復帰は次の命令で行われる。
retC
Cにはリターン型（上述の基本型 i, r, c, b, a と何も返さない場合の p）が指定される。リターン値は適切なセルに格納される。p 以外の各型のリターンでは、その値がスタックに置かれたまま呼び出し側に復帰する。
ユーザープロシージャの呼び出し(cup)ではなく、標準プロシージャ q を呼び出す場合は次の命令を使用する。
csp q
標準プロシージャとは、Pascalの標準ライブラリのようなもので、例えば readln()（"csp rln"）、sin()（"csp sin"）などがある。ただし、eof() はPコードでは1つの命令となっている。
[編集] 例
1976年、ニクラウス・ヴィルトは単純なPコードマシンを自著 Algorithms + Data Structures = Programs で定義した。このマシンには3つのレジスタがある。プログラムカウンタ(p)、スタックベースレジスタ(b)、スタックポインタ(t) である。8種類の命令があり、うち1種（opr）は複数の形式がある。
このマシンのコードは以下のようになる:
procedure interpret;
const stacksize = 500;
var p,b,t: integer; {program-, base-, topstack-registers}
i: instruction; {instruction register}
s: array [1..stacksize] of integer; {datastore}
function base(l: integer): integer;
var b1: integer;
begin b1 := b; {find base l levels down}
while l > 0 do
begin b1 := s[b1]; l := l - 1
end;
base := b1
end {base};
begin writeln(' start pl/0');
t := 0; b := 1; p := 0;
s[1] := 0; s[2] := 0; s[3] := 0;
repeat i := code[p]; p := p + 1;
with i do
case f of
lit: begin t := t + 1; s[t] := a end;
opr: case a of {operator}
0: begin {return}
t := b - 1; p := s[t + 3]; b := s[t + 2];
end;
1: s[t] := -s[t];
2: begin t := t - 1; s[t] := s[t] + s[t + 1] end;
3: begin t := t - 1; s[t] := s[t] - s[t + 1] end;
4: begin t := t - 1; s[t] := s[t] * s[t + 1] end;
5: begin t := t - 1; s[t] := s[t] div s[t + 1] end;
6: s[t] := ord(odd(s[t]));
8: begin t := t - 1; s[t] := ord(s[t] = s[t + 1]) end;
9: begin t := t - 1; s[t] := ord(s[t] <> s[t + 1]) end;
10: begin t := t - 1; s[t] := ord(s[t] < s[t + 1]) end;
11: begin t := t - 1; s[t] := ord(s[t] >= s[t + 1]) end;
12: begin t := t - 1; s[t] := ord(s[t] > s[t + 1]) end;
13: begin t := t - 1; s[t] := ord(s[t] <= s[t + 1]) end;
end;
lod: begin t := t + 1; s[t] := s[base(l) + a] end;
sto: begin s[base(l)+a] := s[t]; writeln(s[t]); t := t - 1 end;
cal: begin {generate new block mark}
s[t + 1] := base(l); s[t + 2] := b; s[t + 3] := p;
b := t + 1; p := a
end;
int: t := t + a;
jmp: p := a;
jpc: begin if s[t] = 0 then p := a; t := t - 1 end
end {with, case}
until p = 0;
write(' end pl/0');
end {interpret};
このマシンはヴィルトのPL/0の実行に使われた。PL/0 はコンパイラ開発の教育用に使われたPascalのサブセットである。
[編集] 参考文献
- Steven Pemberton and Martin Daniels: Pascal Implementation: The P4 Compiler and Interpreter. ISBN 0-85312-358-6; ISBN 0-13-653031-1
- Steven Pemberton's page on Pascal P4 コンパイラとインタプリタのPascalによるソースコード、使用方法、 the P-code of the compiler がある（セルフコンパイルで生成）。
- The Jefferson Computer Museum's page on the UCSD P-System
- Open Source implementation
- Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624
- Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6
- The Byte Book of Pascal, Blaise W. Liffick, Editor, 1979, ISBN 0-07-037823-1
- PASCAL - The Language and its Implementation, Edited by D.W. Barron, 1981, ISBN 0-471-27835-1. Especially see the articles Pascal-P Implementaion Notes and Pascal-S: A Subset and its Implementation.
