この記事は技術書典3にて頒布した「KLabTechBook Vol.1」に掲載したものです。

現在開催中の技術書典14にて新刊「KLabTechBook Vol.11」を頒布（電子版無料、紙+電子 500円）しています。 また、KLabのブログからすべての既刊のPDFを無料DLできます。 合わせてごらんください。

KLabTechBook Vol.11

M4とは、1977年にブライアン・カーニハンとデニス・リッチー（いわずと知れたK&Rその人らである）によって作成されたテキストマクロプロセッサである1。 POSIXにも含まれる基本的なコマンドだが2、読者諸氏の多くはこのコマンドを明示的に使ったことは無いだろう。 しかしながら、間接的にM4の恩恵を受けている人は少なくないはずだ。

configureスクリプト。数多くのOSSで採用されているこのビルド設定スクリプトは、 GNU Autoconfにより呼び出されたM4によって生成されている3。 他にもSendmailの設定ファイルの生成に利用されるなど4、縁の下の力持ちといったツールである。

登場から40年となるこのマクロプロセッサは、驚くべきことにチューリング完全性を備えている。 つまり、コンピュータ黎明期に作られたプログラミング言語のひとつと言っても過言ではない。 しかし、テキストマクロプロセッサ、すなわちテキストの置換という単純作業の繰り返しが チューリング完全になるとは俄に信じがたい。

この章ではそれを確かめるべく、M4のチューリング完全性の証明を試みる。

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

チューリング完全性の一般的な証明方法として、 すでにチューリング完全であることがわかっている言語の処理系を実装するという手法がある。 言い換えると、チューリング完全な言語で書かれたプログラムをすべて実行できるならば、 それはチューリング完全である。

ここでは、チューリング完全な言語であるBrainfuck5（BF）をM4で実装することにより、 M4のチューリング完全性を証明する。

実装方法

この節では、M4によるBFの具体的な実装方法について解説する。 なお、ここで扱うM4はGNU M46とし、 実装したM4の完全なコードはGitHubにて公開しているので7、適宜参照されたい。

BFコードの読み込みとマクロ列への変換

まずBFのコードは標準入力から受け取るものとし、 includeマクロを利用して/dev/stdinをまるごと取り込むようにした。

M4ではBFの命令に使われているような記号そのものをマクロとして処理できないため、 取り込んだBFコードを表1にしたがって、BF命令1文字ずつ対応する文字列に変換し、マクロの列に変換した。 この処理を行うM4マクロをリスト1に示す。

表1 BF命令と変換文字列の対応表
  BF命令 変換文字列
