Vimは万能 (証明編)

この記事は, Vim Advent Calendar 2022 19日目 の記事です.

僭越ながら初参加させて頂きます.よろしくお願いいたします.

はじめに

Vimは非常に便利で,今やこれをなくして生活することはできません.こんなVimをより崇拝すべく,本記事ではVimが万能であること,曲解して言い換えてチューリング完全であることを証明したいと思います.
なお,Vimの基本操作は理解していることを前提に話を進めていきます.Vimを使用したことがないなど,基本操作に疎い方は本記事内の証明に必要な機能を紹介する準備編の記事がありますので先にこちらを拝読ください.

チューリング完全性の証明

チューリング完全であることを示すための方針は簡単です.チューリング完全はあらゆるチューリングマシンを再現できるような万能チューリングマシンに対して呼ばれます.つまり,あるチューリングマシンが何らかの万能チューリングマシンを再現できれば,間接的にそのチューリングマシンはあらゆるチューリングマシンを再現できることになり,チューリング完全性が証明されます.
再現する万能チューリングマシンは何でも良いですが,今回はBrainfu*kを採用しました.VimでBrainfu*kを再現することでVimチューリング完全性を証明します.

Brainfu*k

Brainfu*kは8個の命令からなるシンプルなプログラミング言語です.0で初期化された配列とその配列に対する1つのポインタだけを持ち,次に示す規則を順に適用させます.

