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

Reply via email to