最適化がかからないように書いたフィボナッチが正しくないコードに変換される

[riantkb]

Summary / 概要

行列累乗に変換されないように書いたフィボナッチ数列の第 N 項を求めるコードが、C++ に変換された際にフィボナッチ数列の第 N 項を求めていない

Steps to reproduce / 再現方法

• $ cat a.py

  from typing import *
  
  def solve(n: int) -> int:
      a = 0
      b = 1
      lis = []
      for i in range(n):
          lis.append(0)
      for i in lis:
          c = a + b + i
          a = b
          b = c
      return b
  
  def main():
      n = int(input())
      ans = solve(n)
      print(ans)
  
  if __name__ == "__main__":
      main()

• $ stack run convert a.py > a.cpp
• $ cat a.cpp

  // ...
  int64_t solve(int64_t n_0) {
      std::vector<int64_t> x1;
      for (int32_t i2 = 0; i2 < int32_t(n_0); ++ i2) {
          x1.push_back(0);
      }
      int64_t x5_9 = 1;
      int64_t x5_10 = 0;
      for (int64_t x6 : x1) {
          x5_9 = x6 + x5_9 + x5_10;
          x5_10 = x5_9;
      }
      return x5_9;
  }
  // ... 

• $ echo "10" | python a.py

  89

• $ g++ a.cpp && echo "10" | ./a.out

  512

environments:

• version: (please write the versions of related things, e.g. $ stack run --version)
• $ git log --oneline -1

  a7cafc0 (HEAD -> master, origin/master, origin/HEAD) Merge pull request #149 from kmyk/script-to-add-sample-cases

comment

• core 言語ではノンブロッキング代入みたいな挙動をする書き方になっていたのが C++ に直すタイミングでそうでなくなった結果変なことになっているのかなと思ったりしましたが何もわかりませんでした 😢

[kmyk]

「core 言語ではノンブロッキング代入みたいな挙動をする書き方になっていたのが C++ に直すタイミングでそうでなくなった結果変なことになっているのかな」という予想は正しそうで、バグってるのはたぶん src/Jikka/CPlusPlus/Convert/MoveSemantics.hs か src/Jikka/CPlusPlus/Convert/UnpackTuples.hs の中のどこかです。でも具体的にこの中のどこでどうなってるのかは書いた自分でもすぐには分からない

---

メモ: C++ に変換される直前の core 言語の式

fun (n$607: int) ->
    foldl((fun ($608: int * int) ($609: int) ->
        ($609 + $608.0 + $608.1, $608.0)
    ), (1, 0), iterate(n$607, (fun ($610: int list) ->
        snoc($610, 0)
    ), nil<int>)).0

@uta8a 同じバグで WA になってるものが #150 にもあるかも？

[riantkb]

https://github.com/kmyk/Jikka/blob/a7cafc004079bfa42256544f5cf4f033b31f71ed/src/Jikka/CPlusPlus/Convert.hs#L24 この行をコメントアウトしたら正しいコードが出力されるようになった

int64_t solve(int64_t n_0) {
    std::vector<int64_t> x1;
    for (int32_t i2 = 0; i2 < int32_t(n_0); ++ i2) {
        x1.push_back(0);
    }
    std::array<int64_t, 2> x5 = std::array<int64_t, 2>{1, 0};
    for (int64_t x6 : x1) {
        x5 = std::array<int64_t, 2>{x6 + x5[0] + x5[1], x5[0]};
    }
    return x5[0];
}

[kmyk]

MoveSemantics.hs が以下のような C++ について

int func(vector<int> a) {
    vector<int> b = a;
    b.push_back(10);
    vector<int> c = b;
    c.push_back(10);
    return b.size() + c.size();
}

これを間違えて

int func(vector<int> a) {
    a.push_back(10);
    a.push_back(10);
    return a.size() + a.size();
}

に変換してるぽい

[kmyk]

いや、これは無関係な別のバグでは？

[riantkb]

MoveSemantics をコメントアウトしてもコードがほぼ変わらないので、それは別のバグな気もしています 😇

(a, b) = (c, d)

を

a = c
b = d

に変換するのではなく状況に応じて

tmp_1 = c
tmp_2 = d
a = tmp_1
b = tmp_2

みたいにする、みたいなロジック（もしくはそれと同等な処理）ってどこかに組み込まれていたりしますか？

[kmyk]

core でも let (a, b) = (c, d) in ... のような書き方はできないようになってます。 C++ だと auto [a, b] = ...; は一応はあるが使われていないはず。 なので std::pair<int, int> e = make_pair(c, d); から考えはじめてよいです。

まず

std::pair<int, int> e = make_pair(c, d);
f(get<0>(e));

を

std::pair<int, int> e0 = get<0>(make_pair(c, d));
std::pair<int, int> e1 = get<1>(make_pair(c, d));
f(e0);

にするような変換 (UnpackTuples.hs) があります。これをさらに

int e0 = c;
int e1 = d;
f(e0);

にするような変換 (同じく UnpackTuples.hs) があります。 これ以上のことはしていません。

---

ここまで展開されると

int e1 = d;
f(c);

という copy を move にする変換 (MoveSemantics.hs) が動くこともありますが、今回は関係なかったようです。

[kmyk]

追加です。忘れてたのですが、

std::pair<int, int> e = make_pair(c, d);
f(get<0>(e));
e = make_pair(x, y);

みたいな状況だと

std::pair<int, int> e0 = get<0>(make_pair(c, d));
std::pair<int, int> e1 = get<1>(make_pair(c, d));
f(e0);
e0 = x;
e1 = y;

にするんでした。なんだかこれが悪い気がします 😇

[kmyk]

だから、問題の代入を

pair<int, int> tmp = make_pair(x, y);
e0 = get<0>(tmp);
e1 = get<0>(tmp);

にすればよいはず。 具体的なコードは以下のあたり

https://github.com/kmyk/Jikka/blob/41cc148426aa10eb770aaa08882d8b7268c45606/src/Jikka/CPlusPlus/Convert/UnpackTuples.hs#L164-L179

---

@riantkb かなり手伝ってもらったし、せっかくなので最後の部分やりませんか？ 一時変数を置く処理を足す修正と今回使った a.py をテストに追加する (#141) 作業です

[riantkb]

haskell わからん〜〜〜、となっているんですが、せっかくなのでやりたい気持ちがあります

[kmyk]

ありがとう。任せます

Haskell の言語仕様パートはやればできると思う。 どちらかというと Jikka 内部での C++ の構文木の表現がどうなってるかの方が分かりにくいかもしれません。ドキュメントは https://kmyk.github.io/Jikka/haddock/Jikka-CPlusPlus-Language-Expr.html にあります。(今からもうすこしコメント追加してきます)

[riantkb]

最初に示したコードが（N が小さい範囲では）正しく変換できることを確認し、またその過程で遭遇した問題をこちらのコメントに記したので、この issue は閉じようと思います。 https://github.com/kmyk/Jikka/issues/154#issuecomment-894334767