https://www.m3tech.blog/entry/ruby-m3-quine

エムスリーエンジニアリングG コンシューマチームの松原(@ma2ge)です。

弊社では M3 の文字をアスキーアートで出力する Quine が様々な言語で作られています。筆者も Ruby バージョンを作ることにしたのですが、ただ作るだけではちょっと物足りない。そこで今回は技術的なチャレンジとして、アニメーションしながらコードの一部が空白に置き換わっても自己修復して動く Quine に挑戦してみました。

本記事では、この「壊れても動く」Quine の仕組み、特に誤り訂正処理の実装にフォーカスしてどのような仕組みとなっているか明らかにしていきます。

※誤り訂正処理の理論的な詳細については本記事では扱いません。

Quine とは

Quine とは「プログラムが出力した文字列が、ソースコード自身と完全に同じ文字列になる」ようなプログラムのことを指します。

Ruby で書いてみるとこのようになります。

eval s="puts 'eval s=' + s.inspect"

s に文字列が代入され、そのまま文字列を eval へ渡す。eval される内容は 'eval s=' と s.inspect をくっつけたものを puts しています。s には最初に eval へ渡す直前に代入した文字列が含まれているので、結果として自身と同じ文字列を生成して出力することになります。

シンプルな例だとこのようになるのですが、アスキーアートにマッピングしたり、アニメーションさせるなど技巧を凝らすことで、「本当にこれが動くコードなのですか？」とうなってしまうような作品もあります。

まずはシンプルな M3 Quine

今回は弊社内でなぜか流行っている M3 の文字をアスキーアート出力する Quine を Ruby で作ってみることにしました。社内の #crazy_programming というチャンネルにポコポコと色々な言語の Quine ができあがっていく様子を見ていて、つい作ってみたくなってしまったのです。すでに様々な言語の M3 Quine とそのテックブログ記事が公開されています。

この M3 Quine のレギュレーションは、1行あたり100文字の26行をベースとして、M3 の文字をレイアウト通りアスキーアートとして出力することです。まずはシンプルに Ruby 版を作ってみました。

レギュレーションも満たしているし完成！と言いたいところですが、Ruby のショートコーディング力の高さや、アスキーアート部の zlib による圧縮が効いており、# で埋め尽くす前の部分までが必要なコードで、残りの約3/4は不要なコメントとなっています。コードの大半を何もしないコメントが占めているのは、若干物足りなさを感じてしまいますよね？そこで今回はアニメーションから誤り訂正処理まで行うプログラムを埋め込んでみました。

誤り訂正付きアニメーション M3 Quine

今回作った Quine は GitHub に公開してあります。

次の環境で動作確認をしています。matrix, zlib gem については標準ライブラリとしてインストールされているバージョンから変更していません。

Ruby
- 3.3.10
- 3.4.8
- 4.0.1
matrix gem
- 0.4.2(Ruby 3.3.10, 3.4.8)
- 0.4.3(Ruby 4.0.1)
zlib
- 3.1.1(Ruby 3.3.10)
- 3.2.1(Ruby 3.4.8)
- 3.2.2(Ruby 4.0.1)

実行方法は通常の Ruby プログラムと同じです。ターミナルの画面サイズを100×26文字以上表示できるようにしてください。アニメーションは Ctrl+C で停止できます。

ruby m3_quine.rb

Quine の全体像

Quine の全体像を処理ごとに大まかに色分けすると次のようになります。

色分けした各部分の役割です。

誤り訂正するコード(図中茶)
- アニメーションの状態変数、誤り訂正処理、訂正後のコードを eval で実行
- 誤りがあっても復元できない部分
誤りを含むコード文字列の定義(図中緑)
- Base64 で埋め込んだビットマップを元にコードを描画、アニメーションループ、メッセージや URL の埋め込み
- 誤りを含んで良い領域(図中青)
  - d 変数に格納した文字列のうち、青部分の領域が誤りを訂正する部分
誤り訂正するコードを eval へ渡す部分(図中赤)

Quine の仕様

Quine の仕様ですが、次の条件を入れることを目指しました。