+ ポインタが指す値をインクリメントする
- ポインタが指す値をデクリメントする
> ポインタをインクリメントする
< ポインタをデクリメントする
. ポインタが指す値を出力する
, 入力から1バイト読み込んでポインタが指す値に代入する
[ ポインタが指す値が0なら対応する ] にジャンプする
] ポインタが指す値が0でないなら対応する [ にジャンプする

例えば次に示すBrainfu*kコードは以下のように動作します.ただし,->はポインタとします.

++[->+<]
->0 0 0... 初期状態
->1 0 0... +
->2 0 0... +
->2 0 0... [ (0でないので何もしない)
->1 0 0... -
1 ->0 0... >
1 ->1 0... +
->1 1 0... <
->1 1 0... ] (0でないので [ にジャンプ,つまり繰り返し)
->0 1 0... -
0 ->1 0... >
0 ->2 0... +
->0 2 0... <
->0 2 0... ] (0なので何もしない)

VimコマンドでBrainfu*k

では早速本章にてBrainfu*kを再現していきます.なおEXコマンドなどを使用するとあまりに簡単なので,純粋なVimコマンドのみで再現します.

表記上の注意

EscキーやCtrl+Aなどを押下して得られる特殊な文字は本記事上では正常に表示されないため,以下の表記を用いることとします.

Esc <Esc>
Ctrl+* <C-*>
Enter <CR>もしくは単に改行

全体設計

再現の方針は次の通りです.

  1. Brainfu*kの各命令と等価なVimコマンドを考える
  2. 前処理後処理を含めてBrainfu*kコードを置換してVimコマンド列を作成する
  3. vim -s {コマンドファイル} {入力ファイル}でコマンドを実行してBrainfu*kと等価な出力を得る

早速等価なVimコマンドを考えていきたいところですが,そもそもBrainfu*k実行に必要な0で初期化された配列やポインタがVimコマンドには存在しません.しかし,Vimには現在開いているファイルという広大なメモリ空間が存在します.そこで,開いているファイル内で配列を表現し,かつカーソルをポインタと見ることでBrainfu*kを表現します.実行中のファイルの構造は以下のようにします.

<入力>
0
0 
.
. <0で初期化されて縦に並んだ配列 >
.
0
0
<出力>
<後の様々な処理でつかうフリースペース>

この構造を実現するために,まずは次に示すコマンドを前処理として実行します.

G@s100o0<Esc>o#%output_begin#%#%output_end#%
#%counter#%
<Esc>@l50j

#%で囲まれた文字はカーソルをジャンプさせるための識別文字です.中の文字や#%の表記は何でも良く,出力と競合しないような文字列を適当に選びました.100o0で100個の0を用意し,50jで初期位置をその真ん中としています.
なお,レジスタs,lには次のコマンドを保存しておくものとします.

  • s
i#%save#%<Esc>
  • l
/#%save#%<CR>8x

@sで現在のポインタの位置に#%save#%を書き込み,@lで#%save#%を検索してジャンプし@sを押下した時点でのポインタの位置に戻ります.前処理では最初に用意した0初期化配列の先頭位置を記憶し,全ての書き込みが終わった後にその位置に戻るために使用しています.
さらに全てのコマンドが終わった後に,出力だけを残すための後処理として次のコマンドを実行します.

/#%output_begin#%
kVggD16x/#%output_end#%
DGddddZZ

出力の先頭を示す#%output_begin#%より前の文字列と,出力の最後尾を示す#%output_end#%より後の文字列を全て削除するだけです.最後に保存終了ZZも忘れないようにします.
さて,下準備は済んだので各命令の置換するコマンドを考えていきます.


+

置換コマンド
@a
事前に定義するマクロ
  • a
<C-a>
説明

値をインクリメントするだけなので<C-a>で終わりです.ただし,後で紹介する処理の都合でレジスタに保存してマクロとして呼び出す必要があるので置換自体は@aとしています.


-

置換コマンド
@x
事前に定義するマクロ
  • x
<C-x>
説明

+と同じです.


<

置換コマンド
j
事前に定義するマクロ

なし

説明

配列がファイル上に縦に並んでいるので,ポインタのインクリメントはカーソルを下に動かすのと同義です.


>

置換コマンド
k
事前に定義するマクロ

なし

説明

<と同じです.


.

置換コマンド
@d
事前に定義するマクロ
  • d
0ywi#%save5#%<Esc>/#%output_end#%<CR>i<C-r>=nr2char(@")<CR><Esc>/#%save5#%<CR>9x
説明

まず,+や-と同じで後の処理の都合でコマンドは全てレジスタ内に保存しておき,@dで呼び出すだけにしておきます.具体的な処理手順は下記です.

  1. 0ywで現在のポインタの値をヤンク
  2. i#%save5#%<Esc>で現在の位置に#%save5#%を書き込んでおく
  3. /#%output_end#%<CR>で出力末尾にジャンプ
  4. i<C-r>=nr2char(@")<CR><Esc>でヤンクした値を書き込む
  5. /#%save5#%<CR>9xで#%save5#%で記録しておいた元の位置にカーソルを戻す

位置記憶用文字列が#%save5#%となっていますが他と競合しなければなんでも大丈夫です.(試行錯誤の過程でインデックスが5まで増えてしまいました...


[

置換コマンド
<Esc>@v@p
事前に定義するマクロ
  • v
i#%save3#%<Esc>/#%counter#%<CR>$"mp<C-a>011l"mdw/#%save3#%<CR>9x
  • m
0
  • p
i#%save2#%<Esc>G@tia<C-q><C-q><C-q><Esc>@v@p<Esc>2ki@sGo<Esc>k$"mpgg/#%if2#%1<CR>$w"jDgg/#%if2#%<CR>VGd/#%save2#%<CR>9x@j
  • t
o#%if2#%<CR><CR>#%if2#%1<CR><Esc>
説明

そこそこ複雑なので,]と合わせて後ほど詳しく説明します.


]

置換コマンド
<Esc>@b@q
事前に定義するマクロ
  • b
i#%save3#%<Esc>/#%counter#%<CR>$"mp<C-x>011l"mdw/#%save3#%<CR>9x
  • q
i#%save2#%<Esc>G@tb@xwia<C-q><C-q><C-q><Esc>@b@q<Esc>2ki@l@r@cGdd@z<Esc>k$"mpgg/#%if2#%0<CR>$w"jDgg/#%if2#%<CR>VGd/#%save2#%<CR>9x@j
  • r
0"nyw@cG"wD"wp@f"wp"rp2k"epk$"npgg@g$w"iDgg@hVGd@z@i
  • z
/#%save4#%<CR>9x
  • e
<Esc>
  • c
i#%save4#%<Esc>
  • f
o#%if#%<CR><CR>#%if#%0<CR><Esc>
  • g
/#%if#%0
  • h
/#%if#%
説明

そこそこ複雑なので,]と合わせて次に章で詳しく説明します.


