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`S
~K)
~)
にできて、4バイト縮みます。(これは、改行文字の後に次の行を cons する所で、 consXY マクロではなくて consX マクロを使うことで得られます。)
コード末尾から5文字目辺りの`KK
はK
で良くて、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)