Fork me on GitHub
Ben Sless12:12:34

Anyone ever tried implementing something like syntax-case with meander?


Sort of. syntax-case is the inspiration for what the next iteration of meander will have as its extension mechanism (instead of defsyntax). It looks like

(defoperator boolean
  (_) (`pick true false)
  (_ & ?rest) (`each (boolean) & ?rest))
So (boolean) would expand to (pick true false) and (boolean ?x) would expand to (each (pick true false) ?x). I like this approach a lot because the left side is pattern matching on the form (the _ is boolean). The other thing I like is that the right side is using substitution. I think syntax-case works much like this with ... being usable on the right side IIRC.

Ben Sless05:12:51

It's pretty easy to define a macro which expands to rewrite. The problem (?) is schemes syntax definition has way less semantics and is hygienic. I tried playing around with it and it works, but requires lots of care in the definition. Will paste my experiments later

Ben Sless17:12:44

A question this experiment raises, should ... be greedy? The only way I had to match the correct number was to require the aggregation stop at a certain number on both sides


... is not correct on epsilon and it took me some time to realize this. Basically we need two operators as we do in regular expression: * and *? , greedy and frugal. Greedy star for query (matching) consumes as much as it can, and for yielding (substitution) it produces as much as it can. Frugal star for query gradually consumes more and more of the input like ... does not, and for yielding it does the same for production. ... on epsilon is somewhat of a Frankenstein. It gradually consumes but greedily produces.


This branch is very stale right now as the approach ended up being too slow. The code looks weird because it was designed to construct interpreters and compilers from the same interface. It does this, but rewriting the trees produced by the compiler ended up being too slow and hard to get right though in many cases it was able to produce incredibly compact code.

Ben Sless16:12:03

This was probably answered many times but what literature would you recommend for the theoretical underpinnings if meander?


I read all kinds of stuff about term rewriting/logic programming/unification/regular expression/combinatorics and kinda mixed all the parts of those things together that I liked. The Handbook of Automated Reasoning has a number of good articles that are worth checking out. Many of the articles in that book can be found freely available on line with a little digging. I read most of Term Rewriting and All That which gave me a lot of new vocabulary words (for Google searches) and introduced me to many of the famous problems and algorithms in the space. In the past year, I've found The Art of Computer Programming Combinatorial Alogrithms Part 1 (Vol. 4A of the series) to be an incredible resource. Thanks to that book, I was able to greatly improve the algorithms used to find partitions/permutations of maps and sets far more efficiently than I did before. Of course, there are tons and tons of papers on the influential topics that I enumerated but I can't recall any off the top of my head at the moment that really stand out.


If you're up to it, I would accept a patch for a new section of our documentation for "Resources" with links to books and papers. 🙂

Ben Sless20:12:55

I'll start by chasing these references down and PRing an initial patch if you promise in the future to throw in the papers and other books when they come to mind 🙂


Works for me!

🎉 1
Ben Sless11:12:47

Also separately volunteered some cookbook examples


Thanks a lot.

catjam 1
Ben Sless17:12:44

A question this experiment raises, should ... be greedy? The only way I had to match the correct number was to require the aggregation stop at a certain number on both sides