ICFPC 2020 galaxy.txt を読む (その 1: decompile)
その 0 で ICFPC 2020 をざっと復習しました。では実際に galaxy.txt を見てみます。
galaxy.txt
開いてみると、以下のようになっています
:1029 = ap ap cons 7 ap ap cons 123229502148636 nil :1030 = ap ap cons 2 ap ap cons 7 nil ... :1107 = ap ap c ap c ap ap b :1183 ap ap c ap ap c :1221 0 ap ap cons 2 ap ap cons 2 ap ap cons 0 ap ap cons 0 ap ap cons 0 nil ap ap cons ap :1225 :1040 ap ap cons ap ap cons ap ap cons 0 0 ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 2 0 ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 0 2 ap ap cons ap ap cons 1 2 ap ap cons ap ap cons 2 2 nil ap ap cons ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 1 1 nil ap ap cons ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 2 1 ap ap cons ap ap cons 4 1 ap ap cons ap ap cons 6 1 nil ap ap cons ap :1214 2 nil :1108 = ap ap c ap c ap ap b :1183 ap ap c ap ap c :1221 0 ap ap cons 2 ap ap cons 2 ap ap cons 0 ap ap cons 0 ap ap cons 0 nil ap ap cons ap :1225 :1101 ap ap cons ap ap cons ap ap cons 0 0 ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 2 0 ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 0 2 ap ap cons ap ap cons 1 2 ap ap cons ap ap cons 2 2 nil ap ap cons ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 0 1 nil ap ap cons ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 2 1 ap ap cons ap ap cons 4 1 ap ap cons ap ap cons 6 1 nil ap ap cons ap :1214 64 nil ... :1494 = ap ap c ap ap b c ap ap b ap b c ap ap b ap b ap b s ap ap b ap b ap b ap b c ap ap c ap ap b b ap ap b c ap ap b ap b c ap ap b ap b ap b c ap ap b ap b ap b ap b b ap ap b ap b ap b ap b ap s i ap ap s ap ap b c ap ap b ap b s ap ap b ap b ap b s ap ap b ap b ap b ap b s ap ap b ap b ap b ap b ap b b ap ap b ap b ap b ap b ap b b ap ap b ap c ap ap b b ap ap b b ap ap b b ap eq 1 ap ap b ap b ap c ap ap b c ap c ap ap c :1490 ap :1199 1 ap c ap ap b add ap ap b neg :1117 ap ap b ap b ap c ap ap b c ap ap b ap b c ap ap b ap b ap b c ap ap b ap c ap ap b b ap ap b b ap ap b b ap ap b ap c ap ap b cons ap ap c cons nil ap ap c ap ap b cons ap ap c ap ap b cons ap ap c cons nil nil nil ap ap b ap c ap ap b c ap ap b ap b b ap ap b ap b cons ap ap c ap ap b c ap ap c ap ap b c ap ap c ap ap b b ap ap b :1166 ap add -1 ap add -1 3 3 ap ap c ap ap b b cons ap ap c cons nil ap ap c ap ap b b add :1117 :1172 ap ap s ap ap b :1162 ap ap b ap mul 3 ap ap c ap ap s ap ap b b ap ap c ap ap b b add neg ap ap b ap s mul div 8 ap ap b ap mul 3 ap ap c div 8 galaxy = :1338
さて、このままでは私にはさすがにちょっと厳しいので、もう少し読みやすくするところから始めます。
Decompile
簡単な decompile をします。が、以下の理由で完璧にやるのは結構大変です。
- true と K コンビネータが同じものを使っている
- cons cell 等が関数で定義されているので、全部展開すると再構築するのは大変
なので、多少条件を緩くして、現実的にプログラムが読めればよい、というところを目標にします。
まずは最初の :1029 を見ましょう
:1029 = ap ap cons 7 ap ap cons 123229502148636 nil
まずは処理しやすいように AST を組み上げます。galaxy.txt は 1 行 1 定義なので、行ごとに処理します。今回与えられるプログラムは、単に whitespace で切り分けることで tokenize できます。構文解析は単純な LL(1) parse です。 AST は、
enum Value { Apply(Box<Value>, Box<Value>), Int(isize), Symbol(String), ... // 以下 builtin の関数が並ぶ }
として、ap が出てきたら２つ分後続を読んで、Applyを作る。それ以外は単純な mapping をとります。
Definition { name: ":1029", value: Apply(Apply(CONS, INT(7)), Apply(Apply(CONS, INT(123229502148636)), NIL)) }このままだとまだちょっと読みづらいので、List を導入します。変換は Value を traverse し、
- NIL => 空 List
- Apply(Apply(Cons, x), y) => x, y に変換を適用。加えて y の変換結果が List であれば、x の変換結果を prepend する
- 上記以外の Apply(x, y) => x, y に変換を適用して Apply(x', y') をつくる
- それ以外 => そのまま
とすれば List を構築できます。結果
[7, 123229502148636]
と List に変換できました。何かのデータのようですが、とりあえず保留します。
さて、この変換を適用した上でざっと galaxy.txt を眺めると、最初に何かのデータが埋め込んであるようです。中身はまだわからないので、一旦保留して次を見ましょう。
次は :1122 を追いかけてみます。
:1122 = ap ap c ap ap b s ap ap s ap ap b c lt i i
Definition { name: ":1122", value: Apply(Apply(C, Apply(Apply(B, S), Apply(Apply(S, Apply(Apply(B, C), LT)), I))), I) }コンビネーター を lambda 式で書き換えます。コンビネータは以下のとおりでした。
S = \x \y \z . (x z) (y z) C = \x \y \z . (x z) y B = \x \y \z . x (y z) I = \x . x
単純にこれらで置き換えるだけですが、後の処理を単純にするため、展開するごとに変数名がかぶらないようにしておきます。
(({\x0.{\x1.{\x2.((x0 x2) x1)}}} (({\x3.{\x4.{\x5.(x3 (x4 x5))}}} {\x6.{\x7.{\x8.((x6 x8) (x7 x8))}}}) (({\x9.{\x10.{\x11.((x9 x11) (x10 x11))}}} (({\x12.{\x13.{\x14.(x12 (x13 x14))}}} {\x15.{\x16.{\x17.((x15 x17) x16)}}}) <)) {\x18.x18}))) {\x19.x19})流石にまだちょっと読むには辛いので、これを強引に簡約(もどき)、つまり仮引数の変数を実引数で置き換えます。この式の評価では外部とやりとりすることはなく、また全て遅延評価であることを考慮し、最終的な計算順序は人間の心の目に委ねることにして可能な場所はすべて計算してしまいます。ただし、無限に式が膨れ上がるのはまずいので、「変数が式中で1度しか使われないもの、もしくは引数で与えられるものが単一の変数であるもの」に限って展開することにします。
{\x2.{\x8.((((< x2) x8) x2) x8)}}この式はこのくらいまで来るとなんとか理解できるようになります。まず最初の ((< x2) x8) は、x2 と x8 の比較結果を bool で返します。ここを cond と置くことにすると、残りは ((cond x2) x8) なので、真の場合 (i.e. x2 < x8 の場合) x2 を、偽の場合 (i.e. x2 >= x8 の場合) x8 を返します。つまりこれは、引数を２つとって、その小さい方を返す、という関数になっています。適当に Int.min(x, y) 的に名前をつけておきましょう。
一歩戻って、この条件分岐は galaxy.txt 全般にわたって頻出するのですが、この形だと分岐なのか関数適用なのかをひと目で分別するのは難しいため、ヒューリスティックを用いて if 文のような構造を構築することにします。つまり
((a b) c)
の形で、a が bool である場合、if a then b else c と置き換えます。ここで a が bool であるかどうかの判断が必要になりますが、とりあえず保守的に以下のとおりにすることとします
- true/false
- lt または eq に引数が 2 つ与えられたもの
- is_nil に引数が 1 つ与えられたもの
(あとで、もう少し追加します)
加えて \x.e の形を多少プログラムっぽく fun(x) -> e と書き換えてみます。
fun(x2, x8) -> if x2 < x8 { x2 } else { x8 }最後に、変数名を x0 から振り直すことにして、多少読みやすくしようと試みます。ここまでで
Int.min = fun(_x0, _x1) -> if _x0 < _x1 { _x0 } else { _x1 }とすることができました。
このくらいまでの変換を galaxy.txt に含まれるすべての関数に適用すると、多少様子が見えてきます。まず先頭に何かデータの埋め込みのようなもの。ついで小さな関数群、最後に複雑な関数群、と並んでいるようです。最初に埋め込まれたデータの意味は使われ方を見てみないとわからないので保留しておき、小さな関数群をまずは見ていきましょう。
先頭の方から :1117 を選び見てみましょう。上記の decompile をすると
:1117 = ap ap s ap ap c ap eq 0 1 ap ap b ap mul 2 ap ap b :1117 ap add -1
{\x2.((((== 0) x2) 1) ((mul 2) (:1117 ((add -1) x2))))}というところまでできます。もう少し人間に優しくするために、add, mul, div, neg, ==, < 等の関数は+, *, /, -(単項), ==, < という馴染みの演算子を導入して置き換えることにします。ただし format の際には演算子の強さに留意する必要があります。
fun(x2) -> if 0 == x2 { 1 } else { 2 * :1117(-1 + x2) }また、特に add と neg が組で出てきた場合には、(適当に順序を入れ替えて) 二項演算子の - を導入して置き換えることにします。
fun(x2) -> if 0 == x2 { 1 } else { 2 * :1117(x2 - 1) }と、この関数は引数 x が 0 の時 1, それ以外の時は 2 * :1117(x - 1) を返す、つまり 2^x を返します。Int.pow2 的に名前をつけましょう。
同様に :1118, :1119 を見てみると
:1118 = ap ap s ap ap c ap ap c lt 2 0 ap ap b ap add 1 ap ap b :1118 ap ap c div 2
fun(x2) -> if x2 < 2 { 0 } else { 1 + :1118(x2 / 2) }
:1119 = ap ap s ap ap b s ap ap c ap ap b c lt 0 ap ap b ap b ap add 1 ap ap c ap ap b s ap ap b ap b :1119 div i
fun(x2, x8) -> if x2 < x8 { 0 } else { 1 + :1119(x2 / x8, x8) }と変換され、:1118 は log_2, :1119 は log_x_y であることがわかります。
続いて :1120 を見てみましょう
:1120 = ap ap s ap ap s ap ap c ap c ap ap s ap ap b s ap ap b ap b ap ap s i i lt eq 0 i neg
{\x2.(((({\x29.(x29 x29)} ((< 0) x2)) ((== 0) x2)) x2) (~- x2))}\x.(x x) の式が出てきました。これは logical or で、true = \x.\y.x, false = \x.\y.y に留意して実際に計算してみると
({\x.(x x)} true) c => (true true) c => (\x.\y.x true) c => (\y.true) c => true
({\x.(x x)} false) c => (false false) c => (\x.\y.y false) c => (\y.y) c => cとなります。ここで再びヒューリスティックを持ち出し、(\x.x x) の形が出てきて、かつ続く引数２つが bool であった場合は logical or として扱うことにします。
また、logical or は先の "bool かどうかの判断" に含めることとします。これを適用すると
fun(x2) -> if 0 < x2 || 0 == x2 { x2 } else { -x2 }となり、絶対値を返す関数であることがわかります。Int.abs 的に名前をつけておきましょう。
次の :1121 は
:1121 = ap ap s ap ap b c ap ap c ap ap b s lt i i
fun(x2, x8) -> if x2 < x8 { x8 } else { x2 }から、引数のうち大きい方を返す関数とわかります。Int.max と名前をつけておきましょう。
まとめ
ここまで、簡単な decompile と、整数を扱う基本的な関数を読み解きました。
次回予告: 残りの小さな関数群たちを見ていきます。
