Hexyll.Core.Dependencies をリファクタリングする about hexirp-hakyll HOT 54 CLOSED

中心と思われる関数はこれ。

これを見ると DependencyM は、全てのリソース（の識別子）を環境に、依存関係のデータを状態に、ログを書出に持つ。

from hexirp-hakyll.

DependencyFacts は依存関係の要素を記述する。それぞれのリソース（の識別子）に複数の依存関係があり、それは Map で表される。

from hexirp-hakyll.

これを見ると PatternData に "or" が不要な理由が分かる。

あるリソースの識別子 i があったとき、それに対応する依存関係が a と b とあると考える。それは a .||. b とも記述できる。しかし、このマップの上に i に対応する値として [a, b] を置くことでも表せる。

from hexirp-hakyll.

ood の意味が分からんけど、それは変更が必要なリソース（の識別子）のセットらしい。

根拠は、

ここが、前のリソースになかったら markOod で、

ここが、依存しているリソースが新しくなっていたら markOod で、

これはよく分からない。

from hexirp-hakyll.

なぜ、依存関係の計算が必要なのか？

キャッシュを行うためである。

なぜ、 Dependencies が必要なのか。

Runtime の中で使うからである。

なぜ、 Pattern がシリアライズできる必要があるのか。

キャッシュしたいからである。

なぜ、キャッシュしたいのか？

リソースに変更があった時、その伝播を行いたいからである。新しいリソースが加わった時、その伝播を行いたいからである。

Cabal では、依存の指定をキャッシュする必要はない。どうしてか？

Glob などを使わないからである。バージョンの範囲はあるものの、それが変化しうるのは、本体のパッケージだけで、依存しているパッケージについては既に Hackage に記録されているあるいは commit hash で指定されているなどの理由によって、変化し得ない。

from hexirp-hakyll.

#67 を参考に。

from hexirp-hakyll.

これはひどすぎる。

from hexirp-hakyll.

Cabal では依存関係をどうやって扱っているんだろう？

https://github.com/haskell/cabal/blob/6a97912efb816ee73ca495cfcd957409237b76a6/cabal-install/Distribution/Client/Dependency.hs#L734-L790

from hexirp-hakyll.

こんなかんじ。

https://github.com/haskell/cabal/search?q=Dependency+path%3Acabal-install%2F+in%3Apath

from hexirp-hakyll.

こっちのほうが本体っぽい。

https://github.com/haskell/cabal/search?q=Dependency+path%3ACabal%2F+in%3Apath

from hexirp-hakyll.

Cabal と cabal-install で別々の依存関係の解決のプログラムがあるみたい。

from hexirp-hakyll.

ここが本丸？

https://github.com/haskell/cabal/blob/8c3af1960326180ec6f3daeeec25a19fede7e6cb/Cabal/Distribution/Types/Dependency.hs

from hexirp-hakyll.

バージョンの範囲を扱うために。

• https://github.com/haskell/cabal/blob/8c3af1960326180ec6f3daeeec25a19fede7e6cb/Cabal/Distribution/Version.hs

それはこれらを参照している。

• https://github.com/haskell/cabal/blob/8c3af1960326180ec6f3daeeec25a19fede7e6cb/Cabal/Distribution/Types/Version.hs
• https://github.com/haskell/cabal/blob/8c3af1960326180ec6f3daeeec25a19fede7e6cb/Cabal/Distribution/Types/VersionInterval.hs
• https://github.com/haskell/cabal/blob/8c3af1960326180ec6f3daeeec25a19fede7e6cb/Cabal/Distribution/Types/VersionRange.hs

from hexirp-hakyll.

さらに VersionRange を辿り

• https://github.com/haskell/cabal/blob/8c3af1960326180ec6f3daeeec25a19fede7e6cb/Cabal/Distribution/Types/VersionRange/Internal.hs

ここが本丸。全てのパターンをナイーブに持っていた。否定は言語に含まれていない。

from hexirp-hakyll.

ここの Pattern もシリアライズ可能にする。その際に否定の述語は含まない。これは選言標準形とする。

from hexirp-hakyll.

否定を含むことが出来るようにすることもわりかし簡単にできる。ただ、これに深く踏み入ると SAT とかの分野に入っていく。

from hexirp-hakyll.

