書きかけの記事もあるけど、ちょいとOISC ( One Instruction set computer) の１つ、subleqで遊んでみよう。

TL;DR : 異なるCPUアーキテクチャに触れると、今まで気が付かなかった当たり前のことにも、きちんと感謝ができる

変数のメモリ上での位置を考えるのは、コンパイラ様がやってくれている。ありがとうございます！
定数を加算する処理は、cpu自体が持っていることが多い。ありがとうございます！
実行部分とデータ部分のメモリ空間が分かれていることで、当然メモリ破壊もしにくい（ちゃんと作れば）ありがとうございます！！

われわれは、複雑化しすぎた命令セットに振り回され過ぎていないだろうか？

ソフトウェアエンジニア、とくに組み込みエンジニアは「SIMDだ」「AVXだ」「FP16だ」「Vector Extensionだ」などと、複雑化しすぎた命令セットに振り回されがちではないだろうか？コンパイラが全部よしなにしてくれるかもしれないが、だが、CPUの性能を最大限発揮するためには避けては通れないのだ。きっと。

さて、大学のコンピュータアーキテクチャ講義で、「単一命令セットコンピュータ」。つまり、命令が１つしかないコンピュータというものは理論上作れる、という話は聞いたことはないだろうか？　つい最近、こんな面白ニュースが飛び込んできた。

SubRISC+では、データからの異常検出やデータ探索をする軽量アルゴリズムをリアルタイムに処理し、警告などのかぎられたデータのみ送信する用途を想定。命令数を4つに限定することで小型/低消費電力化を図った。一方でチューリング完全であり、これらの用途以外の汎用プログラムも処理できるとしている。

命令数が4つ…！！！　これはロマンあふれる！！　とはいえ、現物は当然ないので手元でテストもできない。

だったら、命令数の少ない命令セットの１つである、subleqを動かしてみようという気持ちになってみた。今回はこんな感じ。

subleqって何？

シンプルにいうと、１命令しかない命令セット、もしくは当該命令セットを実行するCPUですね。

    subleq a, b, c   ; Mem[b] = Mem[b] - Mem[a]
                     ; if (Mem[b] ≤ 0) goto c

ここに記載はされていないが、 Mem[b] > 0 であれば、次の命令を実行する。

ただし……　日本語の情報が無い/間違っている

2021/3/14現在、日本のWikipediaの記載は間違っているように思われます。参考にするならば、en版のwikipediaか、https://esolangs.org/wiki/Subleqですね。

subleqのメモリモデル・制約

では、subleqのメモリモデルや制約などを簡単にまとめていく。

メモリ長さは、無限長である
- （現実的ではないので適当に切る）
1要素は、無限幅のsigbed integer
- (現実的ではないので適当にint32_t や int64_t)
- なお、足し算をしたりする都合上、配列要素はunsignedではなくsignedが望ましい。
ロード時に内容が読み込まれなかったメモリは、内容を0とする。
メモリ先端位置0番地から実行を開始する。
subleq命令において、第1引数、第2引数、第3引数が負の数である場合、不正命令となる（原則）
- プログラムでは、第２引数に-1が指定されたら、第1引数で指定されているアドレスの内容を10進数で表示している。
- プログラムでは、第２引数に-2が指定されたら、第2引数で指定されているアドレスの内容を文字として表示している。

ARMやx86との違いは……

レジスタという概念がありません。
- 直接メモリのアドレスを指定するだけです。
addやmovなど、普通ある命令も全部subleq命令に置き換えなければなりません。
プログラムが自分自体の内容を書き換えられる。
- 例えば、あるアドレスの内容を参照したい場合、Operandで読み出す先を指定しているアドレスを直接書き換えます。

subleqをちょっと動かしてみよう

プログラムを終了してみよう

これは標準的な命令ではないので機能拡張で。

subleq -1 -1 0

Mem[-1] はOut of boundaryなメモリアクセスなので、これをプログラム終了コードとする。

データを格納してみよう

通常のプログラムだと、.textやら.bssやら、メモリ用とでメモリがいくつかのブロックに分割されている。

subleqにはそのような複雑な機構はない。プログラム部分も全部データとして使える！！（メモリ破壊できる...)

0d1000 : subleq  0  0 1003 ; Mem[0] =  0, Mem[1] =  0, Mem[3] = 1003

メモリ内容をmov/copyしてみよう

アドレスTの内容を、アドレスXにコピーする場合は一度アドレス[A]を踏み台にして…

0d1000 : subleq A A 1003 ; mem[A] = 0
0d1000 : subleq T A 1006 ; mem[A] = mem[A] - mem[T] = -mem[T]
0d1000 : subleq X X 1009 ; mem[X] = 0
0d1000 : subleq A X 1012 ; mem[X] = mem[X] - mem[A] = mem[T]

メモリ内容をincrement/decrementしてみよう

+1, -1だったら、dataにそれを持たせるのが簡単。レジスタが存在しないので、直接加算・減算するイメージ。