どのフレームで切っても Quine として動作
表示中に文字の位置が固定され、なめらかに次のフレームを表示

前者は作るプログラムが Quine であると考えるとぜひ満たしておきたい条件です。後者については、空白以外の部分にコードを配置する手法では、アニメーションさせて空白の位置がズレたときにコードの位置もずれてしまい、ガタガタとした表示となってしまいます。言葉だとわかりにくいので実例を挙げてみます。

空白部分を除いてコードを埋めていくと、フレーム遷移時にガタガタとした見栄えになる

画像中ではコード文字列部分が背景となっていますが、フレームが移るたびにコード文字列の描画位置が変わってガタガタした印象を受けます。記事先頭にある完成系と見比べるとよりわかりやすいかと思います。

そこでなめらかなフレーム遷移を実現するため、コードを表示領域全体に描画し、空白でコード部分を消すことでアスキーアートを表現します。「えっ、でもそうなるとコードが欠けてしまうので動かないのでは？」と思われますよね。ここで誤り訂正の出番です。

誤り訂正手法の選択

誤り訂正といっても色々な種類があります。今回取り入れた誤り訂正は、TRICK 2022 で金賞を受賞した tompng さんの作品で使われている手法を元にしました。この作品は誤り訂正を入れているためコードが欠けていても、全部で960枚あるどのフレームで切り取っても続きの状態からコード実行ができるという驚異的な内容となっています。私も話題になったときにコードを読もうと試みたのですが、その当時はほとんど何も分からずに途中で断念した覚えがあります。

この作品で使われている誤り訂正は、QRコードなどでも使われているリード・ソロモン符号をベースに、誤り位置特定部分を除いたもののようです。具体的には、使用可能な文字を89種類に限定し、素数89を法とする有限体（四則演算ができる要素数が有限の集合）として扱います。一定のブロックごとに元の文字列に対して符号化を付与し、複合時は欠損した文字列を求めるための連立方程式を行列を使って解いています。

この連立方程式を解くために、matrix gem を使用しているのですが、これを誤り訂正処理に対応させるために gem 内で使われている Integer クラスの #quo および #abs メソッドを再定義して実現しています。標準クラスのメソッドを上書きするという Hacky な内容ですが、これを行うことでわずかなコードで訂正処理を実現できてしまいます。一体どうやってこの案を思いついたのか発想力に脱帽しました。

誤り訂正の理論詳細については本記事では扱いませんが、興味のある方は記事末尾の参考資料をご覧ください。

この手法を元にして今回作る Quine に取り入れていきます。

誤り訂正の仕様

まず使用可能な文字数ですが変えずに 89 種類としました。使える文字に少し制限が出ますが今回書くコードでは必要十分です。ちなみに最初勘違いしていて、使える文字を増やそうと次の素数である 97 種類にしていたのですが、そこまで増やすと今度はエスケープの必要な文字(例えば \ など)がどうしても含まれてしまうため、意図しないエスケープが含まれて想定していない計算になってしまいハマりました。

次にブロックについてはサイズを 55 としました。符号化する部分の全体 2145 文字をちょうど 39 個に割り切れて、空白で消される箇所が各ブロックに分散するようなサイズということで 55 にしています。 55 文字のうち 33 を元となるコード文字列、22 を誤りの符号としました。22/55 で 40% までの誤りに耐えられる設計となっています。

39個に分けたことでブロックは次のように斜めになるような形で1ブロックずつ切り取られ、誤りが含まれる部分(空白文字の部分)がある程度分散するようにしています。

これをシンプルに先頭から55文字ごとのブロックにしてしまうと、アスキーアートの連続する空白と重なって誤り率が40%を超えてしまうためこのようにしています。画像中の誤り訂正ブロックについて空白部分を数えると16個なので16/55すると誤り率は29%となり、今回の設定率である40%以下なので問題なく復元できます。

誤り訂正のコード

今回書いた誤り訂正部分のコードを抜粋したものを載せます。理論部分の説明を載せていませんが、コードコメント中に関連するワードを散りばめているので、興味のある方の参考になったらと思います。実際に Quine に埋め込んでいるコードは、ここからコメントを全削除、変数名を頭文字1文字にし、空白を全て除去しています。

