Zenn
🐟

Jellyfish(esolang)の紹介

2021/04/11に公開
esolang
codegolf
jellyfish
tech

はじめに

去る2021/3/5(金)～7(日)に開催された第7回Esolang Codegolf Contest(Write-upはこちら)に参加させて頂く機会がありました。
コンテストの名称の通り、多数のesolangに挑むものであったのですが、そこで標題のJellyfishに興味が湧きました。さりとて公式のドキュメントではなかなか分からないことも多かったため、コンテスト終了後に色々読み解く必要がありました。そしてある程度Golfができるレベルまでには組めるようになりました。
今回は、その読み解いた内容の紹介という形になります。後半の方では、実際にそのコンテストのお題でGolfした成果についても解説します。

Jellyfishとは

特徴

公式のドキュメント(再掲)によれば、Golf用の言語であるJellyと、2次元的なプログラミングを行うesolangの><>(Fish)から発想を得て、両者を組み合わせたような言語として作成したとのことです。
と言いつつも、私は両者共に詳しくないため、実際にこのJellyfishを調べてみた所感として述べますと、次のようになります。

  • かなり? 純粋な関数型言語
  • 2次元型に処理の依存関係のネットワークを組む感覚が楽しい
  • リストデータをそのままベクトル演算できる機能が多く、ハマれば簡潔な処理が書ける

基本

Jellyfishを理解するためには、ネットワークを組む以下の4種類のコード上の構成要素 (公式の文法ドキュメントに記載されている ) を把握する必要があります。

  • 値(Value)
    数値なり文字列なりの文字通りの値であり、コード上では、数値定数や文字・文字列リテラルが該当します。
    加えて、プログラム開始時に標準入力から静的に読み込まれる入力データも、コード上はこの「値」に分類されます。( 動的に読み込むには次項の関数を用います )
    コード上に直接記載はできませんが、Jellyfishではリスト(ネスト可)も値として取り扱うことができます。
  • 関数(Function)
    評価されることで値を生成する、文字通りの関数です。標準で40個程度の関数が用意されています。
    1引数、あるいは2引数で使う必要があり、引数の数や種類(主にリストかどうか)で挙動を変える場合が多いです。( 1引数・2引数片方にしか対応していないものもあります )
  • 演算子(Operator)
    値や関数を元に、新たに関数を作り出す機能を持つ要素です。全部で13個用意されており、演算子自体を新たに作り出すことはできません。
    関数を元に関数を作り出すという点を見ると、一種の高階関数の趣を持った要素です。が、関数を作り出すと同時にネットワーク構成の組み換えも発生し、なかなか複雑な挙動を示します。
    演算子も1引数、あるいは2引数で使う必要がありますが、引数が値か関数か、また混合の場合は値-関数の順か関数-値の順かまで区別するため、同一の演算子でも最大6種類の機能を持つことになります。
    ※作成された関数が1引数で使われるか、2引数で使われるかも考慮すると最大12種類。
  • 制御文字(Control Character)
    ネットワークの構成に影響を与える要素です。全部で7個あり、要素同士の接続を阻害したり、接続方向を曲げるような効果を持っています。

この中で、制御文字については公式の文法ドキュメントに、関数・演算子については公式の標準ライブラリドキュメントに載っています。

Jellyfishでは、コード上に2次元に配置されたこれらの要素でまずネットワークを構成し、それから決まった順番に沿って「評価」を行っていくことでプログラムを実行します。

プログラムの実行

この章では、サンプルコードをもとに、プログラムが実行される様子を見てみます。

実行の手順

前章の通り、プログラムの実行はネットワーク構築→評価という段階を踏みます。
ネットワーク構築はコードの解釈とグラフの作成、評価に関しては関数評価と演算子評価からなります。

ネットワーク構築

では、実際に以下のコードを元にネットワーク構築の部分を見てみます。

サンプルコード
p_+>-
  B
 /0p
   i
 E  1

ただこれだと2次元データとしてパースする際に同じ列のつながりが見え辛いので、次の図のように表にした方が分かり易いでしょう