[, ]によるループの実現

Brainfu*kの[,]命令はC言語でいうwhile(*ptr!=0){}と同じです.つまり,実現するには条件分岐とループをVimコマンドで実装する必要があります.本章ではこれらの実現方法を説明します.

条件分岐

検索機能をうまく使うことで条件分岐を実現します.より具体的に「ポインタが指す値が0ならば{コマンド列A},それ以外ならば{コマンド列B}を実行する」を実現します.手順を以下に示します.

  1. ポインタが指す値をヤンクし,現在の位置を記録する(記録は@sと同様)
  2. ファイル末尾に以下の形式のテキストを書き込む
{検索用文字列}{ポインタが指していた値}
{コマンド列A}
{検索用文字列}0
{コマンド列B}
  1. gg/{検索用文字列}0<CR>として検索する.すると,値が0ならば{コマンド列A}の上,それ以外なら{コマンド列B}の上にジャンプする
  2. j"{レジスタ}Dで分岐したコマンドをヤンクする
  3. gg/{検索用文字列}<CR>として検索し,ジャンプした行から4行分(書き込んだ4行)を削除する
  4. 記録しておいた位置に戻り,(@lと同様),@{レジスタ}で実行する

実装上では{検索用文字列}として#%if{数値}#%を用いています.これも競合しなければ何でもよいです.

ループ

[{コマンド列}]となっている内の{コマンド列}を0回以上繰り返し実行する必要があります.しかし,Vimコマンドの実行時に"戻る"という操作はなく1回の実行しか行うことができません.そこで,以下に示す{コマンド列}遅延評価機構を作成しました.

  1. [の置換としてGoを含める.つまり,[の実行後はファイル末尾で挿入モードとなる
  2. 挿入モードのためコマンド列は実行されず,コマンド列は全てファイル末尾に書き込まれる
  3. ]の置換として0D@"を含める.つまり,ファイル末尾に書き込まれたコマンド列を実行する

この仕組みによりコマンド列をレジスタに保存されることができ,何回でも呼ぶことが可能になりました.さらに,「ポインタが指す値が0でない場合は繰り返す」機構は,次のようなマクロで実現できます.「ポインタが指す値が0の時は何もしない,そうでない時はファイル末尾のコマンドを実行した上でもう一度このマクロを呼ぶ(自分自身の再帰呼び出し)」.
なお,コマンド列を挿入モードで書き込む際に,<C-a>などの文字は正常に書き込むことができません(先に<C-q>を押下する必要がある).そこで,特殊文字を使用するコマンドを予め全てレジスタに保存しておくことで,書き込み時に@{レジスタ}のように特殊文字が不要になるようにしました.+-で文字数が長くなるにも関わらずマクロ化していたのはこのためです.

多重ループ

先に説明したループを多重ループに拡張する上で致命的な欠陥があります.それはコマンド列書き込みの際に<Esc>がコマンド列の一部なのか書き込みの終了を表すのかを判別不能だということです.例えば[+[-]+]は,簡略化してGo+Go-<Esc>+<Esc>のようになります.この時,1つ目の<Esc>はコマンド列として書き込まれて欲しいのですが,挿入モードの終了として解釈されて書き込まれません.そこで,カウンタの導入と条件分岐による特殊<Esc>機構を導入することで多重ループを実現しました.以下に手順を記します.

  1. []のネストがいくつかを表すレジスタm(以下カウンタ)を0で初期化する
  2. カウンタをインクリメントするv,デクリメントするbを定義しておく
  3. [<Esc>@v@pとする.@pはカウンタが1であれば何もせず挿入モード,2以上であれば<Esc>@v@p([そのもの)を書き込んで挿入モードに入る.
  4. ]<Esc>@b@qとする.@qはカウンタが0であればループ末尾と解釈してファイル末尾のコマンド列を再帰実行,1以上であれば<Esc>@b@q(]そのもの)を書き込んで再び挿入モードに入る.

分岐や再帰実行は前節で説明した機構を用います.この処理により,ネストが1のコマンド列は純粋に再帰実行され,2以上の場合はファイル末尾に書き込まれてネストが1減った状態でまたこの処理が走る,という再帰処理が実行されます.
なお,[]Vimコマンドへの置換や各マクロの詳細は先に記した通りです([,]).

動作確認

実際にBrainfu*kコードを用意し,これをVimコマンドに置換して次のコマンドで実行します.

vim -u None -s {Vimコマンドに置換したファイル} {出力ファイル}
cat {出力ファイル}

VimコマンドファイルはBrainfu*kの置換だけでなく前処理なども含んで次のような構成なっています.

<マクロ定義部>
<前処理部>
<Brainfu*c置換コマンド部>
<後処理部>

1. 基本動作

まずは出力を含めたシンプルなコードが動くか確かめます.

Brainfu*kコード
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.>++++++++++.
Vimコマンド
Go<Esc>qa<C-a>qqe<Esc>qqx<C-x>qqsi#%save#%<Esc>qqci#%save4#%<Esc>qqz/#%save4#%
9xqql/#%save#%
8xqi0"nyw@cG"wD"wp@f"wp"rp2k"epk$"npgg@g$w"iDgg@hVGd@z@i<Esc>0"rDi0ywi#%save5#%<C-q><Esc>/#%output_end#%<C-q><CR>i<C-q><C-r>=nr2char(@")<C-q>
<C-q><Esc>/#%save5#%<C-q>
9x<Esc>0"dDqfo#%if#%

