時代遅れひとりFizzBuzz祭り GNU m4編(20言語目なので特別編)

時代遅れひとりFizzBuzz祭り、今回は――気がついたら20言語目ということで特別編。GNU m4によるFizzBuzzの作成開始から完成までの流れを書いてみることにした。

これはつまり、自分がどのような思考過程を経てFizzBuzzを実装したかを晒す訳で、結構勇気がいる。「嗚呼、何て無駄を……」とか「何だよその変態的思考はっ」とか色々と突っ込まれる気がしてならない。

それはともかく、GNU m4は私にとっていわくつきの言語だ*1。以前Windows上でテキスト置換のツールとして使おうとして、日本語がらみの変換がうまくいかなくて止めたのだ*2。その時は実質的に「触る」の「さ」の字にも満たない程度だった。

だが今回は日本語を使わないFizzBuzzなので心配は無用だ。GnuWin32のGNU m4 1.4.4でチャレンジしてみた。

書く前にm4の日本語資料を探す

何はともあれ、コードを書く前にm4のマニュアル等が欲しい。できれば日本語のもの。

日本語でのまとまった資料はこれぐらいしか見つからなかった。

GNU m4のマニュアル日本語訳は別のサイトでも公開されていたが、ここでは省略する。

とりあえず3の倍数を `Fizz' に変換する仕組みを考える

ではさっそくFizzBuzzを書こうと思うが、m4のことは殆ど分からない状態*3なので、いきなり大きなことに手を出すのは危険だ。まずは小さな所で、3の倍数を `Fizz' に変換する方法から挑戦してみる。

与えられた値が1以上の正の整数である場合、それが3の倍数か否か判定する方法としては「3で割った際の剰余が0であるか否か調べる」というものが考えられる。

m4はマクロプロセッサなのでテキスト置換がメインの機能となるが、整数式を計算するevalという組み込みマクロがある。

eval(1 % 3)
eval(2 % 3)
eval(3 % 3)

これで3で割った剰余を求めることができる。注意点:evalが返す結果は文字列だ。

次に、剰余が0か否か調べるにはどうするか? 文字列を比較する条件構文ifelseを使えばよさそうだ。

