3/18にEmacs勉強会やります
僕は「Emacs Lispによるスクリプト処理」というお題で30分ほど喋らさせていただきます。Emacs勉強会と銘打ってますが、僕の話す内容はむしろ非Emacsユーザー向けです。人間というのは多種多様なのです。肌に合わないならわざわざEmacsなんて使う必要はありません。ただ、強力なテキスト処理言語であるEmacs Lispを同時に見捨ててしまうのは、非常にもったいないのです。今回はその点を説明・啓蒙して「Emacs Lispユーザー」を増やすのが目的です。というわけで、Emacsユーザーはもちろんのことながら、非Emacsユーザーも大歓迎なので、ぜひご参加ください。
2009年下期未踏ユースで採択されました
本家HPで詳細情報が掲載されるまでとっておくつもりでしたが、結構待たされるようなので今さらですが公表してしまいます。知っている人は知っていると思いますが、2009年下期未踏ユースで採択されました。
http://www.ipa.go.jp/jinzai/mitou/2009/2009_2/youth/k_koubokekka.html
テーマ名は「Emacsにおける高精度コード補完機能の開発」です。簡単に概要を説明すると、EclipseやVisual Studioなどが提供している高精度なコード補完機能をEmacsでも実現してしまおうというプロジェクトです。対応するプログラム言語はC++, Java, Ruby, Pythonなどとしていますが、内容の変更は十分にありえますので悪しからず。
Emacsでの補完インターフェースはもちろんauto-complete.elで実現します。現状のauto-complete.elでは補完の選択の手間やポップアップの表示がうるさいので、その辺りを改善して、より自然に呼吸するかのようにコード補完を行えるようにする予定です。例えば、auto-complete.elの開発版では統計的手法とヒューリスティックに基づいて、次に補完されるであろう候補を上位にもってきて、可能な限りポップアップメニューを表示しないということができます。これらが完成して、うまく組合されば、これまで以上の開発効率の向上が見込めます。
開発終了は公式には7月となっていますが、当然のことながら、僕はもっと長いスパンでソフトウェアの開発を考えています。できるだけ早い時期に成果を出すようにしますが、7月中にでなかったからといってサボってんじゃないぞとか言わないで下さい。かなりがんばってますので（がんばってる様子はTwitterで確認できます @m2ym）。
以上、報告まで。
auto-complete.elに補完候補を賢くソートしてくれる機能、comphistを実装
最近、auto-complete.elの拡張ばかりでパフォーマンスや安定性を度外視してる感がありますが、今回も凝りずにauto-complete.elの拡張の話をします。お許しを。
auto-complete.elの開発を始めて以来、補完候補の選択の手間を減らせないか、という意見を定期的に頂いています。その時に提案された方法には様々ありましたが、ここで説明するのは面倒くさいので、その基本となるアイデアを要約しますと、補完候補の文字列や補完中の文字列の長さからヒューリスティックを用いて、次に補完されそうな補完候補を先頭にもってくるというものでした。ヒューリスティックを用いるのは全く否定しないのですが、そのヒューリスティック自体の有効性に疑問がありました。そういうわけで、かなり長い間その手の実装を回避していたのですが、未踏でやると公言した手前、やらないわけにはいかないので、実験的に実装してみました。
今回用いた手法はある種のヒューリスティックと言えますが、ある程度統計的手法にも基づいています。詳しいアルゴリズムは説明しませんが*1、補完回数が多いものが上にくる、というのではあまりに簡単すぎなので少し補足します。このアルゴリズムは補完回数をそのまま用いるのではなく、どの場所で補完が実行されたかという統計も同時に採取し、それを利用して補完回数に重み付けを行うことにより、ユーザーの入力習性をうまく学習・利用するようになっています。例えばfiと打ったところでfind-fileを補完することを何回か繰り返せば、以後はfiと打った時点でfind-fileが補完候補の先頭になります。ただ、find-と打ったときにもfind-fileが先頭に来るかと言えばそういう訳でもなく、この場合ではfiの時より距離として3離れているわけですから、その分重み付けが軽くなります。結果的にfind-の後にfind-libraryを補完するようなユーザーの入力習性をうまく捕むことができるのです。
とまあ、このあたりは完全な仮定に基づいた理論でしかないので、実際の有効性を調べるには皆さんのお力を拝借しなければなりません。もし、この機能の有効性を調べてくれる方がいらっしゃいましたら、githubのHEADからソースコードをpullしてインストールしてください。色々な拡張・習性によりパフォーマンスや安定性に問題があると思いますが、実作業環境で利用していただけるほうが、意味のあるデータを採取できるはずです。フィードバックはこのブログのコメントかTwitter(@m2ym)までよろしくおねがいします。
なお、この機能はまだ実験中なのでac-use-comphistをtにしないと利用できません。その際、一度M-x auto-complete-modeでauto-complete-modeをoffにしてから再度onにしてご利用ください。
auto-complete.elが曖昧マッチに対応
auto-complete.elを曖昧マッチに対応させるため、今回からfuzzy.elという拡張が同封されるようになりました。この拡張は必須ではありませんが、曖昧マッチを使う場合は必要になります。
曖昧マッチで補完を行うにはac-fuzzy-completeコマンドを実行します。このときカーソルが赤色になりますが、これが曖昧マッチで補完を行っていることを表わしています。
曖昧マッチによる補完はauto-completeコマンドからでも行うことができます。このとき曖昧マッチを使うかどうかのフラグであるac-use-fuzzy変数がtである必要があります。デフォルトはtなので、曖昧マッチを使いたくない人のみ適宜nilにしてください。auto-completeコマンドが実行されると、従来のマッチで補完候補の生成を試みますが、このときに一つも補完候補を生成できない場合のみマッチの方法を曖昧マッチに変更して補完候補の生成を仕直します。ac-fuzzy-completeコマンドと同様、カーソルが赤色になります。
曖昧マッチによる補完では文字入力によるパターンの更新が無効になります。パフォーマンスに問題があるからです。
以下にスクリーンショットを示します。このスクリーンショットが示すストーリーは、defaultを間違ってdefualtと入力し、補完が一つも表示されないからauto-completeコマンドで曖昧マッチによる補完を行って、無事目的の補完を行うことができた、というところでしょうか。
補足としてfuzzy.elの簡単な使いかたを説明しておきます。
fuzzy.elは曖昧マッチ用の関数と曖昧isearchの機能とで構成されています。主に使う関数は以下のようになります。
fuzzy-match関数は二つの文字列を引数にとり、ある程度同じであればtを返します。
fuzzy-edit-distance関数は二つの文字列を引数にとり、それらの編集距離を返します。
fuzzy-search-forward関数は引数の文字列でバッファを曖昧に前向き検索を行い、マッチしたポイントを返します。
fuzzy-search-backward関数は引数の文字列でバッファを曖昧に後ろ向き検索を行い、マッチしたポイントを返します。
fuzzy.elの曖昧isearchの機能を利用すれば、標準のisearchが一定関数フェイルしたときに、自動的に曖昧にisearchを行うようになります。この機能を有効にするにはturn-on-fuzzy-isearch関数を呼びだします。この機能を無効にするにはturn-off-fuzzy-isearch関数を呼びだします。曖昧isearchはうまくキャッシュを利用しているので、かなり大きなバッファでも快適に検索することができます。
popup.elの関数名の変更に関して
先日、github上のIssue Tracking Systemにおいて、popup.elで使用しているpopup-menuという関数がEmacsに標準登載されているmouse.elの関数をシャドウしているというバグが報告されました。Emacs Lispの流儀に従えばファイル名と名前空間が一致するため、popup.elという名前の拡張が存在しないということはつまり、popup-*という関数は存在しないということを想定していたのですが、見事に期待を裏切られ、このようなみじめな結果になってしまいました。根本的には私のミスなのですが、いまいち腑に落ちないのは、mouse.elが定義している関数が、X環境でしか動作せず、しかもキーマップからのみメニューを表示できるという汎用性に欠くものであったということです。そのような特殊な関数に一般的な名前を付けることのモラルのない行為に憤りを覚えつつ*1、名前空間をviolateするのも良心が痛むので、結局のところpopup-menuという関数名をpopup-menu*という関数名に変更しました。つきましては、popup.elのpopup-menu関数を利用しているユーザーの皆さま、面倒は承知ですが、popup-menuをpopup-menu*に修正しただけるようお願いいたします。
*1:しかもオフィシャルな関数ではない
Lisp的直積集合
可変なループ構造を必要とする問題*1に関しては、再帰やスタックを使って可変なループ構造に対応するのがプログラミングの常套手段ですが、そのような手段がそもそも必要になるのは、for文を動的に増やせないという問題に絡んでいます。それじゃfor文を動的に増やせばいいのではないか、と考えるかもしれませんが、CやJavaなどのevalがない言語ではそんなことできません。
ところが我らのLispにはevalがあります。しかもデータ構造がプログラムテキストであるため、動的にプログラムテキストを生成しても不自然に見えません*2。それでは、n個の集合から直積集合を生成する関数を例にとって考えましょう。
直積集合とは{1,2}と{3,4}から生成された{(1,3), (2,4)}{(1, 3), (1, 4), (2, 3), (2, 4)}ことを言います。詳しくはWikipediaを参照してください。
通常、直積集合を求める関数は二つの集合を取りますが、ここでは少し拡張してn個の集合を取れるようにします。礼儀正しく実装するなら、次のように、まず二つの集合の直積集合を求める関数を定義して、次にその関数を利用してn個の集合の直積集合を求める関数を定義することになるでしょう。
defun flatten (a) (if (nlistp a) (list a) (apply 'append (mapcar 'flatten a)))) ;; 二つの集合の直積集合を求める関数 (defun product (s1 s2) (let (result) (dolist (a s1) (dolist (b s2) (push (flatten (list a b)) result))) (nreverse result))) ;; n個の集合の直積集合を求める関数 (defun product-list (&rest list) (if (null list) list (let ((a (car list))) (dolist (b (cdr list)) (setq a (product a b))) a)))
実装がシンプルなのは良いですが、効率が少し悪そうに思えます。
それではevalを使った方法で実装してみましょう。今回のエッセンスは上記のproduct関数の二つの(dolist ...)に注目して、このループ構造を動的に拡張することです。
まず内側の(dolist ...)あるいは(push ... result)を生成するproduct-form関数を定義します。
(defun product-form (n len syms) (if (eq n len) `(push (list ,@(reverse syms)) result) (let ((sym (intern (format "x%s" n)))) `(dolist (,sym (nth ,n list)) ,(product-form (1+ n) len (cons sym syms))))))
この関数は三つの引数を取ります。第一引数は処理中のリストの要素番号、第二引数は集合のリストの長さ、第三引数は現在保持しているシンボルのリストです。始めのif文で、nがリストの長さと同じなら(push ... result)を生成し、そうでなかったら(dolist ...)で一段深いproduct-formを囲むようにしています。(dolist ...)でバインドされるシンボルは適宜x0, x1, x2のような名前を与えられてsyms変数に追加されていきます。
実際の実行結果は以下のようになります。
(product-form 0 3 nil) ;; (dolist (x0 (nth 0 list)) (dolist (x1 (nth 1 list)) (dolist (x2 (nth 2 list)) (push (list x0 x1 x2) result))))
これは長さが3のリストのループ構造を表わしています。あとは、これを利用してn個の集合の直積集合を求める関数を定義するだけです。
(defun product-list (&rest list) (let (result) (eval (product-form 0 (length list) nil)) (nreverse result)))
実行結果を示します。
(product-list '(1 2 3) '(4 5 6) '(7 8 9)) ;; ((1 4 7) (1 4 8) (1 4 9) (1 5 7) (1 5 8) (1 5 9) (1 6 7) (1 6 8) (1 6 9) (2 4 7) (2 4 8) (2 4 9) (2 5 7) (2 5 8) (2 5 9) (2 6 7) (2 6 8) (2 6 9) (3 4 7) (3 4 8) (3 4 9) (3 5 7) (3 5 8) (3 5 9) (3 6 7) (3 6 8) (3 6 9))
プログラムの長さとしては前者・後者とも差がないように感じます。実行効率としては、ちゃんと実装すれば後者のほうが速くなるでしょう。もちろんJITなどが効く言語では前者のほうが良いでしょうが。
結論としては、プログラムもデータ構造として扱えるLispでは、このエントリで紹介したような手法が意外に有効だと言えます。読み易さの点では課題が多いかもしれませんが、複雑なアルゴリズムを書くよりこちらの手法のほうがわかりやすくなるケースは少なからずあると思います。
