Show HN: Clojure DSL for pattern-matching, parsing and generic programming | Hacker News Reader

Show HN: Clojure DSL for pattern-matching, parsing and generic programming

scattered-thoughts.net

204 pointsjamii16 comments

This is why I feel like hn needs the ability to, on occasion, double upvote. Like maybe you get one double-plus-up-vote per week for when you come across an article that screams "THIS IS WHY I READ HACKER NEWS".

This comment makes me far happier than the extra vote :D

This. I think the simplicity of HN is brilliant, especially since everything is geared toward encouraging thoughtful, productive discussion.

If you think something is especially interesting for some reason, or that a certain kind of content should be featured more, say so! And give a convincing argument for why! That's far more interesting than a double upvote, or trying to somehow limit content you deem inferior, and you will actually influence people in the long run.

I'm with shaunxcode, posts like this make up for all the junk.

Thanks so much for creating and sharing this.

How does this compare to https://github.com/clojure/core.match ?

He mentions that core.match is better at efficiently compiling complicated patterns, but little else is said as to exactly why strucjure was made rather than just using core.match.

Author here.

Strucjure has much more expressive power. Strucjure views are first-class values and can call other views (or recursively call themselves). This allows them to recognise eg context free grammars. Most of the examples in this post cannot be expressed with core.match

Currently, this power comes at the expense of speed but I hope to be able to get reasonably close to core.match for simple patterns. Core.match will always be somewhat faster because it can reorder decisions and eliminate redundant tests.

core.match has a very narrow focus compared to Strucjure - efficient pattern matching and eventually efficient predicate dispatch.

The generality of Strucjure should not be underestimated :)

I tried using core.match to turn arbitrary Clojure expressions into Disjunctive Normal Form. I found that doing sequence matching ended up being less readable than I expected (from memory):

  (match exp
    [([not ([or & rest] :seq)] :seq)] ...)

From the looks of it, solving this problem using strucjure might be a little more elegant.

This has some similarities to Bondi http://bondi.it.uts.edu.au/ by Barry Jay (but implemented in Clojure rather than being a Binary.)

I'm interested to hear your thoughts on Bondi and/or Barry's work.

I'm vaguely aware of Bondi but I haven't gotten around to trying it out. It definitely influenced me when deciding to make patterns first class instead of sticking to OMeta's OOP design.

was this influenced by the famous [well, back in the day] regexp in scheme post by that gun guy? [if not, you may find it interesting]

[edit: ok, so forgive my slow memory. it was olin shivers and ended up as http://www.scsh.net/docu/post/sre.html]

[edit2: gun context http://www.wanderings.net/notebook/Main/BitterAcknowledgment... (cannot find original); meant only in fond, amused recollection, although not personal, having never met him, of course.]

No, but I will go read that. Thanks.

Awesome, great work. I'll have to play around with this later and dig into the source. I'm looking forward to that - I'm just beginning to dive into this area.

What are your thoughts on implementing reversible patterns?

> What are your thoughts on implementing reversible patterns?

I'm thinking something like this

    (defprotocol Pattern
      (extract [this input] "=> bindings")
      (replace [this input bindings] "=> new-input"))

This should obey some rule like:

    (submap? (extract p (replace p input bindings)) bindings)

That would make the data-grammar/generic-traversal experiments much nicer and also cleanly delineates patterns from views. It may also help when I try to do things like generative testing.

Not quite sure how that would work for (or ...) and (not ...) patterns, so it still needs more hammock time.

There is an example which turns infix math expressions into sexps. Could Strucjure be used to write a Computer Algebraic System (CAS)? I would guess that most algebra is probably simpler than the Red/Black tree example.

The math that goes into making a useful CAS can be beautiful, but "simpler than red-black trees" is not a description that springs to mind. A toy CAS might be pretty easy, though.

Reply on news.ycombinator.com