Hello Slime developers,
For the past while, I've been using a Mac OS X program called Quicksilver, which is sort of a multi-purpose quick access tool. It features a fuzzy completion algorithm that I've quite grown to like. For example I can hit Command-Space and type "liswp<return>", and it will match and launch "LISpWorks Personal".
I decided I wanted to add something like this (only better :) to Slime, to go alongside the existing completion algorithm. It can't really be a replacement as they are good at different things. The existing one is good for incrementally typing and completing a symbol. The fuzzy one is good for typing a short version of the symbol, running the completer, and then picking the right result, which hopefully scored at or near the top.
While I've attached a patch, this is more a request for comments than a request to commit the code. As I'll discuss, the Emacs interface is incredibly lacking, mostly on account of this being my first time using elisp for anything but configuration. It's very ugly. Also, the completion core code in Swank should be cleaned up - it still looks somewhat hacky. Finally, everything needs documentation.
The elisp code has some chunks from isearch.el. Since they are both GPL, I figured this is okay. Besides, it will probably change anyway. :)
----------------------------------------------------------------------
The low level core of the algorithm are implemented in Swank, just like the old completer. The interface looks very similar:
; SLIME 2004-06-10 CL-USER> (setq *print-pretty* t) T CL-USER> (swank::completions "m-v-" "CL-USER") (("multiple-value-bind" "multiple-value-call" "multiple-value-list" "multiple-value-prog1" "multiple-value-setq" "multiple-values-limit") "multiple-value-") CL-USER> (swank::fuzzy-completions "mvb" "CL-USER") (("multiple-value-bind" 26.588236 ((0 "m") (9 "v") (15 "b"))) ("most-negative-double-float" 12.416667 ((0 "m") (11 "v") (17 "b"))) ("most-positive-double-float" 12.416667 ((0 "m") (11 "v") (17 "b"))) ("named-variable" 10.833333 ((2 "m") (6 "v") (11 "b"))) ("*compile-verbose*" 10.666667 ((3 "m") (9 "v") (12 "b"))) ("environment-variable" 10.555555 ((7 "m") (12 "v") (17 "b"))) ("remove-symbol-profiler" 3.5 ((2 "m") (4 "v") (10 "b"))))
The return value is obviously a bit more complicated. :) The fields are (completion score chunks), where "chunks" are a description of where the completion matched.
There's a convenience function in Swank that is not used by the Emacs interface to print this information in a human readable form. I used this to tune the scoring algorithm. This shows a little more clearly how the algorithm matches:
CL-USER> (swank::format-fuzzy-completions (swank::fuzzy-completions "mvb" "CL-USER")) Multiple-Value-Bind score 26.59 ((0 m) (9 v) (15 b)) Most-negatiVe-douBle-float score 12.42 ((0 m) (11 v) (17 b)) Most-positiVe-douBle-float score 12.42 ((0 m) (11 v) (17 b)) naMed-VariaBle score 10.83 ((2 m) (6 v) (11 b)) *coMpile-VerBose* score 10.67 ((3 m) (9 v) (12 b)) environMent-VariaBle score 10.56 ((7 m) (12 v) (17 b)) reMoVe-symBol-profiler score 3.50 ((2 m) (4 v) (10 b)) NIL
Here are some more examples, which might show why I think something like this can be useful. (There is an optional third argument to swank::fuzzy-completions, limit. This limits the number of results, which is important for this completer since completing, say, "a" will match many, many symbols. This isn't currently used from Emacs however.)
CL-USER> (swank::format-fuzzy-completions (swank::fuzzy-completions "stdout" "CL-USER" 5)) *STanDard-OUtpuT* score 34.83 ((1 st) (5 d) (10 ou) (15 t)) moST-negative-DOUble-floaT score 22.48 ((2 st) (14 dou) (25 t)) moST-positive-DOUble-floaT score 22.48 ((2 st) (14 dou) (25 t)) leaST-positive-DOUble-floaT score 22.45 ((3 st) (15 dou) (26 t)) leaST-negative-DOUble-floaT score 22.45 ((3 st) (15 dou) (26 t)) NIL CL-USER> (swank::format-fuzzy-completions (swank::fuzzy-completions "prp" "CL-USER" 5)) *PRint-Pretty* score 23.83 ((1 pr) (7 p)) PRint-Profile-list score 23.62 ((0 pr) (6 p)) *PRint-Pprint-dispatch* score 23.48 ((1 pr) (7 p)) *step-PRint-Pretty* score 20.59 ((6 pr) (12 p)) *trace-PRint-Pretty* score 20.56 ((7 pr) (13 p)) NIL CL-USER> (swank::format-fuzzy-completions (swank::fuzzy-completions "norm-df" "CL-USER" 5)) least-positive-NORMalized-Double-Float score 32.31 ((15 norm) ...) least-negative-NORMalized-Double-Float score 32.31 ((15 norm) ...) NIL CL-USER> (swank::format-fuzzy-completions (swank::fuzzy-completions "udc" "CL-USER" 1)) Update-instance-for-Different-Class score 26.30 ((0 u) (20 d) (30 c)) NIL CL-USER> (swank::format-fuzzy-completions (swank::fuzzy-completions "urc" "CL-USER" 1)) Update-instance-for-Redefined-Class score 26.30 ((0 u) (20 r) (30 c)) NIL
Despite being expensive (it tries all combinations of matches up to a relatively high cutoff per symbol to maximize the score) and not optimized at all, the completion speed doesn't seem bad at all on compiled Lisps on my 500mhz Powerbook. I haven't tried it on interpreted Lisps, but I imagine it wouldn't be too fun.
There are some scoring configuration parameters in swank.lisp that are mostly self-explanitory. Adjust to fit your own symbol naming schemes; these seemed to be the five-minute opinion of #lisp. Some way to set these from Emacs would probably be nice in the future.
(defparameter *fuzzy-completion-symbol-prefixes* "*+-%&?<") (defparameter *fuzzy-completion-symbol-suffixes* "*+->") (defparameter *fuzzy-completion-word-separators* "-/.")
The scoring algorithm is currently completely static. It would probably be a nifty project to implement some machine learning on it.
----------------------------------------------------------------------
Now, the Emacs interface. Well, it kind of sucks. I bound slime-fuzzy-complete-symbol to C-c M-i in the Slime map. The problem is that since the first letters of the short form aren't necessarily the first letters of the matches, the existing Emacs completion system will fail miserably with this algorithm.
What I did was, if there was more than one completion, pop up a window with the results (formatted nicely like above, but with a bold face instead of upcasing). Point starts on the highest scoring result, and the result is immediately placed into the Lisp buffer in place of the short form. Then the user can hit 'n' and 'p' to navigate the list of completions. As they do, the replacement is updated. To pick a completion and keep it, hit Return. To abort and revert to the short form, hit almost anything else. It is a recursive edit, like isearch, so doing anything else in Emacs will abort the completion. It's also implemented very poorly.
I don't really like this, but I'm not sure what a better option is. If you have the completion buffer come up normally, it will have embedded state from the Lisp source buffer. If the Lisp source buffer changes before a completion is picked, it may modify the wrong position. And again, it can't really work like the (stateless) normal completion.
----------------------------------------------------------------------
So anyway, I'd appreciate it if people could try it out. If anyone has good interface ideas (or even better, would implement them :) I'd like to hear them, since I'm not so happy with what I've got.
Thanks, -bcd
Here is the new and improved interface for the fuzzy completion system. Please don't try the old one at this point, it was crap.
The modality of the previous attempt at an interface is completely gone. Now all normal emacs commands work in the completions buffer. (Yay!)
What happens is that if the completion area changes in the destination buffer outside the control of the completions buffer, it will automatically close the next time it tries to replace it. This seems much better to me than the hacky overriding keymap that I used before.
In addition to all normal commands working in the completion buffer, I added the typical mouse-2 gesture for picking a completion by mouse.
I tied into the window-configuration-change-hook to try and make the completions buffer go away all the time when closed, but never if the user has changed window configurations in the interim.
I also added documentation to the external interfaces (more is still needed, but at least it's documented from a user perspective now.)
Finally, the score function was modified a tiny bit to give some more weight to longer matched chunks.
It is still bound to C-c M-i. I personally have bound it to C-c C-i in my local config, alongside the regular slime-complete-symbol which I have always used with C-M-i.
This is a patch from pristine CVS as of Wed Jun 16 07:30:00 GMT 2004. (disregard the old patch, this supersedes it.)
Again, comments and thoughts for improvement are appreciated.
-bcd
On Wed, Jun 16, 2004 at 02:48:13AM -0500, Brian Downing wrote:
Again, comments and thoughts for improvement are appreciated.
Commenting to myself, it would probably be nice if space were bound to scroll-up and delete bound to scroll-down in the completion buffer, a la view-mode and info-mode.
-bcd
Here's a third version of the patch. Added is a function, SWANK::FUZZY-COMPLETION-SELECTED, which is called when a fuzzy completion is selected off the interface in emacs. Currently this doesn't do anything. I added it so that if somebody wants to play with adaptive scoring and machine learning for the fuzzy completions that they wouldn't have to worry about the boring interface parts.
-bcd
On Fri, Jun 18, 2004 at 03:14:31PM -0500, Brian Downing wrote:
Here's a third version of the patch. ...
I forgot to implement my own suggestion! Please stick these:
(define-key map "\d" 'scroll-down) (define-key map " " 'scroll-up)
in the definition for slime-fuzzy-completions-map.
-bcd
Well, Luke seemed to like it. :)
Here it is with documentation, finally. (Full patch against CVS within the last hour.)
This is your last chance to tell me that you hate the algorithm/interface/idea and want it to be completely different! (Or more constructive suggestions -- I'm interested. :)
-bcd
On Mon, Jun 21, 2004 at 08:13:02PM -0500, Brian Downing wrote:
Here it is with documentation, finally.
And here is a quick manual entry. Customization is not discussed yet, but the variables involved aren't exported yet either.
-bcd
Brian Downing bdowning@lavos.net writes:
Well, Luke seemed to like it. :)
Yes indeed, I'll commit this soon.
Currently digesting the code and doing some Xemacs-compat hacking.
-Luke
Brian Downing bdowning@lavos.net writes:
Well, Luke seemed to like it. :)
Here it is with documentation, finally. (Full patch against CVS within the last hour.)
This is checked in now. I made a few minor mods (see ChangeLog).
Rather than have a separate keybinding I just used our existing choose-your-own-completion indirection, so you can do this:
(setq slime-complete-symbol-function 'slime-fuzzy-complete-symbol)
Or experiment with it by pressing `M-x slime-fuzzy-complete-symbol' or choosing from the menubar. This is a really funky feature.
This is your last chance to tell me that you hate the algorithm/interface/idea and want it to be completely different! (Or more constructive suggestions -- I'm interested. :)
One idea I have is that if you press a self-inserting character in the completions buffer then it would be dismissed and the character inserted in the target buffer. The idea is that if fuzzy completion guesses the right symbol for the first choice then you can just keep typing and the completion window will disappear.
I'll play with that tomorrow.
Great feature :-)
Cheers, Luke
On Tue, Jun 22, 2004 at 11:05:53AM +0200, Luke Gorrie wrote:
This is your last chance to tell me that you hate the algorithm/interface/idea and want it to be completely different! (Or more constructive suggestions -- I'm interested. :)
One idea I have is that if you press a self-inserting character in the completions buffer then it would be dismissed and the character inserted in the target buffer. The idea is that if fuzzy completion guesses the right symbol for the first choice then you can just keep typing and the completion window will disappear.
I like that, but I'd also like to keep space, backspace, and q behaving they way they do now. (q is so common to get out of an unwanted popup I think it would be unnatural to lose it.)
Unfortunatly with changes the code doesn't work for me right now, but I mailed Luke privately about that.
-bcd
Brian Downing bdowning@lavos.net writes:
I like that, but I'd also like to keep space, backspace, and q behaving they way they do now. (q is so common to get out of an unwanted popup I think it would be unnatural to lose it.)
It appears that my changes were a bit.. "hasty." :-) I've backed them out so now it's a "pristine" patch in CVS. Fuzzy-completion is bound to `C-c M-i'.
-Luke
On Tue, Jun 22, 2004 at 07:08:02PM +0200, Luke Gorrie wrote:
It appears that my changes were a bit.. "hasty." :-) I've backed them out so now it's a "pristine" patch in CVS. Fuzzy-completion is bound to `C-c M-i'.
Okay, I've recommitted most of Luke's changes. Fuzzy completion is customizable for `slime-complete-symbol-function', but I've retained its keybinding as C-c M-i, mostly because I actively use both completion styles and expect others would want to as well.
Also some documentation has been added to the Texinfo manual about this feature.
Tested and working in Emacs 21.2, Emacs CVS, and XEmacs 21.4. In XEmacs however the mouse click events don't seem to work to select a completion. On closer examination, it doesn't look like any Slime mouse events work in XEmacs.
-bcd
-
Brian Downing -
Luke Gorrie