☝️

subleqの再実装

2025/04/28に公開

scheme

gauche

tech

前段

枯れたゲーム機のエミュレーターを再実装したかったが前提知識の不足を感じたので、極限までハードルを下げた。結果、esolangのCPUインタプリタに取り組むことになったのでした。

subleqの紹介

SUBLEQ（SUBtract and branch if Less than or EQual to zero）は、1命令セット計算機（OISC）の一つ、シンプルなCPUインタプリタです。

制約を満たせばチューリング完全性になる。今記事ではメモリが有限なので違う。

制約

命令セットは1つのみ：「メモリアドレスAの値をメモリアドレスBの値から引き、結果をBに格納し、結果が0以下なら命令アドレスCにジャンプする」

SUBLEQ a, b, c
Mem[b] := Mem[b] - Mem[a]
if (Mem[b] ≤ 0) goto c

各命令は3つのオペランド（A B C）で構成される
- A：引く値が格納された場所のアドレス
- B：引かれる値が格納され、結果が格納される場所のアドレス
- C：結果が0以下の場合にジャンプする命令のアドレス
プログラムはメモリ上に連続して配置され、通常は0番地から始まる
メモリセルのサイズは実装により異なる（理論上はチューリング完全性のために無制限）
入出力は多くの実装ではメモリマップド方式で行われる（例：-1番地に対する操作で文字出力）
条件分岐は減算の結果によってのみ制御される
負の数を計算できる
プログラムの終了は通常、負のアドレスへのジャンプによって行われる

実装

https://github.com/aosjmi/subleq

C言語

まずは無難に実装しました。

#include <stdio.h>

#define BYTES (9999)

static int pc = 0; 
static int mem[BYTES];

static void subleq(){ // *命令はこれだけ*
  int a = mem[pc++],b = mem[pc++],c = mem[pc++];
  if(a < 0) mem[b] += (int)getchar();
  else if(b < 0) printf("%c", (char)mem[a]);
  else if((mem[b] -= mem[a]) <= 0) pc = c;
}

int main(int argc, char *argv[]) {
    FILE *fin = fopen(argv[1], "r");
    int *i = mem;     
    while(fscanf(fin, "%d", i++) > 0);
    while(pc >= 0) subleq();    
    return 0;
}

今回は命令が一つで簡単でしたが、命令が複数になった時の大きなswitchに取り組むのを想像すると気が遠くなります。

Scheme/Gauche

次はc言語の無難なコードを見ながらGaucheで実装しました。

(use gauche.uvector)
(use gauche.generator)

(define (subleq prg)
  (let ((m (rlet1 v (make-s32vector 9999 0) 
            (vector-for-each-with-index (^[i n] (set! (~ v i) n)) prg))))
    (letrec ((run (^[pc]
              (if (or (< pc 0) (>= pc 9996))
                  #f
                  (let ((a (~ m pc)) (b (~ m (+ pc 1))) (c (~ m (+ pc 2))))
                    (when (or (not (= a b c 0)) (= pc 0))
                      (newline)
                      (format #t "~4d | ~5d ~5d ~5d | " pc a b c))
                    (inc! pc 3)
                    (cond ((< a 0) (let1 i (read-byte)
                                         (unless (eof-object? i) 
                                        (inc! (~ m b) i)))
                                    (run pc))
                          ((< b 0) (write-char (integer->char (~ m a)))
                                    (run pc))
                          (else    (dec! (~ m b) (~ m a))
                                   (run (if (<= (~ m b) 0) c pc)))))))))
      (run 0))))
(define (main args)
  (display "   pc|     a     b     c |output\n")
  (display "-----|-------------------|------")
  (subleq (list->vector 
            (with-input-from-file (cadr args)
              (^[] (generator->list (cut read))))))
  0)

以下のコンテクストが初見だったので苦痛でしたが、わくわく関数辞典1とわくわく関数辞典2のおかげで楽しく乗り切ることができ、末尾再帰に触れられて嬉しい内容でした。

rlet1 letrec with-input-from-file list->vector vector-for-each-with-index read-byte eof-object? inc! write-char integer->char dec! cadr ~ ^[] cut let1 make-s32vector generator->list

サンプルコード&解説

hello world

hello subleqを標準出力します。

input

39 -1 3
40 -1 6
41 -1 9
42 -1 12
43 -1 15
44 -1 18
45 -1 21
46 -1 24
47 -1 27
48 -1 30
49 -1 33
50 -1 36
0 0 -1
104 101 108
108 111 32
115 117 98
108 101 113

output

pcはプログラムカウンタ
abcは制約上で示したabc
outputは標準出力されたモノです。

   pc|     a     b     c |output
-----|-------------------|------
   0 |    39    -1     3 | h
   3 |    40    -1     6 | e
   6 |    41    -1     9 | l
   9 |    42    -1    12 | l
  12 |    43    -1    15 | o
  15 |    44    -1    18 |  
  18 |    45    -1    21 | s
  21 |    46    -1    24 | u
  24 |    47    -1    27 | b
  27 |    48    -1    30 | l
  30 |    49    -1    33 | e
  33 |    50    -1    36 | q
  36 |     0     0    -1 | %

制約においてbが負の値の時はaの指すアドレスの値をASCIIコードとして読み取り、標準出力します。
例えば最初の39 -1 3はa=39 b=-1 c=3となり、この場合cの値に意味はなくaとbのみが機能します。0から始まり39番目の104を参照して、104に対応するASCIIコードはHなのでHが出力される。

((< b 0) (write-char (integer->char (~ m a)))

0 0 -1で(b - a)<=0となりcへジャンプする。cは負の値を返し、再帰が終わる。

 (else    (dec! (~ m b) (~ m a))
                                   (run (if (<= (~ m b) 0) c pc))))))

