1202バイトの Lazy K FizzBuzz をほとんど理解しないまま1117バイトに縮めた話(ネタバレ)

Anarchy Golf で長らく最短記録の座にあった rst76 さんの1201バイトの Lazy K FizzBuzz が公開されているのを見つけました。

https://github.com/rst76/Lazy-K/blob/master/fizz_buzz.lazy

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K`SK)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`
K(SS(SSSS(SS`SK))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S
`KS(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(S
S`SK))(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K`SK)
`KI)))))))(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`
S`KS(S`K`S`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K
`SK))))`K`KI)))))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS
(SS(SSS))))(SS`SK))S(S`KSK)))))))`KK)))))`SK))))`KI)(S(S(S`K
S(S`K`S`K(S`KSK)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K
(S`K`S(SI`K(S(S(S(SSS)(SS`SK))S)(SSSS(SS(SS`SK)))(S`KSK)))K)
(S`K`S(SI`K(S(S(S(SS(SS(SSS)))(SS`SK))S)(SSSSSS(SS`SK))(S`KS
K)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K`SK)K))(SII))))))`KK))
)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(
SS(SSSS(SS(SS`SK))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS`
SK))S)(SSSSSS(SS`SK))(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S
`K`S(SI`K`SK)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(
SS`SK)(SS(SS(SSSS(SS`SK)))))(S`KSK)))K))))(S`K`S`K`S(SI`K(SS
(SSSS(SS`SK))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK
))))))))`K`K(S(SS`SK)(SS(SSSS(SS`SK)))(S`KSK)(S`K`SIK)`KK))I
)

これを、コードの意味をあまり考えずに、局所的な最適化だけで1117バイトに縮めました。

1. Jot記法

Lazy K では、 SKI 記法の他に Jot 記法という書き方ができます。 Jot 記法の詳細はさておき、`SK`KIと同じ意味を0の1文字で書けることが、 Lazy K 処理系のソース の353行目辺りを読んでみるとわかります。上記のコードには`SK`KIが合計26回使われていますので、これらを0に書き換えれば52バイト縮みます。

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K`SK)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`
K(SS(SSSS(SS`SK))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S
`KS(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(S
S`SK))(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K`SK)
`KI)))))))(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`
S`KS(S`K`S`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K
`SK))))`K`KI)))))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS
(SS(SSS))))(SS`SK))S(S`KSK)))))))`KK)))))`SK))))`KI)(S(S(S`K
S(S`K`S`K(S`KSK)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K
(S`K`S(SI`K(S(S(S(SSS)(SS`SK))S)(SSSS(SS(SS`SK)))(S`KSK)))K)
(S`K`S(SI`K(S(S(S(SS(SS(SSS)))(SS`SK))S)(SSSSSS(SS`SK))(S`KS
K)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K`SK)K))(SII))))))`KK))
)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(
SS(SSSS(SS(SS`SK))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS`
SK))S)(SSSSSS(SS`SK))(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S
`K`S(SI`K`SK)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(
SS`SK)(SS(SS(SSSS(SS`SK)))))(S`KSK)))K))))(S`K`S`K`S(SI`K(SS
(SSSS(SS`SK))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK
))))))))`K`K(S(SS`SK)(SS(SSSS(SS`SK)))(S`KSK)(S`K`SIK)`KK))I
)

↓(-52 Bytes)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS(SS(SSS))))(SS
0))S(S`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S
(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)
(SS0))S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SS(SS(SS
S)))(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`
K`S(SI`K0)K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(S
I`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`
S(SI`K(S(S(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(
S`K(SII(S(S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)
I(S`K`S(SI`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K
`S`K`S(SI`K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)
))`K`S(S`KSK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SI
K)`KK))I)

2. 数値の表現の短縮

コードにSS(SS(SS(SSS)))という部分があります(ちなみに、これは1桁の数値に48('0'の文字コード)を加えて数字に変換しているコードの一部分です)。ところで、試しに括弧を全て取り除いたSSSSSSSSSというものをひたすらβ簡約してみると、先程のSS(SS(SS(SSS)))に戻ることがわかります。よって、この部分は単にSSSSSSSSSと書くことができて、6バイト縮みます。

同様に、SS(SS(SSS))という部分(これはチャーチ数の105('i'の文字コード)を生成するコードの一部分です)もSSSSSSSで良いので、4バイト縮みます。

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS(SS(SSS))))(SS
0))S(S`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S
(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)
(SS0))S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SS(SS(SS
S)))(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`
K`S(SI`K0)K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(S
I`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`
S(SI`K(S(S(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(
S`K(SII(S(S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)
I(S`K`S(SI`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K
`S`K`S(SI`K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)
))`K`S(S`KSK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SI
K)`KK))I)

↓(-10 Bytes)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SSSSSSSSS)(SS0))S(S
`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S(SI`K(
SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS0))
S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SSSSSSS)(SS0))
S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K0)
K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`
K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`S(SI`K(S(S
(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(SII(S(
S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI
`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K`S`K`S(SI`
K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`K
SK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SIK)`KK))I)

