Zenn
🏌️

Functional()版Quine 602bytes実装

2022/12/24に公開
functional
esolang
golf
quine
tech

はじめに

導入

今年のAdvent Calendarとして、既にFunctional() (esolang)の紹介とFizzBuzz 273bytes 実装を公開したのですが「Quineも書けないとね」ということで、Qiitaの「esolang Advent Calendar 2022」の一環(12/24分)として、今度はFunctional()でQuineを「golf的に(なるべく短く)」実装したものです。
結果、コード文字数602bytesを実現しました。
なお、本記事に先駆けてこのコードはStackExchangeにも投稿しています。
※紆余曲折あって、記事公開直前に劇的に縮みました。

Functional()とは

Functional()とは、基本の関数が9つのみのシンプルな関数型言語です。概要については、前述の紹介記事をご覧ください。
今回のQuineを短いコードで実装するにあたっては、かなり言語仕様というか言語処理系の細かい部分に踏み込む必要がありました。その点についても改めてコード解説とともに触れていきます。

Quineとは

Quineとは、色々なバリエーションもあるものですが、基本的には「プログラムコード自身を出力するプログラム」を指します。たとえばQuine・難解プログラミングについて等が参考になると思います。
esolang wikiにもFunctional()のQuine実装が載っているのですが、今回は文字数短縮に攻めた実装となっています。

Quine実装

方針

さて、コードを説明するにあたって、コード本体を先に見てもおそらくワケワカラン状態になると思いますので、先に実装方針の説明からにします。この時にFunctional()自体の仕様・挙動の理解が大きく効いてきます。

エンコード方針

ポピュラーなQuineの実装法として、「コア部分のコードをエンコードしたデータを用意し、コア部分(エンコードデータ) のようなコードを組むと、デコードされたデータとエンコードデータが連結して出力されて、結果としてコード全体と出力が一致する」というものがあります。
※つまり、コア部分の処理は、デコード+連結ということになります。

Functional()でも同じような方針を採る以外におそらく手はないのですが、基本がbit単位出力であることから、出力する文字種毎に1関数を用意することがほぼ必然となり、その関数の連続処理としては、次の2通りの選択肢が出てきます。

  • コールチェインによる連続処理
    「自分自身を返す関数」を用意し、DECODE(a)(b)(c)… のように、コールチェインで連続処理をこなす方法。
    この例だと、a,b,cとコード上の出現順序の通り処理が行われる。
  • 関数の入れ子による連続処理
    単純に、…(c(b(a())))… と関数を入れ子にして連続処理をこなす方法。
    この例だと最内の a が最初に処理され、以降b,c,…の順のため、コード上の出現順序の逆になる。

