第265回　MySQLの再帰CTEを使ってBrainf*ckを動かしてみる

MySQL 8.0で導入された再帰CTE（WITH RECURSIVE）は、階層構造の走査やグラフ探索に使われることが多い機能です。しかし再帰CTEの本質は「ある行から次の行を生成する反復処理」にあります。この特徴を見ると、再帰CTEは単なるデータ取得機能ではなく、状態遷移を伴う計算を記述できる仕組みとも捉えられます。

そこで今回は、その性質を体感するためにBrainf*ckインタプリタをMySQLの再帰CTEだけで実装してみました。Brainf*ckは8命令だけで構成された難解プログラミング言語の一種で、メモリテープ・命令ポインタ・データポインタという単純な状態を持つ仮想マシンとして動作します。簡単に内容を確認したい人はWikipediaのBrainf*ckの項目に簡単に記載があるので参照してみてください。この「状態を持って1命令ずつ進む」という所が、再帰CTEの「行から次の行を生成する」という評価方式と非常に相性が良いのです。

CTEに関しては、第181回　SQLの共通テーブル式（CTE）を使ってみようで解説されているので、一読していただいてから読んでもらえると理解が進むと思います。

検証環境

Dockerを使用したMySQLを使用します。以下のコマンドでMySQLを起動します。

docker run --name mysql84 --rm -d \
  -e MYSQL_ROOT_PASSWORD=password \
  mysql:8.4

以上で起動したMySQLに対して接続を行います。

$ docker exec -it mysql84 bash
bash-5.1# mysql -uroot -ppassword

いつものMySQLのシェルが表示されたら大丈夫です。

Server version: 8.4.7 MySQL Community Server - GPL

Copyright (c) 2000, 2025, Oracle and/or its affiliates.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql>

CTE（Common Table Expression）とは

第181回　SQLの共通テーブル式（CTE）を使ってみように詳しい説明があるのですが、簡単におさらいをしておきます。

CTEは WITH 名前 AS (クエリ)という形で実行したクエリに名前を付けて再利用できる仕組みになります。

WITH nums AS (
  SELECT 1 AS n UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
  SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL
  SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
)
SELECT n
FROM nums
WHERE MOD(n, 2) = 0
ORDER BY n;

ちょっと冗長ですが、1～9までの連番を生成するnumsというCTEを作成して、その中からクエリを出力するクエリになります。CTEを生成するために固定値でSELECTして、UNION ALLしています。

さらに再帰CTEで書くと、もっとシンプルに書けます。再帰CTEはseedという初期値を決めて、そこから終了条件までの値を勝手にUNIOON ALLしてくれる仕組みです。実際に上のクエリを再帰CTEで書き直したものが、以下のクエリになります。

WITH RECURSIVE nums AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM nums WHERE n + 1 < 10
)
SELECT n
FROM nums
WHERE n % 2 = 0
ORDER BY n;

このようにすっきりと書けます。n+1を繰り返していって、n+1が10より小さい間（つまり9まで）実行する、という仕組みになります。

これらを組み合わせてBrainf*ckを実装していきたいと思います。

Brainf*ckとは？

冒頭でも説明しましたが、8個の命令で構成されているプログラミング言語です。以下にこのプログラミング言語で記述されたhello, world!を書いておきますが、読んでもなんのこっちゃ、となるに違いありません。俗に“⁠難解プログラミング言語⁠”と呼ばれる理由が一目瞭然だと思います。

Brainf*ckでのhello,world!

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

持っている言語機能は、以下の表にある8個になります。

命令	意味
>	データポインタを右へ
<	データポインタを左へ
+	現在セルをインクリメント
-	現在セルをデクリメント
.	現在セルを出力
,	入力
[	ループ開始
]	ループ終了

今回は非常に心苦しいのですが、処理の途中で入力を受け付ける方法が思い浮かばなかったため、,命令は省かせてもらってます。入力は受け付けますが、何もしないで次の命令に進むnop扱いとなってます。

プログラム本体

というわけで、いきなり成果物を持ってきました。以下のparamsの中身の1列目の値（program）を変更することで、任意のBrainf*ckが実行できます。

