Zenn
🏌️

Aubergine (esolang)の紹介とFizzBuzz 222bytes 実装

2023/08/31に公開
#
fizzbuzz
#
esolang
#
codegolf
#
golf
#
aubergine
tech

はじめに

別記事Esolang CodeGolf Contest #8 番外編 Functional()解でも触れましたが、2023/7/15～17の3日間、TSG/KMC開催のesolangを対象にしたコードゴルフコンテストに参加させて頂きました。
その際に修得したAubergineの簡単な紹介と、StackExchangeに投稿したFizzBuzz 225B/222B実装について解説したいと思います。
※なお、上記コンテストで実装したコードの解説はEsolang Codegolf Contest #8 WriteupのAubergineの項にあります。

Aubergineとは

Aubergineは、Brainf**kとは別の意味で非常に簡素な構造を持った手続き型なesolangの一種です。
最大の特徴は、2オペランドのRISC用アセンブリ言語っぽい文法と、コード領域・データ領域が一体化した実行モデルです。これにより、同一のメモリ空間の中でのデータ・コードの配置と、データ操作やジャンプ操作のためのアドレス調整をうまく行って、効率の良いコードを実装することを心がけることとなります。
esolang wikiのAubergineのページにも説明はあるのですが、以下簡単に説明していきます。
なお、実行環境はesolang wikiのPython2実装を前提とします。これは、各種言語の実行を試せるTIO(Try It Online!)でも採用されている実装です。

データとレジスタ(変数)

  • メモリ構造
    Aubergineでは、0～ 1刻みにアドレス付けられた、整数値を保持する読み書き可能なメモリとして、コードの文字数分のセルが用意され、コードテキストの文字コードにより初期化されます。 ※以下は、12 bytesのQuineコード =aa=oA+a1-ii のメモリ配置の状態です。

    他の実装については調査していませんが、TIOでも採用している前述のPython2実装の場合、各バイト(文字コード範囲0～255)が各メモリセルに対応し、12 bytes のコードなら 0～11 のアドレスが割り振られます。そして、esolang wikiにある言語仕様には反するのですが、データアクセスに関して末尾を -1 とする負のアドレスも有効です。しかしコードアクセスには負のアドレスは使えません。
    なお、後述しますが命令は3セル一組で構成されますので、末尾2セルはコード用のアドレスとしては無効です。

    初期データは非負のバイトデータではありますが、プログラム実行中にセルに保存するデータは符号付きの無限精度整数に対応しています。要はPython2の普通の整数型です。

  • レジスタ(変数)
    Aubergineコード実行時には、メモリ領域とは別に幾つかのレジスタ(変数)が用意されており、メモリセルと同様に整数データを扱うことができます。以下レジスタ名はコード中に記述するテキストと一致しています。

    • a および b
      演算に用いる汎用のレジスタです。また、格納している値をアドレスとしてメモリ領域を操作するために用いることもできます。その際はコード中のテキストを A または B とします。
    • i
      現在実行中の命令が収められている3セル組の先頭セルのアドレスを格納するレジスタです。また、このレジスタの値を書き換えることで次に実行する命令位置を調整する、すなわちジャンプも実現します。
    • 1
      読み取り専用のレジスタで、文字通り数値の 1 を取り出すことができます。
    • o
      入出力用の特殊レジスタです。次章「命令と実行」で説明する =(代入) 以外で使用することはできません。読み取り用に使った場合は標準入力から読み込んだ文字の取得として、書き込み用に使った場合は標準出力へ書き込む文字の指定として働きます。

命令と実行