#%if#%0
<Esc>qV3kdqto#%if2#%

#%if2#%1
<Esc>qV3kdi/#%if#%0<C-q><CR><Esc>9h"gDi/#%if#%<C-q><CR><Esc>8h"hDqm0qii#%save3#%<C-q><Esc>/#%counter#%<C-q>
$"mp<C-q><C-a>011l"mdw/#%save3#%<C-q>
9x<Esc>0"vDii#%save3#%<C-q><Esc>/#%counter#%<C-q>
$"mp<C-q><C-x>011l"mdw/#%save3#%<C-q>
9x<Esc>0"bDii#%save2#%<C-q><Esc>G@tia<C-q><C-q><C-q><C-q><C-q><C-q><C-q><Esc>@v@p<C-q><Esc>2ki@sGo<C-q><Esc>k$"mpgg/#%if2#%1<C-q>
$w"jDgg/#%if2#%<C-q>
VGd/#%save2#%<C-q>
9x@j<Esc>0"pDii#%save2#%<C-q><Esc>G@tb@xwia<C-q><C-q><C-q><C-q><C-q><C-q><C-q><Esc>@b@q<C-q><Esc>2ki@l@r@cGdd@z<C-q><Esc>k$"mpgg/#%if2#%0<C-q>
$w"jDgg/#%if2#%<C-q>
VGd/#%save2#%<C-q>
9x@j<Esc>0"qD
G@s100o0<Esc>o#%output_begin#%#%output_end#%<CR>#%counter#%<CR><Esc>@l50j
@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@d@a@d@a@dj@a@a@a@a@a@a@a@a@a@a@d
/#%output_begin#%
kVggD16x/#%output_end#%
DGddddZZ
実行結果
ABC

無事に動きました.置換した部分は下から4行目だけで,Vimコマンドの大半はマクロ定義で埋まっています.

2. ループ

次に[]によるループが正しく動くか確かめます.

Brainfu*kコード
+++++++++[>++++++++>+++++++++++>+++>+<<<<-]>.>++.+++++++..+++.>+++++.<<+++++++++++++++.>.+++.------.--------.>+.>+.
Vimコマンド
Go<Esc>qa<C-a>qqe<Esc>qqx<C-x>qqsi#%save#%<Esc>qqci#%save4#%<Esc>qqz/#%save4#%
9xqql/#%save#%
8xqi0"nyw@cG"wD"wp@f"wp"rp2k"epk$"npgg@g$w"iDgg@hVGd@z@i<Esc>0"rDi0ywi#%save5#%<C-q><Esc>/#%output_end#%<C-q><CR>i<C-q><C-r>=nr2char(@")<C-q>
<C-q><Esc>/#%save5#%<C-q>
9x<Esc>0"dDqfo#%if#%