大きすぎるので、次ではWITH句ごとに区切って説明をしていきます。

WITH RECURSIVE
params AS (
  SELECT
    ',]++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.' AS program,
    128  AS tape_size,
    999 AS max_steps
),

tape_init AS (
  SELECT 0 AS i, JSON_ARRAY(0) AS tape
  UNION ALL
  SELECT i+1, JSON_ARRAY_APPEND(tape, '$', 0)
  FROM tape_init, params
  WHERE i+1 < params.tape_size
),

scan AS (
  SELECT 1 AS pos, JSON_ARRAY() AS stack,
         CAST(NULL AS UNSIGNED) AS open_pos,
         CAST(NULL AS UNSIGNED) AS close_pos
  UNION ALL
  SELECT
    s.pos + 1,
    CASE
      WHEN SUBSTRING(p.program, s.pos, 1) = '['
        THEN JSON_ARRAY_APPEND(s.stack, '$', s.pos)
      WHEN SUBSTRING(p.program, s.pos, 1) = ']'
        THEN JSON_REMOVE(s.stack, CONCAT('$[', JSON_LENGTH(s.stack)-1, ']'))
      ELSE s.stack
    END AS stack,
    CASE
      WHEN SUBSTRING(p.program, s.pos, 1) = ']'
        THEN CAST(JSON_EXTRACT(s.stack, CONCAT('$[', JSON_LENGTH(s.stack)-1, ']')) AS UNSIGNED)
      ELSE NULL
    END AS open_pos,
    CASE
      WHEN SUBSTRING(p.program, s.pos, 1) = ']'
        THEN s.pos
      ELSE NULL
    END AS close_pos
  FROM scan s
  JOIN params p
  WHERE s.pos <= CHAR_LENGTH(p.program)
),
brackets AS (
  SELECT open_pos, close_pos
  FROM scan
  WHERE open_pos IS NOT NULL
),

exec(step, ip, dp, tape, output_txt) AS (
  SELECT
    0 AS step,
    1 AS ip,
    0 AS dp,
    (SELECT tape FROM tape_init ORDER BY i DESC LIMIT 1) AS tape,
    CAST('' AS CHAR(10000)) AS output_txt
  FROM params

  UNION ALL

  SELECT
    e.step + 1,

    CASE SUBSTRING(p.program, e.ip, 1)
      WHEN '>' THEN e.ip + 1
      WHEN '<' THEN e.ip + 1
      WHEN '+' THEN e.ip + 1
      WHEN '-' THEN e.ip + 1
      WHEN '.' THEN e.ip + 1
      WHEN ',' THEN e.ip + 1
      WHEN '[' THEN
        CASE
          WHEN CAST(JSON_EXTRACT(e.tape, CONCAT('$[', e.dp, ']')) AS UNSIGNED) = 0
            THEN b1.close_pos + 1
          ELSE e.ip + 1
        END
      WHEN ']' THEN
        CASE
          WHEN CAST(JSON_EXTRACT(e.tape, CONCAT('$[', e.dp, ']')) AS UNSIGNED) <> 0
            THEN b2.open_pos + 1
          ELSE e.ip + 1
        END
      ELSE e.ip + 1
    END AS ip,

    CASE SUBSTRING(p.program, e.ip, 1)
      WHEN '>' THEN e.dp + 1
      WHEN '<' THEN e.dp - 1
      ELSE e.dp
    END AS dp,

    CASE SUBSTRING(p.program, e.ip, 1)
      WHEN '+' THEN
        JSON_SET(
          e.tape,
          CONCAT('$[', e.dp, ']'),
          (CAST(JSON_EXTRACT(e.tape, CONCAT('$[', e.dp, ']')) AS UNSIGNED) + 1) % 256
        )
      WHEN '-' THEN
        JSON_SET(
          e.tape,
          CONCAT('$[', e.dp, ']'),
          (CAST(JSON_EXTRACT(e.tape, CONCAT('$[', e.dp, ']')) AS UNSIGNED) + 255) % 256
        )
      ELSE e.tape
    END AS tape,

    CASE SUBSTRING(p.program, e.ip, 1)
      WHEN '.' THEN
        CAST(CONCAT(e.output_txt, CHAR(CAST(JSON_EXTRACT(e.tape, CONCAT('$[', e.dp, ']')) AS UNSIGNED))) AS CHAR(10000))
      ELSE e.output_txt
    END AS output_txt

  FROM exec e
  JOIN params p
  LEFT JOIN brackets b1 ON b1.open_pos = e.ip
  LEFT JOIN brackets b2 ON b2.close_pos = e.ip

  WHERE
    e.step < p.max_steps
    AND e.ip BETWEEN 1 AND CHAR_LENGTH(p.program)
    AND e.dp BETWEEN 0 AND (p.tape_size - 1)
)