Functional()的には前者のような処理はポピュラーで、カッコを省いて DECODE a b c と1文字の処理にコード2文字で処理できて効率も悪くありません。
しかし、実はFunctional()にはコードの最後の閉じカッコは省略可という仕様があります。つまり、最後の処理群に限っては、…(c(b(a())))… の記述を …(c(b(a( で済ますことができ、これで1文字の処理に対してコード2文字で済むことになります。

その他の細々した要素も加味すると、結局この関数の入れ子+閉じカッコ省略が最も縮む書き方という判断になりました。

文字の選択

上で出力する文字種毎に1関数を用意することがほぼ必然と説明しましたが、そうすると使用する文字種を減らすことは、コード短縮にとって最重要ポイントとなります。
コードを記述する上で、空白と2種のカッコ ()、カンマ , の4種は省くことができず、また別の文字で代用することはできませんが、それ以外の文字をどう基本関数に割り当てるかは選択のポイントになります。
※空白に関して言えば、厳密には使わない形での記述も可能ではあるのですが、空白を使った短いコード記述ができる場面がそれなりに多いので事実上省略できません。また、タブ、改行等でも代用はできるのですが、今回は素直に空白を使うことにメリットがあります。

ここで、基本関数をなるべく絞ることを考えると one, assign, function, write の4種類のみを使うのがギリギリの線です。そうすると、上記4種と併せ、8種類の文字に対応するのが素直な考えとなります。
※zeroは引数省略や未割当文字の先行利用等で、案外無くても代替が効きます。
しかし、状況限定で (), の3種は識別子(変数)としても使用できるという仕様・挙動があります。流石にそれでも ) はほぼ実用できませんが、(, の2種は十分実用可能です。
更に、使用頻度の少ない関数は2文字の識別子に割り当てることで文字種を減らせるということに土壇場で気付き、基本関数を (, ともう1文字種のみで構成することで5種類まで文字種を削減することに成功しました。

なお、8種類の場合でもそうですが、5種類の文字出力処理を共通化することを考えると、最低限3bitの情報、つまり関数実装時に3つの引数が必要になります。
この「共通化」も踏まえ、空白(0x20), ((0x28), )(0x29), ,(0x2c) の4種に加えて、ASCIIコード 0x20 代で下から2bit目が0である残り4種の中で $(0x24) を使用する文字として選びました。更にそれぞれ下から5bit目を1にした 0489<(0x30,0x34,0x38,0x39,0x3c)を、各文字に対応した出力関数用としました。
※空白をタブ等で代用しなかったのは、このように 0x20代のコードの文字で統一するためです。

エンコード方法

さて、上ではエンコードの方針を説明しましたが、ここでは具体的にどうするかにもう少し踏み込みます。

基本的に、1文字出力するのに1関数を割り当てるということで、例えば A,B,C,D という文字の出力用に a,b,c,d という関数を設けたとします。これで、ABCDd(c(b(a( が無事 Quine になることを考えると、

  • a 関数はまず A を出力して、後で a( を出力する ( 後処理に付け加える )
  • b 関数はまず B を出力して、後で b( を出力する ( 後処理に付け加える )
  • …

と言ったように、「Xを出力して、後処理に (x の出力を付け加える」という、共通の枠組みがあれば良さそうに思えます。
※この大文字で書いてる方を「表の文字」小文字で書いてる方を「裏の文字」としておきます。

ところが、これだと問題があります。それは、「裏の文字」自体もコード本体で使うところ、先ほどの方式では「表の文字」しかコードの本体部分に使えないからです。
そんため一工夫を加えます。各関数が引数の0,1によって表・裏に両対応するというものです。
※各関数の返り値を 0 にしておけば、引数 0 の場合は先ほどと同じ形になります。

つまり、a関数なら a( と単純に呼び出せば表の A を、a(1, と1を付け加えれば裏の a を出力するということです。
後処理も考えると、「引数 0 なら X を出力して、後処理に x( の出力を付け加える、引数 1 なら x を出力して、後処理に x(1, の出力を付け加える」ということです。
これで d(1,d(c(1,c(b(1,b(a(1,a( を実行すると AaBbCcDd が出力された後、後処理で d(1,d(c(1,c(b(1,b(a(1,a( の出力が行われますから、ちょうど Quine の動作に叶います。

これをエンコード方法として、本体部分のコードは、「裏の文字」を名前とする各出力関数の定義、後処理の発火部分を記載すれば完成ということになります。

コード詳細

コード全容とジェネレータ

それでは、ようやくコード本体を見ていきたいと思います。まずは、Quineコードそのものです。

Quineコード
),$,$$,($(8,( $(($(<,$(,,,)),($(4,$(9,,)),($(9,$(,,0,,)),($(0,$()),$ 4)(((0,9,,$)(((,)(( $(($($$,( 9((()(9($ <($ 4(8(, 4))))))$$),, $))(( $(,(,$),,(),, 9,, 0,, $,, 4,,(,())))))),(()($$())(8(9(9(8(4(4(8(9(8(8(<(9(9(9(9(9(9(9(8(<(8(<(<(4($,0(<(<(4(0(<(<(0($,0(<(<(9($,0(<(<(9(8(<(<(9(4(<(8(<(8(4(0(8(8(9(9(4(0(<(<(9(4(4(9(9(9(9(9(9(4($,0(<(8(8($,8(4($,0(4(8(<($,0(4(8(9($,8(9(8(8(8(9($,0(8(<(4(4(8(4(8(8(4(0(8(8(9(<(8(8(8(9(4(<(<(9($,<(0($,8(8(8(9(4($,0(4(<(9(9(8(4(<(0($,8(4(8(<(9(9(<(<(0($,<(<(8(4(<(9($,8(4(8(<(9(9(<(<(9($,8(4(<(4($,8(4(8(<(9(9(<(<(<(8(4(<(<($,8(4(8(8(4(0(8(<(8($,8(4(8(<(4(4(<(4(<(9(

hakerh400.github.ioでのオンライン実行

しかし、これだけだとよく分からないところかと思いますので、そのジェネレータコードを以下に示します。ジェネレータと言っていますが、使っている文字が違うこと、適宜改行やインデントで整形していることを除けば、論理的には Quine 本体と内容は変わりません。

ジェネレータコード
),1,P,
:(h,
  & 1(
    :(l,1(>,>)),
    :(d,1(i,>)),
    :(i,1(>,`,>)),
    :(`,1()),
    1 d
  )(
    &(`,i,X)(
      &(>)(
        & 1(
          :(P,
            & i(
              &()(
                i(1 l(1 d(h(> d))))
              )
            )P
          ),
          > 1
        )
      )(
        & 1(
          >(X),>(),> i,> `,> 1,> d,>(>())
        )
      )
    )
  )
),
&()(
  P()
)(

h(i(
  i(h(d(d(
h(i(h(h(
l(i(
  i(
    i(
      i(
        i(
          i(i(h(l(h(l(l(d(1,`(l(l(d(`(l(l(`(1,`(l(l(i(1,`(l(l(i(h(l(l(i(d(l(h(l(
        h(d(`(h(
      h(i(
        i(
          d(`(l(
          l(i(
            d(d(i(
              i(
                i(i(i(i(d(1,`(l(h(h(1,h(d(1,`(d(h(l(1,`(d(h(i(1,
              h(i(h(h(
            h(i(1,`(h(
          l(d(d(h(d(h(
        h(d(`(h(
      h(i(l(h(h(
    h(i(d(l(l(i(1,l(`(1,h(h(
  h(i(
    d(1,`(d(
    l(i(i(h(d(l(`(1,h(d(h(
    l(i(i(l(l(`(1,l(l(h(d(l(i(1,h(d(h(
    l(i(i(l(l(i(1,h(d(l(d(1,h(d(h(
    l(i(i(l(l(l(h(d(l(l(1,h(d(h(
  h(d(`(h(
l(h(1,h(d(h(
l(d(d(l(d(l(i(

hakerh400.github.ioでのジェネレータオンライン実行

以降、このジェネレータコードの方の記述に沿って説明していきます。

全体構成

では、ジェネレータ/Quineの全体構成についてです。が、まず先に各文字、識別子の役割を示します。
ジェネレータ上では、冒頭に挙げた紹介記事と揃える形で基本関数を 1:&> ( それぞれ one, assign, function, write ) で書いていますが、:(assign)とその他に設けたP,Xは2文字の識別子で置き換えてエンコードにあて、その上で生成されるQuineでは文字の選択の章で挙げた文字に変換しています。
ちなみに、特に機能上の意味はないのですが、ジェネレータ上の裏の文字は 0x30代の代わりに 0x60台のコードを対応させたものにしています。

  • 2文字識別子対応表
識別子 2文字変換後 識別子の役割
: (1 基本関数assign
P 11 後処理用関数 ( 実行開始時は基本関数equal )
X ,1 関数の仮引数専用 ( 割り当てられる識別子が足りないため用意した )
  • 表/裏の文字対応表
表の文字
(ジェネレータ)		 裏の文字
(ジェネレータ)		 表の文字
(Quine本体)		 裏の文字
(Quine本体)		 表の文字の役割
空白 ` 空白(0x20) 0(0x30) 区切り文字
1 d $(0x24) 4(0x34) 基本関数one
& ( h ( (0x28) 8(0x38) 基本関数function, 開きカッコ(兼用)
) i ) (0x29) 9(0x39) 閉じカッコ
> , l , (0x2c) < (0x3c) 基本関数write, 区切り文字(兼用)

その上でコード構成ですが、おおまかには次のようになっています。

全体コード構成
{d`hil 5文字分の裏の文字の関数定義},
&()(
  P()     … 後処理用関数を呼び出す
)(
  h(i(i(h(d( … エンコードした出力関数(裏の文字)のコールチェイン
※最後の閉じカッコを省略

実は構成自体は非常に単純で、裏の文字分の関数定義を済ませたら、「後処理用関数Pを呼び出す関数」に、引数として出力関数のコールチェインを渡しているだけです。
これにより、引数評価の時点でデコードされたコード本体がまず出力され、その後後処理用関数Pが呼び出されることでエンコード文字列が出力されるという挙動になります。
※&()( P() )( コールチェイン と、間に関数定義を挟むのではなく、直接 P( コールチェイン ではどうかと思われるかも知れませんが、それだとコールチェイン実行中に行われる後処理登録の前に P の内容が確定されてしまうので、うまくいきません。

コード細部

さてでは、全体構成が単純だとすると、コードの肝となるのは「5文字分の裏の文字の関数定義」ということになります。この中に出力処理や後処理への登録等の処理を定義しているからです。

が、しかしその前にコード開始部分に、実は言語仕様に沿った工夫があります。
コードの最初の5行分を、インデント・改行なしでまとめてみます。

最初の5行分
),1,P,:(h,& 1(:(l,1(>,>)),:(d,1(i,>)),

一般のコードだと、先頭は 0,1,=,:,$,&,<,>,?, と、9種の基本関数の割り当てを列挙するところですが、そうなっていないように見えます。
実は、Functional()は「最初に9つの識別子を列挙して基本関数を割り当てさせる」のではなく、「コードの中に現れるユニークな識別子9つに順に基本関数を割り当てる」という仕様になっているので、今回のように使わない基本関数がある場合は、先頭にずらずら列挙しなくて済むのです。
この仕様をうまく活かすことで、単なる列挙によるコード長増大を避け、コード本体と基本関数割り当てをオーバーラップさせています。具体的には、このコードでは ),1,P,:,h,&,l,>,d に基本関数が割り当てられます。
なお、) もここでは識別子として使用できます。他の場所では閉じカッコとしての機能が強く優先されてしまうので、識別子として実用できるほとんど唯一に近い事例となっています。

では、話を戻して裏の文字の関数定義部分ですが、おおまかには次のような構成になっています。
※見易さのため、識別子は適宜替えています。

関数定義部分2～29行目
:(h,
  & Gen(
    :(l,Gen(>,>)),
    :(d,Gen(i,>)),
    :(i,Gen(>,`,>)),
    :(`,Gen()),
    Gen d
  )(
    &(bit4,bit3,bit1)(
      3ビット分の情報に基づき、実際の処理を行う関数を作成する
    )
  )
),

つまり、実際に関数を作成するコアの部分を引数でまとめてしまい、文字の bit1,bit3,bit4 に応じてパラメータを与えることで、それぞれの関数を作り出している処理になっています。h だけは関数 & Gen( … の中で assign するのではなく、最後に評価された Gen d を、冒頭の :(h, で assign する形になっています。( この形にしたのは、先ほど説明した基本関数割り当ての調整のためです )
パラメータ自体は、ゼロ/非ゼロを指定すれば十分なので、ゼロの代わりに未割当の識別子 i` を ( そのため定義順が重要です )、非ゼロの代わりに >d を使っています。

続いて、そのコアの部分ですが、次のような構成になっています。
こちらも適宜識別子を分かり易い形に置き換えていますが、実際は数少ない識別子を必死に使いまわして構成しています。

関数定義のコア部分11～26行目
      &(Writebyte)(
        & selector(
          :(P,
            & Old_P(
              &()(
                Old_P(selector l(selector d(h(Writebyte Nonzero))))
              )
            )P
          ),
          Writebyte selector
        )
      )(
        & bit5(
          >(bit1),>(),> bit3,> bit4,> bit5,> Nonzero,>(>())
        )
      )

まず、1文字分を書きだす処理がデコード時と後処理時の2回分ありますので、それをまとめて引数 Writebyte として渡す関数の形にしています。この Writebyte は、下位から2,6,7,8ビット目が固定、1,3,4ビット目が上位から与えられたゼロ/非ゼロパラメータに対応、5ビット目が表(ゼロ)/裏(非ゼロ)で調整可能な関数になっています。

そして、そのWritebyteを使って、「現在の P を Old_P として使ってエンコード文字列出力処理を追加し、改めて P として再assignする」という処理の後、デコードされた文字列を出力します。この順番にすることで、関数の最終的な返り値は、Writebyteの返り値であるゼロ ( 出力の8bit目 ) になります。
表/裏を調整するパラメータは selector として、デコードされた文字の 5ビット目の調整と、後処理で 1, を追加で出力するかどうかの調整で使います。
再assignされている後処理の部分ですが、これは入れ子になった関数の内側から順に実行されますから、裏の文字をWritebyteで出力→(をhで出力→裏指定なら1,をdとlで出力→再assign前の後処理Pを実行ということになります。

これで関数定義の全容が明らかになりました。

エンコーダ

最後に、本体コードをエンコードするためのスクリプトを示します。
変換規則自体は単純なのですが、流石に手動で変換していては大変なので、スクリプトを作って対応しています。

変換ルールとしては次の通りです。

  • 本体コードの逆順に構成する ( 行順序、行内の文字順序共に逆 )
  • 見易さのため、インデントは保存する ( ジェネレータの動きに影響はない )
  • :PX は対応する2文字識別子 (1,11,(1 に、&> の2文字は兼用にしている (,, に、それぞれに変換した上で以降の変換を施す
  • 1 (), はそれぞれ対応する文字出力関数の呼び出し d(, `(,h(,i(,l( に変換する
  • 文字出力関数の識別子 d`hil は、同関数を引数1で呼び出す形に変換する。例えば d なら d(1,、h なら h(1, といった変換になる。

この最後2つの変換で順序を間違えると2重に変換が起こったりしますので、エンコーダ上では一旦 s や { という文字を中間的に使用しています。
ということで、エンコーダのPerlスクリプトは次のようになります。

エンコーダコード
while (<>) {
  chomp;
  s/^ *//;
  $i=$&;
  s/:/&1/g;
  s/P/11/g;
  s/X/>1/g; 
  tr/&>/(,/;
  s/[`a-z]/{s$&/g;
  s/[ 1(),]/s$&/g;
  tr/ 1(),/`dhil/;
  s/{/,1/g;
  s/s/(/g;
  unshift @L,$i.reverse($_)."\n";
}
print @L;

tio.runでのエンコーダオンライン実行

おわりに

当初は662Bのつもりで記事を書き始めていたのですが、急遽602Bまで縮み、それに伴い内容も大幅に変わってしまいましたが、なんとかAdvent Calendarの予定日には間に合わせました。( その分割りを喰った記事が出たのですが、それは見なかったことにします )
早い段階でそこまで詰め切れなかった自分の甘さが恨めしいところでもありますが、しかし縮めるネタを次々見つけていくというのも、それもまたgolfの醍醐味ではないかと思います。

Discussion