自作レジスタマシン簡易仕様書

今回は前から作ってちょこちょことアドバイスもらったり、紹介したりしていたレジスタマシンがとりあえず納得いく形になりましたのでその仕様をまとめておこうかと思います。(PDFはTwitterだと共有が面倒くさいので、もうブログにしてしまえホトトギスとこうなりました。)

とりあえず現物がないと読んでても何も面白くないのでオンラインIDEで実装したURLがこちら
→Repl.it - 4th register-machine

先に言っておくとパーサー作るのさぼって実装言語であるLispの特定のデータ型のパターンを「プログラム」とか「行」とか言ってます。(オンラインIDEで作ってる以上、実装状況に大きく依存するファイル処理に大きく依存するパーサー書いても空しい、というのと、僕はプログラマーではなくロジシャンなので理論上動くことがわかったらもういいでしょ、となったのが大きな理由です。)
そのためここではレジスタマシンそのものの仕様と、それがLispの中でどう表現されているかの両方を説明します。

0 概要・仕様

今回作成したのは以下で説明するようなプログラムと任意個の引数（自然数、現在はリストとして表現されている）を受け取り、仮想レジスタマシンをエミュレートする関数、register-machine-kerです。コマンドによって命令の内部表現や、実行中の各段階のプログラムカウンタやレジスタの様子を出力することもできます。
仮想レジスタマシンには整数(自然数でなく)で添え字(番地)づけられた自然数が格納できる無限個のレジスタ(メモリー)があり、プログラムの実行開始に際して与えられた引数(仮にn個とする)が1番レジスタからn番レジスタまでに格納され、それ以外のレジスタには0が格納されます。
レジスタマシンは与えられたプログラムを0番目の命令から原則的に番号順に1つづつ実行していき、halt(停止)命令に至った時かつその時に限り、その時点での0番レジスタの値を返して止まります。

第一引数→レジスタマシンのプログラムを後述するようにリストで受け取る。
第二引数→レジスタマシンの実行時の引数を任意の長さのリストとして受け取る。リストの先頭が第一引数となる。
第三引数→内部表現出力フラッグ。#tになっていると、エミュレートを行う前にレジスタマシンのプログラムを多少モディファイした内部表現を標準出力に出力する。作成者である僕のデバッグ用なので基本的には#fを渡しておいてください。
第四引数→プログラムカウンタ逐次出力フラッグ。#tになっているとエミュレート中のプログラムカウンタを標準出力に出力する。
第五引数→レジスタ逐次出力フラッグ。#tになっているとエミュレート中のレジスタ(ただし非負かつ一度でも0でない値になったことがある番地まで)をベクタ形式で標準出力に出力する。

出力→halt命令が実行された時点での0番レジスタの値。

1 基本語彙

「文字」という語彙に関しては読者は十分な直観を持つことができるとします。さしあたっては「アルファベット+数字+いくばくかの記号」程度の認識でも大きな問題は生じません。

Def1.1 プログラム

レジスタマシンのプログラムは「行」からなる0から始まる自然数で添え字づけられた列です。現在は「行」のリストとして表現されています。なおプログラムの「終わり」は明確に定義されておらず、あたかも無限に空行が続いているかのように意味論上扱います。

Def1.2 行

行はシンボルがいくつか区切り文字で区切られて並んだものです。現在はシンボルのリストとして表現されています。

Def1.3 シンボル

シンボルは区切り文字以外の文字からなる文字列です。現在は(Lispの)シンボルとして表現されています。

2.命令

命令とは特定の形をした行です。

Def2.1 命令

