haskell-jp / mokumoku-online #49

本日はこれの他に、cabal replの件については依存しているcabal-installを更新したりしました
https://twitter.com/igrep/status/1601862213442359297

Implementing Functional Languages:a tutorial の 3 The G-machine の 3.5 Mark 3: let(rec) expressions から読み始めて、
写経と一部実装を行いながら、3.5.4 The compiler の途中まで読み進めました。

CTFP は章末まで読了
AOC 2022 は part 2 を悪戦苦闘中

AOC day10 part 2 が通りました

S.K.です。今週もお世話になります。よろしくお願いします。
Implementing Functional Languages:a tutorial の 3 The G-machine の
3.5 Mark 3: let(rec) expressions 3.5.4 The compiler の続きから読み進めていこうと思います。

山本悠滋です。いつもどおりmakeMistakesToLearnHaskellの続きを少し進めてから、cabal replの件を進めます。まだお昼ご飯の途中だけど！ :rice:

"Category Theory for Programmers," Bartosz Milewski, (Lulu), Part Three, Ch. 31 Monads, Monoids, and Categories　いよいよ最終章
あとハシゴで https://www.youtube.com/watch?v=Fh2ivzJaivw

白鳥です。遅れて参加させていただきます。「コンピュータシステムの理論と実装」の7章の問題をhaskellでやろうと思います。

https://twitter.com/igrep/status/1604393637991043072 の後、ユーザーが使用しているcabal-installのバージョンを調べる方法を調べていました

Implementing Functional Languages:a tutorial の 3 The G-machine の 3.5 Mark 3: let(rec) expressions 3.5.4 The compiler の続きから読み始めて、
Exercise 3.16 (compileLetrec関数の実装)まで進めました。今回も時間かかってしまいました。
とりあえず、テキストに載っていた不動点コンビネータYのコンパイル結果は、同じ結果となりました。

最終章読了で感無量　とはいえ Ch. 29 Topoi あたりから霧が立ちこめて　ひたすら写経だけの消化不良だったうらみがある
著者の結論が "all told, a category is just a monad in the bicategory of spans." には　まだ手ぶらのままなのに放り出された感
とりあえず Haskell と圏論については一段落なので　また別の教材を考えよう

「コンピュータシステムの理論と実装」７章のバーチャルマシンコードのパーサを作りました。続いてアセンブリコード生成の実装方法を考ているところで終わってしまいました

山本悠滋です。今日はmakeMistakesToLearnHaskellの続きを書きながら他の私用を進めます。

S.K.です。今週もお世話になります。よろしくお願いします。
Implementing Functional Languages:a tutorial の 3 The G-machine の
Mark3 Gマシンのletrec構文を使ったテストプログラムの動作確認から進めていこうと思います。
他に私用も少し進めたいと思います。

AtCoder 鉄則本 B20 Edit Distance https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cs

チェシャ猫です。1 時間だけですがちょっとでも進めます。

こちらの進捗の他、cabal replの件でcabal --versionの結果をパースする処理を適当に実装し、テストを書いてみています。
https://twitter.com/igrep/status/1606935440665513984

Mark3 Gマシンでletrec構文を使ったテストプログラムが一応正しく動作したようなので、3.6 Mark 4: Adding primitives を読み進めました。
3.6.3 The new instruction transitions の Evaluator instructions の途中まで読み進めました。

先人が GitHub に公開していたテストケースを実行する部分を作っていました。実行はできるものの全ケースが Fail しているので、個々のケースではなく共通してチェックサムを取る部分にバグがあるんじゃないかと踏んでいます。

AtCoder 鉄則本 A23 - All Free https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_w

S.K.です。今週もお世話になります。よろしくお願いします。
Implementing Functional Languages:a tutorial の 3.6.3 The new instruction transitions の
Evaluator instructions の続きから読み進めようと思います。

山本悠滋です。実家にいるのでのんびりmakeMistakesToLearnHaskellをちょっとだけ進めます。

ちょっと早いですが本日の成果です。
https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/01fb1649a7da1bdae3deef7fb03d80ba91a2c4d4

写経と一部実装を行いながら、何とか 3.6 Mark 4: Adding primitives の最後まで読み進めました。
Appendix B.3 Arithmetic のテストプログラムで確認したところ、nfib を除いて一応正しい結果が得られたようです。
nfib は処理が止まる気配なしでした。
Wikipediaのフィボナッチ数計算式に合わせてテストプログラムを書き換えて試したところ、
一応正しい結果が得られましたが、900ステップ以上かかってしまいました。

