Chat

[kmyk]

This is a chat space. Both English and Japanese are welcome. Please use like a Twitter.

[kmyk]

ここの chat 欄をもっと雑に使っていくといい気がする

[kmyk]

よし

[kmyk]

にゃん

[kmyk]

thread 式なのか。話題ごとに整理するとかじゃなくて、もっと Twitter 感覚で適当に書き込める感じがいいんだけどな

[kmyk]

まあいいか。Twitter だと思えば任意の場所が Twitter です

[kmyk]

最適化の実装を任せられるぽいので、私は人には任せられないしんどいパートをやっていきます (しんどい…)

[kmyk]

とりあえず core 言語のパーサを書きます

[kmyk]

なんと C++ のパーサの予定もあるぞ！ なんで 1 個のコンパイラに 3 個のパーサがいるんや、おかしいやろ

[kmyk]

Python はしんどかったが core なら単純だからいける気がしてきた

[kmyk]

できた

[kmyk]

バグってる

[kmyk]

@hotman78 chat 欄がここにあります。質問があるときとかないときとかに気軽に使ってね

[hotman78]

ありがとうございます！

[hotman78]

二度手間防止/ルール案の発見のためにoptimization.mdに書いてないような細かい最適化を挙げてく

[kmyk]

とりあえず、細かい最適化のうちで他のルールを書くときに重要そうなやつを挙げておきます

• ArithmeticalExpr: 算術式を整理する。n - (n - i - 1) - 1 が i になったりする。式の中の自由変数が減るとやれる最適化が増える
• Alpha: alpha 変換をする。(fun x -> fun x -> e(x)) みたいな式の変数名を付け替えて被りをなくし (fun x -> fun y -> e(y)) にする
• Beta: beta 簡約をする。つまり (fun x -> e(x)) a を e(a) にする
• BubbleLet: foldl (fun y x -> let z = c in e) y0 xs を可能なら let z = c in foldl (fun y x -> e) y0 xs にする。c の計算が重いなら計算量が落ちる
• ConstantFolding: すべてが定数の式を計算してしまう。たとえば 3 + 4 を 7 に置き換えるとか
• Eta: eta 変換をする。たとえば foldl (+) 0 xs を foldl (fun y x -> y + x) 0 xs にする

完全なリストは https://kmyk.github.io/Jikka/haddock/ を見るのがよい気がする

[hotman78]

バグの内容メモ
coreにするところでバグってる

バグる式

# before
return (-n)*(n+1)
# after
return -n+n*n ;

# before
return (-1)*(n+1)
# after
return -n+2

# before
return 2*(n+1)
# after
return n * 2 + 4

# before
return 2*(n-1)
# after
return n * 2 - 4

バグらない式

# before
return 2*(n-n*n)

# after
return 2*n-2*n*n

# before
return 2*(1+3)

# after
return 8

[hotman78]

https://github.com/kmyk/Jikka/blob/8aac3c02a5d035df06d5024eca3e30ee5e017536/src/Jikka/Core/Convert/StrengthReduction.hs#L44
ここ怪しいけどここだけではなさそう

[hotman78]

定数項が二倍になってる？

[kmyk]

rewrite rule が今より簡単に書けるようになりました。#133

いままでは

