Lを探す日常

I lov esoteric programming

Hexagony コンバータを作成しました (1)

この記事は TSG Advent Calendar 2018 の23日目です。TSG のチームが今日 SECCON で優勝しました。おめでとうございます!
昨日は hakatashi さんの「koresuki-bot の話」の予定でした。
今日は Hexagony という言語(esolang)へのコンバータについてお話を書きます。

はじめに

6日目の記事で、Hexagony の独自コンバータを作りたいと言いました。
Hexagony を書くのはとても大変で、さらに最短を目指すとなるとかなり労力が必要ですが、自動化できそうなところが多数ありました。それらの自動化を書いて、より快適な Hexagony コーディングを目指します。
(この記事に(1)とついているのはまだ一部しか自動化できていないためです。次の TSG ゴルフ大会までには全て完成させます。)

Hexagony とは

https://esolangs.org/wiki/Hexagony
Hexagony は2次元六角形のマス上を6方向に動くインストラクションポインタの指す命令に従って、これまた六角形(の辺)状のメモリを操作していく難解プログラミング言語です。
私がこの言語に出会ったのは TSG 第3回コードゴルフ大会のときで、id:satos___jp さんとの激戦の末最短を勝ち取りました。
その結果この言語が好きになって、 Hexagony IDE という(そこまで使い物にならない)ツールを作ったりしました。

作りたいもの

今回は人が書く言語 HexHappy と、中間言語 HexJumpable を導入します。

Hexagony コーディングではメモリ上の変数や配列の配置を考えて、それらを指すポインタ(メモリポインタ)の移動を実装していきます。
この移動が結構厄介で機械的に扱いづらいので、今回生成するプログラムはレジスタ3つと配列1つのみを扱えるようにしました。
2つの配列がほしい場合は偶数番目と奇数番目で分けるなどします。

HexHappy は(Hexagony 向けに最適化された)アセンブラみたいな言語です。アセンブラを人が書くのは大変なので「Happy」はおかしい、という人もいるかもしれませんが Hexagony の苦しみ(agony)に比べると圧倒的に楽ができるのでこの名前がついています。
仕様は後述します。

HexJumpable はほぼ Hexagony プログラムと同一ですが、「ブロック」の機能があって各ブロックの末尾から他ブロックの先頭にジャンプすることができます。
つまりこれは Hexagony の「プログラムを2次元に敷き詰める難しさ」を取り除いた言語になっています。
Hexagony の敷き詰めは厄介で、インストラクションポインタの移動方向が6つあるにもかかわらず単純な方向転換命令が4つしかなく、行きたい方向に行くのに2命令必要なことがあります。
HexJumpable → Hexagony の変換を自動化できれば、敷き詰めで悩むことは減るはずです。

作った(間に合った)もの

HexHappy と HexJumpable の仕様を考え、HexHappy → HexJumpable のコンバータを書くところまでは終わりました。
コンバータのソースコードはぐちゃぐちゃな状態で GitHub にあります。
HexJumpable → Hexagony の部分は残念ながら未完成です。今度またブログ書きます。

HexJumpable

以下のコードは、五月祭2018 Live Codegolf Contest day2 の課題を解く HexJumpable プログラムです。

表示

