accomplish nothing

Common Lispでの実装がPackrat ParsingとPackrat Parsing: 遅延版にあった。この方の書く記事は実践的でいつも面白い。

確かに、構造体を利用した遅延版は速いかもしれないんだけど、富豪的なメモリの使い方。パーザの数をn、文字列の長さをlとすると、クロージャをn * l個必ず作らなければならない。遅延評価のHaskellとかなら問題ないのかもしれないけど、Lispだと結構辛い。構造体を作る処理自体も重そう。それと、パーザを定義するごとに構造体のフィールドを増やさないといけないのは、色々と面倒な気がする。マクロで、パーザの定義ごとに構造体を再定義する方法はあるかもしれないけど、ちょっと泥臭い。

自分で使う分には、ハッシュテーブルで十分かとも思うけど、実際にどれだけ高速化するか測ってみないとなんとも言えない。