ICFPC 2020 galaxy.txt を読む (その 2)

その 1 ではざっと decompile して、基本的な算術関数を読み解きました。
その 2 では、まだ小さめの関数群が残っているので、これを読み解いてみます。

:1124 = ap ap s ap ap b b ap ap c isnil ap s t ap ap c b ap ap s ap ap b c ap ap b ap b b ap ap b ap b ap ap s i i ap c eq ap c :1124
 {\x2.{\x8.(((isnil x2) f) (x2 {\x29.{\x38.(({\x47.(x47 x47)} ((== x29) x8)) ((:1124 x38) x8))}}))}}

ここで isnil が登場するので、これに着目してみます。(isnil x2) とあるので、x2 は List であることがわかります。一方で後半に着目すると、適宜改行いれて多少見やすくすると

(x2 {\x29.{\x38.
    (({\x47.(x47 x47)}
      ((== x29) x8))
      ((:1124 x38) x8))}})

となっています。その 1 あったとおり ((== x29) x8) は boolean なので、 {\x47.(x47 x47)} は logical or と解釈できます。実際、この後ろの ((:1124 x38) x8) は isnil の分岐で false を返していることからも :1124 自体は 2 引数かつ bool を返す関数とすると全体で辻褄があうので、これを採用することにします。
更に、最初の (x2 {\x29.{\x38. ... }}) に注目すると、List が cons cell でできていたこと、及び cons cell の定義から、これは x29 に car(x2), x38 に cdr(x2) を束縛する decompose と読むことができます。ここも見た目を良くするために let hd::tl = e1 in e2 の形の式を持ち込むことにします。すると

fun(x2, x8) -> if isnil(x2) { false } else { let x29::x38 = x2 in x29 == x8 || :1124(x38, x8) }

と、かけることがわかります。特に isnil + let decompose は頻出するので、関数型言語っぽく match も導入してしまうことにします。

fun(x2, x8) -> match x2 { [] => false, x29::x38 => x29 == x8 || :1124(x38, x8) }

さて、中をもう少し追いかけてみます。空 List が与えられると false. そうでなければ car(x2) が x8 と一致すると true, しなければ、cdr(x2) を第一引数に持ってきて再帰、となっていて、これは List に (正確には == で比較しているところから int の List に限られます) 整数 x8 が含まれるかどうか、という関数です。IntList.mem 的に名前をつけておきましょう。

次は 1126 と 1127 です。