#<HexJumpable
  @main0:                                                                -> input_loop
  input_loop:              ,                                             -> input_loop_body / input_loop_end
  input_loop_body:         ="L~&{=*48='-{=R&}*"R&'L~&00]"){              -> input_loop
  input_loop_end:          =*=                                           -> output_loop
  output_loop:             'L~&00[="L~&{=*5'+{=R&}*"='L~&00[='*{=R&}*"*7'+{=R&}*"='L~&00[='*{=R&}*"*5'+{=R&}*"='L~&00[='*{=R&}*"R&!A'-{=R&}*"==R&= -> @exit / output_loop_forward
  output_loop_forward:     *49'+{=R&}*"=                                 -> output_loop
  @main5:                                                                -> @main5_loop
  @main5_loop:             }{N~"'                                        -> @get_forward
  @get_forward:                                                          -> @get_forward_body / @get_forward_end
  @get_forward_body:       'd{=-'R&                                      -> @get_forward
  @get_forward_end:        P"=R&'                                        -> @get_backward
  @get_backward:           R&"L~&'                                       -> @get_backward_tmp / @get_backward_end
  @get_backward_tmp:                                                     -> @get_backward
  @get_backward_end:       =*=}{{*"*"=]                                  -> @main5_loop
  @main1:                                                                -> @main1_loop
  @main1_loop:             }{N~"'                                        -> @set_forward
  @set_forward:                                                          -> @set_forward_body / @set_forward_end
  @set_forward_body:       'd{=-'R&}{R&"L~&{P"'                          -> @set_forward
  @set_forward_end:        R&"L~&"L~&{{                                  -> @set_backward
  @set_backward:           }{                                            -> @set_backward_tmp / set_backward_end
  @set_backward_tmp:                                                     -> @set_backward
  @set_backward_end:       *"[                                           -> @main1_loop
>


Hexagony を書いたことがある人なら、各行の2列目は Hexagony プログラムであることがわかるでしょう(多用されている R&L~& を除く)。
@ から始まるラベルは予約されていて、@main0 がエントリポイント、@exit が終了命令を表すラベルです。 HexHappy からのコンバータの実装で、@main1@main5 はそれぞれ配列の set/get 用に使用されています。
3列目のラベルはジャンプ先であり、/区切りの場合は条件付きジャンプ(>0 or <=0)です。
ソース: jumpable.rb:1-8

HexHappy

先ほどの HexJumpable プログラムの生成元となる HexHappy プログラムは以下のようになります。不自然な表記があるかもしれませんが、正規表現を変えるだけで対処できるのでこの文法は暫定的なものということで許してください。

表示

@main0:
  ! input_loop
input_loop:
  t = getb
  t ? +input_loop_body -input_loop_end
input_loop_body:
  x = t
  t = '0'
  x -= t
  t = x
  a[i] = t
  i++
  ! input_loop
input_loop_end:
  i = 0
  ! output_loop
output_loop:
  t = a[i]
  x = t
  t = 5
  i += t # i = i0 + 5
  t = a[i]
  x *= t
  t = 7
  i += t # i = i0 + 12
  t = a[i]
  x *= t
  t = 5
  i += t # i = i0 + 17
  t = a[i]
  x *= t
  t = x
  puti t
  t = 65
  i -= t # i = i0 - 48
  t = i
  t ? +@exit -output_loop_forward
output_loop_forward:
  t = 49
  i += t # i = i0 + 1
  ! output_loop


仕様は happy.rb#3-33 に書きました。レジスタ3つと配列1つがあり、レジスタごとに使える命令が違うこともあります。
たとえば配列の添字に使えるのは i だけだったり、xi は(遠いので)値を交換できなかったりします。

HexHappy → HexJumpable の変換

まずはメモリ上のレジスタや配列の位置を以下のように決めました。

xの斜め下にt、tの斜め下にi、iから横に離れてa_0, a_1, a_2, …
HexHappy のメモリ配置
このように txi 双方と隣り合わせる事で Hexagony の命令数を減らしています。

即値

Hexagony で数値を設定する方法は大きく分けて2通りあります。

  • 数値(0-9): 現在地のメモリの値に10をかけた後リテラルの値(0-9)を足す
  • アルファベット(A-Za-z): 現在地にその文字のASCIIコードを設定する

たとえば1024を作りたい場合、f 4 で行うことができます(f の ASCII コードが102なので)。
一方たとえば2048を作りたい場合、単に 2 0 4 8 とするだけではだめで、最初に現在地の0クリアをする必要があります。メモリ上に「ここは HexHappy の各命令開始時必ず0である」という場所を大量に置いておくことで、即値0が掛け算1回で(hoge * 0で)得られて便利です。

マルチバイト文字

Hexagony の実装を見て、「未定義の文字は全てアルファベットと同様に扱われる」ということがわかりました。
Hexagony は Ruby で実装されていてデフォルトで UTF-8 を受け付けてくれるので、たとえば コマンドは現在地に12354を設定してくれます。これを利用して即値のコンバータを実装すると、多くの数値が1命令で表せ、出力が格段に縮みました。

配列アクセス

配列の get/set は圧倒的多数の命令を要し、その度に命令を吐いていると出力が長くなりすぎてしまいます。
そこで、Hexagony には実は6つのインストラクションポインタが用意されているので、そのうち IP5 と IP1 をそれぞれ get/set 処理専用にしてしまい、配列アクセスはこれらのIPにジャンプするようにしました。上の HexJumpable のサンプルコードでも @main5 の行から最後まで多くの命令が生成されています。

配列アクセスの際にはもう一つ重要なことがあります。添字を即値で指定するとき、メモリ配置上どうしても0クリアに必要な命令が多くなってしまいます。そこで(0の場合は諦めて、1以上に有効な手として)添字は100倍したものを指定することにしました。
100、200、300、…、1114100はマルチバイト文字を有効にすれば全て1命令で表すことができます(多分)。さらにレジスタ i を添字として用いる場合でも100倍は2命令 (0 0) で済みます。

今後の展望

配列アクセスは2箇所にまとまったとはいえ、現状ではまだかなりスペースを取っています。ゴルフの際は基本的には配列は全く使わないことを目標としたいので、レジスタの数を9個ぐらいに増やすべきかなあという感じがします。

HexJumpable → Hexagony

まだ完成していないので何とも言えないですが、方針は2つあります。

  • 賢い敷き詰めアルゴリズムを考えて、入力の HexJumpable に対する最小の(or 十分小さい) Hexagony コードを完全自動生成する
  • ユーザーに方向転換命令だけを入力してもらい、それを基に HexJumpable の命令を埋めていく。

アルゴリズムは少し考えましたが全く思いつかなかったので、強い方々いいアルゴリズムがあれば教えてください…… (具体的な仕様も後で追記しておきます)
今実装を進めているのは後者の方法です。入力を支援するためにリアルタイムで HexJumpable の命令を埋めていって適当にビジュアライズします。

まとめ

言語 HexHappy と HexJumpable を定義し、HexHappy → HexJumpable のコンバータを作成しました。
今作っている HexJumpable → Hexagony コンバータが完成すれば、誰でも気軽に Hexagony プログラムを作れる理想の世界になります。がんばるぞい!
明日、TSG Advent Calendar 2018 24日目は JP3BGY 氏の「OVMF のソースデバッグの方法」の予定です。