AARASS-REGI名称設定・仕様更新
今回はずいぶん前から作ってはアドバイスを貰ったり、紹介したりしていたレジスタマシン
に大幅アップデートを入れましたのでまとめておきます。(PDFはTwitterだと共有が面倒くさいので、もうブログにしてしまえホトトギスとこうなりました。)
また今回の仕様からこの仕様および仕様の実装を”AARASS-REGI"と呼称することにし、過去のものも遡ってそう呼びます。
とりあえず現物がないと読んでても何も面白くないのでオンラインIDEで実装したURLがこちら
→https://repl.it/@takumim97/7th-register-machine#main.scm
(コードが目に晒せるサイトとして使ってますが1000行を超えるコードを書くとこのサイトまともに動かないのであとでなんかいい方法を考えます。githubってソフトの共有には向いてるけどこういう実装を合わせてみてもらいたいコードの共有ってどうなんでしょうね…。というか大まかにはブラウザ上で動くJSのインタープリターのはずなのに、なんで1000行やそこらでこんなに重いんでしょう…?アプリとブラウザタブの開きすぎで僕のローカル環境が重いだけって説あります?)
1章.AARASS-REGIについて
1.1 名称・経緯
このAARASS-REGIの仕様や実装を「Aaronさんのレジスタマシン」と呼んでくださる方がいてうれしいのだが、実は一つ悩みがあった。
AARASS-REGIの最大の特徴であると思われる、「ジャンプを(それ専用の命令を用意するのでなく)自然に考えるとpartial functionになるdecr命令のフォローとして用意することによって命令数が減っている」という特徴は、実は僕の学部時代に計算理論の講義を担当していただいた新井敏康先生の講義及び著書で見ることのできるレジスタマシンからいただいたアイデアである(ただし新井先生のレジスタマシンには無条件ジャンプのGOTO命令は存在していた)。また前回までの入出力方法やメモリの初期状態についての制約もまた新井先生のレジスタマシンと同一である(ただし後述するようにこの部分は今回大幅に変更されている)。このようなことからむしろ僕はこれを「新井先生のレジスタマシン」と呼んでいたのである。
しかし新井先生のオリジナルの方のレジスタマシンは「save命令が存在しない。」「halt命令が存在せずプログラムファイルのEOFで停止する。」、「AARASS-REGIでいうincr,decrの引数の「値の表現」がなく、常に1とみなされる。」、「ポインタやラベルなどといった高級な表現はなくすべて自然数で処理される。」、「そもそも機械上の実装を伴ったものではなく仮想上のモデルである。」など、現在のAARASS-REGIとはかなり異なったものである(しかしながら実は僕が開発を始めた当初はAARASS-REGIのようなものを定義するつもりはなく、新井先生のオリジナルのレジスタマシンの実装を目指していた。表現力が貧弱すぎてプログラマの能力と実行時間を考えると事実上まともなプログラムを書けない事の解決策としてAARASS-REGIの初期版が生まれたのである。)。また新井先生本人に確認してみたところ、decr(新井先生のオリジナル版ではDECREMENT)のこの仕様は先生ご自身のアイデアではないらしく、これらのことからAARASS-REGIを「新井先生のレジスタマシン」と呼ぶのはかえって失礼であろうとも思える。そこでこの"AARASS-REGI"の名称を作成した。このレジスタマシンに影響を与えた三つの要素、すなわち実装者である僕自身(Aaron)、キーアイデアを与えてくれた新井先生、そして仕様を拡張する際参考にしたアセンブリ言語からちょうど三字ずつとって組み合わせたものである。
1.2 パラダイム・思想
AARASS-REGIは以下の特徴がある。
1.レジスタマシンとして挙動するチューリング完全なヴァーチャルマシンである。
2.極端に小さな命令セットと、極めて明瞭な操作的意味論を持つ。
3.各AARASS-REGIの実装は実行時に確保できるレジスタの最大個数や一つのレジスタに格納できる自然数の大きさの限界、許容されるプログラムファイルの長さを陽に制限・宣言する必要はなく、実行環境が許す限りとしてよい(がそうすることをAARASS-REGIの仕様として要求するわけではない)。
4.2と3から実装が極めて容易である。
AARASS-REGIはBrainfuckやその亜種と同様に、この命令セットでプログラムを行おうとする者にとってではなく、この処理系を実装する者にとって容易であることを目指すのが特徴と言える。
1.3 命令ファイルの書式とパーサーについて
本記事はAARASS-REGIの命令ファイルの書式とそのパーシングについて、全く何も規定・要求しない(が提案や推奨や許可はするかもしれない)。
各AARASS-REGIの実装は独自の仕様の命令ファイルとそのパーサーを持ってよいし、パーサーを持たず、ヴァーチャルマシンを構築するプログラム上のデータとして命令を管理する実装があってもよい(僕の手元の実装はそうである)。
AARASS-REGIはあくまでもマシンモデルと命令セットとその挙動の仕様である。
1.4 レイヤー構造
AARASS-REGIを動作させる命令表現は、仮想機械を実際に動作させる「コア命令表現」と、コア言語にいくつかの拡張表現を追加したものであり、ごく小さなコンパイラーによってコア言語に簡約される「拡張命令表現」と、さらに高級な表現仕様を含んだ「マクロ表現」に分類される。この記事ではコア言語に要求される仕様について述べる。拡張命令表現およびマクロ表現については別記事を出す。
「AARASS-REGIの実装」とはコア命令表現によって挙動する仮想機械及び拡張命令表現をコア命令表現に、マクロ表現を拡張命令表現に簡約する二つのコンパイラーの組の事を指す。ただし各実装は必要に応じてマクロ表現のコンパイラー、場合によってはさらに拡張命令表現のコンパイラーをも省略してもよい。
2章.基本語彙
2.1 プログラム
AARASS-REGIが処理する(コア命令表現による)プログラムは「命令」の任意の長さの(0-basedに)自然数で添字づけられた列である。プログラムの終わりは必ずしも明確に定義される必要はなく、無限に空命令(後述)が続くように見なしてもよい。
2.2 命令
命令は以下のいずれかの命令ジェネレータ
「incrジェネレータ」
「decrジェネレータ」
「haltジェネレータ」
「emptyジェネレータ」
「putnジェネレータ」
「putcジェネレータ」
にそれぞれ規定される数の引数の表現を続けたものである。各命令ジェネレータについては3章で述べる。
2.3 レジスタ
レジスタはAARASS-REGIの記憶領域であり、整数で添え字づけられている。
またレジスタのうち負の添字(番地)を持つものにはプログラム実行のどの段階でも常に0が格納されており、命令によって値を書き換えられても直ちに0に戻る(ただし書き換えようとする試みがエラーするわけではない)。
実装は-1より小さい番地のレジスタをサポートしなくてもよい。
3章. 命令表現
この章では命令がどのように表現されるかに焦点を当て、各命令の効果は大まかに述べるにとどめる。各命令が詳しくどのような効果を持つかは4章で操作的意味論の一部として与える。
3.1 incr命令
incrジェネレータに「レジスタの表現」と「値の表現」を与えたものがincr命令である。
実装は「値の表現」がない形式のincr命令を許してもよい。その場合「値の表現」として即値の1を受け取ったように見なすことを要求する。
incr命令は大まかには与えられたレジスタに格納された値を増やす命令である。
3.2 decr命令
decrジェネレータに「レジスタの表現」と「継続の表現」と「値の表現」を与えたものがdecr命令である。実装は「値の表現」がない形式のdecr命令を許してもよい。その場合「値の表現」として即値の1を受け取ったように見なすことを要求する。
decr命令は大まかには与えられたレジスタに格納された値を減らす命令であるが、自然数には下限0があるためこの命令は失敗することがあり、その場合にジャンプが引き起こされる。
3.3 save命令
saveジェネレータに「レジスタの表現」と「値の表現」を与えたものがsave命令である。
save命令は大まかには与えられたレジスタに格納された値を強制的に変更する命令である。
3.3 putn命令
putnジェネレータは「値の表現」を受け取りputn命令を作る。
putn命令は大まかには値を出力する命令である。
3.4 putc命令
putcジェネレータは「値の表現」を受け取りputc命令を作る。
putc命令は大まかには文字を出力する命令である。
3.5 halt命令
haltジェネレータは追加の表現を必要とせず、単独でhalt命令を作る。
3.6 空命令
emptyジェネレータは追加の表現を必要とせず、単独で空命令を作る。実装はemptyジェネレータ用に記号を用意せず、空白を持ってこれに変えてもよいし、それが推奨される。
空命令は大まかには「何もしない事」を表す命令である。
3.7 値の表現
各AARASS-REGI実装は値の表現として少なくとも以下の3種類をサポートしなくてはならない。
1.即値表現
自然数の表現を書き込まれ、そのまま値として用いる表現。
2.直接参照表現
整数の表現を書き込まれ、「それを番地に持つレジスタに格納されている自然数」を値として用いる表現。
3.間接参照表現
整数の表現を書き込まれ、「『それを番地に持つレジスタに格納されている自然数』を番地に持つレジスタ」に格納されている自然数を値として用いる表現。
3.8 レジスタの表現
各AARASS-REGI実装はレジスタの表現として少なくとも以下の2種類をサポートしなくてはならない。
1.インデックス
整数の表現を書き込まれ、「それを番地に持つレジスタ」をレジスタとして用いる表現。
2.ポインタ
整数の表現を書き込まれ、「『それを番地に持つレジスタに格納された自然数』を番地に持つレジスタ」をレジスタとして用いる表現。
3.9 継続の表現
継続の表現は値の表現と同等の表現能力のものを要求する。
4章. AARASS-REGIの操作的意味論の概要
4.1 プログラムカウンタ
AARASS-REGIの操作的意味論にはプログラムカウンタ(以下PC)と呼ばれる自然数が重要な役割を果たす。
PCは直感的に言えば「次に実行するべき命令の添字」である。
AARASS-REGIのコアマシンがなんらかのプログラムの実行を始めたときはいつでも、PCは0である。
動作中のAARASS-REGIコアマシンは命令実行中でない場合、PCに等しい添字が割り当てられた命令を探して実行しはじめるが、その直前にPCを1だけ増やす。
そしてその命令の実行が終わると、またPCに等しい添字の命令の実行を行おうとする。
命令のうちdecr命令(後述)だけがプログラムカウンタを強制的に変更する可能性がある。
以降では命令について述べる。
4.2 incr命令
incr命令の実行は、「受け取ったレジスタ」に格納された値を、「受け取った値」だけ増加させる。
4.3 save命令
save命令の実行は、「受け取ったレジスタ」に、「受け取った値」を格納する。
4.4 decr命令
decr命令の実行には「成功」と「失敗」が存在する。
decr命令の「受け取った値」が「受け取ったレジスタ」に格納されている値以下ならばdecr命令は成功し、「受け取ったレジスタ」を「受け取った値」だけ減少させる。
逆に「受け取った値」が「受け取ったレジスタ」に格納されている値より大きけれならば、decr命令は失敗となる。
decr命令は失敗するとレジスタは一切書き換えず、PCを「受け取った継続」に変更する。
4.5 空命令
空命令の実行はレジスタもPCも変更しない。
4.6 halt命令
halt命令も空命令同様レジスタもPCも変更しない。
halt命令が空命令と違うのは、halt命令が実行されたとき、AARASS-REGIコアマシンは動作を終了することである。
4.7 putn命令・putc命令
putn命令及びputc命令は内部状態に関しては完全に空命令と同一である。
しかるにputn命令及びputc命令の実行は「受け取った値」を外部に出力する(「出力」は本記事では定義されない。各実装が対応するデータないし標準出力を含むファイルを割り当てること)。
putn命令は「受け取った値」を自然数として、人間が視覚的に数だと認識できる形式で出力するものである。この書き方はいささか解釈の余地があるが2進数、8進数、10進数、16進数のいずれかが標準的であろう。
putc命令は「受け取った値」を何らかの文字コードを通して文字として出力する。使用する文字コードをこの仕様が規定することはしない。
4.7 初期化
AARASS-REGIコアマシンは、プログラムの実行開始に際して全てのレジスタとPCを0に初期化することを保証する。
拡張命令表現仕様→
マクロ表現仕様→
参考)
新井敏康著,数学基礎論 = Mathematical logic,岩波書店, 2011.5
(実際に直接参考にしたのは先生が講義で扱ったものですが、ほとんど同様のものがこちらに出ています)
