haskell-jp / questions #68

@igrep
あ!!spacesがspaceになっているのが原因でした..
ありがとうございます
前々からspacesはやたら出てくるなぁと感じていたので教えていただいたものを使うとだいぶスッキリ書けました
@as_capabl これ、やりたかったけど書き方がわからなくて断念したものに近いです!ありがとうございます

ちなみにこんな感じになりました
https://github.com/mrsekut/plp-hs/commit/7f2a2425244ae40f028d9b1fa3cde321726399dc
@takenobu.hs
choiceとchainl1は初見でした
早速試してみます
ありがとうございます!
chainl1ヤバいですね..
おまけにひけらかし: Megaparsecには、chainlを便利にしたmakeExprParserというのがあります
https://hackage.haskell.org/package/megaparsec-6.4.0/docs/Text-Megaparsec-Expr.html
なるほど!!
Parsecを拡張(?)したAuttoparsecやMegaparsecなるものがあるのですね
初めて知りました
ありがとうございます!
makeExprParser、ちょっと調べてみます
Megaparsecについてはそうです。Parsecのイケてないところをいろいろ改善するために作られたライブラリーなので。
Attoparsecについては、Parsecとちょっと方向性が違っていて、詳しいエラーメッセージを出せない代わりに速度を高めています
なるほど、それぞれ目的が異なるのですね
なにも知らないですが、処理速度と詳しいエラーが出せないことがトレードオフになるのが少し不思議に感じます
ここでいう「詳しいエラーメッセージ」とはエラーが発生した位置を含んでいる、という意味です。
既知かも知れませんが参考までに、Megaparsecなどの情報です。

Bigmoonさんのところの記事(日本語)
https://haskell.e-bigmoon.com/posts/2019/07-14-megaparsec-tutorial.html

Switch from Parsec to Megaparsec(英語)
https://markkarpov.com/megaparsec/switch-from-parsec-to-megaparsec.html

Mizunashiさんの、いろいろなパーサまとめ記事もあり。
https://qiita.com/Mizunashi_Mana/items/115855bf2af9b9970198
うおお、ありがとうございます:man-bowing:
質問ばかりで恐縮ですが、こんどはコード生成に関する雑な質問です。

ASTまで得られた状態で、他の言語などへのコード生成の処理を書きたいと思っています。
関数型言語が構文解析が得意なのは耳にしていましたが、コード生成も得意なのは初めて知りました。

以下のような記事を見つけ、読んでみました。
https://keigoi.hatenadiary.org/entry/20111206/haskell_tagless_dsl
http://nebuta.hatenablog.com/entry/2013/08/01/143926
一度読んだだけでは正直、わからないところもわからないという感じですが、
とりあえず以下のような話題を理解するように感じました

- 型クラスの自作
- モナドの自作
- モナド変換子の概念の理解と、扱い方

この記事を参考にして一つずつわからないところを潰していくつもりではありますが、もしこの「コード生成」の部分に関して入門者向けの良い記事や書籍、ライブラリや実装例、検索のための語彙などをご存知でしたら教えていただけると嬉しいです。

ターゲットなる言語は特に問うてませんが、実装中なのはアセンブリを吐くコンパイラです。
現状、コード生成部分はすごい手続き的な書き方になってしまっています..
https://github.com/mrsekut/hcc/blob/master/app/Main.hs

よろしくお願いします。
モナド変換子ならこちらがオススメです
http://bicycle1885.hatenablog.com/entry/2012/12/08/165236
モナド変換子を勉強すると、モナド変換子の型別名や newtype ラッパーを作るだけで事足りるので、オリジナルのモナドを作ることはほぼないと思います
コード生成、とは少し違うかもしれませんが、いちにぃさんのPDFを読んで生成する話の記事は読みやすくて面白いです~
ステップバイステップ何回も読んだなー笑
@kakkun61
スッテプばいステップ読み進めています
学びが深くてうずうずしています
ありがとうございます!
@永江良一 has joined the channel
@lotz

まだちゃんと読んでいませんが、PDFを生成する記事もヤバそうです!(長い!そしてはてぶ数がすごい!)
モナド変換子の記事をやり終えたら読んでみたいと思います
ありがとうございます!
@kajitack has joined the channel
MacOS Sierra で stack lts-12.26 (GHC 8.4.4)だと平気なんだけど、lts-14.2 (GHC 8.6.5) だとリンカで死ぬ :cry:
Linking .stack-work/dist/x86_64-osx/Cabal-2.4.0.1/build/site/site ...
Undefined symbols for architecture x86_64:
  "_utimensat", referenced from:       
      _cazW_info in libHSdirectory-1.3.3.0.a(Posix.o)
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
`gcc' failed in phase `Linker'. (Exit code: 1)
Completed 166 action(s).               