:1126 = ap ap s ap ap b b ap ap c isnil nil ap ap c b ap ap s ap ap b c ap ap b ap b b ap b :1115 ap c :1126
fun(x2, x8) -> match x2 { [] => [], x26::x35 => :1115(x8(x26), :1126(x35, x8)) }
:1127 = ap ap s ap ap b b ap ap b b ap ap c isnil nil ap ap c ap ap b b b ap ap s ap ap b s ap ap b ap b c ap ap b ap b ap b b ap ap b ap b ap b :1115 c ap ap c ap ap b b ap ap b c ap c :1127 ap ap c add 1
fun(x2, x8, x14) -> match x2 { [] => [], x47::x59 => :1115(x8(x47, x14), :1127(x59, x8, x14 + 1))

:1115 を見てみると

:1115 = cons

となっているので、これをそのまま代入します。

fun(x2, x8) -> match x2 { [] => [], x26::x35 => cons(x8(x26), :1126(x35, x8)) }
fun(x2, x8, x14) -> match x2 { [] => [], x47::x59 => cons(x8(x47, x14), :1127(x59, x8, x14 + 1))

２つを比べると、非常に似た形であることがわかります。 1126 は List x2 の全要素に x8 を適用する関数です。 List.map と名前をつけておきましょう。
1127 は 1126 に加えて、もうひとつ引数 x14 をとり、これが x8 にも渡されています。再帰で呼ぶときに x14 + 1 となっていることから、これが List の index であることが予想されます。実際 :1127 を呼んでいる他の関数をみると、0 を第3引数に渡しています。こちらは List.mapi と名前をつけておきましょう。

ここから先は少々 List に関する操作が並びます。素直な定義が並ぶので、ここでは単に列挙することにします。

:1128 = ap ap s ap ap c isnil 0 ap ap b ap add 1 ap ap b :1128 cdr
fun(x2) -> if isnil(x2) { 0 } else { 1 + :1128(cdr(x2)) }
:1128 = List.len

:1131 = ap ap s ap ap b s isnil ap ap c b ap ap b ap c ap ap b b :1115 ap c :1131
fun(x2, x8) -> match x2 { [] => x8, x20::x26 => :1115(x20, :1131(x26, x8)) }
:1131 = List.concat

:1132 = ap ap s ap ap b s ap ap b ap b b isnil ap ap c ap ap b b b ap ap c ap ap b s ap ap b ap b c ap ap b ap b ap b c ap ap b ap b ap b ap c :1132 ap ap c ap ap b c ap ap b ap b b ap c i i i
fun(x2, x8, x17) -> match x2 { [] => x8, x47::x59 => :1132(x59, x17(x8, x47), x17) }
:1132 = LIst.foldl

:1133 = ap ap s ap ap b s ap ap b ap b b isnil ap ap c ap ap b b b ap ap c ap ap b c ap ap b ap b b ap ap b ap b c ap ap b ap s b ap ap b c ap c :1133 i
fun(x2, x8, x17) -> match x2 { [] => x8, x47::x56 => x17(:1133(x56, x8, x17), x47) }
:1133 = List.foldr

:1134 = ap ap c ap ap c :1133 nil ap c :1131
fun(x2) -> :1133(x2, [], fun(x7, x8) -> :1131(x8, x7))
fun(x2) -> List.foldr(x2, [], fun(x7, x8) -> List.concat(x8, x7))
:1134 = List.flatten

:1135 = ap ap c ap ap b b ap ap c :1133 nil ap ap c ap ap b s ap ap b ap b c ap ap c ap ap b b s ap c :1115 i
fun(x2, x8) -> :1133(x2, [], fun(x20, x29) -> x8(x29, :1115(x29, x20), x20))
fun(x2, x8) -> List.foldr(x2, [], fun(x20, x29) -> x8(x29, cons(x29, x20), x20))

ここはちょっと心の目が必要で、x8 が 3 引数関数であるかのように書かれていますが、天下りですがこれは実は bool を返す 1 引数関数と思い直すことにします(実際は次の 1136 での 1135 の使われ方をみると第2引数が1引数関数であることがわかります)。すると

fun(x2, x8) -> List.foldr(x2, [], fun(x20, x29) -> if x8(x29) { cons(x29, x20) } else { x20 })
:1135 = List.filter

ということがわかります。

:1136 = ap ap c ap ap b c ap ap b ap b :1126 ap ap c ap ap b b ap ap b :1135 ap ap c ap ap c :1127 cons 0 ap ap c ap ap b s ap ap c b car cdr car
fun(x2, x8) -> :1126(:1135(:1127(x2, cons, 0), fun(x41) -> x8(car(x41), cdr(x41))), car)
fun(x2, x8) -> List.map(List.filter(List.mapi(x2, cons, 0), fun(x41) -> x8(car(x41), cdr(x41))), car)

ちょっと複雑になってきました。まず List.mapi(x2, cons, 0) は、x2 = [e1, e2, e3, ...] という List を [(e1, 0), (e2, 1), (e3, 2), ...] と index との pair の List にします。
これに filter 関数をかけますが、x41 は今作った index との pair の List の各要素で、この car と cdr を x8 の第1,2引数として渡します。結果 x8 には x2 の各要素とその index が渡され、bool を返すことを期待します。最後に filter された List に対して List.map(..., car) として、index を外します。結局 filter 関数 x8 に追加で index を渡す関数ということになります。 List.filteri と名前をつけておきましょう。

:1137 = ap ap b ap b c ap ap b ap b isnil :1135
{\x2.{\x5.{\x7.{\x8.(((isnil ((:1135 x2) x5)) x8) x7)}}}}

内側の構造に着目すると {\x7.{\x8.(((...) x8) x7)}} となっていて、かつここで (...) = (isnil *1 と bool を返す式になっています。このパターンは logical not で、その 1 同様 true = \x.\y.x, false = \x.\y.y を思い出すと

{\x7.{\x8.((true x8) x7)}} => {\x7.{\x8.x8}} = false
{\x7.{\x8.((false x8) x7)}} => {\x7.{\x8.x7}} = true

となっています(Note: 本来関数の内部は引数が与えられるまで計算しませんが、今回は同値のものが得られます)。! 単項演算子を導入して、簡潔にかけるようにします。

fun(x2, x5) -> !isnil(:1135(x2, x5))

この logical not の置き換えは多少注意が必要で、特に中の bool 式が x7, x8 を含んでいないことを確認する必要があります(仮に含んでいると、書き換え後にその変数が浮いてしまうため)。
:1135 は List.filter であったので、

fun(x2, x5) -> !isnil(List.filter(x2, x5))

filter した結果が nil にならないためには、x5 が true を返すような要素が List x2 に含まれている必要があります。 List.exist と名前をつけておきます。

まとめ

List の操作に関する関数を読み解きました。
次回予告: まだ続く utility 関数を見てみます。

*1::1135 x2) x5