116: print $ a*b + c *d が型エラーになる

↑up

概要

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 ならどうか、とか、いくつか現象をしらべてから、コード調査するのがいいかと思われる。

調査ログ

2020-12-12 (Sat)

以下のプログラムをつかって調査する。

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) e1rest `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。