読者です 読者をやめる 読者になる 読者になる

Vim のマッピングで Fizzbuzz 問題を解く

Vim

この記事は Vim Advent Calendar 2016 19日目の記事です。

締め切りがない世界に行きたいと言いつつ、締め切りがなければ何もしないニート根性の tyru です。メリークリスマス!!(錯乱)

(レジスタ編) Fizzbuzz 問題のコード

以前私はこんなコードを Gist に投稿したことがあります。 パッと見て何をするコードかわかるでしょうか。

"
" doit -> -> getchar:{num} -> fizzbuzz:{type}
"

nmap     <expr> doit join(map(range(1, 100), '"<SID>getchar:entry:".v:val."\<Esc>"'),'')

nmap     <expr> <SID>getchar:entry [setreg('n', '', 'c'), "<SID>getchar"][1]
nmap     <expr> <SID>getchar:0 [setreg('n', @n.'0', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:1 [setreg('n', @n.'1', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:2 [setreg('n', @n.'2', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:3 [setreg('n', @n.'3', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:4 [setreg('n', @n.'4', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:5 [setreg('n', @n.'5', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:6 [setreg('n', @n.'6', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:7 [setreg('n', @n.'7', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:8 [setreg('n', @n.'8', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:9 [setreg('n', @n.'9', 'c'), "<SID>getchar:"][1]
nmap     <expr> <SID>getchar:<Esc> "<SID>fizzbuzz:".str2nr((@n%5==0).(@n%3==0), 2)

nnoremap <expr> <SID>fizzbuzz:0 "o".@n."\<Esc>"
nnoremap        <SID>fizzbuzz:1 oFizz<Esc>
nnoremap        <SID>fizzbuzz:2 oBuzz<Esc>
nnoremap        <SID>fizzbuzz:3 oFizzBuzz<Esc>

使われてる単語からなんとなく分かる気がしますが、FizzBuzz 問題をなるべく Vimマッピングのみで解こうとしたコードです。 doit と押すと現在のバッファの次の行に 1 から 100 までの FizzBuzz の出力結果が書き込まれます。

しかし上記のコードに完全には満足していませんでした。 何が不満かというと、<SID>getchar: で始まるマッピングの部分で レジスタを使ってお茶を濁している点です。

なるべく私のやりたかったことを正確に言うと、 「Vimマッピングのみで解く」というよりは「Vimマッピングを有限状態機械 (以下 FSM) とみなし、FSM の能力の範囲内で FizzBuzz 問題を解く」ということがしたかったのです。 より要約すると「状態遷移のみで FizzBuzz 問題を解く」ということがしたかったのです。

解説

「状態遷移?Vimマッピングと状態遷移が関係あるの?」 と思われるかもしれないので簡単な解説をすると、 上のコードでいえば冒頭のコメントにも書いてある通り、

  1. doit
  2. getchar:{数字}
  3. fizzbuzz:{type}

マッピングの順に実行されます。 まず doit で次のようなマッピングに展開されます。

(実際には改行は入りません)

<SID>getchar:entry:1<Esc>
<SID>getchar:entry:2<Esc>
(省略)
<SID>getchar:entry:100<Esc>

そして doitマッピングnnoremap ではなく nmap なので再帰的に展開されます。 よって先頭の <SID>getchar:entry の部分が展開され、次のマッピングの rhs (右の定義のことです) が実行されます。

nmap     <expr> <SID>getchar:entry [setreg('n', '', 'c'), "<SID>getchar"][1]

ここでは @n レジスタがクリアされたあと、式としては <SID>getchar に評価されます。 そしてまた再帰マッピングにより、<SID>getchar:1マッピングに展開されます。

<SID>getchar:entry:1<Esc>
が以下に展開される
<SID>getchar:1<Esc>

その結果次のマッピングが実行されます。 <SID>getchar:{数字}マッピングではいずれも同じことをやっており、 それぞれの {数字} の部分を @n レジスタの文字列の末尾にくっ付けているだけです。

nmap     <expr> <SID>getchar:1 [setreg('n', @n.'1', 'c'), "<SID>getchar:"][1]

そしてこのマッピング<SID>getchar: に評価され(ry) 次のマッピングが実行されます。

nmap     <expr> <SID>getchar:<Esc> "<SID>fizzbuzz:".str2nr((@n%5==0).(@n%3==0), 2)

ここで @n レジスタに入っている文字列に対して 5 と 3 の余剰が 0 かどうかをチェックして、 次のような 2 進数の文字列を作り、それを str2nr(..., 2) で実際の整数値に変換しています。

{5で割り切れるなら1 (割り切れないなら 0)}{3で割り切れるなら1 (割り切れないなら 0)}

最終的に次のマッピングのいずれかが実行され、バッファに結果が挿入されます。

" 数字を挿入
nnoremap <expr> <SID>fizzbuzz:0 "o".@n."\<Esc>"
" Fizzを挿入
nnoremap        <SID>fizzbuzz:1 oFizz<Esc>
" Buzzを挿入
nnoremap        <SID>fizzbuzz:2 oBuzz<Esc>
" FizzBuzzを挿入
nnoremap        <SID>fizzbuzz:3 oFizzBuzz<Esc>

つまり?

つまりレジスタ (= 変数) を使ってしまっているので、 上記のコードは私のやりたかったこととは違うということになります。 具体的には、まずは以下のようなルールをもとに FizzBuzz を解くことを考えてみます。

  1. (純粋に状態遷移のみで解いていきたいので) <expr> やその他 Vim 式を一切無くす

というわけで前置きが非常に長かったですが、この記事では Vimマッピングだけでどこまでできるのか、その可能性を探っていきたいと思います (ドキュメンタリー番組調)。

(バッファ編) 設計の概要

  1. (純粋に状態遷移のみで解いていきたいので) <expr> やその他 Vim 式を一切無くす

では今回、上記のルールを実装するために必要な設計をぼんやりと考えていきます。

まず

  • 3 の倍数の判定
  • 5 の倍数の判定

を分けて考えます。 具体的には

  • 3 の倍数は全ての位の数の和が 3 の倍数であるかどうか
  • 5 の倍数は 1 の位が 0 か 5 であるか

で判定できます。

それでは具体的に 15 のような数字がやってきた場合にどのように判定すればいいでしょうか。 まず 3 の倍数の判定から考えていくと、

  • まず 3 の余剰が 0, 1, 2 となった状態をそれぞれ q0, q1, q2 と定義します。 初期状態は q0 です。
  • 最初の状態、つまり初期状態は q0 で、最初の桁 (左から処理していくので最上位の桁) の余剰が 0 の場合は繰越す余剰分がないため、状態 q0 に留まります。しかし 余剰分が 1, 2 の場合はそれぞれ q1, q2 に遷移します。
    • 最初の入力は 1 ですから 3 の余剰は 1 になります。 つまり q0 → q1 のように遷移します。
  • 状態 q1 の時に余剰分が 1, 2 だった場合は、それぞれ q2, q0 に遷移します。
    • 次の入力は 5 ですから 3 の余剰は 2 になります。 つまり q1 → q0 のように遷移します。
  • 入力が <Esc> の時に q0 であれば受理 (= 3 の倍数である)、それ以外は拒否します。

このように各桁ごとに 3 の余剰を「繰越す」 (足し込む?) 動作にすると状態遷移図で表現できます。

f:id:tyru:20161218230706p:plain


5 の倍数の場合はもっと簡単です。

  • 入力に対し 0 か 5 である場合の状態を q1、それ以外の場合を q0 とします。 初期状態は (どっちでもいいけど) q0 です。
  • 入力が <Esc> の時に q1 であれば受理 (= 5 の倍数である)、それ以外は拒否します。

f:id:tyru:20161218230714p:plain


3 の倍数は上記の通り 3 パターンで、5 の倍数の状態は入力が 0 か 5 であるか、またはそうでないかの 2 パターンです。 つまり 3 × 2 で合計 6 つの状態が必要となります。

加えて、少なくとも Vimマッピングで実現する場合、'0'~'9' と数字の区切りを表す <Esc> (何でもいいですが) を入力として受け取るために 11 個 × 6 通りの 66 個のマッピングを定義する必要があります。 具体例を出すと以下のようなフォーマットのマッピングになります。

getchar {3の余剰 (0,1,2 のいずれか)} {5の倍数であれば1、そうでなければ0} : {次の桁の数字}

FSM の形式的定義でいうところに遷移関数そのままですね。 コロンの前が状態でコロンの後が入力です。 以下は「3 の余剰が 1 で」「5の倍数で」「次の桁の数字が 2」の時の具体例です (なお「: (コロン)」は見やすさのためだけに付けてあります)。

getchar11:2

ちなみに次の桁の数字が存在しない場合は数字ではなく <Esc> が来るので、「3 の余剰が 0 で」「5の倍数で」「次の桁の数字が存在しない」の時は以下のようになります。

getchar01:<Esc>

(バッファ編) コード

コードは以下の通りになります。

"
" 1. doit
" 2. getchar:{numchar}
" 3. getchar{n % 3}{n % 5 == 0 ? 1 : 0}:{numchar}
" 4. Result
"   1. <SID>(result:fizz)
"   2. <SID>(result:buzz)
"   3. <SID>(result:fizzbuzz)
"   4. <SID>(result:number)
"

" nmap     <expr> doit join(map(range(1, 100), '"<SID>getchar:entry:".v:val."\<Esc>"'),'')
nmap doit <SID>getchar:1<Esc><SID>getchar:2<Esc><SID>getchar:3<Esc><SID>getchar:4<Esc><SID>getchar:5<Esc><SID>getchar:6<Esc><SID>getchar:7<Esc><SID>getchar:8<Esc><SID>getchar:9<Esc><SID>getchar:10<Esc><SID>getchar:11<Esc><SID>getchar:12<Esc><SID>getchar:13<Esc><SID>getchar:14<Esc><SID>getchar:15<Esc><SID>getchar:16<Esc><SID>getchar:17<Esc><SID>getchar:18<Esc><SID>getchar:19<Esc><SID>getchar:20<Esc><SID>getchar:21<Esc><SID>getchar:22<Esc><SID>getchar:23<Esc><SID>getchar:24<Esc><SID>getchar:25<Esc><SID>getchar:26<Esc><SID>getchar:27<Esc><SID>getchar:28<Esc><SID>getchar:29<Esc><SID>getchar:30<Esc><SID>getchar:31<Esc><SID>getchar:32<Esc><SID>getchar:33<Esc><SID>getchar:34<Esc><SID>getchar:35<Esc><SID>getchar:36<Esc><SID>getchar:37<Esc><SID>getchar:38<Esc><SID>getchar:39<Esc><SID>getchar:40<Esc><SID>getchar:41<Esc><SID>getchar:42<Esc><SID>getchar:43<Esc><SID>getchar:44<Esc><SID>getchar:45<Esc><SID>getchar:46<Esc><SID>getchar:47<Esc><SID>getchar:48<Esc><SID>getchar:49<Esc><SID>getchar:50<Esc><SID>getchar:51<Esc><SID>getchar:52<Esc><SID>getchar:53<Esc><SID>getchar:54<Esc><SID>getchar:55<Esc><SID>getchar:56<Esc><SID>getchar:57<Esc><SID>getchar:58<Esc><SID>getchar:59<Esc><SID>getchar:60<Esc><SID>getchar:61<Esc><SID>getchar:62<Esc><SID>getchar:63<Esc><SID>getchar:64<Esc><SID>getchar:65<Esc><SID>getchar:66<Esc><SID>getchar:67<Esc><SID>getchar:68<Esc><SID>getchar:69<Esc><SID>getchar:70<Esc><SID>getchar:71<Esc><SID>getchar:72<Esc><SID>getchar:73<Esc><SID>getchar:74<Esc><SID>getchar:75<Esc><SID>getchar:76<Esc><SID>getchar:77<Esc><SID>getchar:78<Esc><SID>getchar:79<Esc><SID>getchar:80<Esc><SID>getchar:81<Esc><SID>getchar:82<Esc><SID>getchar:83<Esc><SID>getchar:84<Esc><SID>getchar:85<Esc><SID>getchar:86<Esc><SID>getchar:87<Esc><SID>getchar:88<Esc><SID>getchar:89<Esc><SID>getchar:90<Esc><SID>getchar:91<Esc><SID>getchar:92<Esc><SID>getchar:93<Esc><SID>getchar:94<Esc><SID>getchar:95<Esc><SID>getchar:96<Esc><SID>getchar:97<Esc><SID>getchar:98<Esc><SID>getchar:99<Esc><SID>getchar:100<Esc>

nmap <SID>getchar: <SID>getchar00:

nmap <SID>getchar00:0 <SID>append:0<SID>getchar01:
nmap <SID>getchar00:1 <SID>append:1<SID>getchar10:
nmap <SID>getchar00:2 <SID>append:2<SID>getchar20:
nmap <SID>getchar00:3 <SID>append:3<SID>getchar00:
nmap <SID>getchar00:4 <SID>append:4<SID>getchar10:
nmap <SID>getchar00:5 <SID>append:5<SID>getchar21:
nmap <SID>getchar00:6 <SID>append:6<SID>getchar00:
nmap <SID>getchar00:7 <SID>append:7<SID>getchar10:
nmap <SID>getchar00:8 <SID>append:8<SID>getchar20:
nmap <SID>getchar00:9 <SID>append:9<SID>getchar00:
nmap <SID>getchar00:<Esc> <SID>(result:fizz)
nmap <SID>getchar01:0 <SID>append:0<SID>getchar01:
nmap <SID>getchar01:1 <SID>append:1<SID>getchar10:
nmap <SID>getchar01:2 <SID>append:2<SID>getchar20:
nmap <SID>getchar01:3 <SID>append:3<SID>getchar00:
nmap <SID>getchar01:4 <SID>append:4<SID>getchar10:
nmap <SID>getchar01:5 <SID>append:5<SID>getchar21:
nmap <SID>getchar01:6 <SID>append:6<SID>getchar00:
nmap <SID>getchar01:7 <SID>append:7<SID>getchar10:
nmap <SID>getchar01:8 <SID>append:8<SID>getchar20:
nmap <SID>getchar01:9 <SID>append:9<SID>getchar00:
nmap <SID>getchar01:<Esc> <SID>(result:fizzbuzz)
nmap <SID>getchar10:0 <SID>append:0<SID>getchar11:
nmap <SID>getchar10:1 <SID>append:1<SID>getchar20:
nmap <SID>getchar10:2 <SID>append:2<SID>getchar00:
nmap <SID>getchar10:3 <SID>append:3<SID>getchar10:
nmap <SID>getchar10:4 <SID>append:4<SID>getchar20:
nmap <SID>getchar10:5 <SID>append:5<SID>getchar01:
nmap <SID>getchar10:6 <SID>append:6<SID>getchar10:
nmap <SID>getchar10:7 <SID>append:7<SID>getchar20:
nmap <SID>getchar10:8 <SID>append:8<SID>getchar00:
nmap <SID>getchar10:9 <SID>append:9<SID>getchar10:
nmap <SID>getchar10:<Esc> <SID>(result:number)
nmap <SID>getchar11:0 <SID>append:0<SID>getchar11:
nmap <SID>getchar11:1 <SID>append:1<SID>getchar20:
nmap <SID>getchar11:2 <SID>append:2<SID>getchar00:
nmap <SID>getchar11:3 <SID>append:3<SID>getchar10:
nmap <SID>getchar11:4 <SID>append:4<SID>getchar20:
nmap <SID>getchar11:5 <SID>append:5<SID>getchar01:
nmap <SID>getchar11:6 <SID>append:6<SID>getchar10:
nmap <SID>getchar11:7 <SID>append:7<SID>getchar20:
nmap <SID>getchar11:8 <SID>append:8<SID>getchar00:
nmap <SID>getchar11:9 <SID>append:9<SID>getchar10:
nmap <SID>getchar11:<Esc> <SID>(result:buzz)
nmap <SID>getchar20:0 <SID>append:0<SID>getchar21:
nmap <SID>getchar20:1 <SID>append:1<SID>getchar00:
nmap <SID>getchar20:2 <SID>append:2<SID>getchar10:
nmap <SID>getchar20:3 <SID>append:3<SID>getchar20:
nmap <SID>getchar20:4 <SID>append:4<SID>getchar00:
nmap <SID>getchar20:5 <SID>append:5<SID>getchar11:
nmap <SID>getchar20:6 <SID>append:6<SID>getchar20:
nmap <SID>getchar20:7 <SID>append:7<SID>getchar00:
nmap <SID>getchar20:8 <SID>append:8<SID>getchar10:
nmap <SID>getchar20:9 <SID>append:9<SID>getchar20:
nmap <SID>getchar20:<Esc> <SID>(result:number)
nmap <SID>getchar21:0 <SID>append:0<SID>getchar21:
nmap <SID>getchar21:1 <SID>append:1<SID>getchar00:
nmap <SID>getchar21:2 <SID>append:2<SID>getchar10:
nmap <SID>getchar21:3 <SID>append:3<SID>getchar20:
nmap <SID>getchar21:4 <SID>append:4<SID>getchar00:
nmap <SID>getchar21:5 <SID>append:5<SID>getchar11:
nmap <SID>getchar21:6 <SID>append:6<SID>getchar20:
nmap <SID>getchar21:7 <SID>append:7<SID>getchar00:
nmap <SID>getchar21:8 <SID>append:8<SID>getchar10:
nmap <SID>getchar21:9 <SID>append:9<SID>getchar20:
nmap <SID>getchar21:<Esc> <SID>(result:buzz)

nnoremap <SID>append:0 a0<Esc>
nnoremap <SID>append:1 a1<Esc>
nnoremap <SID>append:2 a2<Esc>
nnoremap <SID>append:3 a3<Esc>
nnoremap <SID>append:4 a4<Esc>
nnoremap <SID>append:5 a5<Esc>
nnoremap <SID>append:6 a6<Esc>
nnoremap <SID>append:7 a7<Esc>
nnoremap <SID>append:8 a8<Esc>
nnoremap <SID>append:9 a9<Esc>

nnoremap <SID>(result:fizz) ccFizz<CR><Esc>
nnoremap <SID>(result:buzz) ccBuzz<CR><Esc>
nnoremap <SID>(result:fizzbuzz) ccFizzBuzz<CR><Esc>
nnoremap <SID>(result:number) o<Esc>

<expr> が 1 個もありません。 つまり Vimマッピングのみで FizzBuzz 問題を解けたということになります。 やったぜ。

(PDA 編) PDAFizzBuzz が解けるかの考察

さて、上記で一旦解けた気になりましたが、気になる点が1つあります。 それはバッファの書き換えを許している点です。 (a コマンドなどでの 挿入 ならともかく) cc などで 一度挿入した文字列を変更 するのを許可してしまったら、変数代わりにバッファを使っているのと何ら変わりありません。 しかし、FizzBuzz はプッシュダウン・オートマトン (以下 PDA) の範囲で解けるのか?を考えて、 一応方法は思いついたのですが、

  • スタックから数字を取り出す時に出力が逆になってしまう

という問題が浮かび上がってきました。 「ということは最初の doitマッピングで 100 の代わりに 001 みたいな逆順の数字を与えればいいのか?」 と考えたのですが、そうするとさらに以下のような問題 (というか疑問) も浮かび上がってきます。

  1. 5 の倍数の判定アルゴリズムが使えなくなる (誤判定する)
    • 15 という数字を判定する場合、51 といった入力が来るので、 最終的な状態は 1 に対する判定になってしまう
  2. そもそも各桁を逆順にした数字を「数」として扱っていいのか?

1 の解決方法はすぐ見つかりました。 ようは「桁が逆転しても使える 5 の倍数の判定方法」が分かればいいので、「最初の桁 (=元の数でいう最後の桁) だけ見て判定して、あとはずっと読み飛ばす」でいけるはずです。

f:id:tyru:20161218234845p:plain

2 はそもそも PDA の形式的定義には 状態、初期状態、入力文字、遷移関数、受理状態の5つだけで、 「数」の定義はこれっぽっちもありません。 よって PDA で数を扱うとは一体どういうことなんだ…? と無い頭で悩んだ末、無視することにしました (ズコー)。

おまけ:加算器と乗算器 in Vim script

無視するとは言っても少し気になったので、 「おそらく計算できればいいんだろう」から「そういえば FSM は論理回路にも応用されてるんだっけ」で 適当にググった結果、加算器と乗算器の Wikipedia のページが出てきたので Vim script で実装してみました。

https://gist.github.com/tyru/e057fefe483c43954fb8933076eb22cb

実装したら Vimマッピングで実装するヒントが出てくると思ったのですが、出てきませんでした (ズコー)。 ひらめきドリブン開発 (HDD)、失敗です。*1

閑話休題:(PDA 編) PDAFizzBuzz が解けるかの考察

2. そもそも各桁を逆順にした数字を「数」として扱っていいのか?

PDAFizzBuzz を解くためのルールとして上記を挙げましたが、 そもそも問題設定が間違っている気もします。 より適切なものに言い換えると

2. 都合の良いように調整した入力を使っても問題を解いたとみなせるのか?

ではないでしょうか (というか、本当にこれで解いたと言えるのか分からないので誰か教えてください)。 で、これが許容できるなら PDA っぽいものでも解ける、ということになります (それに何の意味があるかって?そんなもの、とっくにこの記事の落としどころを見失った私には分かりません)。

(PDA 編) ルールの定義

はい、というわけで細かいことは考えず「許容できる」ものとして、2 は無視して目と耳を塞ぎ口を噤み孤独に暮らしましょう PDA っぽいやり方で実装してしまいましょう。

おっと、その前にルールの定義がまだでした。 変更点としては、バッファに対する書き換えを禁止したことと、 代わりにスタック用の変数を導入し、それに対する限られた操作しか許可しないようにしたことです。

  1. (PDA の範囲で実現するため) 使用する変数はスタック用の変数 s:stack のみ
  2. <expr> やその他 Vim 式を一切無くす。しかし 1 の変数に対するリスト操作は当てはまらないことにする
  3. 出力はバッファに対して行う。a コマンドでのバッファ末尾への挿入のみ可能とする。バッファの書き換えは禁止とする。

(PDA 編) コード

コードは以下の通りです。

" nmap     <expr> doit join(map(range(1, 100), '"<SID>getchar:entry:".(join(reverse(split(v:val, "\\zs")), ""))."\<Esc>"'),'')
nmap doit <SID>getchar:1<Esc><SID>getchar:2<Esc><SID>getchar:3<Esc><SID>getchar:4<Esc><SID>getchar:5<Esc><SID>getchar:6<Esc><SID>getchar:7<Esc><SID>getchar:8<Esc><SID>getchar:9<Esc><SID>getchar:01<Esc><SID>getchar:11<Esc><SID>getchar:21<Esc><SID>getchar:31<Esc><SID>getchar:41<Esc><SID>getchar:51<Esc><SID>getchar:61<Esc><SID>getchar:71<Esc><SID>getchar:81<Esc><SID>getchar:91<Esc><SID>getchar:02<Esc><SID>getchar:12<Esc><SID>getchar:22<Esc><SID>getchar:32<Esc><SID>getchar:42<Esc><SID>getchar:52<Esc><SID>getchar:62<Esc><SID>getchar:72<Esc><SID>getchar:82<Esc><SID>getchar:92<Esc><SID>getchar:03<Esc><SID>getchar:13<Esc><SID>getchar:23<Esc><SID>getchar:33<Esc><SID>getchar:43<Esc><SID>getchar:53<Esc><SID>getchar:63<Esc><SID>getchar:73<Esc><SID>getchar:83<Esc><SID>getchar:93<Esc><SID>getchar:04<Esc><SID>getchar:14<Esc><SID>getchar:24<Esc><SID>getchar:34<Esc><SID>getchar:44<Esc><SID>getchar:54<Esc><SID>getchar:64<Esc><SID>getchar:74<Esc><SID>getchar:84<Esc><SID>getchar:94<Esc><SID>getchar:05<Esc><SID>getchar:15<Esc><SID>getchar:25<Esc><SID>getchar:35<Esc><SID>getchar:45<Esc><SID>getchar:55<Esc><SID>getchar:65<Esc><SID>getchar:75<Esc><SID>getchar:85<Esc><SID>getchar:95<Esc><SID>getchar:06<Esc><SID>getchar:16<Esc><SID>getchar:26<Esc><SID>getchar:36<Esc><SID>getchar:46<Esc><SID>getchar:56<Esc><SID>getchar:66<Esc><SID>getchar:76<Esc><SID>getchar:86<Esc><SID>getchar:96<Esc><SID>getchar:07<Esc><SID>getchar:17<Esc><SID>getchar:27<Esc><SID>getchar:37<Esc><SID>getchar:47<Esc><SID>getchar:57<Esc><SID>getchar:67<Esc><SID>getchar:77<Esc><SID>getchar:87<Esc><SID>getchar:97<Esc><SID>getchar:08<Esc><SID>getchar:18<Esc><SID>getchar:28<Esc><SID>getchar:38<Esc><SID>getchar:48<Esc><SID>getchar:58<Esc><SID>getchar:68<Esc><SID>getchar:78<Esc><SID>getchar:88<Esc><SID>getchar:98<Esc><SID>getchar:09<Esc><SID>getchar:19<Esc><SID>getchar:29<Esc><SID>getchar:39<Esc><SID>getchar:49<Esc><SID>getchar:59<Esc><SID>getchar:69<Esc><SID>getchar:79<Esc><SID>getchar:89<Esc><SID>getchar:99<Esc><SID>getchar:001<Esc>

nmap <SID>getchar:0 <SID>(stack:init)<SID>stack:push:0<SID>getchar01:
nmap <SID>getchar:1 <SID>(stack:init)<SID>stack:push:1<SID>getchar10:
nmap <SID>getchar:2 <SID>(stack:init)<SID>stack:push:2<SID>getchar20:
nmap <SID>getchar:3 <SID>(stack:init)<SID>stack:push:3<SID>getchar00:
nmap <SID>getchar:4 <SID>(stack:init)<SID>stack:push:4<SID>getchar10:
nmap <SID>getchar:5 <SID>(stack:init)<SID>stack:push:5<SID>getchar21:
nmap <SID>getchar:6 <SID>(stack:init)<SID>stack:push:6<SID>getchar00:
nmap <SID>getchar:7 <SID>(stack:init)<SID>stack:push:7<SID>getchar10:
nmap <SID>getchar:8 <SID>(stack:init)<SID>stack:push:8<SID>getchar20:
nmap <SID>getchar:9 <SID>(stack:init)<SID>stack:push:9<SID>getchar00:

nmap <SID>getchar00:0 <SID>stack:push:0<SID>getchar00:
nmap <SID>getchar00:1 <SID>stack:push:1<SID>getchar10:
nmap <SID>getchar00:2 <SID>stack:push:2<SID>getchar20:
nmap <SID>getchar00:3 <SID>stack:push:3<SID>getchar00:
nmap <SID>getchar00:4 <SID>stack:push:4<SID>getchar10:
nmap <SID>getchar00:5 <SID>stack:push:5<SID>getchar20:
nmap <SID>getchar00:6 <SID>stack:push:6<SID>getchar00:
nmap <SID>getchar00:7 <SID>stack:push:7<SID>getchar10:
nmap <SID>getchar00:8 <SID>stack:push:8<SID>getchar20:
nmap <SID>getchar00:9 <SID>stack:push:9<SID>getchar00:
nmap <SID>getchar00:<Esc> <SID>(result:fizz)
nmap <SID>getchar01:0 <SID>stack:push:0<SID>getchar01:
nmap <SID>getchar01:1 <SID>stack:push:1<SID>getchar11:
nmap <SID>getchar01:2 <SID>stack:push:2<SID>getchar21:
nmap <SID>getchar01:3 <SID>stack:push:3<SID>getchar01:
nmap <SID>getchar01:4 <SID>stack:push:4<SID>getchar11:
nmap <SID>getchar01:5 <SID>stack:push:5<SID>getchar21:
nmap <SID>getchar01:6 <SID>stack:push:6<SID>getchar01:
nmap <SID>getchar01:7 <SID>stack:push:7<SID>getchar11:
nmap <SID>getchar01:8 <SID>stack:push:8<SID>getchar21:
nmap <SID>getchar01:9 <SID>stack:push:9<SID>getchar01:
nmap <SID>getchar01:<Esc> <SID>(result:fizzbuzz)
nmap <SID>getchar10:0 <SID>stack:push:0<SID>getchar10:
nmap <SID>getchar10:1 <SID>stack:push:1<SID>getchar20:
nmap <SID>getchar10:2 <SID>stack:push:2<SID>getchar00:
nmap <SID>getchar10:3 <SID>stack:push:3<SID>getchar10:
nmap <SID>getchar10:4 <SID>stack:push:4<SID>getchar20:
nmap <SID>getchar10:5 <SID>stack:push:5<SID>getchar00:
nmap <SID>getchar10:6 <SID>stack:push:6<SID>getchar10:
nmap <SID>getchar10:7 <SID>stack:push:7<SID>getchar20:
nmap <SID>getchar10:8 <SID>stack:push:8<SID>getchar00:
nmap <SID>getchar10:9 <SID>stack:push:9<SID>getchar10:
nmap <SID>getchar10:<Esc> <SID>(result:number)
nmap <SID>getchar11:0 <SID>stack:push:0<SID>getchar11:
nmap <SID>getchar11:1 <SID>stack:push:1<SID>getchar21:
nmap <SID>getchar11:2 <SID>stack:push:2<SID>getchar01:
nmap <SID>getchar11:3 <SID>stack:push:3<SID>getchar11:
nmap <SID>getchar11:4 <SID>stack:push:4<SID>getchar21:
nmap <SID>getchar11:5 <SID>stack:push:5<SID>getchar01:
nmap <SID>getchar11:6 <SID>stack:push:6<SID>getchar11:
nmap <SID>getchar11:7 <SID>stack:push:7<SID>getchar21:
nmap <SID>getchar11:8 <SID>stack:push:8<SID>getchar01:
nmap <SID>getchar11:9 <SID>stack:push:9<SID>getchar11:
nmap <SID>getchar11:<Esc> <SID>(result:buzz)
nmap <SID>getchar20:0 <SID>stack:push:0<SID>getchar20:
nmap <SID>getchar20:1 <SID>stack:push:1<SID>getchar00:
nmap <SID>getchar20:2 <SID>stack:push:2<SID>getchar10:
nmap <SID>getchar20:3 <SID>stack:push:3<SID>getchar20:
nmap <SID>getchar20:4 <SID>stack:push:4<SID>getchar00:
nmap <SID>getchar20:5 <SID>stack:push:5<SID>getchar10:
nmap <SID>getchar20:6 <SID>stack:push:6<SID>getchar20:
nmap <SID>getchar20:7 <SID>stack:push:7<SID>getchar00:
nmap <SID>getchar20:8 <SID>stack:push:8<SID>getchar10:
nmap <SID>getchar20:9 <SID>stack:push:9<SID>getchar20:
nmap <SID>getchar20:<Esc> <SID>(result:number)
nmap <SID>getchar21:0 <SID>stack:push:0<SID>getchar21:
nmap <SID>getchar21:1 <SID>stack:push:1<SID>getchar01:
nmap <SID>getchar21:2 <SID>stack:push:2<SID>getchar11:
nmap <SID>getchar21:3 <SID>stack:push:3<SID>getchar21:
nmap <SID>getchar21:4 <SID>stack:push:4<SID>getchar01:
nmap <SID>getchar21:5 <SID>stack:push:5<SID>getchar11:
nmap <SID>getchar21:6 <SID>stack:push:6<SID>getchar21:
nmap <SID>getchar21:7 <SID>stack:push:7<SID>getchar01:
nmap <SID>getchar21:8 <SID>stack:push:8<SID>getchar11:
nmap <SID>getchar21:9 <SID>stack:push:9<SID>getchar21:
nmap <SID>getchar21:<Esc> <SID>(result:buzz)

" Stack operations
let s:stack = []

function! s:stack_init() abort
  call s:stack_dump('init')
  let s:stack = [s:SNR_PREFIX . "result:number:\<Esc>"]
  return ''
endfunction

function! s:stack_pop() abort
  call s:stack_dump('pop')
  return remove(s:stack, -1)
endfunction

function! s:stack_push(n) abort
  call s:stack_dump('push')
  let s:stack += [s:SNR_PREFIX . 'result:number:' . a:n]
  return ''
endfunction

let s:DEBUG = 0
function! s:stack_dump(caller) abort
  if !s:DEBUG | return | endif
  echomsg a:caller ':' string(s:stack)
endfunction

function! s:SID()
  return matchstr(expand('<sfile>'), '<SNR>\zs\d\+\ze_SID$')
endfunction
let s:SNR_PREFIX = "\<SNR>" . s:SID() . '_'

nnoremap <expr> <SID>(stack:init) <SID>stack_init()
nmap <expr> <SID>(stack:pop) <SID>stack_pop()
nnoremap <expr> <SID>stack:push:0 <SID>stack_push(0)
nnoremap <expr> <SID>stack:push:1 <SID>stack_push(1)
nnoremap <expr> <SID>stack:push:2 <SID>stack_push(2)
nnoremap <expr> <SID>stack:push:3 <SID>stack_push(3)
nnoremap <expr> <SID>stack:push:4 <SID>stack_push(4)
nnoremap <expr> <SID>stack:push:5 <SID>stack_push(5)
nnoremap <expr> <SID>stack:push:6 <SID>stack_push(6)
nnoremap <expr> <SID>stack:push:7 <SID>stack_push(7)
nnoremap <expr> <SID>stack:push:8 <SID>stack_push(8)
nnoremap <expr> <SID>stack:push:9 <SID>stack_push(9)

" Output
nnoremap <SID>(result:fizz) aFizz<CR><Esc>
nnoremap <SID>(result:buzz) aBuzz<CR><Esc>
nnoremap <SID>(result:fizzbuzz) aFizzBuzz<CR><Esc>
" Pop until <SID>result:number:<Esc>
nmap <script> <SID>(result:number) <SID>(stack:pop)
nmap <script> <SID>result:number:0 a0<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:1 a1<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:2 a2<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:3 a3<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:4 a4<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:5 a5<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:6 a6<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:7 a7<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:8 a8<Esc><SID>(stack:pop)
nmap <script> <SID>result:number:9 a9<Esc><SID>(stack:pop)
nnoremap <SID>result:number:<Esc> o<Esc>

おまけ:Vimマッピング正規表現エンジンを実装できるか?

個人的にモヤっとした終わり方だったので、別のことを考えてお茶を濁すことにしました。

というわけでいきなりですが、表題の通り、Vimマッピングオートマトンの能力を持つなら、当然正規表現エンジンを実装する事も可能なはずです。 キー入力が文字列、マッピング (lhs) がパターンです。 この場合、以下のような動作を実現できれば「Vimマッピング正規表現エンジンを実装した」と言えるでしょう。

  1. 正規表現のパターンを元にマッピングを定義する
  2. 任意のキー入力に対してそれが正規表現にマッチするなら最終的な rhs が実行される
    • rhs は :<C-u>echo 'match!'<CR> などが分かりやすいでしょう
  3. マッチしなければタイムアウトして上記の rhs は実行されない
    • 必要であれば、タイムアウト時にそれまでのキー入力が実行されないよう受理状態以外の状態は <Nop> で無効化する必要があるかもしれません

おそらく、Vimマッピングでは ε (空列) を扱えないと思われるため、NFA ではなく DFA として扱う必要があると思っています。 まだ色々と無知なため間違っているかもしれませんが、原理上は可能なような気がしています。

Vimマッピング正規表現が扱えるとなれば、つまりキー入力に正規表現を適用できます。 そうなると便利な場合もあるのではないでしょうか。

例えば、submode.vim の作者である Vim 神こと kana さんのプラグインctxabbr.vim というものがあります (GitHubリポジトリは空ですが vim.org にはちゃんとアップロードされています)。 このプラグインがどんなものかというと、「using(空白)」の後に「sc」と入力するだけで「using System.Collection」と展開してくれるプラグインらしいです (使ったことはありません)。 「『using(空白)』の後に『sc』を押すと『using System.Collection』に展開」という部分、正規表現マッピングを定義できると嬉しいと思いませんか?

…と煽っておいて元も子もないことを言うと、

  • ユーザーによるキー入力しか考慮されない
    • バッファの内容によって動作を変えたいといったことはできない
  • ctxabbr.vim がやっているように <expr> な abbreviation を作った方が自由度も高い
  • 補完でやった方が自由度も UI に対する驚き最小の原則としても優れている

などなど様々な反論は思い浮かびましたが、 Vim の可能性が広がるだけでも突き詰める意味はあると思っています。 まぁこの際、役に立つかどうかなんぞあまり意味はありませんね???

感想

Vim でできることをより知りたいと思って、最近は計算機科学をちゃんと勉強したりしていました。 勉強するにつれ、より面白い Vim の遊び方が思いつくようになり、毎日 Vim 人生が充実しています。 当初の目的からズレている気がしますが、初めから何もかもが間違っているので気にしないことにしました。

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 2.計算可能性の理論

計算理論の基礎 [原著第2版] 2.計算可能性の理論

つまり私がこの記事で言いたかったのは、現実の問題を Vim モデル化し解決する Vim 力が今の時代求められているのではないでしょうか、そういうことです。

つまり

f:id:tyru:20161218212602j:plain

*1:これに関してはもうちょっとあれこれ悩んだので、後日気が向いたらまた記事を書くかもしれません…