uDiary

◆ 自作 Wiki へ移行

また Wiki エンジンを自作してしまった。

こんどのやつは、常用しようと思っていて、にっきも、それ以外も、
全部そっちで書くことにする。

とりあえず、4 月の日記はこちら

◆ さくらのサーバに Graphviz をいれた。

まず、make install でこけた。↓を参考に回避。
http://scissorhands.jpn.org/2008/04/visitorsgraphviz.html

pangocairo を入れるのは大変そう(根性はない)で、デフォルトのレンダラだとあんまり品質よくない。

http://scissorhands.jpn.org/2008/04/visitorsgraphviz.html

妥協策として、svg を介して、dpi 高めでビットマップを吐くというのでどうかな。

$ ~/bin/dot -T svg -o sample.svg sample.dot
$ convert -resample 300 -units PixelsPerInch sample.svg sample.pdf

いまいちだけど。

◆ 可換図式

Graphviz では数式書けないし、さくらには Graphviz ちゃんとしたの用意するのしんどげだったので、こっちの方がメインになるかも。

  platex web00351
  dvipdfmx web00351
  convert -trim web00351.pdf web00351.png

jsarticle にして文字大きめ、convert -trim くらいがミソかな。

http://uhideyuki.sakura.ne.jp/files2015/web00351.png

参考：
http://www.biwako.shiga-u.ac.jp/sensei/kumazawa/tex/web0035.html

◆ 可換図式２

http://www.jmilne.org/not/CDGuide.html

amscd は斜めの線が引けないとか。xymatrix がいいのかも。

platex xy.txt 
dvipdfmx xy
convert -trim xy.pdf xy.png

http://uhideyuki.sakura.ne.jp/files2015/xy.png

ふつうに数式環境で書けばよい。

MathJax ではなく LaTeX にまかせる数式環境というのをプラグインにすればいいだけかも（studs はなし）

参考： http://www.jmilne.org/not/Mxymatrix.pdf

usepackage に追加するものは、conf に書けた方がよい。

◆ 本よみ進捗

「情報学における論理」を主に読み進めている。１章もうすぐ終わって、次は２章の述語論理。どうして学生のころ、ちゃんと勉強しておかなかったかなぁという感じだが。

「プログラム意味論」は、チャーチ・ロッサー定理の証明になっとくがいかなくて、いまは脱線して "The Lambda Calculus" のその部分を読んでる。

圏論の教科書は、最後になるかなぁ。

◆ [Euler] 昨日の進捗

気がつくと、細かい時間や、仕事以外でPCに向かえる時間をすべて Project Euler に持っていかれている感じだったので、平均 1 問/日 に制限することにした。

◆ [Euler] 今日の進捗

昨日、おとといは、腰痛で寝込んでいたので、１問/日ペース守るなら３問かなといったところ。

ぱっと見とけそうなのが４つあったので、とりあえず。

あと、#19 も解いた。これは、ずいぶんいい加減にやってしまった感。

その後、#50, #48 も。うむむ。

◆ [Euler] Project Euler はじめてみた

Haskell で。毎日少しでもコード書くための題材としていいかなと思って始めたのですが、なんか、最初の方の問題はとっとと済ませてしまいたくなって、当初思ってたより時間をつかってしまっているかもしれない。

はじめ、１から順番にやってたんだけど、９までやったところで、順番にやるのに飽きてしまい。先の方のやつを見てたら、とりあえず #40 簡単そうだったのでやって、間を埋めてる。

書いたコードは一応 GitHub に置いてたりするけど、まぁ、ひとのコード読む気にはならないよなぁ。（解く前にはもちろんひとのコードなんてみないし、解いてしまったらしまったで、読む気なくなる感じ）

https://github.com/unnohideyuki/Euler

◆ [Haskell][Hand] サンプル入力

とりあえず これ が処理できるようなコンパイラを書きたいなと思ってたのが 2012 年 10 月だったらしいので、２年以上たってる！