#%if#%0
<Esc>qV3kdqto#%if2#%

#%if2#%1
<Esc>qV3kdi/#%if#%0<C-q><CR><Esc>9h"gDi/#%if#%<C-q><CR><Esc>8h"hDqm0qii#%save3#%<C-q><Esc>/#%counter#%<C-q>
$"mp<C-q><C-a>011l"mdw/#%save3#%<C-q>
9x<Esc>0"vDii#%save3#%<C-q><Esc>/#%counter#%<C-q>
$"mp<C-q><C-x>011l"mdw/#%save3#%<C-q>
9x<Esc>0"bDii#%save2#%<C-q><Esc>G@tia<C-q><C-q><C-q><C-q><C-q><C-q><C-q><Esc>@v@p<C-q><Esc>2ki@sGo<C-q><Esc>k$"mpgg/#%if2#%1<C-q>
$w"jDgg/#%if2#%<C-q>
VGd/#%save2#%<C-q>
9x@j<Esc>0"pDii#%save2#%<C-q><Esc>G@tb@xwia<C-q><C-q><C-q><C-q><C-q><C-q><C-q><Esc>@b@q<C-q><Esc>2ki@l@r@cGdd@z<C-q><Esc>k$"mpgg/#%if2#%0<C-q>
$w"jDgg/#%if2#%<C-q>
VGd/#%save2#%<C-q>
9x@j<Esc>0"qD
G@s100o0<Esc>o#%output_begin#%#%output_end#%<CR>#%counter#%<CR><Esc>@l50j
@a@a@a@a@a@a@a@a@a<Esc>@v@pj@a@a@a@a@a@a@a@aj@a@a@a@a@a@a@a@a@a@a@aj@a@a@aj@akkkk@x<Esc>@b@qj@dj@a@a@d@a@a@a@a@a@a@a@d@d@a@a@a@dj@a@a@a@a@a@dkk@a@a@a@a@a@a@a@a@a@a@a@a@a@a@a@dj@d@a@a@a@d@x@x@x@x@x@x@d@x@x@x@x@x@x@x@x@dj@a@dj@a@d
/#%output_begin#%
kVggD16x/#%output_end#%
DGddddZZ
実行結果
Hello World!

無事に動きました.

3. 多重ループ

最後に[]による多重ループが正しく動くか確かめます.サンプルコードでは最大3重のループが存在します.

Brainfu*kコード
++++++[->++++>>+>+>-<<<<<]>[<++++>>+++>++++>>+++>+++++>+++++>>>>>>++>>++<<<<<<<<<<<<<<-]<++++>+++>-->+++>->>--->++>>>+++++[->++>++<<]<<<<<<<<<<[->-[>>>>>>>]>[<+++>.>.>>>>..>>>+<]<<<<<-[>>>>]>[<+++++>.>.>..>>>+<]>>>>+<-[<<<]<[[-<<+>>]>>>+>+<<<<<<[->>+>+>-<<<<]<]>>[[-]<]>[>>>[>.<<.<<<]<[.<<<<]>]>.<<<<<<<<<<<]
Vimコマンド
Go<Esc>qa<C-a>qqe<Esc>qqx<C-x>qqsi#%save#%<Esc>qqci#%save4#%<Esc>qqz/#%save4#%
9xqql/#%save#%
8xqi0"nyw@cG"wD"wp@f"wp"rp2k"epk$"npgg@g$w"iDgg@hVGd@z@i<Esc>0"rDi0ywi#%save5#%<C-q><Esc>/#%output_end#%<C-q><CR>i<C-q><C-r>=nr2char(@")<C-q>
<C-q><Esc>/#%save5#%<C-q>
9x<Esc>0"dDqfo#%if#%

#%if#%0
<Esc>qV3kdqto#%if2#%

