Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Regular expressions and are popular matching patterns in strings. What similar handy languages exist to match other data structures? I know XPath for XML trees, but I have not seen use of it for other tree structures (e.g. JSON objects, S-Expressions, or nested record structures in your programming languages). I have heard of SNOBOL patterns and Perl6 grammars, maybe someone can point me to concrete examples and and documentation of pattern matching data structures? For graph structures my only idea is graph patterns in Notation3 and SPARQL (limited to RDF graphs), and for patterns in multi-dimensional arrays I don't know anything.

Regular expressions seem to be the only pattern matching language that is used in most programming languages, but matching languages for non-strings are much less common. I cannot believe that the reason is the dominance of strings over other structures like arrays, lists, records, tables, trees, and graphs.

share|improve this question

closed as too broad by gnat, MichaelT, GlenH7, Bart van Ingen Schenau, Konrad Morawski Feb 11 at 14:13

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

    
At the end of the day, data structures are ultimately recorded as a 1 dimensional string of bytes. And so, mechanically making sense of some unknown data structure mapped to a string would be impossibly difficult, because not only do you need to recognize the content but also the structure, which could be implemented in any way. Impossibly difficult to me, anyway. –  whatsisname Jan 25 '11 at 20:26
2  
@whatsisname: But the structure isn't unknown. You get to choose the data structure (on an abstract level) when you invent the DSL and when you implement it, you know the implementation of the target data. It's not (much) harder than any other programming: Just pile up abstractions until the brain stops hurting (and stop before it start hurting again). –  delnan Jan 25 '11 at 21:45
add comment

4 Answers

Functional Programming languages have had a generalized form of pattern matching for quite some time.

share|improve this answer
    
Very good. Do you know of libraries that bind these elements of a function language to another host language? Regular expressions can be used this way in any other language, so it should be able to do similar with functional patterns. –  Jakob Jan 25 '11 at 21:19
    
See here: code.msdn.microsoft.com/FunctionalCSharp –  Robert Harvey Jan 25 '11 at 21:29
    
There is a number of pattern matching libraries for both Common Lisp and Scheme. –  SK-logic Jan 26 '11 at 14:01
add comment

If you want to generalize away from Strings to real-valued and/or multi-dimensional data, you get into signal analysis: pattern recognition, whether it's image-based, sound-based, seismic data to look for oil, climate trend data, and so forth.

Because it's hard to express a high-dimensional search 'pattern' in code (which is, after all inherently one-dimensional and discrete), algorithms often are looking for partial patterns (e.g. SETI which is just looking for any sort of strong signal), or score how closely a sample matches to examples. Do you consider that a 'language'?

share|improve this answer
    
Well, my question aimed at exact matches of patterns in formal languages ("pattern matching"). I would call the examples you name "pattern recognition". If the data to match against is fuzzy or noise, pattern recognition is surely is more appropriate - but the "language" used for this will most likely be a programming language. Pattern matching languages should better be decidable. Thanks to your input I found another relevant question: stackoverflow.com/questions/315340/… –  Jakob Jan 28 '11 at 21:25
add comment

Apache Commons PropertyUtils for Java would fit your definition.

It can be used to get/set values from Java objects - simple (first level), nested, indexed (Array or List), and mapped (getters/setters with a single string parameter).

For a Cat object:

Property                      Equivalent/Description
"name"                        getName()
"owner.name"                  getOwner().getName() - Owner's name
"siblings[0].owner.name"      getSiblings()[0].getOwner().getName()
"food(treat)"                 getFood("treat") - Food of type "treat"
share|improve this answer
    
Looks like this could also be used to express some patterns in JSON (without the getter/setter pattern)... Oh, there already is goessner.net/articles/JsonPath which looks the same :-) –  Jakob Jan 28 '11 at 21:31
add comment

Graph rewriting is a very well-studied approach to graph transformation based on pattern matching and replacement inside graphs.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.