命令(command)は以下のいずれかの形をした行です。
$\{\lt label \gt\lt\ labelless{\text -}command\gt\}\\\{\lt labelless{\text -}command\gt\}$
ここで $\lt label \gt$ (ラベル)は「:」で終わる文字列であり、 $\lt labelless{\text -}command\gt$ は以下のいずれかです。
$\{{\rm incr}\lt index\gt (\lt value\gt )\}\\ \{{\rm decr}\lt index \gt\lt jump\gt (\lt value \gt)\}\\\{{\rm save}\lt index\gt\lt value\gt\}\\\{{\rm halt}\}\\\{\}$
$()$ で囲まれているのはその部分が省略可能であること、ローマン体で $\lt\gt$ に囲まれずに書かれている部分はその部分が（ほかの部分のような抽象構文でなく）そのままシンボルであることを意味します。
また見てもらった通り、どの命令にもちょうど一個の $\lt labelless{\text -}command\gt$ が含まれるので、この部分をラベルレスコマンド部分などと呼びます。
$\lt index\gt$ は操作するレジスタのレジスタ番号を、 $\lt jump\gt$ は後述する制御構造において発生する実行する命令番号の強制的な変更(ジャンプ)における移動先の行番号を、 $\lt value\gt$ は操作に際して使用する引数を意味しますが、後述するようにこれらに(数学の教科書に出てくるようなレジスタマシンに比べると)かなり柔軟な表現を許している(ことによって先のリンク先で僕が実際にやって見せたように、何とか手動かつ実行時間も常識的な範囲内で、「階乗」などそれなりに高級な関数を実装することができる)のが今回の仮想機械の特徴です。
しかし、理論上はここに自然数( $\lt index\gt$ には整数)しか書けないとしてもモデルはTuring完全なことが示せますので、ここでは一旦、単に自然数(整数)だと思っていただくことにして次の章でさっさと操作的意味論をやってしまうことにします。またincrとdecrにおいて $\lt value\gt$ を省略した場合、1を引数に取ったかのように振舞います。実際には数学の教科書に出てくるようなレジスタマシンは大抵引数が1に限定されていますし、saveは命令そのものがないことすらあり、それでもなおTuring完全です。その意味では先ほど少し話したような柔軟な表現がなくとも、すでに僕たちはかなり恵まれた境遇にいるとも言えます。

3.操作的意味論

(そんなに形式的にやる気は)ないです。

Def3.1 プログラムカウンタ

プログラムカウンタは自然数でプログラムの行数と対応しており、実行中逐次的に変化する。
実行開始時は0である。

Def3.2 命令サイクル

レジスタマシンは原則として、以下の命令サイクルを単位として挙動する。

プログラムカウンタに対応した行の命令を読み込む。
プログラムカウンタを1進める。
読み込んだ命令を実行する。
1に戻る。

ただし例外として強制的にプログラムカウンタが変更される「ジャンプ」と、実行した時点でプログラムの実行全体が終了する命令の「halt」がある。
注意すべきは、(本物のアセンブリ言語がそうであるように)ある命令の実行中プログラムカウンタはすでに1つ先の命令の行に進んでいることです。

Def3.3 incr命令

ラベルレスコマンド部分がincrで始まる命令はincr命令です。
incr命令は $\lt index\gt$ 番レジスタに格納されている値を $\lt value\gt$ だけ増加させます。

Def3.4 save命令

ラベルレスコマンド部分がsaveで始まる命令はsave命令です。
save命令は $\lt index\gt$ 番レジスタに $\lt value\gt$ を格納します。

Def3.5 decr命令

ラベルレスコマンド部分がdecrで始まる命令はdecr命令です。
他の命令と異なり、decr命令には成功と失敗があります。
$\lt index\gt$ 番レジスタに格納されている値が $\lt value\gt$ 以上ならばdecr命令は成功し、 $\lt index\gt$ 番レジスタに格納されている値を $\lt value\gt$ だけ減らします。
もし、 $\lt index\gt$ 番レジスタに格納されている値が $\lt value\gt$ 以下ならばdecr命令は失敗しジャンプが発生します。
このときプログラムカウンタが $\lt jump\gt$ に強制的に書き換わります。

Def3.6 halt命令

ラベルレスコマンド部分がhaltのみからなる命令はhalt命令です。
halt命令が実行されたときプログラム全体の実行が終了し、その時点での0番レジスタの値がプログラム全体の返り値(結果)になります。

Def3.7 空命令

ラベルレスコマンド部分が空白からなる命令は空命令です。
空命令の実行は何も実行しないことと同じです。

Def3.8 負番地レジスタ

