hmm… yes… I just noticed that one can use an EQL or EQ clause in the Optima patterns. No more need for the alpha-conversions, and it works just fine with these two (EQ and EQL) in the presence of an OR clause. Never mind that…

- DM


On Jul 19, 2016, at 23:58, David McClain <dbm@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

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