AtCoderに登録したら解くべき精選過去問 10問のうち3問をUnlambda で解いてみた(またはTSGコードゴルフ大会の宣伝)
宣伝
4/30に、TSG主催の第四回コードゴルフ大会
tsg.connpass.com
が開かれます。第一～第三回まではサークル内メンバーでの対抗戦でしたが、今回は(多分新歓もかねて)東大生ならだれでも参加できるようになりました！esolangの腕に覚えのある方、esolang沼に足を踏み入れてみたい方など、興味のある人はぜひ上のconnpassリンクから参加してみてください。
本題
https://beta.atcoder.jp/contests/abs を解くシリーズのやつです。
提出可能言語の中に、Brainf*ckと並んでUnlambdaが存在していたので、Unlambdaの勉強もかねて挑戦することにしました。
Unlambdaについて
いわずとしれた関数型esolangの大御所。 公式の解説は長くてかったるいので、http://wada314.jp/tcf/unlambda/ などのほうが読みやすいと思います。インタプリタは https://inazz.jp/unlambda/ が便利*1でよいです。
Unlambdaの書き方
基本的に、通常のλ式でプログラムを書いた後、それをコンビネータに直します。
以下、N M などはλ式、[M] で M をコンビネータに変換したものを表すことにします。
(1) [M N] => [M] [N] (2) [λx.x] => I (3) [λx.y] => K y (4) [λx.M] => K [M] (xはM中に自由に出現しない) (5) [λx.M N] => S [λx.M] [λx.N] (6) [λx.λy.M] => [λx.[λy.M]] ([λy.M] はなにがしかのコンビネータになるので、3か5に落ちる)
となります。 (4) がなくても帰納法は回りますが、これをしないと変換後の項が爆発的に増大してしまいます。
Unlambdaを書く際の注意(というか僕がめっちゃ詰まったところ)
Unlambda の評価規則は直観的ですが、通常のλ式を Unlambda に直すととたんに非直観的な評価をされるようになります。
Unlambda において、 M N は、『 M を正規形M'まで簡約 』→『 N を正規形N'まで簡約 』 → 『 M' N' を正規形まで簡約 』 の順に簡約されます。
このとき、(λx.M) N をコンビネータに変換すると [(λx.M)] [N] となるので、もしMの中に簡約可能な部分が存在する場合、そちらが先に評価されてしまいます！！
たとえば、おなじみYコンビネータ*2は λf.(λx. f (x x)) (λx. f (x x))) ですが、これをそのままコンビネータに変換して使用すると、 (Y f) x → f (Y f) x → f (f (Y f)) x と簡約されてしまい、ここだけで無限ループに陥ってしまいます。通常はこれをZコンビネータ λf.(λx. f λy.(x x y)) (λx. f λy.(x x y)) にすることによって解消しますが、今回はλ抽象の内側が先に簡約されるので、どちらにせよ無限ループに陥ってしまいます。*3
そこで、Unlambdaのプリミティブであり評価順を変更するd演算子で包んで、これを解決します。すなわち、Y コンビネータを λf.(λx. f (d (x x))) (λx. f (d (x x))) としてやると、
Y f ≡ (λf.(λx. f (d (x x))) (λx. f (d (x x)))) f →
(λx. f (d (x x))) (λx. f (d (x x))) →
f (D (λx. f (d (x x))) (λx. f (d (x x))) ≡ f (D (Y f))となって、d より内側が簡約されないので、無限ループにならずにすみます。
また、IOの評価タイミングにも注意が必要です。たとえば、1文字読み込んで~~~ みたいなやつを、単純に Y (f. x. @ I ~~~) みたいにかくと、 xの適用より先に @ I が簡約されてから再帰が展開され、読み込みが1回しか起こりません。そこで、たとえば、 Y (f. x. K I x @ I ~~~) とすると、 x が適用されるまでは @が簡約されないので、ちゃんと動くようになります。
高速化について
自然数のencoding
通常のチャーチエンコーディング λs. λz. s (s (s ... (s z)) を用いて自然数を実装すると加算に O(n) かかってしまうので、
irori.hatenablog.com
の手法を参考にして、v終端のリストで表現するようにしています。 その他、加算などもこの記事を参考にしました。
その他のTips
λx. λy. x を上の手順でコンビネータに変換すると、
[λx. λy. x] = [λx. [λy. x]] = [λx.K x] = S [λx.K] [λx.x] = S (K K) I
となってしまいますが、明らかにこれは K と等価なので、 K に変換するようにしています。
実践例
λ式っぽく書いたやつをUnlambdaのコードに変換するスクリプトをRubyで*4実装しました。ソースコードは、 https://github.com/satos---jp/lambda_implementation の unlambda_ruby 内にあります。
以下に貼っているのはUnlambdaに変換する前のオレオレλ記法*5のソースコードです。
ABC081A Placing Marbles
https://beta.atcoder.jp/contests/abs/submissions/2297587
(a. b. c. a (b (c .3 .2) (c .2 .1) ) (b (c .2 .1) (c .1 .0) )) ($iv2tf (@ ?1)) ($iv2tf (@ ?1)) ($iv2tf (@ ?1)) I
($iv2tf (@ ?1)) は 入力を1文字受け取り、 '1'なら true を、 そうでないなら false を返す関数です。
ABC086A Product
https://beta.atcoder.jp/contests/abs/submissions/2297608
(ri. z. ($iseven (ri z)) $t ($iseven (ri z)) (i. i .E .v .e .n) (i. i .O .d .d) I I) $read_int *0
PracticeA はじめてのあっとこーだー
Submission #2293682 - AtCoder Beginners Selection
K ((ri. $print_int ($add (ri *0) ($add (ri *0) (ri *0)))) $read_int) (.g I) (Z (f. i. @ (x. | x f i)) I)
と、ここまではよかったんですが...
ABC081B Shift Only
Submission #2345160 - AtCoder Beginners Selection
約 2100 msec でTLE
ABC049C 白昼夢 / Daydream
Submission #2345136 - AtCoder Beginners Selection
約 2700 msec でTLE
となって、どちらも微妙にTLEしてしまいます。AtCoderのTLE厳しくないですか？？？
どうにかして縮めようとしましたが、なんだかもうどうしようもなくなってしまった*6ので、かわりに適当なA問題を通してUnlambdaのsolved数1位を奪取しました。
まとめ
Unlambdaを使うと、AtCoderのA問題は解けるが、B,Cを解くにはTLEが厳しい。
再度宣伝
4/30に、TSG主催の第四回コードゴルフ大会
tsg.connpass.com
が開かれます。興味のある人はぜひ上のconnpassリンクから参加してみてください！