負の番地を持つレジスタは命令によって値を書き換えられても瞬時に0に戻る、と約束します。

4.拡張表現(アドレッシングモード)

Def4.1 $\lt index\gt$ の拡張表現

$\lt index\gt$ として以下の表現を書くことができる。
1.直接参照{記法:[整数](e.g. 2)}
記述された値を番地にもつレジスタを表す。
2.間接参照{記法:p[整数](e.g. p3)}
「pに続く整数を番地にもつレジスタに格納されている値」を番地に持つレジスタを表す。

Def4.2 $\lt value\gt$ の拡張表現

$\lt value\gt$ として以下の表現を書くことができる。
1.即値{記法:[整数](e.g. 2)}
記述された値をそのまま使う。
2.レジスタ値{記法:v[整数](e.g.v2)}
「vに続く整数を番地にもつレジスタに格納されている値」を使う。
3.ポインタ値(間接参照レジスタ値){記法:p[整数](e.g.p2)}
「『pに続く整数を番地にもつレジスタに格納されている値』を番地に持つレジスタに格納されている値」を使う。
4.プログラムカウンタ{記法:pc}
「現在のプログラムカウンタの値」を使う。

Def4.3 $\lt jump\gt$ の拡張表現

$\lt jump\gt$ として以下の表現を書くことができる。
1.即値{記法:[整数](e.g. 2)}
記述された値をそのまま使う。
2.レジスタ値{記法:v[整数](e.g.v2)}
「vに続く整数を番地にもつレジスタに格納されている値」を使う。
3.プログラムカウンタ{記法:pc}
「現在のプログラムカウンタの値」を使う。
4.ラベル名{記法:上記以外の実装言語Lisp上でシンボルとして認識できる文字列}
上記に当てはまらない表現はラベル名とみなされる。「[ラベル名]:」の形の文字列を「[ラベル名]に対応するラベル」と呼び、ラベル名が $\lt jump\gt$ として与えられた場合、対応するラベルで始まる命令が書かれた行へのジャンプとみなされる。

なお $\lt jump\gt$ としてポインタ値を書く構文は現在サポートしていない。
気まぐれで追加するかもしれないが、割といらないと思っている。

ここまでで規約は一通り説明したことになる。

5 典型的なプログラミング手法

いくつかの典型的なプログラミング手法を紹介する。
1. ラベル及び空命令を利用したコメントアウト
 コメントアウトの機能は実装されていないが、(ジャンプには使用しない)ラベルを(場合によっては空命令を作って)張ることによってある程度行うことができる。空白(区切り文字)が入るとラベルとみなされなくなるため、_や-を使うこと。
2. iszero分岐
iszero分岐が必要なら以下のようにする

decr [判定したいレジスタ] then
incr [判定したいレジスタ]
else: {非ゼロの場合の処理}
...
then:{ゼロの場合の処理}

3. 無条件のジャンプ
無条件のジャンプをしたいなら負番地レジスタに対してdecr命令を使えばよい。

4.関数(サブルーチン)コール
以下で関数コールができる。
save [メモ用のレジスタ] pc
incr [メモ用のレジスタ] 2
decr -1 [関数名]
…
[関数名]:{関数の処理}
…
decr -1 v[メモ用のレジスタ]

それでは皆様楽しい計算モデルライフを！

(9/12追記:
やや可読性の高い後継言語として
Repl.it - 5th-register-machine
を作成しました。
仕様は大筋で似ていますが、 $\lt jump\gt$ を$で囲む記法となったこと及びニーモニックに割と大きな変更が入っています。
$\lt index\gt$ の直接参照が「[整数]」から「i[整数]」に、
$\lt value\gt$ 及び $\lt jump\gt$ のレジスタ値が「v[整数]」から「rv[整数]」に、
$\lt value\gt$ のポインタ値が「p[整数]」から「pv[整数]」に
それぞれ変更されています。
また内部表現へのコンパイルと実行を分離したため、register-machine-kerに食わせる前にmodify-commandsで内部表現(ソースコード見るとわかりますが、ジャンプの拡張表現が潰されるだけなので人によっては直接手で書けるかもしれません)化できます。