0d1000 : subleq A    A 1006  ; mem[A] = 0
0d1003 : subleq -1  +1    0  ; data 
0d1006 : subleq 1003 A 1009  ; mem[X] = mem[X] - mem[1003] = mem[X] + 1
0d1006 : subleq 1004 A 1012  ; mem[X] = mem[X] - mem[1004] = mem[X] - 1

2つのアドレス内容に応じて、処理を分岐してみよう

0d0000 : subleq  0 0 6  ; _mainまでのジャンプ
                        ; Variable A,B にも流用
0d0003 : subleq  0 1 2  ; Data     X=0,Y=1,Z=2
0d0006 : subleq  0 0 9  ; mem[A] = 0
0d0009 : subleq  3 0 12 ; mem[A] = mem[A]-mem[X] = -mem[X]
0d0012 : subleq  1 1 15 ; mem[B] = 0
0d0015 : subleq  0 1 18 ; mem[B] = mem[B]-mem[A] = mem[X]
0d0018 : subleq  4 1 36 ; mem[B] = mem[B]-mem[Y] = mem[X]-mem[Y]
                        ; mem[B]が0以下ならば36から実行 
0d0021 : subleq  0 0 24 ; mem[A] = 0
0d0024 : subleq  3 0 27 ; mem[A] = mem[A]-mem[X] = -mem[X]
0d0027 : subleq  5 5 30 ; mem[Z] = mem[Z]-mem[Z] = 0
0d0030 : subleq  0 5 33 ; mem[Z] = mem[Z]-mem[A] = mem[X]
0d0033 : subleq  0 0 48 ; goto _END
0d0036 : subleq  0 0 39 ; mem[A] = 0
0d0039 : subleq  4 0 42 ; mem[A] = mem[A]-mem[Y] = -mem[Y]
0d0042 : subleq  5 5 45 ; mem[Z] = mem[Z]-mem[Z] = 0
0d0045 : subleq  0 5 48 ; mem[Z] = mem[Z]-mem[A] = mem[Y]
0d0048 : subleq  5 -1 51 ; mem[Z] を出力
0d0051 : subleq  -1 -1 0 ; 終了

(1)実行結果(X=2,Y=1->Z=2を期待)

Iter 0 : PC=0 Operand = [0 0 6 ]Result = {0 0 6 2 1 2 }
Iter 1 : PC=6 Operand = [0 0 9 ]Result = {0 0 6 2 1 2 }
Iter 2 : PC=9 Operand = [3 0 12 ]Result = {-2 0 6 2 1 2 }
Iter 3 : PC=12 Operand = [1 1 15 ]Result = {-2 0 6 2 1 2 }
Iter 4 : PC=15 Operand = [0 1 18 ]Result = {-2 2 6 2 1 2 }
Iter 5 : PC=18 Operand = [4 1 36 ]Result = {-2 1 6 2 1 2 }
Iter 6 : PC=21 Operand = [0 0 24 ]Result = {0 1 6 2 1 2 }
Iter 7 : PC=24 Operand = [3 0 27 ]Result = {-2 1 6 2 1 2 }
Iter 8 : PC=27 Operand = [5 5 30 ]Result = {-2 1 6 2 1 0 }
Iter 9 : PC=30 Operand = [0 5 33 ]Result = {-2 1 6 2 1 2 }
Iter 10 : PC=33 Operand = [0 0 48 ]Result = {0 1 6 2 1 2 }
Iter 11 : PC=48 Operand = [5 -1 51 ][2]Result = {0 1 6 2 1 2 }
Iter 12 : PC=51 Operand = [-1 -1 0 ]Result = {0 1 6 2 1 2 }... END

-> oMem[5] が 2になっている

(2)実行結果(X=0,Y=1->Z=1を期待)

Iter 0 : PC=0 Operand = [0 0 6 ]Result = {0 0 6 0 1 2 }
Iter 1 : PC=6 Operand = [0 0 9 ]Result = {0 0 6 0 1 2 }
Iter 2 : PC=9 Operand = [3 0 12 ]Result = {0 0 6 0 1 2 }
Iter 3 : PC=12 Operand = [1 1 15 ]Result = {0 0 6 0 1 2 }
Iter 4 : PC=15 Operand = [0 1 18 ]Result = {0 0 6 0 1 2 }
Iter 5 : PC=18 Operand = [4 1 36 ]Result = {0 -1 6 0 1 2 }
Iter 6 : PC=36 Operand = [0 0 39 ]Result = {0 -1 6 0 1 2 }
Iter 7 : PC=39 Operand = [4 0 42 ]Result = {-1 -1 6 0 1 2 }
Iter 8 : PC=42 Operand = [5 5 45 ]Result = {-1 -1 6 0 1 0 }
Iter 9 : PC=45 Operand = [0 5 48 ]Result = {-1 -1 6 0 1 1 }
Iter 10 : PC=48 Operand = [5 -1 51 ][1]Result = {-1 -1 6 0 1 1 }
Iter 11 : PC=51 Operand = [-1 -1 0 ]Result = {-1 -1 6 0 1 1 }... END

-> oMem[5] が 5になっている