ようやく、これを構文解析できるところまではいった。

$ sample/parser_sample <  testcases/tqd.hs 
Right (Module {modid = Nothing, exports = Nothing, body = ([],[ValDecl (FunAppExp (VarExp (Name {name_base = "qsort", name_qual = "", name_pos = (2,1)})) (VarExp (Name {name_base = "[]", name_qual = "", name_pos = (2,7)}))) (UnguardedRhs (VarExp (Name {name_base = "[]", name_qual = "", name_pos = (2,16)})) []),ValDecl (FunAppExp (VarExp (Name {name_base = "qsort", name_qual = "", name_pos = (3,1)})) (ParExp (InfixExp (VarExp (Name {name_base = "x", name_qual = "", name_pos = (3,8)})) (Name {name_base = ":", name_qual = "", name_pos = (3,9)}) (VarExp (Name {name_base = "xs", name_qual = "", name_pos = (3,10)}))))) (UnguardedRhs (InfixExp (InfixExp (FunAppExp (VarExp (Name {name_base = "qsort", name_qual = "", name_pos = (3,16)})) (VarExp (Name {name_base = "smaller", name_qual = "", name_pos = (3,22)}))) (Name {name_base = "++", name_qual = "", name_pos = (3,30)}) (ListExp [VarExp (Name {name_base = "x", name_qual = "", name_pos = (3,34)})])) (Name {name_base = "++", name_qual = "", name_pos = (3,37)}) (FunAppExp (VarExp (Name {name_base = "qsort", name_qual = "", name_pos = (3,40)})) (VarExp (Name {name_base = "larger", name_qual = "", name_pos = (3,46)})))) [ValDecl (VarExp (Name {name_base = "smaller", name_qual = "", name_pos = (5,18)})) (UnguardedRhs (ListCompExp (VarExp (Name {name_base = "a", name_qual = "", name_pos = (5,29)})) [BindStmt (VarExp (Name {name_base = "a", name_qual = "", name_pos = (5,33)})) (VarExp (Name {name_base = "xs", name_qual = "", name_pos = (5,38)})),ExpStmt (InfixExp (VarExp (Name {name_base = "a", name_qual = "", name_pos = (5,42)})) (Name {name_base = "<=", name_qual = "", name_pos = (5,44)}) (VarExp (Name {name_base = "x", name_qual = "", name_pos = (5,47)})))]) []),ValDecl (VarExp (Name {name_base = "larger", name_qual = "", name_pos = (6,18)})) (UnguardedRhs (ListCompExp (VarExp (Name {name_base = "b", name_qual = "", name_pos = (6,29)})) [BindStmt (VarExp (Name {name_base = "b", name_qual = "", name_pos = (6,33)})) (VarExp (Name {name_base = "xs", name_qual = "", name_pos = (6,38)})),ExpStmt (InfixExp (VarExp (Name {name_base = "b", name_qual = "", name_pos = (6,42)})) (Name {name_base = ">", name_qual = "", name_pos = (6,44)}) (VarExp (Name {name_base = "x", name_qual = "", name_pos = (6,46)})))]) [])]),TypeSigDecl [Name {name_base = "main", name_qual = "", name_pos = (8,1)}] (Nothing,AppTy (Tycon (Name {name_base = "IO", name_qual = "", name_pos = (8,9)})) (Tycon (Name {name_base = "()", name_qual = "", name_pos = (8,12)}))),ValDecl (VarExp (Name {name_base = "main", name_qual = "", name_pos = (9,1)})) (UnguardedRhs (DoExp [LetStmt [ValDecl (VarExp (Name {name_base = "helo", name_qual = "", name_pos = (10,10)})) (UnguardedRhs (LitExp (LitString "Hello, World!" (10,17))) [])],ExpStmt (FunAppExp (VarExp (Name {name_base = "putStrLn", name_qual = "", name_pos = (11,6)})) (VarExp (Name {name_base = "helo", name_qual = "", name_pos = (11,15)}))),ExpStmt (InfixExp (InfixExp (VarExp (Name {name_base = "putStrLn", name_qual = "", name_pos = (12,6)})) (Name {name_base = "", name_qual = ".", name_pos = (12,14)}) (VarExp (Name {name_base = "show", name_qual = "", name_pos = (12,15)}))) (Name {name_base = "$", name_qual = "", name_pos = (12,20)}) (FunAppExp (VarExp (Name {name_base = "qsort", name_qual = "", name_pos = (12,22)})) (ListExp [LitExp (LitInteger 3 (12,29)),LitExp (LitInteger 1 (12,32)),LitExp (LitInteger 4 (12,35)),LitExp (LitInteger 1 (12,38)),LitExp (LitInteger 5 (12,41)),LitExp (LitInteger 9 (12,44)),LitExp (LitInteger 2 (12,47)),LitExp (LitInteger 6 (12,50)),LitExp (LitInteger 5 (12,53))]))),ExpStmt (InfixExp (InfixExp (VarExp (Name {name_base = "putStrLn", name_qual = "", name_pos = (13,6)})) (Name {name_base = "$", name_qual = "", name_pos = (13,15)}) (VarExp (Name {name_base = "show", name_qual = "", name_pos = (13,17)}))) (Name {name_base = "$", name_qual = "", name_pos = (13,22)}) (FunAppExp (VarExp (Name {name_base = "qsort", name_qual = "", name_pos = (13,24)})) (VarExp (Name {name_base = "helo", name_qual = "", name_pos = (13,30)}))))]) [])])})