Aubergineのコードは、3セル1組で1つの命令と解釈されます。先頭のセルが処理内容、2番目・3番目がそれぞれ第1・第2オペランドを表します。( 各オペランドには前項のレジスタを指定します )
処理内容は以下の4通りのみです。

  • = ( 代入 )
    第1オペランドの示すレジスタ、あるいはメモリ位置 ( A,Bの場合 ) に、第2オペランドの示すレジスタあるいはメモリ位置のデータをコピーします。
    例えば =ab という命令であれば、bレジスタの内容がaにコピーされますし、=A1 という命令であれば、aレジスタに保存されている値をアドレスとするメモリセルに値1が保存されます。
    オペランドにoを指定した場合、前章の oレジスタの説明の通り、入力あるいは出力が行われます。第1オペランドに指定した場合は第2オペランドの示す内容を文字コードと解釈し出力処理が行われ、逆に第2オペランドに指定した場合は1バイト入力処理を行い、その文字のコードをコピーするデータとします。前提としているPython2実装の場合、TIO環境ではバイトデータとして出力されます。なお、データを mod 256 で扱うということはなく、0～255の範囲外の数値の場合は出力そのものがされません。
    ※なお、手元で実行する場合、UTF8ロケールで対話(tty出力)状態だと出力データがユニコードのコードポイントだと解釈するため、挙動が変わります。同じ挙動にするには、環境変数 LANG を C と設定して Cロケールにするのが無難です。
  • + ( 加算 )
    第1オペランドの示すレジスタ、あるいはメモリ位置に、第2オペランドの示すレジスタあるいはメモリ位置のデータを加算します。
  • - ( 減算 )
    第1オペランドの示すレジスタ、あるいはメモリ位置に、第2オペランドの示すレジスタあるいはメモリ位置のデータを減算します。
  • : ( 条件付きジャンプ )
    第2オペランドの示すレジスタ、あるいはメモリ位置が非0の場合に限り、iレジスタに第1オペランドの示すレジスタ、あるいはメモリ位置のデータをコピーします。iレジスタの値が変わることで次の命令の位置が変わることになるため、この命令は条件付きジャンプとして機能します。

以上の4命令を駆使して処理を行うわけですが、プログラム実行は次のように行われます。

  • 初期状態で、a,b,i のレジスタは全て値が 0 となっている
  • iレジスタの値が、コードのアドレスの範囲外になるまで実行を続ける ( 範囲外ならその時点で終了 )
  • その時点でのiレジスタの示すアドレスを先頭に3セル分読み込み、コードと解釈して実行する。この時以下のような場合にはエラー終了する。
    • データが何らかのコードを示す数値に一致しない場合
    • 命令に指定されたオペランドが適切でない ( oレジスタを=以外の命令に使う、1レジスタを書き込み用に使う等の ) 場合
    • A,B の指定で有効でないアドレスを通じてメモリセルの参照が行われた場合
    • oレジスタで入力を行う際に既にEOFだった場合
      ※このためEOF検出を行うコードは書けません。が、EOF時に即終了となるためgolfは却ってやりやすいと言えます
  • 命令実行後、iレジスタの値を3増加させ、次の命令の解釈・実行に進む

この最後の「iレジスタの値を3増加」のため、特に調整しなければ 0, 3, 6, 9, … と3セル(文字)ずつコードが進んでいくわけですが、最初に実行されるアドレス 0 分を除き、3の倍数のアドレスにコードを配置しなければいけない決まりはありません。そこはiレジスタに設定する値次第となります。
なお、プログラム制御に必要なジャンプはiレジスタの値の調整によって行われるわけですが、=i? が絶対アドレス指定ジャンプ、+i?, -i? が相対アドレス指定ジャンプ、:?? が条件付き絶対アドレス指定ジャンプとして機能します ( ?は何らかのオペランドの指定 )。条件付きの相対アドレス指定ジャンプは直接的にはできません。
この時の注意事項として、命令実行後の「iレジスタの値を3増加」は、iレジスタを変更する場合にも同じように適用されるということです。そのため、例えば次にアドレス15の命令を実行したければ、iレジスタの値を12に設定するように3ずらしておく必要があります。

コードサンプル

以下、基本コードサンプルとして Hello, world! と Quine を挙げます。

  • Hello, World!
    -a1=oA-a1:bA\0
!dlroW ,olleH
    ※注: コード中 \0 はNUL文字(ASCIIコード0)を指します。
    TIOでのHello, World!実行
    ということで、基本中の基本である Hello, World! ですが、これはコード領域末尾に逆順に配置された文字列データ(NUL終端)をなぞってループで1文字ずつ出力させる、という実装をとります。
    bレジスタの値はずっと変更されず0のままのため、アドレス9の :bA まで来ると、aレジスタの値をアドレスとするセルの内容が 0 になるまで条件付きジャンプでアドレス 0 (実際は+3の影響でアドレス3) に戻ることでループが実現されます。そのループの中で =oA での文字出力と -a1 でのアドレスのデクリメントを行っているわけです。
    最終的には a=-15 でNUL文字のあるセルを指すようになったところでループから抜け、アドレス12をコード解釈しようとしてエラーとなり終了します。
  • Quine
    =aa=oA+a1-ii
    TIOでのQuine実行
    データとレジスタ(変数)の章の冒頭でも紹介したQuineコード(の一例)です。本来、他の言語でのQuineはそこそこ組むのに労力がいるのですが、コードとデータが共存しているAubergineの場合は単純な文字出力ループでQuineが実現できます。
    Hello, World!とは違い、こちらはアドレス 9 の -ii でアドレス 0 ( +3で実質3 ) へのジャンプを行っており、コード的には無限ループです。しかし =oA によるメモリアドレス参照が範囲外になったところでエラーとなり停止します。