damaged_code = '空白で壊されたコード'

# `Matrix::LUPDecomposition` で連立方程式を解く際にモジュロでの計算用に調整する必要のあるメソッドを上書き
Integer.class_eval{
  # フェルマーの小定理から逆元を求め、その数をかけることで割り算を表現
  define_method(:quo) { |n| self * n.pow(87, 89) % 89 };
  # matrix gem がゼロ除算するのを避けるために、モジュロ計算する上で 0 である 89 や 178 を 0 として渡す
  define_method(:abs) { self % 89 }
};

require"matrix";

# 使用可能な文字列89種類を定義(文字リテラル `?a` を使用して短く)
usable_chars = *?\"..?};
usable_chars -= [?@, 92.chr, ?`];

# 誤り訂正を含むブロックを取り出して誤り訂正を行う(付与する場合は必要な符号数分空白を埋めてから渡す)
39.times { |i|
  # 対象ブロックは39文字ごとに置かれているので、文字を取得して index となる 0-88 の数値へ変換
  target_block = (0..54).map { usable_chars.index(damaged_code[i + 39 * _1]) };

  # 文字が欠損している部分の係数を格納する正方行列
  a = [];
  # 連立方程式の右辺行列、文字がわかっている部分の合計値をマイナスしたもの
  b = [];

  # 誤り訂正可能な22文字までの連立方程式を組み立てる
  22.times { |i|
    b << 0;
    a << [];

    target_block.zip(1..).each { |w, j|
      # 成分ごとの係数を計算(パリティ検査行列としてヴァンデルモンド行列を使用)
      coefficient = j.pow(i, 89);
      # w が nil ではない場合文字がわかっているため b の行列へ値を足す
      # w が nil の場合は欠損部分であるため a の行列へ係数を追加
      (w) ? b[-1] += -w * coefficient : a[-1] << coefficient
    }
  };
  result = *Matrix[*a].lup.solve(b);

  # 誤りを置き換え
  55.times { damaged_code[i + 39 * _1] = usable_chars[target_block[_1] || result.shift] }
};

誤り訂正処理コード自体は誤り訂正符号をかけられないので、可読性を確保しつつ、最初の空白（M3アスキーアートの3の頭の部分）までにコードを全て収めるようにするのは苦労しました。特にデバッグ時は eval に渡すコードがショートコードになっているので、間違った時にどこでエラーが起こっているか推測する力が試されます。慎重にコード変更しつつ、短縮するためのアイデアを探したり、あと何文字！と追い込んでいく過程はパズルのようで楽しかったです。

まとめ

誤り訂正のおかげで、どのフレームで止めても Ruby コードとして動作するアニメーション Quine を実現できました。ある程度までなら誤り訂正を含んで良い領域を空白文字に置き換えても動くので面白いです。ただし空白を入れすぎて訂正能力を超える部分があるとエラーで落ちます。

作る前はコードを押し込めるだろうかと心配でしたが無事動くものが作れてホッとしました。年末に数学の勉強ができたのも普段あまりしてこなかったことなので良い刺激になりました。

ちなみに Quine 実行時に -a オプションを渡して実行すると、元のコードが全て見える状態になるので読解してみたい方がいましたらご参考にしてください。

tompng さんの作品は今回紹介した誤り訂正以外の部分にもトリッキーなコードが埋め込まれていて、Ruby ってこんなことができるのかといった発見や、ショートコーディングするための工夫が詰め込まれていて勉強になるのでお勧めです。筆者もコードリーディング中に何度も気づきがあって興味深かったです。

エムスリーでは技術的チャレンジを通して開発・運用をよくしていきたい技術好きなエンジニアを募集しております。ご興味のある方は、ぜひお気軽にお問い合わせください。

jobs.m3.com

参考

筆者が今回記事中に出てくる誤り訂正を理解するにあたり、これらが最初から頭にあればもう少し早く理解できていただろうなと思うものを集めてみました。理論について知りたい方は参考にしてみてください。