🐟

Jellyfish版Quine 32bytes実装

2022/12/17に公開

はじめに

導入

今年のAdvent Calendarとして、既にJellyfish版FizzBuzz 92bytes実装を公開したのですが「Quineも書けないとね」ということで、Qiitaの「esolang Advent Calendar 2022」の一環(12/17分)として、今度はJellyfishでQuineを「golf的に(なるべく短く)」実装したものです。
結果、コード文字数32bytesを実現しました。
なお、本記事に先駆けてこのコードはStackExchangeにも投稿しています。

Jellyfishとは

以前に「Jellyfish(esolang)の紹介」で紹介した、2次元的にノードを配置してネットワークを構成することで処理を実現するという特徴を持つ、一種の関数型言語です。
ある程度の処理の流れを把握していないと以降の説明を読み解くのは厳しいと思いますので、先に同記事の「プログラムの実行」の章を一読されることをお勧めします。
また、コード内で使用している組み込み関数等のリファレンスとしては公式の"Standard Library"ページをご覧ください。

Quineとは

Quineとは、色々なバリエーションもあるものですが、基本的には「プログラムコード自身を出力するプログラム」を指します。
なので、正常に実行できているかどうか、出力のみを見て判断することはできず、必ずソースコードの内容と出力が一致しているかを見る必要があります。
なお、Quine のバリエーションとしては「あるコードを実行すると、別のコードが生成されて、さらにそのコードを実行すると更に別のコードが…」のように連鎖的にコードを生成するようなものもあり、非常に頭おかしい洗練されたコード実装を目の当たりにすることができます。たとえばQuine・難解プログラミングについて等をご覧になると良いのではないかと思います。

Quine実装

方針

どのような言語でもQuineを考える時「print("hoge")とするとhogeは出力できるけど、そうするとコードにあるprint("とかどう補っていこう…」ということは考えるのではないかと思います。
Jellyfishの場合、出力を担当するのは基本的に P による matrix-print で、P"hogehoge が出力できます。( 文字列リテラル区切りの " は行末なら省略できます )
そうすると同じように「P" の部分どう補っていこう…」という考えが出てくるわけです。

しかしここで、Jellyfishの場合2つポイントがあります。

  • ,(concatinate)で下側に指定した文字列をプレフィクスとして前に連結できる
    つまり、P,"hoge の形にして , の下に P," を連結してあげることで、プレフィクス部分が補えるのです。
  • P(matrix-print)は出力内容を返すので更に加工に使える
    そうすると、,の下につなげた部分をどうフォローするのかという話が出てきますが、Pは出力するだけではなく、更にその出力内容を値として返します。
    なので、それを使いまわせば、下の分のフォローになるだろうということです。

この2つのポイントを踏まえて、次の図のようにコードを構成するのが、今回の基本方針です。

つまり、次のような方針です。

  • 1行目に配置する文字列の左側 ( プレフィクス ) は、, の下側に連結して、右側の P の出力に入れ込む。
    ※1行目が P・・・P,"hogehoge であれば、プレフィクス文字列を "P・・・P,\" で設定することでフォローできる
  • 2行目の内容をエンコードして1行目の文字列に仕込み、デコード処理をかけることで、左側の P の出力で2行目の分を賄う。

なお、どうしても文字列の中に ",\ が入ってしまうこと、一旦追加したプレフィクスが2行目出力用には邪魔になることを考えると、素の文字列のままでなく、なんらかのエンコードを考える必要があります。

コード全容

では、上記方針を踏まえ、コード全容を見てみます。

32B実装コード
PvxP,"DC!^@$Vp~V*Z$
BE'^F"PvxP,\"

※注: 本来のコードには制御文字が含まれているため、上の記述では別の文字に置き換えています。そのため、そのままコピペしても正常動作しません。対象は、1行目の ^@ の部分が NUL(ASCII 0)、2行目の ^F の部分がACK(ASCII 6)です。

このコードはtio.runでの実行ページで実行させることができます。

コード自体はとても短く、構造も単純なのですが、一応制御文字を解釈してネットワークまで構成した段階の図を次に示します。記号の意味は上述の「Jellyfish(esolang)の紹介」での説明に合わせています。

