# 116: print $ a*b + c *d が型エラーになる
[↑up](bunny_notes)

- issued: 2020-11-29
- 分類： A サンプルコードが fail
- status: Closed (2020-12-12)

## 概要

[Hakell プログラムをコンパイルしたものを Android 上で動かす](https://uhideyuki.sakura.ne.jp/studs/editor.cgi/ja/thirtydays2release09#2020-11-27p0)
のときに気づいたのですが、$<verb>{print $ a*b + c*d} が型検査において、エラーする。
$<verb>{print (a*b + c*d)} であれば Ok なので、fixity resolution が期待通りにできていないものと思われる。

まずは、発覚時と同じケースを再現するテストプログラムを用意 (testcases/infixerr.hs):

$$<pre>{
main = print $ 1*2 + 3*4
$$}

$<verb>{print $ 1*2} ならどうか、とか、いくつか現象をしらべてから、コード調査するのがいいかと思われる。

## 調査ログ
## 2020-12-12

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

$$<pre>{
main = print $ 1*2 + 3*4
$$}

コンパイルした結果は、型エラー。おそらく結合性解決にしくじっていて、 $<verb>{(print $ 1*2) + (3*4)} のような式を型検査しようとしているのだろう。

$$<pre>{
$ 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: 

$$<pre>{
$ 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 フェーズで行われる：

$$<pre>{
$ 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 になっていないので、ちょっと読みづらいが、それぞれ次のようになっている。

$$<pre>{
Absyn: ((((print $ 1) * 2) + 3) * 4)
Ren: ((($) print) (2*1)) + (3*4)
$$}

エラーの原因から予想したとおり。これは、resolveFixity 関数がいい加減だったのが原因だった。修正前の実装では、Absyn のツリーを自然にたどることで、右から順にみていき、
$<verb>{rest `op2` e2 `op1` e1} を二つの演算子の結合性に応じて、
$<verb>{op1 (rest `op2` e2)  e1} か $<verb>{rest `op2` (op1 e2 e1)} に変形していた。rest がまた InfixExp ならば、これが再帰的に処理されるという形。

そこで今回は、Haskell 2010 Language Report の
[10.6 Fixity Resolution](https://www.haskell.org/onlinereport/haskell2010/haskellch10.html#x17-18100010.6) 
の記述にしたがってきちんと処理できるように書き直した。

まず、自己流で右から処理するのはやめて、左から処理する。そのために、いったん InfixExp ツリーをたどって左から順に処理するためのリストを作成。あとは、左から処理するのだけど、
$<verb>{resolve (a op1 b ((op2  c): rest)} を

- $<verb>{resolve (op1 a b) op2  c rest} (op1 の方が強かった場合）
- $<verb>{op1 a (resolve b op2 c rest)} (op2 の方が強かった場合）

のように再帰してはいけない（最初、こうしてしまった）。これでは、優先度の低い演算子を右結合してしまって、たとえば $<verb>{a*b + c*d + d*f} を
$<verb>{(a*b + (c*d + d*f))} のように解釈しています。足し算であれば、計算の結果が変わらないのでわかりづらいが、$<verb>{a^b `div` c^d `div` e} などでは計算の結果が変わってしまう。

つまり、レポートにあるとおりに実装すればいいのだけど、ミソは左端と右端をいかに特別扱いするかというところ。レポートでは、左端を示すためにダミーの演算子（優先度が負）を用い、右端は rest が空であることで表現している。Bunny では、第一引数を用いた（0の場合に左端）。

修正によって正しく動くようになった３つのプログラムを、test/samples に加えることとする。

$$<pre>{
main = print $ 1*2 + 3*4
$$}

$$<pre>{
main = print $ 2^3 `div` 2^2 `div` 2
$$}

$$<pre>{
-- 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。