Typing Haskell in Haskell をみながら書いた型推論器もいちおうもうあるので、構文木を加工して型推論にかけられるように加工する部分（Desugar 的な）を書いてやればよいはず。

ちなみに、今日これを Parse しようとして、layout まわりのバグをみつけた。do の直後の let がうまく処理されていなかったという。

この例には明に型付けされた束縛と、明に型付けされていない束縛が１つづつあって、defaulting も行われるので、型推論の最初の動作確認にはちょうどよさそう。依存解析はまだ省ける。

$ runhaskell -Wall tqd.hs

tqd.hs:2:1: Warning:
    Top-level binding with no type signature:
      qsort :: forall a. Ord a => [a] -> [a]

tqd.hs:12:29: Warning:
    Defaulting the following constraint(s) to type `Integer'
      (Num a0) arising from the literal `3' at tqd.hs:12:29
      (Ord a0) arising from a use of `qsort' at tqd.hs:12:22-26
      (Show a0) arising from a use of `show' at tqd.hs:12:15-18
    In the expression: 3
    In the first argument of `qsort', namely `[3, 1, 4, 1, ....]'
    In the second argument of `($)', namely `qsort [3, 1, 4, 1, ....]'
Hello, World!
[1,1,2,3,4,5,5,6,9]
" !,HWdellloor"

◆ [Re:View] 数式向け改造

@<m>{} のなかで {, } を気軽に書きたかったので改造。互換性上、プルリクは無理そうなのがわかったけど、自分はこれが使いたいので勝手に使いつづけよう。

現状の改造版では、次のように書ける。

@<m>{\sigma_{2} = \\{ 5/x \\} \cup \sigma_{1}}