実装上のTips

Aubergineでコードを実装する場合、究極的にはレジスタとメモリ上のデータをどう扱うか、コード配置をどのようにしてジャンプ命令でつなぐかを考えることになるのですが、よく使うことになるTipsを知っておくと大分やり易さが違うと思いますので、少し紹介しておきます。

  • 小さな数の無からの生成
    Aubergineで命令に指定できるのはレジスタだけなので、ちょっとした数値を作る方法を知っておくと便利です。以下のような方法があります。
    • レジスタ 1 による数値 1 の利用
      これはそのままですね。=a1 のように 1 をセットするようにも使えますし、+a1 や -a1 のように 1 変化させる用途でも使えます。
    • レジスタ/メモリ領域のゼロクリア
      -aa のように、第1・第2オペランドを同じにして減算することで 0 を作ることができます。
    • レジスタ/メモリ領域の倍化
      +aa のように、第1・第2オペランドを同じにして加算することで倍の値を作ることができます。これとレジスタ 1 を併用することで、手間はかかるにしても任意の数を作り出すことができます。
      例えば、57=0b111001(2進法) であれば、=a1+aa+a1+aa+a1+aa+aa+aa+a1 というように、最上位の1を=で設定した後、残りの1の桁の分は +aa+a1 0 の桁の分は +aa をつなげていくことで計算できます。
    • 3の倍数の利用
      iレジスタは、ジャンプがない限り3ずつ自動的に増えていきますので、その差分を取ることで3の倍数を作ることができます。
      最も手っ取り早いのは、=ai-ai による -3 の生成や、-ai+ai による3の加算等ですが、iを参照するタイミングをずらすことでもう少し大きい数にも対応できます。例えば -aa-ai??????+ai ( ?はなんらかの命令 ) とすると、a をゼロクリアした後 i の差分によって 9 が得られる、といった具合にです。
  • プログラム先頭領域のポインタ利用
    アドレス0からの3セル ( あるいは4セル ) は、プログラム開始時に命令として使った後、ほぼ命令として再利用することがありません。( なぜなら、負のアドレスを i に設定する必要があり、手軽な 0, 1 に比べ面倒だから )
    このことから、ここをメモリアクセス用のポインタ(アドレス値)データとして利用するのが有用です。
    典型的には、最初の命令を nop的な :Ba 等にして、アドレス0の数値が58、アドレス1の数値が66ということで、アドレス60前後一体をデータ置き場として使ってしまう方式です。
    ※特に B で得られる66は、アドレス33からの +ii でのジャンプとオーバーラップさせることができ使い易いところです。
    あるいは、=i1 や :1A にすることで、直後の命令がアドレス4～となりアドレス3も空きとなるので、そこもポインタあるいは変数・定数置き場として活用することも考えられます。
  • 小規模なループ
    Aubergineのプログラムでは、データの置き場やコードの配置 ( ジャンプ先 ) をどこにするか考え、アドレス値を調整して作っていくことを考える必要があります。しかし、小規模なループであれば、ループ先頭のアドレスを一時的に記憶しておくことで、簡単に実装することができます。
    例えば、レジスタ a をアドレス値としてメモリ内容をNUL文字になるまで出力するような典型的な処理であれば、=bi=oA+a1:bA と、: でのジャンプ先を b に一旦保存してループを実装することができます。( 終了判定はメモリ内容 A が 0 になること )

FizzBuzz実装

注意点

StackExchangeに投稿したFizzBuzz 225B/222B実装では、主に225Bの実装( TIOでの実行例 )での説明を書きましたので、この記事では222B版について説明していきます。

基本方針

まず、Aubergineでは命令セットがとても素朴です。なので、例えばBrainf**kで採るような戦略と同じく、各種カウンターを管理していくのが素直な方針と言えます。
次のC疑似コード ( TIOでの実行例 ) のように、3周期,5周期の c3,c5、プログラム全体の終了を判断するためのグローバルカウンタ g、5,10,15,…の時に繰り上がりを行うかどうかを判定するための2周期の h が主なカウンターとなります。その他、数字を2桁出力するかのフラグ ( 下では d ) も必要となるでしょう。