--  While building package matsubara0507-ghpages-0.3.1.0 using:
      $HOME/.stack/setup-exe-cache/x86_64-osx/Cabal-simple_mPHDZzAJ_2.4.0.1_ghc-8.6.5 --builddir=.stack-work/dist/x86_64-osx/Cabal-2.4.0.1 build exe:site --ghc-options " -fdiagnostics-color=always"
    Process exited with code: ExitFailure 1

utimensat 使えないのに、utimensat 使えるフラグが立っちゃうせいだと思うんだけど、うーん、なぜだろ
いろんなパターンで試した結果、GHC 8.6.4 からダメっぽい(lts-13.11 は行けて lts-13.19 はダメだった、Cabal も関係なかった)
Undefined symbols for architecture x86_64: “_utimensat”, referenced from: _cazW_info in libHSdirectory-1.3.3.0.a(Posix.o)


似たようなの見つけました。
そうそう、それみた
High Sierra 以上にすれば平気なんだろうけど
@i-kanto has joined the channel
@Maillein has joined the channel
@y_ahiru has joined the channel
@sekikano has joined the channel
Nobuyuki Tomizawa
@Nobuyuki Tomizawa has joined the channel
@zak has joined the channel
GHCのRTSについての質問です。 https://twitter.com/igrep/status/1167019215489863681 に書いたとおりなのですが、
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/haskell-execution/pointer-tagging で解説されている「tagged pointerによる最適化」というのは、 https://gitlab.haskell.org/ghc/ghc/blob/bd660edeb783a74e5ca3f1f82713b2aeedae19dc/includes/Cmm.h#L279-285 で行われている、
「タグを取得してみてタグが0じゃなかったらタグの値をそのまま返して、0だったら %INFO_PTR というマクロを呼ぶ」処理のこと、という理解で正しいでしょうか?
Pointer Tagging は、ヒープオブジェクトが評価済みか否かを、ポインタの下位ビットを使って表す実装方法になります。

タグが0でなければ「評価済み」であると判断して、そのヒープオブジェクトの評価を省略できます。
そのヒープオブジェクトが値コンストラクタの場合は、タグのビットが値をそのものを表します。
例えば、Maybe型の値であれば、タグが1なら「Nothing」で、タグが2なら「Just x」であることがわかります。

なお、タグが0の場合は「未評価」であるとして、そのヒープオブジェクトを評価(ENTER)します。

参考までに、pointer taggingの実装イメージはこんな感じです。
https://takenobu-hs.github.io/downloads/haskell_ghc_illustrated.pdf#page=37
なお、Pointer Tagging を使ったコードは、GHCのランタイムシステムだけでなく、GHCによるコンパイル結果のコード側にも表れます。例えば、 case x of ... x が評価済みかを、pointer tagging で切り分けています。

少しコード例が古いですが、Pointer Tagging については、以下の箇所付近も参考になります。
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/generated-code#example-7-case-expressions
型の切り出しによる関数の書き換え方ついて質問させてください。

今まで以下のような型だったものを
data Expr = Add Expr Expr
          | Sub Expr Expr
          | Nat Int
            deriving (Show, Eq)


以下のように切り出したいと考えています
data BinOp = Add | Sub deriving (Show, Eq)
data Expr = BinOp Expr Expr
          | Nat Int
            deriving (Show, Eq)


それに伴い、今まで使っていた関数も少し手を加えなければいけないのですが、書き換え方がわかりません。
-- 従来のもの
-- add ::= term | term ('+' add | "-" add)
add :: Parser Expr
add = term `chainl1` skipW1 addop

addop :: Parser (Expr -> Expr -> Expr)
addop = Add <$ char '+' <|> Sub <$ char '-'


欲しいaddopの型は`addop :: Parser (Expr -> Expr -> Expr)`ですが、このままだと`addop :: ParsecT String () Identity BinOp`になってしまいます。

今まで通り以下のように書けば、コンパイルは通りますが、欲しい物と結果が異なります。
addop :: Parser (Expr -> Expr -> Expr)
addop = BinOp <$ char '+' <|> BinOp <$ char '-'


欲しい物の例→`Add (Nat 1) (Nat 2)
得られる物の例→`BinOp (Nat 1) (Nat 2)

怒られている理由はわかりますが、直し方がわからないという状態です。