反復処理でhello

input

12 12 3
36 37 6
37 12 9
37 37 12
0 -1 15
38 36 18
12 12 21
53 37 24
37 12 27
37 37 30
36 12 -1
37 37 0
39 0 -1
72 101 108
108 111 44
32 87 111
114 108 100
33 10 53

output

   pc|     a     b     c |output
-----|-------------------|------
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    39    -1    15 | H
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    40    -1    15 | e
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    41    -1    15 | l
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    42    -1    15 | l
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    43    -1    15 | o
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    44    -1    15 | ,
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    45    -1    15 |  
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    46    -1    15 | W
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    47    -1    15 | o
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    48    -1    15 | r
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    49    -1    15 | l
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    50    -1    15 | d
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    51    -1    15 | !
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    52    -1    15 | 
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 |

大きいので最初の部分だけ解説する。

   pc|     a     b     c |output
-----|-------------------|------
   0 |    12    12     3 | 
   3 |    36    37     6 | 
   6 |    37    12     9 | 
   9 |    37    37    12 | 
  12 |    39    -1    15 | H
  15 |    38    36    18 | 
  18 |    12    12    21 | 
  21 |    53    37    24 | 
  24 |    37    12    27 | 
  27 |    37    37    30 | 
  30 |    36    12    -1 | 
  33 |    37    37     0 | 
   0 |    12    12     3 |

pc=0はm[12]=0なので0-0となり、制約によってpc=3
- (ジャンプしなくてもpcは3毎進むけど、出力せず値の変化なしなら0-0をする)
pc=3はm[37] -= m[36]つまり m[37] = -39
pc=6はm[12] -= m[37]つまりm[12] = -(-39) = 39
- m[39]にHのASCIIコードがあり、ここで出力するための準備が整った
pc=9はb - a = 0でpc=12
pc=12はb<0なので、アドレス12の指すm[39]=72がASCIIコードで出力される。
- H
pc=15はm[38]=-1なのでm[36]-=m[38]つまりm[36] = 39 -(-1) = 40
- m[40]にはeのASCIIコード101がある。m[41]以降も
pc=18はm[12]-m[12]でm[12]=0にする。pc=21
pc=21はm[37]-=m[53]つまりm[37]=0-53=-53 pc=24
pc=24はm[12]-=m[37]つまりm[12]=-(-53)=53
pc=27はm[37]-=m[37]つまりm[37]=0 pc=30
pc=30はm[12]-=m[36]つまりm[12]=53 - 40 = 13
pc=33はm[12]-m[12]つまりm[12]=13 - 13 = 0 b<=0よりpc=0へジャンプ

と続いていきます。pc=15で加算した数値の指すアドレスが次の文字列であるeで最終的にはhello,world!と出力される。

条件分岐

AとBの値を比較して、出力を変える。

input

36 37 15
30 -1 6
32 -1 9
31 -1 12
0 0 -1
30 -1 18
33 -1 21
34 -1 24
31 -1 27
0 0 -1
65 66 60
62 61 -1
A B -1  // here!!!

output

A=30,B=100

   pc|     a     b     c |output
-----|-------------------|------
   0 |    36    37    15 | 
   3 |    30    -1     6 | A
   6 |    32    -1     9 | <
   9 |    31    -1    12 | B
  12 |     0     0    -1 | %

A=100,B=30
A=150,B=150

   pc|     a     b     c |output
-----|-------------------|------
   0 |    36    37    15 | 
  15 |    30    -1    18 | A
  18 |    33    -1    21 | >
  21 |    34    -1    24 | =
  24 |    31    -1    27 | B
  27 |     0     0    -1 | %

比較した結果でジャンプ先を変えている。

ループ

input

output

101から1まで除算されるまでループ
   0 |     3     4     6 | 
   6 |    12    13    15 | 
   9 |     3     4     0 | 
   0 |     3     4     6 | 
   6 |    12    13    15 | 
  15 |    27    -1    18 | E
  18 |    28    -1    21 | N
  21 |    29    -1    24 | D
  24 |     0     0    -1 | %

所感

エミュレータのシンプルな実装を求めるとesolangかつCPUエミュレータのsubleqがあって、データを処理するならエミュもコンパイラも処理系で同根なんだなと思った。処理ということ。

schemeの体験は良かった。

lisp系は再帰の入門に最適な構文だった。再帰もfor文みたいにフラットに扱いたい。

最後までご覧いただきありがとうございます。

参考資料

https://esolangs.org/wiki/Subleq
https://srfi.schemers.org/

前段

subleqの紹介

制約

実装

C言語

Scheme/Gauche

サンプルコード&解説

hello world

input

output

反復処理でhello

input

output

条件分岐

input

output

ループ

input

output

所感

参考資料

Discussion