Hakell プログラムをコンパイルしたものを Android 上で動かす のときに気づいたのですが、print $ a*b + c*d が型検査において、エラーする。 print (a*b + c*d) であれば Ok なので、fixity resolution が期待通りにできていないものと思われる。
まずは、発覚時と同じケースを再現するテストプログラムを用意 (testcases/infixerr.hs):
main = print $ 1*2 + 3*4
print $ 1*2 ならどうか、とか、いくつか現象をしらべてから、コード調査するのがいいかと思われる。
以下のプログラムをつかって調査する。
main = print $ 1*2 + 3*4
コンパイルした結果は、型エラー。おそらく結合性解決にしくじっていて、 (print $ 1*2) + (3*4) のような式を型検査しようとしているのだろう。
$ bunny tcompile b116.sh /home/unno/bunny/0.9.0/bin/bunnyc -d ./jout/b116.sh --xno-implicit-prelude /home/unno/bunny/0.9.0/lib/Prelude.hs /home/unno/bunny/0.9.0/bin/bunnyc -d ./jout/b116.sh --xlibrary-path /home/unno/bunny/0.9.0/lib -v b116.sh implicitPrelude ... done. doCompile ... bunnyc: context reduction: IsIn "Prelude.Num" (TAp (TCon (Tycon "Prelude.IO" (Kfun Star Star))) (TCon (Tycon "Prelude.()" Star))) tcompile: failed to compile b116.sh
Rename 前後の内部表現を表示させてみる:
まず、Rename 前の Abstuct Syntax:
$ bunny tcompile --ddump-absyn b116.sh /home/unno/bunny/0.9.0/bin/bunnyc -d ./jout/b116.sh --xno-implicit-prelude /home/unno/bunny/0.9.0/lib/Prelude.hs /home/unno/bunny/0.9.0/bin/bunnyc -d ./jout/b116.sh --xlibrary-path /home/unno/bunny/0.9.0/lib -v --ddump-absyn b116.sh implicitPrelude ... done. Module {modname = Nothing, exports = Nothing, body = ([],[VDecl (ValDecl (VarExp (Name {origName = "main", namePos = (1,1), isConName = False})) (UnguardedRhs (InfixExp (InfixExp (InfixExp (InfixExp (VarExp (Name {origName = "print", namePos = (1,8), isConName = False})) (Name {origName = "$", namePos = (1,14), isConName = False}) (LitExp (LitInteger 1 (1,16)))) (Name {origName = "*", namePos = (1,17), isConName = False}) (LitExp (LitInteger 2 (1,18)))) (Name {origName = "+", namePos = (1,20), isConName = False}) (LitExp (LitInteger 3 (1,22)))) (Name {origName = "*", namePos = (1,23), isConName = False}) (LitExp (LitInteger 4 (1,24)))) []))])} doCompile ... bunnyc: context reduction: IsIn "Prelude.Num" (TAp (TCon (Tycon "Prelude.IO" (Kfun Star Star))) (TCon (Tycon "Prelude.()" Star))) tcompile: failed to compile b116.sh
次に、Rename 後の Typing.Expression。Fixity Resolution は Rename フェーズで行われる:
$ bunny tcompile --ddump-ren b116.sh /home/unno/bunny/0.9.0/bin/bunnyc -d ./jout/b116.sh --xno-implicit-prelude /home/unno/bunny/0.9.0/lib/Prelude.hs /home/unno/bunny/0.9.0/bin/bunnyc -d ./jout/b116.sh --xlibrary-path /home/unno/bunny/0.9.0/lib -v --ddump-ren b116.sh implicitPrelude ... done. doCompile ... ---- ddumpRen ---- ---- BindGroup#0 -- [Expl] Main.main# :: (Prelude.IO Prelude.()) Main.main# [] = AP (AP (Var Prelude.>>) (Var Main.main)) (AP (Var Prelude.return) (Var Prelude.())) -- [[Impl]] -- Is#0 Main.main [] = AP (AP (Var Prelude.+) (AP (AP (Var Prelude.$) (Var Prelude.print)) (AP (AP (Var Prelude.*) (Lit (LitInt 1))) (Lit (LitInt 2))))) (AP (AP (Var Prelude.*) (Lit (LitInt 3))) (Lit (LitInt 4))) bunnyc: context reduction: IsIn "Prelude.Num" (TAp (TCon (Tycon "Prelude.IO" (Kfun Star Star))) (TCon (Tycon "Prelude.()" Star))) tcompile: failed to compile b116.sh
このあたりの内部表現のダンプは、あまりきちんとつくっていなくて、Pretty な Printing になっていないので、ちょっと読みづらいが、それぞれ次のようになっている。
Absyn: ((((print $ 1) * 2) + 3) * 4) Ren: ((($) print) (2*1)) + (3*4)
エラーの原因から予想したとおり。これは、resolveFixity 関数がいい加減だったのが原因だった。修正前の実装では、Absyn のツリーを自然にたどることで、右から順にみていき、 rest `op2` e2 `op1` e1 を二つの演算子の結合性に応じて、 op1 (rest `op2` e2) e1 か rest `op2` (op1 e2 e1) に変形していた。rest がまた InfixExp ならば、これが再帰的に処理されるという形。
そこで今回は、Haskell 2010 Language Report の 10.6 Fixity Resolution の記述にしたがってきちんと処理できるように書き直した。
まず、自己流で右から処理するのはやめて、左から処理する。そのために、いったん InfixExp ツリーをたどって左から順に処理するためのリストを作成。あとは、左から処理するのだけど、 resolve (a op1 b ((op2 c): rest) を
のように再帰してはいけない(最初、こうしてしまった)。これでは、優先度の低い演算子を右結合してしまって、たとえば a*b + c*d + d*f を (a*b + (c*d + d*f)) のように解釈しています。足し算であれば、計算の結果が変わらないのでわかりづらいが、a^b `div` c^d `div` e などでは計算の結果が変わってしまう。
つまり、レポートにあるとおりに実装すればいいのだけど、ミソは左端と右端をいかに特別扱いするかというところ。レポートでは、左端を示すためにダミーの演算子(優先度が負)を用い、右端は rest が空であることで表現している。Bunny では、第一引数を用いた(0の場合に左端)。
修正によって正しく動くようになった3つのプログラムを、test/samples に加えることとする。
main = print $ 1*2 + 3*4
main = print $ 2^3 `div` 2^2 `div` 2
-- problem_1 : https://wiki.haskell.org/Euler_problems/1_to_10#Problem_1 problem_1 = sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0] main = print problem_1
番号は順に sample320, 321, 322。