そもそも Pattern が Monoid でなければならない理由は？

from hexirp-hakyll.

http://bach.istc.kobe-u.ac.jp/lect/soft/org/proplogic.html

へえ。選言節の連言節を短く変換できるのが Tseitin 変換で、それは比例した大きさに変換することが出来る。ただし、二つの新しい命題変数の導入を要する。

from hexirp-hakyll.

いろいろ雑に調査した。

• https://qiita.com/hakobera/items/d7742cc0801a9c62ef72
• https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88
• https://postd.cc/version-sat/

たぶん、ここでの依存関係はパターンにより複数のリソース（の識別子）が指定されうるので、そのまま適用できないと思う。また、バージョンは存在しない（同じ名前だけど別物）ので順序による比較はいらない。

でも、なんか調査していくうちにSATソルバの分野に入り込んでいくなあと思ってたらやっぱりSATソルバが必須……

from hexirp-hakyll.

Haskell では継続によって「基本的なバックトラッキングソルバ」を簡潔に実装できることは注目すべきである。

• http://www.cse.chalmers.se/~algehed/blogpostsHTML/SAT.html
• http://andrew.gibiansky.com/blog/verification/writing-a-sat-solver/
• https://www.slideshare.net/sakai/writing-a-sat-solver-as-a-hobby-project

from hexirp-hakyll.

継続モナドによるSATソルバ―、前にみたことがあるはずなんだけど見つからない！

from hexirp-hakyll.

論文。うーん。

• https://www.ai-gakkai.or.jp/jsai2016/webprogram/2016/pdf/835.pdf

from hexirp-hakyll.

あった。これ。

• https://julesh.com/2016/09/22/abusing-the-continuation-monad/

こうだそう。

import Control.Monad.Cont
sat n = runCont $ sequence $ replicate n $ cont $ \k -> k $ k True

from hexirp-hakyll.

https://twitter.com/koteitan/status/1213271273083691008

制約にはどういう種類があるのですか？「AにはBまたはCかつDまたはEが必要」「AとBは共存できない」の２種類でしょうか

https://twitter.com/hexirp_prixeh/status/1213272789865467905

「AにはBまたはCかつDまたはEが必要」のみです

https://twitter.com/hexirp_prixeh/status/1213273489894821889

ん、「AとBは共存できない」はパッケージのバージョンにおいては複数のバージョンの同じパッケージが存在してはいけないに該当しますね。私が作ろうとしているシステムは、バージョンが存在しないので前記のみの制約です

つまりトポロジカルソートの類似物だけで済む？

from hexirp-hakyll.

ここのせいで Pattern が Monoid でなければならない。

かなり必要性が怪しいなあ。

from hexirp-hakyll.

こんな感じの構造にするか？

data PrimPattern -- 原子的なパターン
data PatternExpr -- パターンの構文
data PatternData -- パターンをCNFに変換したもの
data Pattern -- パターン (Identifier -> Bool)

from hexirp-hakyll.

なんと rulesPattern はどこにも使われていない。

from hexirp-hakyll.

rulesPattern は必要。あるルールの中で必要なリソースを識別するため。

ただし、それを Pattern で実装する必要はなくて、 [Pattern] とかでも良さそう。

from hexirp-hakyll.

それは Or を基礎としたモノイドとして Pattern を扱っているから。

from hexirp-hakyll.

これでいいのかな。

data PrimPattern -- 原子的なパターン
data PatternExpr -- パターンの構文
data PatternConj -- パターンのリストを論理積により結合されたものとして扱う
data PatternDisj -- パターンのリストを論理和により結合されたものとして扱う
data Pattern -- パターン (Identifier -> Bool)

from hexirp-hakyll.

前記の構造に従って Hexyll.Core.Identifier.Pattern を変更した。

from hexirp-hakyll.

ちょっと待て。

https://github.com/jaspervdj/hakyll/blob/e146dac323a5eb9346bc948906c222d8d94360a7/lib/Hakyll/Core/Rules/Internal.hs#L58-L74

ここで mempty = Everything なのに mappend に該当するものとして (.||.) を使っている。

from hexirp-hakyll.

#66 で Pattern と Pattern.Internal をくっつけたおかげで 5ac85b7 のような変更ができる。

from hexirp-hakyll.

