Pコードマシン

pコードマシンとは、プロセッサの一種であるが、ハードウェアではなくソフトウェアで、すなわちエミュレータや仮想機械のようなインタプリタ型のプログラムで実装されることを目的としたものであり、p-code と呼ばれる中間コードを解釈実行する。この用語は、そのような仕様一般を指すこともあるが、多くの仕様はそれぞれ個々の名称を持っている。特にUCSD Pascalの p-Machine を指すことが多い。「p」の意味については、Pascal処理系の場合はPascalの頭文字ともされるが、他言語の場合はpseudoやportableなどとされる。

このコンセプトは1966年ごろ、BCPLのO-codeやニクラウス・ヴィルトのEuler のPとして実装されたのが最初であるが、pコード  と呼ばれるようになったのは1970年代初期であった。pコードを生成する初期のコンパイラとしては、1973年、Nori、Ammann、Jensen、Hageli、Jacobi が開発した Pascal-P コンパイラと、ヴィルトが1975年に開発した Pascal-S コンパイラがある。

ソースコードからコンパイラのコード生成によってpコードが生成され、そのpコードはpコードマシンのエミュレータ、言い換えればインタプリタによって解釈実行される。商業的に十分意味があるとみて、pコードを直接実行するハードウェアが実装された例もある。

1. pコードによる実装の利点と欠点
------------------

1.1. 利点
-------

機械語コードに直接変換するのに比べ、途中でpコードを経由してインタプリタや実行時コンパイラでpコードを実行する方式にはいくつかの利点がある。

移植性が高い。コンパイラを他のプラットフォームに移植する際、小さなpコードインタプリタを移植するほうが簡単である。そうすれば、コンパイラ本体は修正なしで移行できる。
実装が単純化される。コンパイラ作成にあたっては、機械語生成部分は最も複雑な部分の1つである。その点で、pコードを生成する方が簡単である。それによりコンパイラ開発が早くなる。
コードのサイズが小さくなる。pコードは理想的な仮想機械に基づいているため、多くの場合、生成されたpコードは実機の機械語コードよりも小さくなる。
デバッグしやすい。pコードはインタプリタで実行されるため、インタプリタに各種実行時チェックを入れることで本来の機械語では困難なデバッグが可能となる。Pascalのいくつかの実装では、pコードの解釈実行にジャストインタイムコンパイル方式を利用している。ニクラウス・ヴィルトは Pascal の後継である Modula-2 向けの m-code について言及している[1] 。1980年代、イギリスでpコードのプログラムを実行するクロスプラットフォームのオペレーティングシステム Business Operating System  が開発された。UCSD p-System はpコードを使ったマシン非依存の移植性の高いオペレーティングシステムであった。

1.2. 欠点
-------

pコードの最大の欠点は実行速度が遅い点だが、実行時コンパイラを使えばある程度おぎなえることもある。

2. UCSD p-Machine
-----------------

2.1. アーキテクチャ
------------

pコードマシンはスタックマシンであり、ほとんどの命令がスタックからオペランドを持ってきて、結果をスタックに戻す。例えば、add 命令はスタックの先頭2要素を取り出し、加算結果をスタックに戻す。一部の命令は即値オペランドを持つ。Pascalと同様、pコードも型があり、ブーリアン、文字、整数、実数、集合、ポインタが最初から用意されている。

以下に簡単な命令を示す。命令名、実行前のスタック状態、実行後のスタック状態、解説の順に並んでいる。

adi:  ⇒  - 2つの整数の加算adr:  ⇒  - 2つの実数の加算dvi:  ⇒  - 整数の除算inn:  ⇒  - メンバーシップを設定。b1 には i1 が s1 のメンバーかどうかが設定される。idci i1:  ⇒  - 整数定数をスタック上にロードする。mov:  ⇒  - メモリ間のコピーnot:  ⇒  - ブーリアンの否定

2.2. 環境
-------

FORTHやJava仮想マシンのような他のスタックベースの環境とは異なり、pコードマシンはコールスタックとしても使われる1つのスタックしか持たない。マシンの持つ3つのレジスタは、それぞれスタック内の位置を指している。スタックはアドレスの大きくなる方向に成長する。