ポインタのインクリメント > `'ip
ポインタのデクリメント < `'dp
ポインタの指す値のインクリメント + `'ic
ポインタの指す値のデクリメント - `'dc
ポインタの指す値の表示 . `'pr
ループ開始点 [ `'bn(`
ループ終点 ] ')`'ed
リスト1 BFコードを読み込みマクロ列へ変換する
# 引数の1文字を対応する文字列に変換するマクロ
define(`token', `changequote({,})ifelse(
		{$1}, {>}, {`'ip},
		{$1}, {<}, {`'dp},
		{$1}, {+}, {`'ic},
		{$1}, {-}, {`'dc},
		{$1}, {.}, {`'pr},
		{$1}, {[}, {`'bn(`},
		{$1}, {]}, {')`'ed}){}changequote')

# 1文字ずつtokenマクロにかけるマクロ
# 引数の長さが0になるまで再帰的に呼び出す
define(`parse', `ifelse(
	eval(len(`$*')>0), 1,
	`token(substr(`$*',0,1))`'parse(substr(`$*',1))')')

# 標準入力をまるごとparseマクロにかけ、その結果をinternalとして定義する
define(`internal', parse(include(`/dev/stdin')))

ここで定義したparseマクロは、引数文字列の先頭1文字を取り出してtokenマクロに渡し、 残りの文字列を自分自身に再び渡すという、再帰的なマクロである。

このマクロにより、たとえば!1文字を表示するBFのプログラムを変換すると リスト2のようになる。

リスト2 !を表示するBFプログラムと変換後のマクロ列
変換前：
>++++[-<++++++++>]<+.

変換後（改行は含まない）：
`'ip`'ic`'ic`'ic`'ic`'bn(``'dc`'dp`'ic`'ic`'ic`'ic`'ic`'ic`'ic`'ic`'ip')
`'ed`'dp`'ic`'pr

ここで`'は空文字列で、マクロ同士のデリミタとして働く。 また、BFにおいてループを表す[〜]は、bn(`〜')`'edのように展開され、 間に入るマクロ列がまるごとクォートされた文字列としてbnマクロの引数になるように変換される。

ポインタとバイト配列

BFのメモリ空間は、30000要素以上のバイト配列とその上を自由に動くポインタで構成される。

M4には配列が無いため、バイト配列をそのまま実装することはできない。 そこで、数字入りのマクロを動的に定義することで擬似的な配列とした。 つまり、_0_、_1_、…_30000_といった具合のマクロを配列の要素として扱う。

ポインタはptrというマクロを初期値0として定義し、この定義を動的に書き換えることで実現した。

ポインタの値はdefnマクロでptrの定義を取り出せば参照でき、 ポインタの指す値は_でポインタの値を挟んだマクロ名の定義を取り出せばよい。 これらの処理の実装をリスト3に示す。

リスト3 ポインタとバイト配列の実装
# ポインタの定義. 0で初期化
define(`ptr', `0')

# 擬似的な配列からポインタの指す値を取り出すマクロ
define(`cv', `eval(defn(`_'defn(`ptr')`_')+0)')

cvマクロはeval(〜+0)と実装した。 これにより、たとえば_1_が未定義だった場合その定義は空文字列になるので、 cvはeval(+0)となり、0に展開される。 バイト配列の要素の初期値は0クリアされているというBFの仕様をこのような形で実現した。

各命令に対応するマクロの実装

ここからBFの各命令に対応するマクロを実装していく。

ポインタのインクリメント・デクリメント（> <）

前述のとおり、ポインタの操作はptrマクロを動的に書き換えることで実現した。

リスト4 ポインタのインクリメント・デクリメントの実装
# ポインタのインクリメント (>)
define(`ip', `define(`ptr', incr(defn(`ptr')))`'')

# ポインタのデクリメント ptr (<)
define(`dp', `define(`ptr', decr(defn(`ptr')))`'')

M4ではdefineマクロで既存の定義を上書きできることに加え、 incr・decrという引数の値をインクリメント・デクリメントするマクロも用意されている。

これを利用して、「defn(`ptr')で取り出したポインタの値をincrマクロに渡し、 その結果を新たなptrとして定義しなおす」という文字列に展開されるマクロとしてipを定義した。 つまり、処理対象のテキストにipが現れるたび、 define(`ptr', incr(defn(`ptr')))`'という文字列に置き換わり、それが処理される。

ポインタのデクリメントはincrの代わりにdecrを使う以外は同じである。

ポインタの指す値のインクリメント・デクリメント（+ -）

この命令もM4のincr・decrを利用し、 すでに定義したcvマクロで取り出した値を処理するようにした。

書き換えるべきマクロ名は、前述のとおり、_でポインタの値を挟んだ文字列である。

リスト5 ポインタの指す値のインクリメント・デクリメントの実装
# ポインタの指す値のインクリメント (+)
define(`ic', `define(`_'defn(`ptr')`_', incr(cv))`'')

# ポインタの指す値のデクリメント (-)
define(`dc', `define(`_'defn(`ptr')`_', decr(cv))`'')

ループ（[ ]）

リスト6 ループの実装
# ループ開始点 ([)
define(`bn', `pushdef(`s', `ifelse(eval(cv>0), 1, `$1`'s')')')

# ループの終点 (])
define(`ed', `s`'popdef(`s')')

BFで[ ]に囲まれた部分に対応するマクロ列が、 クォートされた文字列としてbnマクロの引数になることはすでに解説した。

bnではsという名前の、 「cvが0より大きい間、引数（$1）をそのまま展開してからs自身を呼び出す」という 再帰的なマクロを定義している。 そしてループ終点にあたるedマクロにより、 bnで定義されたsが展開され、ループが始まる。

ここでsの定義にはdefineではなくpushdefを使っている。 M4ではpushdef・popdefによりマクロの定義をスタックできる。 これを利用し、多重ループでもsの定義を内側のループで上書きしてしまわないよう実装した。

ポインタの指す値の表示（.）

M4にはC言語のprintf同様のフォーマットで書式化できるformatマクロがある。 ポインタの指す値をそのまま%cで書式化する方法で実装した。

リスト7 ポインタの指す値を表示するマクロの実装
define(`pr', `format(`%c', cv)')

プログラムの実行

ここまででBFの各命令に対応するマクロが定義できた。 この後にBFプログラムから変換しておいたマクロ列、すなわちinternalマクロを展開することで、 マクロ列の中の命令マクロが順次展開され、プログラムが実行される。

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

これにてM4によるBFの実装は完了である。 実際に動作するかどうかはぜひ各々で検証してほしい。

さて、ここでBFに詳しい読者諸氏であれば、命令がひとつ足りないことに気づいたであろう。 そう、標準入力から1文字読み込む,命令である。

今回の実装では標準入力をBFプログラムの入力としてしまっている都合上、 ,にあたる命令を実装することは不可能である。 しかし、その命令によって入力したい文字がたとえばAならば、 ,の代わりに+を65個並べることで代用できる。 つまり、すべての,は別のBFコードに置き換えることが原理的に可能なので、 この命令が無かったところでチューリング完全性が失われることはない。

このように、M4により動作するBFのチューリング完全なサブセットを実装することができた。 したがって、テキストマクロプロセッサ「M4」はチューリング完全である。

終わりに

広く使われているテキストマクロプロセッサといえば、C言語のプリプロセッサを思い浮かべる人も多いだろう。 しかしM4と違い、Cプリプロセッサ単体ではチューリング完全ではない。 この差の要因のひとつは、マクロの再帰的な呼び出し（あるいはループ）ができるかどうかである。

テキストマクロプロセッサにチューリング完全性が必要かどうかはさておき、 M4はチューリング完全性を備えた強力なツールであることは理解していただけたと思う。 そしてその歴史も長く広く使われており、これ以上ないほど安定している。

もし定型的なテキストを量産するような作業に出会った時、 貧弱なテンプレートエンジンを自作する前にM4のことを思い出してみてはいかがだろうか。 書式はややまどろっこしいかもしれないが、やりたいことがすべてできることは証明済みだ。

まあそんなこと言っても積極的に使ったりしないですけどね。

  1. http://wolfram.schneider.org/bsd/7thEdManVol2/m4/m4.pdf ↩

  2. http://pubs.opengroup.org/onlinepubs/9699919799/utilities/m4.html ↩

  3. https://www.gnu.org/software/autoconf/autoconf.html ↩

  4. http://www.sendmail.org/~ca/email/doc8.12/cf/m4/intro_m4.html ↩

  5. http://www.muppetlabs.com/~breadbox/bf/ ↩

  6. https://www.gnu.org/software/m4/m4.html ↩

  7. https://github.com/makiuchi-d/bfm4 ↩