Brainf*ck in SQL

Brainf*ck はチューリング完全らしいですよ。
Brainf*ck 自体に興味のある方は、Brainf*ck や Brainfuck - Wikipedia へどうぞ。

WITH
  -- 入力
  Input(id, bf_program, stdin) AS (
    -- Hello, World!と標準出力に出力するプログラム
    SELECT 0, '
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++
++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.', ''

    -- hogeと標準出力に出力するプログラム
    UNION ALL SELECT 1, '
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
++++++++.
+++++++.
--------.
--.', ''

    -- hogeと標準出力に出力するプログラム(ループ版)
    UNION ALL SELECT 2, '
++++++++++[>++++++++++<-]>
++++.+++++++.--------.--.', ''

    -- echo・・・だけど無限ループなのでコメントアウト
    --UNION ALL SELECT 3, '+[>,.<]', 'hoge'
    
    -- 1 + 2を計算し、標準出力に出力するプログラム
    UNION ALL SELECT 4, '
+>++><<
[->>>+<<<]
>>>[-<+<<+>>>]<<
[->>+<<]
>>[-<+<+>>]<
++++++++++++++++++++++++++++++++++++++++++++++++.', ''

    -- 4 * 2を計算し、標準出力に出力するプログラム
    UNION ALL SELECT 5, '
++++>++><<
[-
  >[->>+<<]
  >>[-<+<+>>]
  <<<
]>>
++++++++++++++++++++++++++++++++++++++++++++++++.', ''

    -- 条件分岐のサンプル
    UNION ALL SELECT 6, '
+++++     # {0} = ?
>+++<     # {1} = ?
>[                    # while( {1} ) do
  <[->>+>+<<<]>       #   {2:3} = !{0}
  >>[-<<<+>>>]<<      #   {0}   = !{3}
  >[[-]<<->>]<        #   if({2}) then decr {0}
  -                   #   decr {1}
]<                    # end
++++++++++++++++++++++++++++++++++++++++++++++++.', ''
  )
, BracketTableSrc(id, open_bracket_pos, close_bracket_pos, stack, src, crnt) AS (
    -- 括弧の対応表の元データ
    -- スタックに開き括弧のインデックスをpushし、
    -- 閉じカッコを見つけ次第そのインデックスとスタックに積まれているインデックスを取り出して、
    -- open_bracket_posとclose_bracket_posに格納する。
    -- 後戻りが発生しないので、文字列消費型(srcがどんどん減っていく)で構成。
    SELECT
        id
      , 0
      , 0
      , CAST('' AS varchar(max))
      , bf_program
      , 1
    FROM
        Input
    UNION ALL
    SELECT
        id
        -- スタックのtopにあるインデックスを設定
      , CASE LEFT(src, 1)
        WHEN ']' THEN CAST(LEFT(stack, CHARINDEX(' ', stack, 1)) AS int)
                 ELSE 0
        END
        -- 閉じカッコのインデックスを設定
      , CASE LEFT(src, 1)
        WHEN ']' THEN crnt
                 ELSE 0
        END
        -- 開き括弧ならスタックにインデックスをpushし、
        -- 閉じカッコならスタックからpopする
      , CASE LEFT(src, 1)
        WHEN '[' THEN CAST(crnt AS varchar(4)) + ' ' + stack
        WHEN ']' THEN SUBSTRING(stack, CHARINDEX(' ', stack, 1) + 1, LEN(stack))
                 ELSE stack
        END
        -- 消費した文字列を取り除いたものが次のsrcになる
      , SUBSTRING(src, 2, LEN(src))
      , crnt + 1
    FROM
        BracketTableSrc
    WHERE
        src <> ''
  )
, BracketTable(id, open_bracket_pos, close_bracket_pos) AS (
    -- open_bracket_posとclose_bracket_posがどちらも格納されているデータのみ抜き出す
    -- このテーブルをひくことで対応括弧のインデックスが取得できる
    SELECT
        id
      , open_bracket_pos
      , close_bracket_pos
    FROM
        BracketTableSrc
    WHERE
        open_bracket_pos <> 0
          AND close_bracket_pos <> 0
  )