SELECT output_txt, step, ip, dp
FROM exec
ORDER BY step DESC
LIMIT 1;

params

params AS (
  SELECT
    ',++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.' AS program,
    128  AS tape_size,
    999 AS max_steps
)

ここにはプログラムと動作の設定を入れてあります。program列にはプログラムのコードを、tape_sizeはメモリーテープのサイズを, max_stepsはこのVMが何ステップまで実行してよいかをまとめています。

注意点として、もっと大きいステップのBrainf*ckのプログラムを実行したい場合は、cte_max_recursion_depthのサイズとparamsの中のmax_stepsの数を変更してください。

tape_init

tape_init AS (
  SELECT 0 AS i, JSON_ARRAY(0) AS tape
  UNION ALL
  SELECT i+1, JSON_ARRAY_APPEND(tape, '$', 0)
  FROM tape_init, params
  WHERE i+1 < params.tape_size
)

これはわかりやすく、0からtape_size-1までの配列を0で初期化しています。

scanとbrackets

scan AS (
  SELECT 1 AS pos, JSON_ARRAY() AS stack,
         NULL AS open_pos, NULL AS close_pos
  UNION ALL
  SELECT s.pos + 1,
         CASE ... END AS stack,
         CASE ... END AS open_pos,
         CASE ... END AS close_pos
  FROM scan s
  JOIN params p
  WHERE s.pos <= CHAR_LENGTH(p.program)
),
brackets AS (
  SELECT open_pos, close_pos
  FROM scan
  WHERE open_pos IS NOT NULL
),

scanでは、事前に括弧に対応するポジションを読み取っています。ここで対応する[]構造を事前に特定しています。[の時に指し示しているポインタ値が0であれば、対応する]の所に、]の時に指し示しているポインタの値が0で無ければ、対応する[に処理を戻してあげる必要があるので、対応関係を取得するCTEを作成しています。paramsをglobal変数のごとく扱いたかったため、ON句が無いJOINをしています。

bracketsでopen_posがNULLのものを弾いて、対象が確定したループ構造だけに限定しています。

exec

プログラムは割愛しますが、ここまで得た情報を使用して、1行ずつSUBSTRINGして値を確認しつつ進めていきます。

初期状態はstep 0からカウントしています。ip（Instruction Pointer）は1文字目を指しています。dp（data pointer）は0を指していて、tapeはtape_initで作成したものを、ouput_txtは最終的な出力された文字列なので空文字を指定しています。

動作に関してはカラムごとに見るのがわかりやすいでしょう。

stepに関してはひたすら+1を実行していきます。
ipは[]構造以外は+1していき[]が登場したときに、条件によって前述のbracketsから対応する値を持ってきて飛ばすか、+1をするか決めています。
dpは> 、<のどちらかが出てきたときに+1、-1をしています。
tapeは+、-のどちらかが出てきたときに、対応するdpの中身の値を+1、 -1しています。
output_txtには.の命令が実行されたときにdpの中身を表示しています。

この流れを繰り返すことで、最終的に結果を得ることができます。

まとめ

MySQL 8.0から導入されたCTEを使って、Branf*ckもどきのプログラムを実行してみました。

従来であればストアドプロシージャを使わないと実現できなかったことが、SQLだけでできるようになったのが非常に有用なのではないかと思います。

こんなことやっておいて言うのはあれですが、計算効率的にもあまりよくないと思うので、凝ったことをするのはおすすめできませんが、MySQLのシェルしか手元にない場合に何ができるか考えてみると、おもしろいかもしれません。