LispのFizzBuzzを解説してみる

はじめに

について解説します。
おそらく出典は
https://gist.github.com/youz/8e2296ce36087a6cc859f174315d187c
だと思います。

元コード

(dotimes'101(format t"~&~[~;~A~v^~;~;Fi~;~;Bu~:;~v^FizzBu~]zz"(gcd .'15).'0))

とりあえずmacroexpandしてみます。

* (macroexpand '(dotimes'101(format t"~&~[~;~A~v^~;~;Fi~;~;Bu~:;~v^FizzBu~]zz"(gcd .'15).'0)))
(BLOCK NIL
  (LET ((QUOTE 0))
    (DECLARE (TYPE UNSIGNED-BYTE QUOTE))
    (TAGBODY
      (GO #:G446)
     #:G445
      (TAGBODY
        (FORMAT T "~&~[~;~A~v^~;~;Fi~;~;Bu~:;~v^FizzBu~]zz" (GCD QUOTE 15)
                QUOTE 0))
      (PSETQ QUOTE (1+ QUOTE))
     #:G446
      (UNLESS (>= QUOTE 101) (GO #:G445))
      (RETURN-FROM NIL (PROGN NIL)))))

Lisperならなんとなくの構造はつかめるのではないでしょうか。

外側から見てみる

(dotimes '101 X)

まずdotimesは他の言語でのforなどに相当するループのマクロです。
本来の記法は

(dotimes (x 101) (print x))

のように用います。この場合0~100までの数値がprintされます。
'はlispのスペシャルフォームであり、'101は(quote 101)に展開されます。なので、

(dotimes (quote 101) X)

に展開されます(よく思いつくなこれ...)。今後quoteにバインドされる数値をQと表記します(quoteでは混同するため)。

(format X)

次にformatです。
最初から見てみましょう。

第一引数 t 標準出力に出力

nilの場合返り値になります。今回は標準出力なのでt。

第二引数 "" control-string

formatでは、第二引数に出力コントロール用の記号(formatディレクティブ)を含む文字列をとってそのコントロール通りに出力します。第三引数以降はformatディレクティブが用いる引数です。
例えば
(format t "~5Aa" 1)
は~5Aがformatディレクティブです。~はformatディレクティブの開始位置を示します。終端位置はAなどの指定されたディレクティブ指定文字です。開始位置でも終端位置でもない部分はパラメータでありformatディレクティブの振る舞いを制御します。Aのディレクティブ指定文字は引数をひとつとって出力するので引数の1が出力されます。このとき、パラメータの5は後ろに文字をパディングするため1とaの間に空白文字を5つ入れます。

~& 行頭でなければ改行

Q=0の時は行頭ではないので改行されません。

~[~;~;~] 引数を1つとって;で区切られた部分を出力する

(format t "~[0~;1~;2~;3~]" 1)
0スタートかつ最後の一つ前の;が:;だった場合当てはまらないそれ以上の数になるので

第三引数	出力される部分
0
1	~A~v^
2
3	Fi
4
5	Bu
6以上	~v^FizzBu

が出力されます。ここに渡される引数は(GCD QUOTE 15)に展開されるので、Qと15の共通因数が渡されます。なので共通因数がない(互いに素)場合1に、3で割り切れる(Qに3の因数がある)場合3に...となります。

~A なんでも出力

おなじみなんでも出力です(ここはAである必要はなくDやSでも動きます)。第四引数に対応します。

~v^ 処理打ち切り

まず^は条件を満たした時にformatの処理を打ち切ります。
これがあるためQが3でも5でも割り切れない場合後続のzzも出力されなくなります。
vは特殊な文字で、パラメータに存在する場合formatの引数をとってパラメータにします。^は第一パラメータが指定されている場合、第一パラメータ=0が条件になり第三引数は0なので必ず処理が打ち切られます。

Fi Bu (文字出力)

そのままFiとBuが出力されます(処理が継続するのでzzが後に出力されます)。

~v^FizzBu (処理打ち切り+文字出力)

~v^は前述の通り引数をひとつとって引数=0のとき処理を打ち切ります。これは(gcd Q 15)が6以上の場合に出力されるのですが、commonlispはどちらかが0の場合最大の因数を返すので、Q=0のとき15を返します。FizzBuzzは1始まりなのでQ=0の時に何も表示しないようにこの部分があります。Q/=0の場合はFizzbuを出力します(処理が継続するのでzzが後に出力されます)。

第三引数 (gcd .' 15)

まず、これは(gcd quote 15)に展開されます(なぜ.'がquoteに展開されるかはわかりません...わかる人情報ください...)。
前述の通り~[~;~;~]にQと15の共通因数が渡されます。なので共通因数がない(互いに素)場合1に、3で割り切れる(Qに3の因数がある)場合3に...となります。

第四引数 .'

前述の通りquoteに展開されます。3でも5でも割れない場合の数値の出力と0の場合の処理打ち切りに利用されます。

第五引数 0

3でも5でも割れない場合の処理打ち切りに利用されます。

終わりに

formatを用いたcodegolfについて解説しました。自分でも知らない仕様があったので勉強にもなりました。特にdotimesとquoteの組み合わせはかなり衝撃的でした。今後使う機会があるかはわかりませんが...

参考文献

http://ais.sys.i.kyoto-u.ac.jp/~task/format-func.html
http://www.lispworks.com/documentation/HyperSpec/Body/s_quote.htm#quote