ifelse(eval(1 % 3), `0', `Fizz')
ifelse(eval(2 % 3), `0', `Fizz')
ifelse(eval(3 % 3), `0', `Fizz')

ifelseの引数の書き方は4パターンぐらいあるが、単純なif - elseの場合は引数を4つとる。第1引数と第2引数の文字列が等しければ第3引数を、でなければ第4引数を展開した結果を返す。

ここで書いたように引数が3つの場合はどうなるか? 第1引数と第2引数が等しければ第3引数を展開した結果を返すが、等しくない場合は何も返さない(空の文字列を返す)。

ちなみにifelseは引数を4つより多くとることもできる。この場合はswitchやcondのような多岐分岐の処理になる。

3の倍数を `Fizz' に変換する方法は分かったので、これをマクロとして定義して再利用できるようにしよう。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl

defineでマクロを定義する。第1引数がマクロ名で、第2引数が展開される内容だ。引数をとるマクロの場合、シェルスクリプトのように `$1' といった記号で引数にアクセスする。末尾の組み込みマクロdnlは、dnlより右にある文字を(末尾の改行も含めて)全て読み捨てる。ここではこのdefineの行が空白行として出力されるのを防ぐ為に使用している。

定義したマクロfizzはこんな感じに使う。

fizz(1)
fizz(2)
fizz(3)

引数が3の倍数なら `Fizz' に変換される。でなければ空の文字列になる。

同じ仕組みでマクロbuzzも定義しておこう。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl
define(`buzz', `ifelse(eval($1 % 5), `0', `Buzz')')dnl

3か5の倍数なら所定の文字列を、でなければ数値を返すようにしてみる

定義したマクロfizzとbuzzを使えば、3か5の倍数の時に所定の文字列に変換する仕組みを作れる。まずは「3か5の倍数なら所定の文字列を返す」という部分だけを考えてみた。

define(`transform', `fizz($1)`'buzz($1)')dnl

このマクロtransformは、3の倍数なら `Fizz' を、5の倍数なら `Buzz' を、両者に当てはまるなら `FizzBuzz' を、どちらも当てはまらないなら空の文字列を返す。

これを使って「どちらも当てはまらないなら数値をそのまま返す」という風に拡張してみた。

define(`fizzbuzz', `ifelse(transform($1), `', $1, transform($1))')dnl

変換した結果が空の文字列なら引数の値をそのまま返す。でなければ変換して返す。実は2度も変換している所が不満なのだが……。

ここまでの成果で一旦FizzBuzzしてみる。

この時点でのコードはこんな感じ。fizzbuzz1.m4という名前で保存しておく。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl
define(`buzz', `ifelse(eval($1 % 5), `0', `Buzz')')dnl
define(`transform', `fizz($1)`'buzz($1)')dnl
define(`fizzbuzz', `ifelse(transform($1), `', $1, transform($1))')dnl

このスクリプトを実行しても、まだなにも表示されない。

ただ `fizzbuzz(1)' から `fizzbuzz(100)' まで順番に定義すれば、変換結果としてFizzBuzzの出力が得られるはずだ。手作業で定義するのは面倒なので、seqとsedを使って自動的に生成して流し込み、動作を確認してみた。

seq 1 100 | sed 's/^\([1-9][0-9]*\)$/fizzbuzz(\1)/' | m4 fizzbuzz1.m4 -

先に変換処理を書いてあるfizzbuzz1.m4を読み込み、その後に標準入力から自動生成した `fizzbuzz(1)' 〜 `fizzbuzz(100)' を流し込んでいる。出力結果を見る限り、特に問題はなさそうだ。

ところでGNU m4の拡張として、コマンドを実行して結果の出力を読み込むesyscmdというマクロがある。このマクロを使ってこうするとFizzBuzzが完成する。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl
define(`buzz', `ifelse(eval($1 % 5), `0', `Buzz')')dnl
define(`transform', `fizz($1)`'buzz($1)')dnl
define(`fizzbuzz', `ifelse(transform($1), `', $1, transform($1))')dnl
esyscmd(`seq 1 100 | sed "s/^\([1-9][0-9]*\)$/fizzbuzz(\1)/"')dnl

しかし、できれば外部のツールを使わずに実装したい。

外部ツールを使わず自力でFizzBuzzさせる

自力で1から100までFizzBuzzするにはループ処理が必要となる。しかしm4にはループ処理の為のマクロは存在しない。なので再帰で書く。

ただ、いきなりFizzBuzz用のループを再帰で書こうとすると躓く可能性があるので、まずは単純に1から100まで生成させてみる。

define(`range',
       `ifelse(eval($1 >= $2), `1', `$1', `range($1, decr($2))'`, $2')')dnl

このマクロrangeは第1引数に初期値を、第2引数に終了値を指定すると、コンマ区切りの数列を生成する。エラーチェックが甘いのは仕様だ*4。中で使っている組み込みマクロdecrは、名前から想像がつくと思うが数値をデクリメントする。

数列を生成できるようになったので、今度は数列に対してマクロfizzbuzzを適用させてみる。

define(`apply_fizzbuzz',
       `ifelse($#, 1, `fizzbuzz($1)', `fizzbuzz($1)
apply_fizzbuzz(shift($@))')')dnl

`$#' は引数の個数を返す。`$@' は全ての引数をコンマ区切りで返す*5。組み込みマクロshiftは最初の引数を取り除き、残りの引数をコンマ区切りで返す。`shift($@)' という書き方は引数への反復処理でよく使うようだ。

ifelseの第4引数中で改行しているので注意。FizzBuzzした結果を改行区切りで出力する為にこうしている。

ここまでのコードはこんな感じになる。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl
define(`buzz', `ifelse(eval($1 % 5), `0', `Buzz')')dnl
define(`transform', `fizz($1)`'buzz($1)')dnl
define(`fizzbuzz', `ifelse(transform($1), `', $1, transform($1))')dnl
define(`range',
       `ifelse(eval($1 >= $2), `1', `$1', `range($1, decr($2))'`, $2')')dnl
define(`apply_fizzbuzz',
       `ifelse($#, 1, `fizzbuzz($1)', `fizzbuzz($1)
apply_fizzbuzz(shift($@))')')dnl
apply_fizzbuzz(range(1, 100))

このスクリプトを実行すれば、FizzBuzzの結果が出力される。

ループ回りをちょっとだけ整理して一旦完成

ここまでのスクリプトでも問題なく動くが、ループ回りを1つにまとめてスッキリさせてみた。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl
define(`buzz', `ifelse(eval($1 % 5), `0', `Buzz')')dnl
define(`transform', `fizz($1)`'buzz($1)')dnl
define(`fizzbuzz', `ifelse(transform($1), `', $1, transform($1))')dnl
define(`do_fizzbuzz',
       `ifelse($1, `1', `fizzbuzz($1)', `do_fizzbuzz(decr($1))
fizzbuzz($1)')')dnl
do_fizzbuzz(100)

マクロdo_fizzbuzzには「引数は1以上の数値である」という暗黙の前提がある。これを守らないと正しく動作しない。

このバージョンの方が高速だ。データ数が少ないうちは気にならないが、例えば1〜10000までFizzBuzzさせてみると前のバージョンは圧倒的に遅くなる。

bash-3.1$ uname -a
windows32 fabrico 2.5.1 2600 i686-pc Intel unknown MinGW
bash-3.1$ m4 --version
GNU M4 1.4.4
Written by Rene' Seindal.

Copyright (C) 2005 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
bash-3.1$ tail -n 1 fizzbuzz2a.m4
esyscmd(`seq 1 10000 | sed "s/^\([1-9][0-9]*\)$/fizzbuzz(\1)/"')dnl
bash-3.1$ time m4 fizzbuzz2a.m4 > /dev/null

real    0m0.922s
user    0m0.015s
sys     0m0.015s
bash-3.1$ tail -n 1 fizzbuzz3a.m4
apply_fizzbuzz(range(1, 10000))
bash-3.1$ time m4 fizzbuzz3a.m4 > /dev/null

real    0m27.766s
user    0m0.015s
sys     0m0.000s
bash-3.1$ tail -n 1 fizzbuzz4a.m4
do_fizzbuzz(10000)
bash-3.1$ time m4 fizzbuzz4a.m4 > /dev/null

real    0m0.344s
user    0m0.015s
sys     0m0.015s
bash-3.1$ _

fizzbuzz2a.m4はseqとsedを使うバージョン、fizzbuzz3a.m4が前のバージョン、fizzbuzz4a.m4が現時点のバージョンだ。それぞれ1〜10000までFizzBuzzしている。前のバージョンは28秒弱も掛かっていて、随分と遅い。

落ち穂拾い

一応完成したが、幾つかやり残したことがある。そのうちの難易度が低そうなものに対応してみる。

まずマクロfizzbuzzの中でマクロtransformを2度も展開しているのだが、1度の展開で済むようにできないだろうか? 論理的には、transformを展開した結果を一旦マクロとして定義し、そのマクロを使いまわせばよさそうだ。

組み込みマクロの中にマクロを一時的に再定義するpushdefと元の定義に戻すpopdefがあるので、それを使ってみた。

define(`fizzbuzz',
       `pushdef(`msg', transform($1))ifelse(msg, `', $1, msg)`'popdef(`msg')')dnl

pushdefやpopdefのコスト次第だが、マクロ展開の回数が若干減るはずなので、微妙に高速になる可能性がある。

次にマクロdo_fizzbuzzに異常入力に対する処理を追加する。とはいっても「引数は数値である」という暗黙の前提は残っているが……。

define(`do_fizzbuzz',
       `ifelse(eval($1 < 1), `1', `',
               $1, `1', `fizzbuzz($1)',
               `do_fizzbuzz(decr($1))
fizzbuzz($1)')')dnl

とりあえずこんな感じにしてみた。

  • 1未満なら何も返さない。
  • 1以上なら、1を始点として指定した個数だけFizzBuzzした結果を返す。

ifelseによる多岐分岐になった。

という訳で、コード全体はこんな感じ。

define(`fizz', `ifelse(eval($1 % 3), `0', `Fizz')')dnl
define(`buzz', `ifelse(eval($1 % 5), `0', `Buzz')')dnl
define(`transform', `fizz($1)`'buzz($1)')dnl
define(`fizzbuzz',
       `pushdef(`msg', transform($1))ifelse(msg, `', $1, msg)`'popdef(`msg')')dnl
define(`do_fizzbuzz',
       `ifelse(eval($1 < 1), `1', `',
               $1, `1', `fizzbuzz($1)',
               `do_fizzbuzz(decr($1))
fizzbuzz($1)')')dnl
do_fizzbuzz(100)

このバージョンは、1つ前のバージョンと比較して高速なのだろうか? 再び1〜10000までのFizzBuzzで計測してみる。

bash-3.1$ tail -n 1 fizzbuzz4a.m4
do_fizzbuzz(10000)
bash-3.1$ time m4 fizzbuzz4a.m4 > /dev/null

real    0m0.344s
user    0m0.015s
sys     0m0.015s
bash-3.1$ tail -n 1 fizzbuzz5a.m4
do_fizzbuzz(10000)
bash-3.1$ time m4 fizzbuzz5a.m4 > /dev/null

real    0m0.313s
user    0m0.015s
sys     0m0.015s
bash-3.1$ _

fizzbuzz5a.m4が現時点のバージョンだ。

何回か計測してみたが、10〜30ミリ秒ほど高速になっている気がする。内部のタイマの刻みや精度の問題があるので、実際のところは不明だ。どちらにしろユーザにとって有意な差があるとは言えない。

GNU m4はオプション `-dt' を付けると全てのマクロ呼び出しをトレース表示する。1行につき1マクロで表示されるので、wcを使ってマクロ展開の回数を調べることができる。

bash-3.1$ tail -n 1 fizzbuzz2.m4
esyscmd(`seq 1 100 | sed "s/^\([1-9][0-9]*\)$/fizzbuzz(\1)/"')dnl
bash-3.1$ (m4 -dt fizzbuzz2.m4 > /dev/null) 2>&1 | wc -l
1610
bash-3.1$ tail -n 1 fizzbuzz3.m4
apply_fizzbuzz(range(1, 100))
bash-3.1$ (m4 -dt fizzbuzz3.m4 > /dev/null) 2>&1 | wc -l
2310
bash-3.1$ tail -n 1 fizzbuzz4.m4
do_fizzbuzz(100)
bash-3.1$ (m4 -dt fizzbuzz4.m4 > /dev/null) 2>&1 | wc -l
1909
bash-3.1$ tail -n 1 fizzbuzz5.m4
do_fizzbuzz(100)
bash-3.1$ (m4 -dt fizzbuzz5.m4 > /dev/null) 2>&1 | wc -l
1709
bash-3.1$ _

マクロ展開の回数が最も少ないのはseqとsedを使うバージョンだ。自身でループしていない分だけ少ない。但し実行時に複数のプロセスを生成するので、低速ではないが高速とも言い切れない。

逆にマクロ展開の回数が最も多いのは、数列を生成してそれにマクロfizzbuzzを適用するバージョンだ。もっともこのバージョンがデータ量が多い時に異常に遅くなる原因は、単にマクロ展開数が多いだけではないはずだ。もしそれが原因だとしたら、もっと異常なまでの展開数になっているだろう。

最後のバージョンはマクロfizzbuzz内でのマクロtransformの展開回数を減らした分だけ全体での展開回数も減っている。しかし実行速度はそれほど向上したとは言えない。恐らく性能に大きな影響を与える箇所ではなかったのだろう。

トレース表示を見ていると、m4がマクロプロセッサだということがよく分かる。ループのマクロがある場合それを全て展開して、それからループの中身の部分を順番に展開している。ループの展開が行われる辺りが実にマクロプロセッサ的だ。

心残り

  • マクロfizzとbuzzとで似たような定義を書くのもアレなので、fizzやbizzの定義を生成するようなマクロを書きたい。つまり「引数付きマクロ」を定義する引数付きマクロ。引数の展開回りがうまくいかなくて断念したが、いつか再チャレンジしたい。
  • マクロrangeの改良。もっと汎用的なマクロに拡張するとどうなるか?

この2点は解決に時間が掛かりそうなので保留。

終わりに

以上、特別編と称して普段とは異なるスタイルで書いてきた。

今回の実装のスタイルは、どちらかというとボトムアップ的だ。小さな部品を作り、それらを組み合わせて大きなものに仕立てていった。それにパーツを作る度に簡単に動作を確かめて、それから別のパーツを作る感じで進めた。

普段のスタイルもボトムアップ的だが、トップダウンと組み合わせることが多い。仕様からブレイクダウンできる所はそうするし、一方で初期の段階から「どうやって実現するのだろうか?」と疑問を抱えている部分があればボトムアップ的に実現方法を探っていく。開発規模が世間一般の水準からすると小規模な部類になるので、そんなスタイルに落ち着いている。

さて、書くのを忘れていたが、前回のT4 Text Templateとの関連はズバリ「テキスト変換」だ。どちらもコード生成に使える。m4はRatforの変換エンジンだったし、T4はVisual Studioにてコード生成用に使われている。もっともm4はともすると「言語を独自拡張する」という通好みの使い方になるが、一方のT4はテンプレート変換に主眼が置かれている訳で、その辺りのスタンスは結構違うと思う。

*1:マクロプロセッサなので言語といっていいのか微妙だけど。

*2:今考えてみれば、m4のデフォルトのトークンはC言語の識別子と同じなので、日本語をトークンとして扱えなくて当たり前なのだが……。

*3:マクロを定義するdefineぐらいしか知らない状態。

*4:「初期値 <= 終了値」という暗黙の前提がある。これが守られなかった場合の挙動が変。

*5:各引数はクォートされている。