SP  はスタックのトップを指す。
MP  は現在のスタックフレームの開始位置を指す。
EP  は現在のプロシージャが使っているトップの位置を指す。他に定数域があり、その下に動的メモリアロケーション域がある。NPレジスタ  はヒープの先頭を指す。EPがNPより大きくなった場合、マシンのメモリが使い尽くされたことを示す。

PCレジスタはコード領域で現在実行中の命令を指している。

2.3. 呼出規約
---------

スタックフレームは以下のようになっている:

EP → ローカルスタック SP → ... ローカル変数 ... 引数 ... リターンアドレス 前のEP 動的リンク 静的リンク MP → 関数のリターン値

プロシージャ呼び出しは次のようになる。まず呼び出しは次の命令で開始される。 mst n ここで、//n// は入れ子レベルを指定する。この命令はスタックに印をつける。すなわち現在のスタックフレームの上の5要素ぶんを予約し、以前のEP、動的リンク、静的リンクなどを設定する。呼び出し側は必要な引数を計算してプッシュし、次の命令を実行する。 cup n, p これでユーザープロシージャが呼び出される。この命令はPCをリターンアドレスとしてスタック上にセーブし、そのプロシージャのアドレスを新たなPCとしてセットする。

ユーザープロシージャは次の2つの命令から開始される。 ent 1, i ent 2, j 1番目の命令はSPを MP + //i// にする。2番目の命令は EP を SP + //j// にする。従って、//i// にはローカル変数用の領域サイズを指定し、//j// には命令実行でローカルに必要なスタック領域が指定される。メモリ不足が発生していないかはこの時点でチェックされる。

呼び出し側への復帰は次の命令で行われる。 retC//C//にはリターン型が指定される。リターン値は適切なセルに格納される。p 以外の各型のリターンでは、その値がスタックに置かれたまま呼び出し側に復帰する。

ユーザープロシージャの呼び出しではなく、標準プロシージャ //q// を呼び出す場合は次の命令を使用する。 csp q 標準プロシージャとは、Pascalの標準ライブラリのようなもので、例えば //readln//、//sin//などがある。ただし、//eof// はpコードでは1つの命令となっている。

3. 例
----

1976年、ニクラウス・ヴィルトは単純なpコードマシンを自著 //Algorithms + Data Structures = Programs// で定義した。このマシンには3つのレジスタがある。プログラムカウンタ、スタックベースレジスタ、スタックポインタ である。8種類の命令があり、うち1種  は複数の形式がある。

このマシンのコードは以下のようになる :

const levmax=3; amax=2047; type fct=; instruction=packed record f:fct; l:0..levmax; a:0..amax; end;

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: 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; 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); 8: begin t := t - 1; s[t] := ord end; 9: begin t := t - 1; s[t] := ord end; 10: begin t := t - 1; s[t] := ord end; 11: begin t := t - 1; s[t] := ord end; 12: begin t := t - 1; s[t] := ord end; 13: begin t := t - 1; s[t] := ord end; end; lod: begin t := t + 1; s[t] := s[base + a] end; sto: begin s[base+a] := s[t]; writeln; t := t - 1 end; cal: begin {generate new
block mark} s[t + 1] := base; 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 = 1; writeln; end {interpret};<WtXmlEndTag />

このマシンはヴィルトのPL/0の実行に使われた。PL/0 はコンパイラ開発の教育用に使われたPascalのサブセットである。

4. 脚注
-----

5. 参考文献
-------

Steven Pemberton and Martin Daniels: [2]. ISBN 0-85312-358-6; ISBN 0-13-653031-1
[3] P4 コンパイラとインタプリタのPascalによるソースコード、使用方法
[4]
[5]
[6] - そのフォーク
//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//.

6. 関連項目
-------

Pascal
UCSD Pascal
UCSD p-System
インタプリタ
スレッデッドコード
バイトコード
コンパイラ
実行時コンパイラ
Sweet16