おー、 DEPRECATED プラグマを使ってみたら派手に警告がでるなあ。

from hexirp-hakyll.

なぜパターンと識別子の二種類あるのか？　パターンだけで十分では？　なぜパターンでは識別子の集合も付けなければならないのか？

from hexirp-hakyll.

ood は out-of-date の略なのか！

from hexirp-hakyll.

パターンに識別子の集合が付いているのは、まあ予想内っちゃ予想内だったけど前にマッチしていたもののキャッシュ。

from hexirp-hakyll.

out-of-date である識別子（で表されるリソース）は更新しなければならない。 markOod である識別子が out-of-date であるとマークできる。

checkNew は新しく追加されたリソースを検出して out-of-date にする。

checkChangedPatterns は、依存関係がパターンで表されるそれぞれの（リソースの）識別子について、（リソースを表している）識別子の一覧にパターンマッチングを掛けて、その結果が以前のものと異なっていたら、その識別子は out-of-date であるという計算をする。

bruteForce は、ある識別子が out-of-date であったら、それに依存する識別子も out-of-date であるという計算を行う。ここでは check という内部関数があり、それを使い when でガードする再帰を行っている。計算が終わったらフラグが立ち、終了する。

……トポロジカルソートを使えば線形時間で終わる。このアルゴリズムじゃたぶん二次多項式時間である。

from hexirp-hakyll.

いや、この場合はパターンにより辺が表されるのでこうならざるを得ないのか？

from hexirp-hakyll.

それでも、以前に計算した識別子の情報を利用すればトポロジカルソートできて無駄を省けるはず。

from hexirp-hakyll.

IdentifierDependency は PatternExpr に吸収させてしまうことにするか。

from hexirp-hakyll.

IdentifierDependency かどうかで分岐するのは Hexyll.Core.Dependencies だけだし。

from hexirp-hakyll.

うーん、こんなかんじで済ませちゃおうかな？

from hexirp-hakyll.

8229765 と 555f510 が関わっている。

さらに何故か以前は幽霊型を使っていたみたい ( 89272dd ) 。

初めて追加されたのは ede51e8 で、この前にどうやっていたかはわからない。

from hexirp-hakyll.

つまり outOfDate :: IdentifierUniverse -> DependencyFacts -> IdentifierCache -> DependencyCache -> (IdentifierOutOfDate, IdentifierCache, DependencyCache, DependencyLog ってことかな？

IdentifierCache はマップのキーとして含まれているからいらないか。

from hexirp-hakyll.

Glob はエスケープを実装していない。アスタリスクを通常の文字として扱いたい場合は fromRegex を使ってエスケープしましょう。

from hexirp-hakyll.

regex-tdfa は POSIX extended regular expressions をベースにしている。

from hexirp-hakyll.

master での下ごしらえがそろそろ終わりそうなのでぼちぼち再開するか。

Hexyll.Core.Identifier.Pattern に fromIdentifier と fromList を追加した。後は fromFilePathM でも作ろうかな。いや、それを元々としてエラーを握りつぶすバージョンを fromFilePath とするか。

from hexirp-hakyll.

binary の Get 型に対して fmap id を掛けた場合の効率が気になって調べた。これは newtype へのインスタンスの実装に fmap とかを使っているのが気になったから。結果は codensity/state monad を使っているから、インライン指定などがないなどは別にしてオーダーが変わるほどのオーバーヘッドはなさそう。

from hexirp-hakyll.

この codensity/state monad を Compiler 型の再実装に応用できないだろうか……？

from hexirp-hakyll.

haddock のメッセージがいつまでも経っても出力されず CTRL+C も効かない状況に遭遇してしまった。シェル環境を強制終了するといつまでも経っても haddock のプロセスが残るので、代わりに haddock のプロセスをタスクマネージャーから殺す必要がある。これは chcp 65001 すると起こらない。

from hexirp-hakyll.

本体の書き換え終了！　とっかかりすらないように見えたけど筋力でやれば何とかなるんだなあ。

from hexirp-hakyll.

変更が波及することにより思ったより長丁場になりそうなので専用のブランチを作る。

from hexirp-hakyll.

ずっと変更が続いている。

ここ、やばい。 O ( n ^ 2 ) の再来だ。

from hexirp-hakyll.