また、この問題を解決するために「Haskell 型 切り出し」などでいくつかググってみたのですが、良い成果が得られませんでした。
もし今回の件のようなものに対して適当な用語などがあれば教えていただけると嬉しいです。

よろしくお願いします。


変更前のコードの全体はいかにあります
https://github.com/mrsekut/hcc/blob/master/src/Parser.hs
この型の切り出し方で、記述する関数の数が減ったりするわけではないので、このように切り出す事自体が微妙なのかなとも思い始めました。
単純にExprの定義が多少見やすくなるかなというのと、こういう切り出し方をしている例をよく見るなというのがモチベーションですが、それがそもそも正しいのかもわかりません
まず、切り出したあとの Expr の定義間違ってない?
Expr = B BinOp Expr Expr | Nat Int じゃないとじゃない?
ただの typo ならいいんだけど
typoのつもりではありませんでした
なるほど!、ただ切り出してエイリアスのように使うものではなく、ネストが一階層深くなるのですね
そうすることでパターンマッチなどもできるのですね.
型コンストラクタや値コンストラクタなどに対する理解が甘いのかもしれません。
ご教示頂いたコードなら動かすことができました。
ありがとうございます!
tagで切り分けている、というのは if (R1 & 3 != 0) goto ccA; の行のことですよね?
はい、 if (R1 & 3 != 0) goto ccA; が1つめの切り分けです。
ここは、 x が「評価済みか否か」を切り分けています。
(未評価の場合のみ、 x を評価(xのコードへjump)します。)

続いて、 if (_ccu::I32 >= 2) goto ccv; が2つめの切り分けです。
ここは、コンストラクタの値を切り分けています。(caseの各節への分岐に相当します。)
tagの部分が「1」なら Nothing で、「2」なら Just を表します。
ここでは、 >= 2 によって、 Just かを切り分けています。
つまり、pointer の tag の部分をみると、「評価済みか否か」に加えて
「そのコンストラクタの値が何か」までをも判別できます。

つまり、 x の実体にメモリアクセスすることなく、 x が評価済みかと、
x の値が何かがわかるのが、pointer taggingの良いところです。
見てみます!ありがとうございます
@linguini has joined the channel
ある式がWHNFまで評価されたときに占めるメモリー消費量の比較を、criterion http://hackage.haskell.org/package/criterion
gauge http://hackage.haskell.org/package/gauge
のような要領で行えたら便利かな、と思うのですが、
(1) そういう目的のパッケージはあるでしょうか?あるいは、素直にGHCのプロファイリング機能を使った方が良いのでしょうか?
(2) 仮にそうした処理を自分で書くとしたら、
System.Mem http://hackage.haskell.org/package/base-4.12.0.0/docs/System-Mem.html
setAllocationCountergetAllocationCounter を使うのが正解なんでしょうか。
というのも、今回の私のユースケースにおいては、基本的に同じサイズのデータを何度も割り当てる式を比較するため、簡易的な比較としてはアリなんじゃないかと思いまして。
Heap allocation なら weigh http://hackage.haskell.org/package/weigh というのがありますね。ただ strict のあれのやつなら測るべきはスタックのサイズなので、それはちょっと分からないですね。 stack leak は rts option でスタックサイズを小さくしてやるとお手軽に確認できます
criterionでも—regress=allocated:itersみたいなオプションでできるはずです
http://www.serpentine.com/criterion/tutorial.html allocatedで検索すると書いてあります
ありがとうございます!
おっしゃる通りStrict拡張の件 https://github.com/haskell-jp/blog/issues/167 なので、RTSオプションでやる方向で検討します。
プログラミング言語を作ってそれをパースするためにAlex+Happyを使ってるのですが、Alexのwrapperを使うと例外を String でしか返してくれない(きちんとしたデータ型で返ってきてほしい)のでどうしたものかなと思ってます。解決策としてLow-levelなAPIを使ってrunAlexを自前で書くのと他のパーサコンビネータ使ってしまうのとがあると思うんですが、どっちのほうが辛くなさそうでしょうか
alex使ったことないのでよくわかりませんが、パーサコンビネータ(megaparsecとか)は別に辛くないと思いますよ(これは罠で、今絶賛megaparsecで消耗中)
ところで言語処理系を作っているのならプログラミング言語処理系slackなんかはどうです?
http://prog-lang-sys-ja.slack.com/
ありがとうございます。今回の質問とは関係ありませんが興味あるので覗いてみます
AlexもHappyも全然使ったことないので逆に気になるんですが、なんでAlex+Happyでやろうとしてるんですか?