, Eval(id, array, ptr, input_pgm, crnt, stdout, stdin) AS (
    -- Brainf*ckの評価エンジン
    -- ループが存在するので、文字列消費型ではなく、
    -- オリジナル文字列とインデックスによる方法(input_pgmは変わらず、crntが変わる)を使用している。
    SELECT
        id
        -- Brainf*ckが使用する配列は5000に制限
        -- SQL Serverに限らず、一行のサイズが制限されていることは多いので一応。
        -- 初期状態は全て(数値の)0
      , CAST(REPLICATE(CHAR(0), 5000) AS char(5000))
      , 1   -- ポインタの初期状態はSQLの文字列のインデックスが1からなので1
      , bf_program
      , 1
      , CAST('' AS nvarchar(max))   -- 標準出力は最初空
      , stdin                       -- 標準出力はInputのものをそのまま使う
    FROM
        Input
    UNION ALL
    SELECT
        id
      , CAST(
          -- 現在見ている文字が+、-、,のいずれかなら配列を操作する
          CASE SUBSTRING(input_pgm, crnt, 1)
          WHEN '+' THEN STUFF(array, ptr, 1, CHAR(ASCII(SUBSTRING(array, ptr, 1)) + 1))
          WHEN '-' THEN STUFF(array, ptr, 1, CHAR(ASCII(SUBSTRING(array, ptr, 1)) - 1))
          -- 標準入力にも一応対応。標準入力を一番最初に与えておかなければいけないのはSQLの限界ですね
          WHEN ',' THEN STUFF(array, ptr, 1, LEFT(stdin, 1))
                   ELSE array
          END
        AS char(5000))
        -- 現在見ている文字が>か<ならポインタを操作する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN '>' THEN ptr + 1
        WHEN '<' THEN ptr - 1
                 ELSE ptr
        END
      , input_pgm
        -- 現在見ている文字が[か]ならインデックスを操作する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN '[' THEN CASE ASCII(SUBSTRING(array, ptr, 1))
                      WHEN 0 THEN (SELECT close_bracket_pos FROM BracketTable
                                   WHERE Eval.id = BracketTable.id AND open_bracket_pos = crnt) + 1
                             ELSE crnt + 1
                      END
        WHEN ']' THEN (SELECT open_bracket_pos FROM BracketTable
                       WHERE Eval.id = BracketTable.id AND close_bracket_pos = crnt)
                 ELSE crnt + 1
        END
        -- 現在見ている文字が.なら標準出力に追記する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN '.' THEN stdout + SUBSTRING(array, ptr, 1)
                 ELSE stdout
        END
        -- 現在見ている文字が,なら標準入力から消費する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN ',' THEN SUBSTRING(stdin, 2, LEN(stdin))
                 ELSE stdin
        END
    FROM
        Eval
    WHERE
        crnt <= LEN(input_pgm)
  )
, Result(id, stdout) AS (
    SELECT
        id
      , stdout
    FROM
        Eval P
    WHERE
        crnt = (SELECT MAX(crnt) FROM Eval C WHERE P.id = C.id)
  )
SELECT * FROM Result ORDER BY id
OPTION (MAXRECURSION 32767)

実装には以下の書籍を参考にしました。超感謝！
カッコのネストのロジックはそのままです。

Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~

Brainf*ck のプログラムは、Brainf*ck をそのまま使わせていただきました。

他に特筆すべきは、スタックの構造を「文字列の先頭が top になるように」変更したところですかね。
気付いてしまえば大したものじゃないんですけど、文字列の末尾を top にしていた逆ポーランド記法の電卓では、REVERSE 関数使いまくりで訳分からんコードになっていました。
それがこちらでは超すっきり記述できています。

実行結果

id	stdout
0	Hello World!
1	hoge
2	hoge
4	3
5	8
6	2

何が言いたい？

えー、Brainf*ck はチューリング完全なので、Brainf*ck が実装できる SQL、少なくとも SQL Server もまたチューリング完全であることが証明されました！
誰だ！ SQL がチューリング完全じゃないなんて言ってるのは！！