• {, } の対応がカウントされた結果、一番外側の {, } の中がインラインコマンドオプションとして解釈される
• \{, \} はカウントされないので、対応とれてない場合に使う。エスケープされて {, } になる。
• なので、\{ が書きたいときには \\{ と書く必要がある。

オプション部分の解析を自前にしたので、一番外側の括弧を選べるようにしてもいいかなとも思ったけど、どっちみち互換性むちゃくちゃなので、ま、凝らなくていいような気がした。

互換性を維持するために、新しいインラインコマンド記法を追加して、その場合には新規の文法が有効になるとかにしないといけないんだな、きっと。

ちなみに、既存の仕様に適応しようかとはおもったのだけど、$ \sigma_{2} = \{ 5/x \} \cup \sigma_{1} $ を得るためにどう書けばいいのか、わかんなかった。

◆ [Haskell][Hand] Parser.y つづき

shift/reduce conflicts:  128 → 72
reduce/reduce conflicts: 151 → 57

ずいぶん減らしたけど、まだまだあるなぁ。

◆ [Haskell][Hand] Parser.y

自分でてきとうに書いた文法を LALR(1) に書き直すのは大変っぽかったので、
自分で一度かいたら読めるようになった GHC の Parser.y を有難く参考にさせていただくことにした。

おかげさまで、↓このとおり。ありがたい！

$ happy -i src/Parser.y
shift/reduce conflicts:  12

どうしてこう書くとよいのか、こう書かねばならないのかは、おいおい理解したい。

んでもって、このままではレイアウト規則の最後の１ピースがはまっていないので、構文エラーになる。

$ src/Parser < testcases/test1.hs 
Left "parseError: TVCCurly (AlexPn 588 17 1)"

でもって、エラートークンがきたらコンテキストを pop するようにしてやると、

-- Layout ---------------------------------------------------------------------
close: vccurly                                  {}
     | error                                    {% popCtx }

…

$ src/Parser < testcases/test1.hs 
Right ()

よしよし。スバラシイ。

この調子で、今週中に抽象構文木をつくるところまではいってしまおう。

ふふふ。次はいよいよ型推論（または型再構築）であーる。

◆ [Haskell][Hand] Parser.y デバッグ

昨日、Haskell 2010 report みながら、えいっと Parser.y を書いたんだけど、
ずいぶん conflict を出してしまった。

unused rules: 5
shift/reduce conflicts:  144
reduce/reduce conflicts: 212

ひとつひとつ、文法の曖昧なのをなくしていこう。
ひとつの問題で沢山の衝突が引き起される傾向があるようなので、この数ほど修正箇所はないだろう。

1. 空の規則じゃなくて error トークンをつかう

レイアウト規則では、そうしないと構文エラーになる箇所には仮想閉じブレースが補われることに
なっている。

そこで、仮想ブレースが閉じていないのを許容する文法にすればいいのかなと思ったんだけど、
こういうのはいかにも衝突の原因になる。

ccurly_opt: vccurly                            {}
  |          {- empty -}                        { {- pop ctx -} }

GHC のパーサーのソースをみると、error トークンが使われていて、Happy のマニュアルにも
そういう利用方法が書かれている。

close : '}'                  { () }
      | error        { () }

ついでに、非終端記号の名前も真似して close にしてみよう。

unused rules: 5
shift/reduce conflicts:  96
reduce/reduce conflicts: 176

shift/reduce が 48 個減、reduce/reduce が 36 個へった。

2. 単純間違い

lpat: gcon seq_apat

は

lpat: gcon seq1_apat

の間違いだった。このせいで apat: gcon と衝突。

unused rules: 5
shift/reduce conflicts:  128 (+32)
reduce/reduce conflicts: 127 (-49)

3. 空規則の除去

やっぱ空の規則をつくりすぎるのよくないもう一つの例。

topdecl: 'class' sctx_opt tycls tyvar 'where' cdecls

ctx_opt: context '=>'
  |      {- empty -}

こんななのだが、context の最初にも tycls と同じ文字列が来てもいいので曖昧。
GHC のソースをみると、A -> (context '=>' |) のような非終端記号をつくるので
はなく、

tycl_hdr -> context '=>' tycls | tycls

のようにしてあった。こうすることで、問題となる還元規則がなくなり、

パーサは tycls が context の一部なのかそうでないのか判明するまで複数のポインタを
持てるようになる。（「lex&yacc プログラミング」p.301)

ただ、このあたりは、上のように文法を書き直すだけじゃなくて、もうちょっと整理しないとだめっぽい。

qconid, qtycls などもいっぱい衝突している。(軒並 qconid に還元しようとしたり)

まいったな、まだまだだな。