基本方針
  c3=3, c5=5, g=10, h=0, d=0, du='0', dl='1', nl='\n';
Lf: // Fizz判定
  c3-=1;
  if ( c3!=0 ) goto Lb;
  c3=3;
  fputs("Fizz",stdout);
  goto Lb;
Lb: // Buzz判定
  c5-=1;
  if ( c5!=0 ) goto Lj;
  c5=5;
  fputs("Buzz",stdout);
  goto Lc;
Lc: // 繰り上がり処理
  h=1-h;
  if ( h!=0 ) goto Le;
  du+=1, dl-=10, d=1, g-=1;
  goto Le;
Lj: // 数値出力
  if ( c3==3 ) goto Le;
  if ( d!=0 ) putchar(du);
  putchar(dl);
Le: // 後処理
  dl+=1;
  putchar(nl);
  if ( g!=0 ) goto Lf; // 先頭へ戻る

ここからAubergineで実装するにあたり、次のような工夫を考えました。

  • カウンタを減らしFizz/Buzz出力を判定する構造を共通化してコード量を削減する
  • Ljでの==条件でのif文はAubergineが苦手とするところなので ( :bA 等で「非ゼロの時に直後の処理をスキップ」なので !=条件に向いている )、そこをジャンプテーブルに置き換えてコードを簡略化する
  • 加えて、2桁出力か1桁出力かを、専用のフラグを持たせず、ジャンプテーブル内のジャンプ距離で調整することで、変数の数を実質的に減らす
  • Lcでの繰り上がり判定カウンタ h をジャンプオフセットと兼用することで、絶対アドレス計算+条件付きジャンプを避ける

疑似コード

というこで、前章のような想定を踏まえ、以下のような疑似コードを実装しました。
( TIOでの実行例 )
言語標準ではありませんが、&&ラベル によって「ラベルへのポインタ」が取得できますので、Aubergineでのジャンプの実装を疑似的に表現するのにC言語は非常に向いています。

Aubergine実装用疑似コード
#include <stdio.h>
#include <stdint.h>

#define I(x) ((intptr_t)&&x)
#define P(x) *(void*)(x)

int main(void) {
  intptr_t
    *cp,*cpt,t,p,
    pvars0[] =
      { I(Tj3)-I(Tj1), I(Tj2)-I(Tj1), I(Tj2)-I(Tj1), 0, I(Tc1)-I(Tj3),
        I(Lb), 3, 'F', 'i', 'z', 'z', 0, I(Lb)-I(Tx2), },
    pvars1[] =
      { I(Lj), 5, 'B', 'u', 'z', 'z', 0, I(Lc)-I(Tx2), },
    dvars[] = { I(Tc2)-I(Tj3), '0', '1', '\n', 10, },
    *pbase[] = { &pvars0[6], &pvars1[1] },
    *dbase3=&dvars[2], *dbase1=&dvars[4];
  int i=0;

Lx: // Fizz/Buzz出力 ( i=0 for Fizz, i=1 for Buzz )
  // カウンタ減
  cp = pbase[i];
  *cp-=1;
  if ( *cp!=0 ) goto P(*(cp-1));  // 出力スキップ時は Lb/Jj へジャンプ
  *cp+=3; // カウンタを3へ復帰 ( Buzz用の+2は Lc の処理で行う )
  cp+=1;
  p=I(Tx1); // ループ戻り先保存
Tx1: // putcharループ
  putchar(*cp);
  cp+=1;
  if ( *cp!=0 ) goto P(p); // Tx1へジャンプ
  goto P(I(Tx2)+*(cp+1)); // Lb/Lcへジャンプ
Tx2:

Lb: // Buzz出力(処理本体はLx)
  i=1;
  goto Lx;

Lc: // Buzz出力後繰り上がり関連
  // カウンタ+2で5へ回復
  cp=pbase[1], *cp+=2;
  // pvars0[3] ( 相対ジャンプ幅 ) を 0, pvars0[4] の2値でスイッチ
  cp=pbase[0]-2;
  t=*cp, cp-=1, t-=*cp, *cp=t;
  goto P( I(Tc1)-t ); // Tc1/Tj3へジャンプ
Tc1: // 繰り上がり処理本体
  // ジャンプテーブルpvars[1],pvars[2]の相対ジャンプ幅をゼロクリア
  // それにより、当初 Lj→Tj2 だったジャンプが Lj→Tj1 と2桁出力対応になる
  cp-=1, *cp=0;
  cp-=1, *cp=0;
  // グローバルカウンタ減
  cp=dbase1, *cp-=1;
  // 下位桁を10減らし'0'に戻す
  cp-=1, t=*cp, cp-=1, *cp-=t;
  // 上位桁を1増やす
  cp-=1, *cp+=1;
  cp-=1;
  goto P(I(Tc2)-*cp); // Tj3への固定ジャンプ
Tc2:

Lj: // 数値出力と後処理
  cp=pbase[0];
  // &pvars[0] ～ &pvars[2] のジャンプテーブルによる相対ジャンプ
  cp-=*cp, cp-=3;
  cpt=dbase3;
  goto P( I(Tj1)+*cp ); // Fizz時はTj3へ、数値出力時は Tj1/Tj2 へジャンプ
Tj1: // 上位桁出力
  cp=cpt-1, putchar(*cp);
Tj2: // 下位桁出力
  putchar(*cpt);
Tj3: // 改行出力と下位桁増
  cp=dbase3, *cp+=1;
  cp+=1, putchar(*cp);
  cp+=1, i=0;
  if ( *cp!=0 ) goto Lx; // ループ先頭へ
}