まずコードのパースとしては、各要素をノードに分解して次の図のように縦・横に接続する処理となります。基本的には1文字で1ノードですが、数値定数(10進の非負整数)や、文字・文字列リテラル( '文字や"文字列" ) は、繋がっている分だけがまとめてノードになります。
接続は単純で、隣接する縦(同じ列)、横(同じ行)のノードを接続するだけです(途中に空白や行末以降の空き部分を挟むのも可)。数値定数などで複数文字からなるノードができた場合、接続されるのは先頭の文字の位置だけで、残りは空白と同じ扱いになります。
なお、ここでは、各ノードの種類(コードの構成要素)を、○…値、□…関数、◇…演算子、△…制御文字として表すことにします。

さて、これ以降、方向については東西南北で表現することにします。
続いてネットワークの構築になりますが、基本は接続している辺を、縦なら南向き、横なら東向きの有向辺に置き換える処理になります。

それに加えて次のような処理が入ります。

  • 静的な入力
    「値」の中で、iやIのノードは、静的な入力として標準入力からの入力値に置き換えます。複数ノードがある場合は、北優先→西優先の順番で置き換えていきます。
    iについては生の文字列ではなく、それを数値等として解釈した値への置き換えになります。詳細は割愛しますが、リストデータを1つの値として解釈させることもできるようになっています。なお、この例では 5 という数字が入力されているという想定になっています。
  • 値からの接続調整
    「値」のノードから南・東方向の接続は切断します。その上で、東から自分へ戻る辺を追加します。この追加する辺は意味のないケースが多いですが、後述の演算子の評価の時に影響する場合があります。
  • 制御文字によるブロック
    「制御文字」の中で、ブロックの機能を持つノードからの接続を切断します。代表的なのはBです。他にもV,F,Aがありますが、これらは条件付きでのブロックとなります ( 詳細は割愛します )。Fに関してはちょっと特殊なので、演算子評価の時に補足します。
  • 制御文字による方向転換
    「制御文字」の中で、方向転換の機能を持つノードからの接続を曲げます。例えば E の場合であれば、東西の接続はそのままで北からの接続を東に曲げる、といった感じです。この他に、西からの接続を南に曲げるS、E,Sの効果を併せたようなXがあります。

これらの処理が終わった後は、制御文字はもう考えなくて良いので、ネットワークから消しておきます。制御文字があった場所は辺が連結されたような状態になります。

そして最終的に上のような図のネットワークが出来上がります。
ここで、辺に色を付けているのは、後での各種評価における順序に関わるためです。青よりも赤の方が優先で、ノードから2本の辺が出ている場合は、南側が赤、東側が青となります。
なお、E,Sを使うことで、「ノードに入る辺が3本以上」という状況も作り出すことができるのですが、しかし辺の向きが北向き・西向きといった状況を作ることはできません。

評価

評価概要

さて、ネットワーク構築が終わると、いよいよ評価が始まります。これがJellyfishのプログラム実行の主要部分となっています。
評価はコードの1行1列目の要素に該当するノードから開始します。( もし該当ノードが無ければ評価は行われずに終了します )
評価には、引数の「値」を元に「値」を作り出す関数評価と、引数の「値」や「関数」を元に「関数」を作り出す演算子評価があります。引数とは、ネットワーク上で1ノード分先にあるノードの値・関数、あるいはノードを評価した結果となります。
この時引数には順序があり、前章で赤く色づけした辺が第一引数になります。また、もし引数のノードが直接引数に使える情報を持っていない場合 ( 値が必要なのに関数のノードであるとか )、先に引数のノードを評価していきます。これは深さ優先で行われ、かつ評価が優先されるのも第一引数の方です。
この評価を繰り返していき、1行1列目のノードの値が確定した時点でプログラム終了となります。

関数評価

では、関数の評価について、先ほどまでとは異なる単純な例で具体的に見てみます。
ちょうど次の図のようなネットワークが構築済みで、北西の隅にあるpのノードから評価が始まるものとします。

そうすると、引数としての値が未評価のため、①②③と深さ優先で辿っていき、ここで2引数とも値であるため④で評価ができ、値が確定します。
ここでは、関数-の2引数版で、第2引数から第1引数を減算した値として 3 が生成されます。

続いては、*のノードの第2引数としてのつながりで、⑤で +のノードが評価されます。こちらは関数+の2引数版で、両引数の和 19 が生成されます。

そうすると、引数の値が確定したので、ノードを戻って⑦⑧と評価が進みます。2引数版の*で両引数の積 57 の生成、pは1引数版のみで、引数の値 57 を改行付きで出力します。( 引数の値がそのまま評価した結果にもなります )

これで評価を開始したpのノードの値が確定したので、全体の評価も終了ということになります。

関数評価に関する注意

さてここで、関数の評価に関して1つ注意点です。
ほとんどの関数には関係ないのですが、入力処理を行うj(1引数版), J、出力処理を行うp, Pは入出力という副作用を持っています。そういった関数の評価についてです。

次の例で、関数ノードの評価の優先順位がA,B,Cの順に高いとし、それぞれから同一のjのノードが接続されているとします。

そうすると、まず①②と深さ優先で評価を辿り、③でjの入力処理が行われます。

ではその後、④や⑥の評価の際に、jのノードがどう扱われるかです。これは、既に評価が済んで値が確定しているため、そのままその値が使われ、新たな入力処理は行われません。

このように、単純に入出力用の関数のノードを設けた場合、それぞれ1回ずつしか処理が発生しないため、複数回処理が必要ならその回数分のノードが必要になります。同一のノードで重複させることはできません。
多数あるいは可変回数の入出力処理が必要であれば、次項で説明する演算子を活用して、その用途の関数を新しく作る必要があります。

演算子評価

それでは今度は演算子の評価になります。
またこれまでのコードとは別に、次の図のような例で考えることにします。
これは、演算子/に、2つの関数ノード^とCが接続されている例です。ここでは関数ノードへの接続にしていますが、演算子側でサポートさえされていれば、値が接続されていても構いません。ただ、接続状況によって作られる関数の機能は変わってきます。

そうすると、先行のノードから評価が伝播してきた時、演算子の評価が行われ、その時に関数の生成とネットワークの再構成が行われます。
次の図でhという仮の名称にしているのがその作成された関数で、もともと演算子/に向いていた辺はその関数に接続し直され、またその関数からは、もともと引数の^から接続されていたノードが接続されます。
なお、演算子の引数が^のような関数ではなく値であった場合、値のノードから自分自身に戻ってくる辺が使われることになります。( この辺が意味を持つのは演算子評価の際のネットワーク再構成の時だけです )

この例では図の中に記載があるように、第1引数の真偽に応じて、2乗か2べきかの計算を行う2引数の関数が作成されます。なお、ネットワーク構成的にそう振る舞うことが確定しているので2引数関数として書いていますが、実際には1引数・2引数両用の関数が作られ、引数の数によって異なる機能を発揮します。
こうして評価が行われた後、先のノードとの接続状況に従って、改めて関数評価が行われたり、あるいはその関数を使ってさらに演算子から新たな関数が作られたり、といった評価が進むことになります。

ところで、演算子から接続されているのが関数の場合、関数評価の時とは異なり、その関数自体の評価は基本行われません。もし関数が評価済みで値が確定していたとしても、その値も演算子からは使われません。あくまで関数本体にのみ意味があるからです。
ただしこれには例外があります。それは制御文字Fを通じて関数ノードが演算子から接続されていた場合で、この時だけは関数としてではなく、関数評価によって得られた値を使う挙動になりますし、未評価であれば先に関数評価が行われます。

さて、先ほどの例では、演算子の引数である^から接続されているノードが、新たに作成された関数から接続されていましたが、次の図のように①②の組か、③④の組か、接続するノードの選択肢が2つできることもあります。
その場合は、引数の評価の優先度(赤→青)とは逆に、青(東側)に接続された引数の先のノード(この場合③④)が選ばれます。逆側は接続されません。

これは接続されているノードの多少に関わりなく東側優先となります。つまり、南側に2ノード、東側に1ノードの接続の場合であっても南側は選ばれず、東側の1ノードのみが接続されることになります。( 東側に接続がない場合のみ、南側のノードが接続されます )

全体の評価例

評価の話の最後の締めとして、冒頭のコードの評価を通しで見てみます。

開始は1行1列目の、図中北西の隅にあるpのノード ① からになります。
引数のノードは値ではなく、また関数でもなく演算子なので、深さ優先で演算子評価を、優先順位の高い赤の方から ②③ と辿っていきます。

そして、ここで接続ノードが値だけなので、値-値の2引数版として演算子/の評価が ④ で行われ、関数の作成と東側のノードの値 0 の自己接続辺の再接続が行われます。
※見辛いので、今後使わない自己接続辺は消しておきます。

更に1つ戻り、関数-関数の2引数版として演算子_の評価が ⑤ で行われ、関数の作成と東側のノード + の先の辺が再接続が行われます。
なお、ネットワーク構成上、作成された関数は1引数用になるのですが、その前提で演算子の機能を考えると / が \lambda(x,y). \lambda(a). ( a ? x : y )、_ が \lambda(f,g). \lambda(a). f(a) であることから、結局 \lambda(a). ( a ? 1 : 0 ) ということになります。

これで、未評価な残りは関数だけなので、⑥⑦⑧と順次辿って評価していくだけとなります。
⑨では、出力の機能を持つp(1引数専用)が評価されて、引数の値 5 が出力されます。

その後、⑪ では1引数-は補数を返す機能で -1 と評価され、⑫ では2引数>で大小比較が真となり 1 と評価されます。

そしていよいよ作成された関数が⑬で評価され、引数の1は真値(Jellyfishでは0や空リストが偽値)なので評価の結果も1となり、最後 ⑭ でpにより 1 が出力されて終了となります。
結果として、このプログラムは入力 5 に対し、5 と 1 を出力する、という挙動になっています。

ECC最短事例の解説

問題概要

問題については、第7回Esolang Codegolf Contestのルールのページに書いてあるのですが、掻い摘んで説明すると、次のようになります。

  • 0,1からなる3文字(改行除く)3行分1セットの入力データが16セット、合計48行標準入力から入力される
  • 各セットにつき結果として 0,1 のいずれかを計算し、空白文字(改行も可)区切りで標準出力に出力する。
  • 各セットに含まれる 1 の文字の数が2～4個という制約のもと、いずれかの行あるいは列に1が2個以上ある場合は 1、それ以外は 0 を結果とする。

問題に対する最適なアプローチは言語によって異なると思いますが、Jellyfishで最適なのは以下の方法と判断しました。

  • 各セットの行を10進数と見做した値 a_i, b_i, c_i から計算した合計 s_i=a_i+b_i+c_i に対し、結果を r_i=sign(mod(408,s_i~xor~109)) とする。
    ※signは正数・0・負数にそれぞれ1,0,-1を返す関数、xorはbit-xorです。

次項ではこれに基づくコードの実装と、評価のシミュレーションを説明します。

コードの解説

最終的なコードは、以下の38B(最終行は改行なし)でした。

最終コード38B
P
*
|408
x109
@ ++S
*3vvLjr48
rBEN0
16

これだけ密集して組んであると、縦横のつながりが見辛いということはないと思いますので、表で表したものは割愛します。これをパースすると、次のようになります。

そして構成されたネットワークが次の通りです ( 値のノードの自己接続は使われないので割愛しています )。制御文字E,Sが1個ずつで、それぞれ接続が曲げられています。

ここから評価になりますが、深さ優先で辿っていく過程は省略し、確定していくところを順に説明します。( 見易さのため、確定したらネットワーク上のノードをその内容に置き換えていきます )
さてこの評価ですが、Jellyfishの各種関数がリストの各要素の一括処理(ベクトル演算)に対応していることを存分に利用し、少しの処理で目的を達成していきます。

まず、①で確定するのは南西の隅です。非負整数1引数のrは、引数の個数分の連番(0～)をリストとして生成します。それに2要素版*の乗算機能で一括で3をかけ、0,3,6,…というリストを作ります。
②の1要素版Nは真偽値反転です。偽値である 0 を反転して 1 が生成されます。
そして③が演算子からの関数生成です。一般的な機能としては説明し辛いのですが、第1引数が 0、第2引数が関数の演算子Lは、ちょうど map のような、リストの各要素を関数の値で置き換えるような関数を生成します。この場合入力処理のjを使っていますので、「リストの各要素を入力値に置き換える関数」ということで、これが入力処理の要となります。

続いて④で早速その関数が評価され、非負整数1引数版rにより生成された48要素のリストから、48行分の入力値のリストが生成されます。
⑤⑥は、第2引数がリストの2引数版vで、第1引数に指定された 1 に従って、先頭1要素ずつを削除したリストが生成されます。

そして⑦の各2要素版+は文字通り加算処理で、これがベクトル演算となるため3要素毎にs_0,s_1,\cdotsが現れるリストを生成します。( リスト全体の長さは、一番短いリストに合わせ46となっています )

最後に⑧で、2要素版@はインデクス指定でのリスト抽出になります。0,3,6,…番目の要素を抽出することで丁度s_0,s_1,\cdots,s_{15}のリストが生成されるのです。
後はそのまま、2引数版xによるxor、2引数版|によるmod(被除数が第2引数なのがちょっと違和感ありますが)、1引数版*によるsignが全てベクトル演算で処理され r_i=sign(mod(408,s_i~xor~109)) の計算による結果のリストを生成し、最後P(1引数専用)がmatrix-printの機能で、空白区切りでリストの全要素を出力する、という具合になります。

まだよく分かっていないこと

さて、ここからはまだ私がJellyfishの機能で読み解けていないところです。

公式の標準ライブラリドキュメントには、ところどころに“threading”と、それに伴う“level”という表現が出てきます。
実際、これらを調整するのが主機能の演算子があるため、フルに活用するには理解する必要がある概念だろうと思うのですが、残念ながら読み解けていません。

ただ、インタプリタの実装を眺めていて感じるのは、おそらくリストのベクトル演算とネストの深さに関する話だろうということです。
例えば、等値判定や大小比較の=,>,<は、乗算・加算であるようなベクトル演算には対応しておらず、すなわち「リストの各要素を比較した真偽値のリストを生成する」という挙動にはなっていません。代わりに、リスト全体同士を比較して、単一の真偽値を生成します。
これが、公式の標準ライブラリドキュメントでの“threading -1”のことではないかと考えています。( 逆に“threading 0”がベクトル演算対応 )

より深くJellyfishを理解したい方は、是非この辺を読み解いていただければ ( そして良ければ読み解いた内容をご教示いただければ ) と思います。

おわりに

ということで、チュートリアルが未整備なところ、自分が読み解いた内容をチュートリアル代わりに書いてみました。Jellyfishに新たに挑戦する方の一助となれば幸いです。
なお、オンラインインタプリタもあるとのことなので、是非1度感触を試してみてはいかがでしょうか。

Discussion