Sharing READTABLE macro bindings?

David McClain dbm at refined-audiometrics.com
Thu Jul 21 03:57:35 UTC 2016


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 <gdiveglia at 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 <dbm at refined-audiometrics.com <mailto:dbm at 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
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/pro/attachments/20160720/ca83bd52/attachment.html>


More information about the pro mailing list