#%if2#%1
<Esc>qV3kdi/#%if#%0<C-q><CR><Esc>9h"gDi/#%if#%<C-q><CR><Esc>8h"hDqm0qii#%save3#%<C-q><Esc>/#%counter#%<C-q>
$"mp<C-q><C-a>011l"mdw/#%save3#%<C-q>
9x<Esc>0"vDii#%save3#%<C-q><Esc>/#%counter#%<C-q>
$"mp<C-q><C-x>011l"mdw/#%save3#%<C-q>
9x<Esc>0"bDii#%save2#%<C-q><Esc>G@tia<C-q><C-q><C-q><C-q><C-q><C-q><C-q><Esc>@v@p<C-q><Esc>2ki@sGo<C-q><Esc>k$"mpgg/#%if2#%1<C-q>
$w"jDgg/#%if2#%<C-q>
VGd/#%save2#%<C-q>
9x@j<Esc>0"pDii#%save2#%<C-q><Esc>G@tb@xwia<C-q><C-q><C-q><C-q><C-q><C-q><C-q><Esc>@b@q<C-q><Esc>2ki@l@r@cGdd@z<C-q><Esc>k$"mpgg/#%if2#%0<C-q>
$w"jDgg/#%if2#%<C-q>
VGd/#%save2#%<C-q>
9x@j<Esc>0"qD
G@s100o0<Esc>o#%output_begin#%#%output_end#%<CR>#%counter#%<CR><Esc>@l50j
@a@a@a@a@a@a<Esc>@v@p@xj@a@a@a@ajj@aj@aj@xkkkkk<Esc>@b@qj<Esc>@v@pk@a@a@a@ajj@a@a@aj@a@a@a@ajj@a@a@aj@a@a@a@a@aj@a@a@a@a@ajjjjjj@a@ajj@a@akkkkkkkkkkkkkk@x<Esc>@b@qk@a@a@a@aj@a@a@aj@x@xj@a@a@aj@xjj@x@x@xj@a@ajjj@a@a@a@a@a<Esc>@v@p@xj@a@aj@a@akk<Esc>@b@qkkkkkkkkkk<Esc>@v@p@xj@x<Esc>@v@pjjjjjjj<Esc>@b@qj<Esc>@v@pk@a@a@aj@dj@djjjj@d@djjj@ak<Esc>@b@qkkkkk@x<Esc>@v@pjjjj<Esc>@b@qj<Esc>@v@pk@a@a@a@a@aj@dj@dj@d@djjj@ak<Esc>@b@qjjjj@ak@x<Esc>@v@pkkk<Esc>@b@qk<Esc>@v@p<Esc>@v@p@xkk@ajj<Esc>@b@qjjj@aj@akkkkkk<Esc>@v@p@xjj@aj@aj@xkkkk<Esc>@b@qk<Esc>@b@qjj<Esc>@v@p<Esc>@v@p@x<Esc>@b@qk<Esc>@b@qj<Esc>@v@pjjj<Esc>@v@pj@dkk@dkkk<Esc>@b@qk<Esc>@v@p@dkkkk<Esc>@b@qj<Esc>@b@qj@dkkkkkkkkkkk<Esc>@b@q
/#%output_begin#%
kVggD16x/#%output_end#%
DGddddZZ
実行結果
1
2
Fizz
4
Buzz
Fizz
7
<長いので中略>
Fizz
97
98
Fizz
Buzz

無事に動きました.実行して荒ぶるVimを見るのが楽しいです.

おわりに

本記事ではVimが万能であることを証明すべく,VimでBrainfu*kの再現を試みました.結果Brainfu*kの再現に成功し,Vimが万能であることが示されました.Vimは万能!Vimは万能!Vimは万能!
余談ですが,なんとVimコマンドのみでBrainfu*kを実現する先行例が10年も前に存在していたようです(参考:マクロ漁船について発表する人への反応 - Togetter).見た感じ私とは実現アプローチが少し異なるようなので,詳しく知りたいなと思いつつも古いせいか詳細が分からず悔しいです.色々なアプローチを知りたいので,読者の皆様もぜひチャレンジしてみてください.