基本方針にあった通り、以下の工夫を盛り込んでいます。

  • Fizz/Buzz処理をラベルLxでの処理にまとめ、インデクス値 i=0 or 1 の違いで切り替えられるようにした
  • Fizz/Buzz処理用に、カウンター(c3,c5相当) と、2か所のgoto用の絶対/相対アドレス、出力用の文字列(NUL込み)を pvars0,pvars1 に同一構成で用意した
  • pvars0の先頭 ( カウンターc3相当の `pvars0[6] の近くに配置するため ) に、Lj用のジャンプテーブルと、繰り上がり判定の h 相当のジャンプオフセット管理領域を配置した。

なお、数値出力用のデータとカウンター g は近い位置にある方が都合が良いので、まとめて dvars として管理します。

Aubregineコード構成

それではいよいよ、Aubergineコードです。
が、実装そのものは、前章のC言語疑似コードでほぼ終わっていて、後はメモリ上の配置のみとなります。それを図示したのが次の画像です。

(ちょっとTx1のところだけ色を間違えてますが) Lx(Tx1), Lb のコードブロック、pvars0, pvars1 のデータ領域、Lc(Tc1,Tc2), Lj(Tj1,Tj2,Tj3) のコードブロックと来て、最後に dvars のデータ領域を配置する構成です。途中配置をずらしているのは、Lcのところから3の倍数+1のアドレスで命令を配置しているからです。
アドレス値と参照用に使う部分は矢印でつないでいますが、pvars0, pvars1 へは先頭の 0, 1 という一番使い易いメモリセルを当てています。また、dvars に関しては負のアドレス値 -1, -3 を使ってアクセスできるよう末尾に置いています。( そのため図中のアドレス値もそこだけマイナス表記にしています )

なお、Tj3の最後(アドレス214)の先頭への条件付きジャンプが行われなかった場合、dvarsの領域をコードとして実行しようとするのですが、命令不正のためエラー終了となります。
stackexchangeに投稿した225B版は、このエラー終了を避けて配置を変更したバージョンです。

最後にコード本体ですが、これは非印字文字がそこそこ含まれるため、代わりに base64 エンコードしたテキストを以下に示します。TIOで実行したかったのですが、コードに単独の \0x9a (アドレス65) が含まれるため、UTF-8クリーンなコードを要求するTIOでは残念ながら実行できません。

base64エンコード後FizzBuzz222Bコード
OkJhPWFBLUExPWJhLWIxOkJBLUFpK0FpK2ExPWJpPW9BK2ExOmJBK2ExK2lBPWExLWlpPwwJCQBR
KgNGaXp6AACaBUJ1enoAHD1hMT1hQStBMStBMS1hYT1hQS1hMS1hMT1iQS1hMS1iQT1BYitpYi1h
MS1BQS1hMS1BQS1hYS1hMS1BMS1hMT1iQS1hMS1BYi1hMStBMS1hMStpQS1hYT1hQS1hQSthaS1h
aT1iaS1iaStpQT1hYi1hMT1vQT1vQj1iaS1iaStCMStiMT1vQitiMS1hYTphQiQwMQoK

さいごに

ということで、Aubergineの言語紹介とFizzBuzz実装について解説しました。
命令自体は単純ですが、コード・データの配置と効率良くアクセスするためのアドレスの調整を考えるのが面白い言語ではないかと思います。機会があれば是非試してみてはいかがでしょうか。

Discussion