simpleRewriteRule $ \case
  Map' t1 t2 f (Reversed' _ xs) -> return' $ Reversed' t2 (Map' t1 t2 f xs)
  _ -> Nothing

と書いてた部分が、代わりに

[r| "map/reversed" forall f xs. map f (reversed xs) = reversed (map f xs) |]

とも書けます。簡潔で見やすくなって、書きやすい + どういう rule があるのか分かりやすいのでうれしい。

Template Haskell という、Rust で言うところのマクロみたいな機能を使って実装されています。

[kmyk]

rule のバグが後になってから発見されるやつしんどいし、もっとテストをたくさん用意しておかないとだめそう。ABC の B, C あたりをひたすら解いて examples/ の中に突っ込む会とかが必要そう

[hotman78]

一気になるとしんどそうなので、合間合間でやっていこうと思います

[kmyk]

docs/internal.ja.md を要約して主張を足した感じの記事を書きました

プログラミング言語処理系の作り方 (競プロer向け) - うさぎ小屋
https://kimiyuki.net/blog/2021/08/05/how-to-make-your-own-interpreter/

[kmyk]

@hotman78 #151 #152 これらに興味ありませんか？ <O(N), O(1)> GCD チャンスです

[hotman78]

ちょうど何から手を付けるか悩んでたのでやります！
issueにないdata_structureも追加できそうなものはどんどん挙げていいですかね？

[kmyk]

追加できそうなものはどんどん挙げていいですかね？

はい。貼ってうれしそうなものはなんでも歓迎です。思い付いたら新しい issue として立てておくとよい

[hotman78]

むーん
min/maxとgcd/lcmで文法が異なるの若干めんどうの元になりそうな気がしてます
(現状変換されなくて悲しくなってるだけなのですが...)

[kmyk]

「文法が異なる」とは、min/max だと max2 : a -> a -> a と max1 : a list -> a があるけど gcd/lcm だと gcd : int -> int -> int しかないということでしょうか？
たしかにそれは面倒そう。gcd1 : int list -> int とかを足してしまってもよいかもしれません。

新しい組み込み関数として足してもよいですし、foldl を使って alias として書くこともできます。以下のように書けば foldl gcd 0 の alias として gcd1 が使えるようになります。

{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ViewPatterns #-}

pattern Gcd1 e <-
  (\case Foldl' IntTy IntTy (Lam2 y IntTy x IntTy (Gcd' (Var y') (Var x'))) (LitInt' 0) e | y' == y && x' == x -> Just e; _ -> Nothing -> Just e)
  where
    Gcd1 e = Foldl' IntTy IntTy (Lam2 "y" IntTy "x" IntTy (Gcd' (Var "y") (Var "x"))) (LitInt' 0) e

[hotman78]

patternなるほどです...
新しい組み込み関数として足してしまいました
上で考えていた内容は少し違う内容だったのですが、自己解決しました
Lit (LitBuiltin Gcd [])
Lit (LitBuiltin Min2 [IntTy])
が同じ型になってくれるので大丈夫そうでした

[kmyk]

整数に最大値はないので max nil がエラーになるやつ、どうにかならないかな。「どうせ後で int64_t になるので、最大値はあります！w」ってやっちゃだめかな？ 変なバグり方してやばそうではあるが

[kmyk]

ここの存在、普通に考えて誰も気付いてないと思うので ping しておく @uta8a @riantkb
まあ Twitter とか issue とかでいいという話もあるんですが

[kmyk]

core から C++ への変換を「とりあえず変換する。そして無駄なコピーを消す」できると思うじゃん。ふたつのパートを分けておいた方が見通しよく書けるはずだったんですよ。なんだかそれではだめらしいです。つらすぎ

[uta8a]

examplesを追加する作業で、examples/README.mdにはなんて書けばいいんだろうか。wipのABC-Bは特別にすごいことをしているわけではないので、Real tasks of competitive programmingに軽く書いちゃっていいのかな？と思いました

[uta8a]

これ慣れてないから非本質で悩んでいるだけな気がしてきた。気にしないことにする。

[kmyk]

気にせず軽く書いちゃって大丈夫です
「愚直がそのまま通る」というのが分かるようになってればうれしいけど、まあ ABC の B だしそのことは問題 ID からも分かる

[riantkb]

ループ内の割り算が消えるの、コメントアウトデバッグをしたら reduceFold が悪さしてそう？ ということが分かったが、何もわからず
https://github.com/kmyk/Jikka/blob/45c04f382c761e0716041efc284b566a6a7d2ca1/src/Jikka/Core/Convert/ShortCutFusion.hs#L116-L119

[kmyk]

reduceFold は正しそうに見えます。となると reduceFold が動作することで起動されるやつが怪しくて、でも検索 https://github.com/kmyk/Jikka/search?q=Iterate%27 してみたけどそれっぽいのを見つけられない

[riantkb]

MatrixExponentiation だけをコメントアウトしても正しいコードが得られましたね……（というかコードを読んだら完全にそれっぽいことをしているやつだ）

[uta8a]

連絡: haskellのフォーマッタormoluのtrailing newline問題、すぐに向こうの方が直してくれた。ありがたい
tweag/ormolu#744

[kmyk]

core から C++ への変換をずっと考えています。やればできるはずなんですけど、頭がこわれる
#177

[kmyk]

#168 できた 🎉

[kmyk]

@hotman78 そういえば FFT のやつとか調子どうですか (何を実装するにしてもしんどすぎることについては申し訳なく思っています……)

[hotman78]

別の用事が重なって途切れてから全然手をつけられてませんでした...
落ち着いてきたので再開します！！

[kmyk]

@soraiemame ここの存在に気付いてないかもなので念のため ping しておく

[kmyk]

@各位
「Jikka の実装のここが分かりにくい」みたいなのがあったら教えてください。もうすでに自己解決したものでもよいです。ドキュメントに書くので

[kmyk]

YouTube で開発配信したりとか Discord で画面を共有してペアプロしたりとかしたらいい気がしてきた