超絶技巧プログラミングやってみた

By Shotaro Kohama on December 17, 2015

この記事は CAMPHOR- Advent Calendar 2015 の 17 日目の記事です。

こんにちは。@shotarok (Twitter: @shotarok28) です。３月までは京都で学生をしていて、今年の４月から東京の FreakOut という広告の会社でソフトウェアエンジニアをしている CAMPHOR- OBです。

Quine って何？

みなさん「Quine」という言葉を聞いたことがありますか？ Quine とは、こんなプログラムのことです。 ※1

クワイン（英: Quine）は、コンピュータプログラムの一種で、自身のソースコードと完全に同じ文字列を出力するプログラムである。
出典: wikipedia クワイン_(プログラミング)

定義を読むだけでは、ぱっとはわからないので、実際にプログラムが動いているところを見てみましょう。

この gif をみると ruby プログラム quine.rb は CAMPHOR- のロゴの形をしていること、ruby で実行すると CAMPHOR- のロゴが出力されることが確認出来ると思います。実は quine.rb は自分自身を出力していて、その出力を実行してもまた同じロゴの形をしたソースコードが出力されます。wiki に書いてあった 自身のソースコードと完全に同じ文字列を出力するプログラム. こんなプログラムが Quine です。ソースコードはこちら(gist)。

僕が初めて Quine に出会ったのは、いつかの ICPC の地区大会のエクスカーションで Google を訪問して、そこで shinh さんのお話を聞いたときでした。その当時は、自分で書いてみたいと思って、調べてみたものの、結局書くことが出来ず、そのまま放置になっていました。

それから数年経った2015年夏、この本と出会いました。

「あなたの知らない超絶技巧プログラミングの世界」

この本は Quine をはじめとする「超絶技巧プログラミング」と呼ばれる、実用性はないけれど、不思議で楽しいプログラミング技法を紹介しています。そして、この本のおかげで念願叶い Quine を書くことができました。詳細な解説は本を読んで頂くことにして、この記事では、僕が書いた quine.rb の簡単な説明と、作成した手順を紹介できればと思います。

はじめての Quine

今回、下のような流れで僕は quine.rb を作成しました。

CAMPHOR- のロゴ画像からコードの整形に使うビットマップの作成。
ビットマップから quine.rb を出力する build_quine.rb を作成。
quine.rb が文法的に正しくなっているかを実行して確認。
失敗したら、 2. に戻ってビットマップを調整。
成功したら、Quine 完成！

1. ロゴ画像からビットマップの作成

まずは quine.rb をロゴの形にするための雛形を画像から作成します。これは jpeg 画像から ASCII アートを生成してくれる jp2a と png から jpeg に変換する convert を使うと作業が楽になります。(OSX をお使いの方は両方とも Homebrew でインストールできます) これらを使うと、例えば、こんな感じでビットマップを作成できます。

$ wget https://camph.net/static/images/navbar_logo.png
$ convert navbar_logo.png jpg:- | jp2a - --chars=012 | tr '2' ' '
1111111                                                        111111                                                                                                                            
 1111111111                                              1111111111                                                                                                                             
  1111111111111                                      111111111111                                                                                                                               
    1111111111111                                 11111111111111                                                                                                                                
      11111111111111                            1111111111111                                                                                                                                   
         1111111111111                       11111111111111                                                                                                                                     
            1111111111111                  111111111111                                                                                                                                         
                1111111111               11111111111                                                                                                                                            
                     111111             111111                                                                                                                                                  
                            111111111111                                                                                                                                                        
                              111111111                                                                                                                                                         
                              1111111                                                                                                                                                           
                               11111                                                                                                                                                            
                                1111                                                                                                                                                            
                                111                                                                                                                                                             
                                 11                                                                                                                                                             
                                 11

2. ビットマップから Quine を作る

作成したビットマップを使ってロゴの形をした Quine を出力する build_quine.rb を作ります。天下り的ですが、まずは build_quine.rb を御覧ください。

これを実行すると quine.rb が出てきます。このコードが何をやっているかを上から順に説明していきます！

Line1-2

ここが Quine の本体と言っても過言ではありません。実はロゴの形にする気がなければ Quine はこんなワンライナーで実現できます。

