Holy Smokes!! This is really interesting! Thanks for that. Looks like I’m going to dive down the rabbit hole for a while…
- DM > On Jul 20, 2016, at 09:11, Gene Diveglia <gdiveg...@mac.com> wrote: > > > Hi David, > > You might also find Trivia to be interesting. > > https://github.com/guicho271828/trivia > <https://github.com/guicho271828/trivia> > > It is functionally compatible with Optima and in fact uses Optima’s test > suite. However, it takes a different approach internally as well as making > available an alternative optimization strategy based on work by Balland et. > al. 2006 (Emilie Balland, Pierre-Etienne Moreau. Optimizing pattern matching > compilation by program transformation - > https://hal.inria.fr/inria-00000763v2/document > <https://hal.inria.fr/inria-00000763v2/document>) with details of the > implementation here: https://github.com/guicho271828/trivia.balland2006 > <https://github.com/guicho271828/trivia.balland2006>. > > > >> On Jul 20, 2016, at 2:58 AM, David McClain <d...@refined-audiometrics.com >> <mailto:d...@refined-audiometrics.com>> wrote: >> >> Having used the NAMED-READTABLES package for several days, I can state that >> it is very good for my purposes. Many thanks for pointing that one out. >> >> For many years I had used the #T reader macro to refer to structs in my >> pattern matching compiler. Then I found CL-UNIFICATION and wanted to give it >> a try. And just as surely, Marco had also invented a #T reader macro for >> nearly the same purpose. >> >> CL-UNIFICATION is quite powerful and useful, but is much more general than >> needed for pattern matching driven computations. Unification works in both >> directions between patterns and data, while pattern matching needs to go >> only from pattern to destructuring of incoming data. CL-UNIFICATION is also >> a runtime process, instead of being compiled into efficient in-line code. >> >> So then I discovered a package called Optima that really is a pattern >> matching compiler, much like my own, which produces efficient in-line code >> to effect the pattern matching. I have to say that Optima really goes a bit >> further than my own compiler. I had used rearrangement of match clauses to >> gain longest common prefix matching. Optima goes further than this, taking >> cues from the more advanced concepts presented in “Optimizing Pattern >> Matching” by Fabrice Le Fessant and Luc Maranget. >> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507 >> <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507> >> >> So, I have been replacing my MATCH with that from Optima. >> >> But along the way, I found that Optima demands linear patterns, and cannot >> handle repeated mention of variables in the pattern. At first this seemed a >> serious restriction. I imagine it is a requirement of the math involved in >> the Pattern Matrices mentioned in the paper by Fessant and Maranget. >> >> I found a way to (mostly) overcome this restriction by including an >> Alpha-conversion preprocess ahead of the Optima compiler, allowing for >> repeated variables in a pattern by renaming the duplicates and tacking on a >> WHEN post-matching clause. This works well, except for OR patterns, which >> will require something more elaborate. >> >> So to overcome the OR pattern problems, I’m thinking of extending Optima >> with REF patterns to replace the VARIABLE nodes on the repeated symbols, >> giving the repeated symbols new names by alpha-conversion and having the REF >> symbols produce a comparison op. But then the question becomes - what kind >> of comparison op? I have been using EQL in my alpha conversions. >> >> I also ran into the limitation that Optima wants proper lists as patterns >> and cannot handle terminal dotted vars representing the rest of the list. >> This was also easily solved by preprocessing de-sugaring ahead of its >> compiler. >> >> Since I have modified the code for Optima a bit, I moved it to a local >> repository. I’m not plugged into any Git groups on the Web and so I won’t be >> updating the extant repositories in any way. But maybe these enhancements to >> Optima would be useful to others? >> >> Cheers, >> >> - DM >> >