うごかしてみた感想

われわれは、どれだけcpu様やコンパイラ様に助けてもらっていたんだろうか……　感謝しかないですね。

変数のメモリ上での位置を考えるのは、コンパイラ様がやってくれている。ありがとうございます！
定数を加算する処理は、cpu自体が持っていることが多い。ありがとうございます！
実行部分とデータ部分のメモリ空間が分かれていることで、当然メモリ破壊もしにくい（ちゃんと作れば）ありがとうございます！！

ソースコード

subleq.h


#ifndef SUBLEQ_H_
#define SUBLEQ_H_

#include <map>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

class Subleq {
private:
	const static int mMemSize = 65536;
	int64_t mMem[mMemSize];
	int64_t mPC;
	map<string,string> mAlias;

public:
	Subleq();
	virtual ~Subleq();

	void load(string fname);
	void run(int _iter);
	bool iter();
	void cont(int _iter);

	int64_t get(const int n) const { return mMem[n]; }
	int64_t getPC() const { return mPC; }
};

#endif /* SUBLEQ_H_ */

subleq.cpp

#include "Subleq.h"

using namespace std;

Subleq::Subleq():mPC(0)
{
	for(auto &it : mMem){
		it = 0;
	}
}

Subleq::~Subleq() {
}


void Subleq::load (string _fname){
	ifstream ifs(_fname);

	int index = 0;
	int line_num = 0;
	mPC = 0;

	string line;
    while (getline(ifs,line)){
    	istringstream ist(line);
    	string oOperand;

    	ist >> oOperand;

    	if ( oOperand == "alias") {
    		string oName, oAddress;
    		ist >> oName >> oAddress;
    		mAlias[oName] = oAddress;
    	}else if ( oOperand == "subleq") {
			string oOP1, oOP2, oOP3;
			ist >> oOP1;
			oOP2 = oOP1;
			oOP3 = to_string( index + 3 );

			if ( ist.eof() == false) {
				ist >> oOP2;
			}
			if ( ist.eof() == false) {
				ist >> oOP3;
			}

			if ( mAlias.find(oOP1) != mAlias.end() ){
				oOP1 = mAlias[oOP1];
			}
			if ( mAlias.find(oOP2) != mAlias.end() ){
				oOP2 = mAlias[oOP2];
			}
			if ( mAlias.find(oOP3) != mAlias.end() ){
				oOP3 = mAlias[oOP3];
			}

			mMem[index++] = atoll( oOP1.c_str() );
			mMem[index++] = atoll( oOP2.c_str() );
			mMem[index++] = atoll( oOP3.c_str() );

			cout << line_num << ":" << oOP1 << " "<< oOP2 << " " << oOP3 << endl;
	    	line_num += 1;

    	}else{
			string oOP1, oOP2, oOP3;
			oOP1 = oOperand;
			ist >> oOP2 >> oOP3;

			mMem[index++] = atoll( oOP1.c_str() );
			mMem[index++] = atoll( oOP2.c_str() );
			mMem[index++] = atoll( oOP3.c_str() );

			cout << line_num << ":" << oOP1 << " "<< oOP2 << " " << oOP3 << endl;
	    	line_num += 1;
    	}
    }
}

bool Subleq::iter (){
	int64_t oA, oB, oC, t = -1;
	oA = mMem [ mPC     ] ;
	oB = mMem [ mPC + 1 ] ;
	oC = mMem [ mPC + 2 ] ;

	if ( oA < 0 ) {
		return false ;
	}

	/*
	 * subleq   A   -1
	 *   -> Aのアドレス内容を 10進数表示
	 * subleq   A   -2
	 *   -> Aのアドレス内容を 文字表示
	 */
	if ( oB == -1 ) {
		t = -1;
		cout << "[" << mMem[ oA ] << "]" ;
	}else if ( oB == -2 ) {
		char c = (mMem[oA]) & 0xFF;
		t = -1;
		cout << "[" << mMem[ oA ] << "]" ;
		cout << "'" << c << "'" ;
	}else if ( oB < 0 ){
		cout << "END-PROCESS";
		return false;
	}else{
		t = mMem [oB] - mMem [oA];
		mMem [oB] = t;
	}

	if ( t <= 0 ) {
		mPC = oC;
	}else{
		mPC += 3;
	}

	return true;
}

void Subleq::cont (int _iter){

	for(int i = 0 ; i < _iter ; i++ ){
		bool ret;
		cout << "Iter " << i << " : PC=" << mPC << " ";
		cout << "Operand = [" ;
		cout << mMem[mPC] << " " << mMem[mPC+1] << " " << mMem[mPC+2] << " " ;
		cout << "]" ;

		ret = iter();

		cout << "Result = {" ;
		for(int j=0;j < 6 ; j++ ){
			cout << mMem[j] << " " ;
		}
		cout << "}" ;

		if ( ret == false ) {
			cout << "... END" << endl;
			break;
		}
		cout << "" << endl;
	}
}

void Subleq::run (int _iter){
	mPC = 0;
	cont(_iter);
}