emacsでパーサーコンビネータみたいなものを作成してみた

Emacs

年末から年始にかけて、忙しくなりそうでちょっとガクブルです。でも3年くらい前は今の5倍くらい残業してたのかと思うと、人間以外となんとかなるもんなんですね。望んでやりたかーないですが。

閑話休題。

Emacsでは、文字列の検索は基本的に正規表現を利用して行っていますが、これをガリガリと書いたあとで見返すと、？？？的な感じによくなります。これはどんな言語の正規表現でも一緒だと思いますし、そう考える方々は、Perl5互換の正規表現を利用できるようにしたり、色々な解決手段が模索されているようです。

ちょっと書捨てする場合とか、そのときだけ検索したいものとかについては、その場で書けばそれでいいと思いますが、Emacs Lispでちゃんとしたスクリプトを書こうとすると、これをちゃんと管理していく必要があります。
ぶっちゃけこれがめんどくさいです。また、規模が大きくなればなるほど、これの管理がどんどん厳しくなっていきます(多分)

Haskell/OCamlとかの関数型言語では、これの解決手段として、パーサーコンビネータが選ばれているようです。Parsecが代表格でしょうか。

じゃあelispでもやってみよう!ということで、あまり知らないのですが作り始めてみました。

現状

で、とりあえずlexerの作成とcombinatorの作成くらいはできるようになった気がする、というところです。

https://github.com/derui/eparse

開発はgithubでやっています。よほどじゃないかぎり、最近はgithubにリポジトリを作ってしまった方が、MacBookでもデスクトップでも作業できるのでイイ!ですね。
ちなみにこのプロジェクトではOMakeを使ってテストとか実行できるようにしています。cloneしてから、

$ omake test

とすれば、ert-expectationsを利用したテストケースが実行されます。それと、24.3から追加された(はず)cl-libs.elというライブラリを利用しているので、24.3以外じゃ動作しません。あしからず。

絶賛開発中というか迷走中というか、という感じで、インターフェースすらよく固まっていません。とりあえず今はこんな感じに書けます。

(funcall (eplib:lex (let (ch)
              (setq ch (<- 'char ?a)))
              (setq ch (<- 'char ?s)))
              (success ch))
     (eplib:make-source "as")))

eplib:プレフィックスは基本的にライブラリなので、実際には利用されない感じ？になると思っています。'charというシンボルは、eplib:define-lexerというマクロで定義したlexerを呼んでいる感じになります。テストの中にわかりづらいですが色々と書いてあります。

作ってみて

elispで、このようなものを初めて作ってみました。macroとかをこれだけちゃんと書いたのも初めてです。lispのmacroは強力だ、とよく聞きますが、今回それを味わったような感じです。

しかし、elisp特有の問題というかなんというか、作っている間に色々と？？？となる部分も散見されました。

  • lexical bindingが上手くいかない
    • どうも「setqとかされた」変数だけがlexical bindingされるらしいです
  • 一時関数がものすごく使いづらい
    • cl-fletを使えばましになりますが。
  • macroがよくわからん
    • 特にシンボルが絡むともう。。。

いくつかについては、経験を積めば大分わかるようになるとも思いますが。ただlexical-bindingだけがどうにもよくわからないっす。

TODO

今の課題としては、半端ないくらいに遅いです。どれくらい遅いかというと、

  • aという文字を1000文字連結
  • できるだけ長い文字列を取得する(正規表現だと a* )

という条件で、benchmarkを行うと、だいたい2000倍くらいの差があります。2000倍て・・・。ちなみに、このlexerは前から順に評価していくので、10000文字とかあっても、最初の何文字かだけしか文字が無いのであれば、正規表現よりも速くなったりします。

これをなんとかしたいんですが、defsubstとかでインラインにしたくても、defsubstを使ってみるとターミナルの文字が化けてしまったりして、テストが動作しません・・・。他にも高速化の手法はあると思うんですが、内部で結構いろいろなことをしているので、その辺を整理する必要もありそうです。

なんにせよ、作ってみないとパーサーコンビネータとかもよくわかりませんね。それっぽく動作するようにはしてみましたが、まだまだ先は長いです。