3. その他

(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0)という部分がありあすが、これは(S`K`S(S(SI`K0)`K0)(S(SII)`K0))で良くて、10バイト縮みます。(ちなみにこれは、数値を文字列に変換するときに、10で割った商が0か判定して分岐している所です。 ifnonzero(Scheme版)とか ifnonzeroNXY(rst76さんのHaskell版)というマクロを使うと (ifnonzero n x y)n(Kx)y に展開され、さらにT変換されて前者のようなコードになりますが、今回はy=Iなので、n(Kx)Iとせずとも(n0)0xで十分です。あまり変わっていないように見えますが、T変換すると後者の方が短くなります。)

(SI`K(SI`K0))という部分が2か所ありますが、これは1か所にまとめることができます。関連する箇所の差分を明示しにくいですが、結果的に6バイト縮みます。

(S`K`S`K`S(S`K`S`KK))(S`K`S`K(S`K`SK))にできて、4バイト縮みます。(これは、改行文字の後に次の行を cons する所で、 consXY マクロではなくて consX マクロを使うことで得られます。)

コード末尾から5文字目辺りの`KKKで良くて、2バイト縮みます。(これは、ループカウンタが100になったときに、出力文字列にチャーチ数として解釈できない文字を入れることでエラー終了させるためのものですが、そのためにはKで十分です。しかし、ループの判定をif<=マクロを使って書くと、最短でも`KKになってしまうので、気付きにくい(気付いても修正が面倒)です。)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K0))))`K0))
)))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SSSSSSSSS)(SS0))S(S
`KSK)))))))`KK)))))0))))0)(S(S(S`KS(S`K`S`K(S`KSK)(S(S(SI`K(
SI`K0))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS0))
S)(SSSS(SS(SS0)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SSSSSSS)(SS0))
S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K0)
K))(SII))))))`KK)))(S(S(SI`K(SI`K0))`K(SII(S`K`S(SI`K`S`K(S`
K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0))))(S`KSK)))K)(S`K`S(SI`K(S(S
(SS`S(SSS)(SS0))S)(SSSSSS(SS0))(S`KSK)))K)))(S`KK(S`K(SII(S(
S`KSK)I)(S`K`S(SI`K0)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI
`K(SS(S(SS0)(SS(SS(SSSS(SS0)))))(S`KSK)))K))))(S`K`S`K`S(SI`
K(SS(SSSS(SS0))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`K
SK))))))))`K`K(S(SS0)(SS(SSSS(SS0)))(S`KSK)(S`K`SIK)`KK))I)

↓(-22 Bytes)

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`
K`S(S(SI`K`KK)`K`K`K0)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(
SS(SSSS(SS0))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(
S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS0))
(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K0)0)))))))
(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S
`KK(S`K`S`K(S`KSK)(S`K`S(S(SI`K0)`K0)(S(SII)`K0))))))`K`K(S(
S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SSSSSSSSS)(SS0))S(S`KSK))))))
)`KK)))))0))))0)(S`K(S(S(S`KS(S`K`S`K(S`KSK)(S(SI`K(SII(S`K`
S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS0))S)(SSSS(SS(SS0)))(
S`KSK)))K)(S`K`S(SI`K(S(S(S(SSSSSSS)(SS0))S)(SSSSSS(SS0))(S`
KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K0)K))(SII))))))`KK))
)(S(SI`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS0
))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS0))S)(SSSSSS(SS0)
)(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S`K`S(SI`K0)K))(SII))
))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(SS0)(SS(SS(SSSS(SS0)))
))(S`KSK)))K)))(SI`K(SI`K0))))(S`K`S`K(S`K`S(SI`K(SS(SSSS(SS
0))(S`KSK)))K)(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))))`K`K(S(SS0
)(SS(SSSS(SS0)))(S`KSK)(S`K`SIK)K))I)

(1117 Bytes)