The following are what I would consider helpful reading and some advice about their content:
- CiteSeerX — Efficient Predicate Dispatching<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553> Good place to start, covers why the feature I'm proposing would be useful. The algorithms described here however can be ignored. - Compiling Pattern Matching to Good Decision Trees<http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf> The heart of the matter. This describes the algorithm I'd like to see implemented. Do not be put off by the mathematical notation! It's really a shorthand so they don't have to write OCaml. It does require a few re-readings but the ideas here are very well expressed and mostly easy to follow. - Warnings for pattern matching<http://moscova.inria.fr/~maranget/papers/warn/warn.pdf> An earlier paper that explains the idea of "usefulness" used in the paper above. The portions on Haskell and lazy-evaluation can be completely ignored. Another interesting book to look at would be The Art of the Metaobject Protocol - The MIT Press <http://mitpress.mit.edu/9780262610742>, but I don't consider it essential. You really don't need to know OCaml or SML very well to understand the above papers. However I have found it helpful to have an StandardML/NJ compiler (REPL) handy to at least test out some of the things described in the papers. I've been pouring over these three papers again and again so I'm more than happy to discuss my understanding of them. Again the most important paper is the second one. My idea is to implement that algorithm and use a very small amount of logic programming to reason about user defined patterns so they can be properly ordered and compiled. To move forward I would suggest: 1) Send in your CA if you haven't already 2) Skim the papers in your free time 3) Dig into the 2nd paper 4) Ping me on #clojure IRC or email me with whatever questions you may have 4) Start hacking :) I have a repo that primarily consists of sketches here, https://github.com/swannodette/match. I think this is less relevant than everyone having some basic grounding in the ideas covered in the mentioned papers. David On Thu, May 12, 2011 at 6:03 PM, David Nolen <dnolen.li...@gmail.com> wrote: > Hello fellow Clojurians, > > As some of you may know I've been doing a bit of research into efficient > predicate dispatch, generic methods, and state-of-the-art implementations of > pattern-matching in OCaml. After a bit of reading and prototyping, I'm quite > confident that it's possible to build something considerably more powerful > than generic methods or predicate dispatch that exhibits the performance of > the fastest pattern matching algorithms to be found in Standard ML, Haskell, > Ocaml, and Scala (without their numerous limitations). > > The main innovation here is to use logic programming to drive the > compilation to decisions tree as some members of the ML family do. This > gives us the following: > > - Open quality of CLOS generic methods > - User customizable specializers like CLOS > - Removes order requirements of ML style pattern matching > - Richer reasoning about errors beyond just non-exhaustiveness. > > I plan on continuing to tackle this myself, but I'm putting this out there > to see if anyone else is interested in joining forces. This project isn't > nearly as daunting as it sounds. The OCaml aglorithms are well described and > we already have a logic engine - core.logic. > > I think the project would find very wide use w/in the Clojure community and > I think it would be a great opportunity to accomplish the following: > > - Learn how to write very, very high performance Clojure (6X-20X faster > than multimethods) > - Leverage relational/logic programming in a functional context > - Give Clojure a notable feature that any sufficiently advanced programming > language should be quite jealous of :D > > Ping me on or off list if you'd like collaborate! > > David > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