@K.N has joined the channel

山本悠滋です。お昼ご飯を食べてから、ですが、例のごとくmakeMistakesToLearnHaskellの続きと、cabal replの件を進めます。

初参加です。よろしくお願いします。
Codewarsという、プログラミングのトレーニングができるサイトで出題されている、haskellの問題を解きます。

S.K.です。今週もお世話になります。よろしくお願いします。
Implementing Functional Languages:a tutorial の 3.7 Mark 5: Towards better handling of arithmetic から読み進めようと思います。

"An Introduction to Recursion Schemes," Patrick Thomson https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html
あとハシゴで AtCoder 鉄則本 A26 - Prime Check https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_z

自作AtCoder library内の整数剰余型 Rem m の (^) :: (Num (Rem m), Integral a) => Rem m -> a -> Rem m (ただし instance Data.Reflection.Reifies m Word => Num (Rem m)) を黒魔術で高速化すべく頑張ります

:kininaru:

うまく行きましたので先抜けします．何をしたかだけ軽く書いておきますね．
自作整数剰余型 Rem m の (^) が遅かったのです．profをとっていないのでよくわからないのですが， この原因は， Data.Reflection.reflect :: Data.Reflection.Reifies m a => proxy m -> a で出てくる reflect :: Reifies m Word => proxy m -> Word の素性が simplifier にから見てよくわからないので，インライン化もされない (*) :: Rem m -> Rem m -> Rem m の呼び出しが何度も reflect を呼んで最適化もされない，ということだったっぽいです．そこで， reflect を (^) の計算の最初だけ呼び，`(^)` の実装内部においては， (*) のかわりに，その実装に使われている modulus つき乗法関数(自作) unsafeModMult :: Word -> Word -> Word -> Word を呼ぶようにする，ということをしたいです．ところが，RULES で (^) を書き換えようとすると type checker が Num (Rem m) を知ってるくせに Reifies m Word を知らない，という事態が生じます． そこで Num (Rem m) だけの制約からmodulusを取ってくる必要に迫られるのですが，`fromInteger :: Integer -> Rem m` が remFromIntegerWithMod modulus に書き換えられるように実装されていることを利用して RULES で computeModulusFromNumConstraint (remFromIntegerWithMod modulus) = modulus と書き換える，みたいな真似をしています． これで， AtCoder ABC282-E の実行速度が https://atcoder.jp/contests/abc282/submissions/37366230 (788ms) から https://atcoder.jp/contests/abc282/submissions/37872422 (173ms) へと高速化しました．手書きの剰余冪乗を用いた (168ms) と遜色ない速度です．

時間になりましたので成果を書きます。下記５問を解くことができました。
一人でやるよりも緊張感があって集中できた気がします。ありがとうございました。
https://www.codewars.com/kata/549ee8b47111a81214000941
https://www.codewars.com/kata/54ce4c6804fcc440a1000ecb
https://www.codewars.com/kata/5a7f58c00025e917f30000f1
https://www.codewars.com/kata/58b57ae2724e3c63df000006
https://www.codewars.com/kata/58b38256e51f1c2af0000081

makeMistakesToLearnHaskellの続きを少し書いてましたが、いろいろ誘惑に負けちゃってあまり捗らず。

3.7 Mark 5: Towards better handling of arithmetic の 3.7.2 The solution の途中まで読み進めました。
Exercise 3.28.を一応何とか解いて、Exercise 3.29. を解こうとしているところです。
今回も時間がかかってしまいました。

延長戦でやっと集中できました。今週のmakeMistakesToLearnHaskellはここまで。cabal replの件もcabal --versionが出力する文字列をパースする処理のテストを書き終えました。
https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/ad194d12e078a47fe859c21b5a2704403a3ebb3c

S.K.です。今週もお世話になります。よろしくお願いします。
Implementing Functional Languages:a tutorial の 3.7.2 The solution の続きから読み進めようと思います。

白鳥です。よろしくお願いします。「コンピュータシステムの理論と実装」9章の問題をHaskellで解いていこうと思います。

"Recursion Schemes, Part II: A Mob of Morphisms," Patrick Thomson https://blog.sumtypeofway.com/posts/recursion-schemes-part-2.html
あとハシゴで AtCoder 鉄則本 A34 - Game 3 https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ah

山本悠滋です。お昼寝が長引いて遅くなりました。
いつもどおりmakeMistakesToLearnHaskellの続きを進めた後、cabal replの件をやります。

チェシャ猫です。あと1 時間ですが Programming Language Foundations in Agda を読んでいます。