はてなブックマーク

言語処理系を書きたくなって、とりあえずはlazykを実装し、gcも書いてみたかったので書きました。 するとふわっと書いた80行ほどのgcなのに、あるケースでのメモリ消費量を5GBから3MBへ、実に1/1000になりました。 すごい。楽しい。 garbage collectionといっても、dfsして到達できないものの使用中フラグを倒すだけなので実際やるだけ。 世代別だとかincrementalだとかに手をだすと楽しくなりそう。 次はcでlisp処理系を書きたいなと思っている。 計測 lazyk製のunlambda interpreterの上でunlambdaのquineを動かして計測した。 他の場合は特に調べていない雑な計測であることに注意。 gc入れると速度も改善してるのは面白い。 gc無し 5.2GB 1 2 $ g++ -std=c++11 -O2 -DNOGC a.cpp && d

Data.Foldable Data.Traversable lensのFold,Traversalの、前提を(私が)理解するために書かれた記事 Foldable 1 2 3 4 class Foldable t where foldMap :: Monoid m => (a -> m) -> t a -> m foldr :: (a -> b -> b) -> b -> t a -> b -- Minimal complete definition: foldMap or foldr. Class of data structures that can be folded to a summary value. 畳み込んで一点に潰す演算の可能な型クラス。Prelude.foldrの一般化。満たすべき制約はない。 具体例をコードで示す。 1 2 3 instance Foldable []

状態は難しい 変数 入出力 難しいなら無くしてしまえばよい 状態を排除 参照透明性 言語処理系の外側の状態はどうしようもないので 一意型 モナド 状態は難しい 状態は難しい。 例えば変数。変数の値が自由に変更可能なら、ある変数を使用する際には、その変数を変更可能な全ての場所を考慮しなければならない。 global変数のようなスコープの広すぎる変数で混乱した、確保した領域を二重に開放するコードを書いた、といった経験は皆あるはずである。 難しいなら無くしてしまえばよい 状態の問題を解決したい。その手段の1つとして、状態を無くしてしまえばよい、という極端なものがある。 変数を無くしてしまう。外部の状態の利用、つまりファイルの操作だとかは当然禁止する。 変数を無くしてもチューリング完全の意味で計算できる範囲に影響はない1ので問題はない。 そうすると、どの関数も、引数が同じならいつ計算しても値が同じ