コード細部

では、基本方針を踏まえた上で今回実装したコードの細部がどう対応しているかを説明します。

  • プレフィクス
    後述しますが、デコード処理用に v,x を採用したため、プレフィクス部分は PvxP," となりました。これを , の下側に文字列として指定し連結させます。
    "をそのまま書くと文字列の終端として扱われるため、\ でエスケープしています。
  • デコード処理
    デコードには、v(drop)とx(xor)の2処理をあてています。いずれも第一引数は文字定数としての ^F ( ASCII 6 の制御文字 ) で、Eを使って接続方向を曲げることで2処理で共有させています。
    • v(drop)によるプレフィクス削除
      vの機能は、単純に追加された6文字のプレフィクス削除です。
      第一引数を文字定数として与えても、数値の6と同等の扱いになるのがミソです。なぜ敢えて文字定数で指定したかは、次のxの処理の方に理由があります。
    • x(xor)による文字コードずらし
      Perlで文字列同士のxorがとれるのは有名かと思いますが、Jellyfishでも同じように文字同士のxorがとれます。つまり、文字コードの数値同士をxorで計算して、その結果を文字コードとする文字列データを作り出すということです。
      これにより、",\をずらして別の文字に変換した状態で、1行目に仕込むことができるようになります。
      なお、xの引数は数値でも良いのですが、数値・文字列の xor だと結果が数値配列になってしまい、文字変換を更にかます必要が出てきてしまいます。ここを文字・文字列の xor とすることで変換をかけなくても済むようにしているのです。結果として NUL文字 ^@(ASCII 0) を使うことになり、オンライン実行環境にブラウザ上で入力するのにちょっと苦労がありましたが、まあ些細な問題でしょう。
      x 以外にも、文字のずらしには +,- も使えるのですが、+を使うと CR(ASCII 12) が出てきてしまい、これがコードの行区切りと見做されるためコードが破綻します。-なら問題ありませんが、制御文字が増えて見辛くなるので x の方を好みで採用しました。

ところで、賢明な皆さんであれば「vで6文字削除じゃなくて5文字削除にして、プレフィクス最後の " のエンコード分を2行目最初にオーバーラップさせれば、更に短縮になるのでは…?」と思いつくことと思いますが、それをすると"のエンコード分が真下にくることで左側 P が「2引数指定」という扱いになってしまい、エラーを引き起こしてしまいます。( Pは1引数で使う必要がある )

ということで、思いつく限りQuineの実装としてはこれが一番短くなるのではないかと思います。

後日更新版(印字文字での実装、2024/8/27追記)

さて、上記コードでは非印字文字の ^F (ACK, ASCII 6) を使っていたわけですが、実はこれコード中に直書きしなくても c 関数に 6 を適用して作り出すことができると気付き、印字文字でのコード実装が可能になりました。( NUL文字も排除できています )
エンコードを x による xor の代わりに - での文字番号の引き算に替えています。

32B印字文字での実装コード
P-vP,"Hi<H(V3|V2b(
Bc6B"P-vP,\"

このコードはtio.runでの実行ページで実行させることができます。

…その延長で、6文字削除→5文字削除の短縮も狙えないか検討したのですが、たまたま " ( ASCII 34 ) から -5 でできる文字が ASCII 29 の GS で、コード解釈時に改行と同じく行区切り扱いされてしまうので、やっぱりうまく使えませんでした…。( - の代わりに +x を使っても別の問題が出るのでやっぱりうまく使えません )
ということで、文字数自体の短縮はできませんでしたが、手で打てるコードで実装できたのは大きいと思います。

おわりに

冒頭で紹介したStackExchangeへの投稿をご覧いただくと、紆余曲折あって32Bまで短縮しているのが分かるかと思いますが、最初はもっと複雑な方針を立てていました。
しかし何事も簡単にアッサリ考えるのが大事だなあと実感するコードになったかと思います。「その言語を理解できたか」のベンチマークとして、一度Quineというのは実装してみるのが良いのではないでしょうか。

Discussion