$ ruby -e 'eval$s=%w(puts(s=%(eval$s=%w(#{$s})*""));)*""'
> eval$s=%w(puts(s=%(eval$s=%w(#{$s})*""));)*""

ざくっと説明すると、変数 $s にソースコードを文字列として代入しています。その代入された文字列内の #{$s} 部分で、変数 $s が展開されて、これが自分自身を出力する秘訣になっています。

また %w(...)*"" は %w で作った文字列型が入った配列を空文字列で join しており，このおかげでソースコードをロゴの形に加工できるようになっています。

$ ruby -e 'eval$s=%w(put
s(s=%(ev
al$s=%w(#{$
s})*"")
);)*""
'
> eval$s=%w(puts(s=%(eval$s=%w(#{$s})*""));)*""

本ではもっと順を追って丁寧に解説されていますので、気になる方は是非ご一読下さい。

Line4

変数 bidmap には、ロゴから作成されたビットマップを36変数に変換したものを入れています。 ruby は多倍長整数と to_s で36進数の変換をサポートしているので、下のようにビットマップから36進数に変換できます。

$ ruby -e 'LOGO=<<END
11111                                     11111
 11111111                             11111111
    1111111111                     1111111111
     111111111                 111111111
         11111111             11111111
            1111111         111111
                    1111111
                     11111
                      111
                      111
                       1
END
puts(LOGO.gsub(/\n/, "").gsub(/[^1]/, "0").reverse.to_i(2).to_s(36));'
> 3mf7nxp6d7yn1up5cf7lkyiexikdcs9mo4xw8j2dv93putn0tbabu2ep3qmdxdel52h7zfwbq7lzz9j8q9amz55h91pwj127

Line6-12

ここの部分は変数 bidmap を使って、ロゴの形でコードを出力しています。bidmap を多倍長整数にして 1bitずつ走査して 1 の場合はコードを1文字出力し、0 の場合は空白 32.chr を出力します。※2.

3. `quine.rb` の動作確認

ここまで来たら、後は微調整です。とは言ってもここが地味に大変だったりするのですが…。

%w() で囲まれた部分は好きに改行できるのですが、eval$s=%w(...)*"" の部分は ruby の文法的に正しくないといけません。正しい文法になるように、ビットマップを調整しましょう。

またビットマップが大きくてソースコードが埋め込めるところが少ないと bitmap が大きくなってコードがはみ出てしまいます。ビットマップを反転させたり、ロゴに含まれるフォントを大きくしたり、コードがはみ出ないようにビットマップを調整しましょう。

逆にビットマップが十分大きくて、ソースコードが足りない場合もあります。そんな時はコメント ; が利用できます。 ; は適切な位置にあれば、どれだけ追加しても文法的に正しいコードとなります。※3.

$ ruby -e 'puts("hello")'
> hello
$ ruby -e ';;;;;;;;;puts("hello");;;;;;;'
> hello

今回はロゴを一つだけ埋め込みましたが、本に紹介されている手法を使えば、下の gif のように複数のロゴを埋め込こんで Quine を作ることもできます。ただ数を増やせば増やすほど、この最後の調整が大変になりました。

最後に

いかがだったでしょうか。自分しか読めないようなメンテナンス不能なコードを「あぁこの bitmap だと実行できない」と１文字消したり足したりするのは、業務にはない楽しさがありました。※4.

超絶技巧プログラミング本には Quine 以外にもいろんな言語で実行できるプログラム、使える文字制限したプログラムなど楽しい超絶技巧が紹介されています。また、つい先日行われた Ruby Kaigi で開催された TRICK 2015 や、先ほどの本の著者である @mametter さんのスライド、また shinh さんの作品ページなども覗いてみると楽しいと思います！

明日は @yui-9 による「型クラスを含んだ型推論を概観する〜Typing Haskell in Haskell より〜」のお話です。お楽しみに！

※1. もともとは、クワインさんという哲学者の名前です。
※2. 空白は %w(...)*"" で潰れてしまうので 32.chr を使用します。
※3. ; だと見栄えが悪いので、ランダムな文字列で埋めちゃっても良いと思います。
※4. commit もせずにコードを書いたり消したり推敲する。ハッカーと画家は似ているという話を思い出しました。