# Programming language with pattern matching in trees [closed]

I'd like to prototype a computer algebra system. An equation would be represented by a tree and rules would be defined - similarly to mathematical axioms - by specifying a pattern (in the tree) and a restructuring rule for the matched part of the tree.

Can you suggest a programming language I could experiment with to test this approach (ideally not too experimental language)? Basically it should support high level data structures like lists (or actually trees) and make it easy to match the tree against a pattern and also replace part of a tree by a substitute. So it's about high level data structure pattern matching and easy modification of that.

EDIT: Of course I could take any programming language to write the program in the end, but I'm looking specifically for something which makes it easy to do first idea prototyping. I don't mind learning a new language (for fun).

• I don't think there exists a standard data structure that does this, though trees certainly exist. It would take little work to adapt it to recursively apply each node to some sort of pattern and perform some operation as a consequence. – Neil May 10 '12 at 10:29
• That isn't really about data structures, but about a programming language. For example there are Prolog programs which in theory you could write in C++ but that would be silly. Prototyping data algorithms in C++ is also silly when there are high level languages around. – Gerenuk May 10 '12 at 10:50
• ML, Haskell, any decent Lisp or Scheme (with pattern matching libraries). – SK-logic May 10 '12 at 10:57
• @SK-logic: sounds good. maybe you can post this as an answer with a very brief outline why they are suited for this particular pattern matching problem? – Gerenuk May 10 '12 at 11:05

There are many languages with built-in pattern matching support:

1. `ML` (all the dialects)

2. `Haskell` - pretty much the same approach as in ML, with one significant advantage, namely - Scrap your boilerplate library which allows to get rid of explicit recursion for most of the typical tree-walking tasks.

3. Any decent `Lisp` or `Scheme`, where an arbitrary complex pattern matching can be implemented with metaprogramming. Many implementations would already include a powerful pattern matching (e.g., `Racket` or `Bigloo`).

4. `Mathematica`. It is quite expensive, but worth looking at, at least as a source of ideas to be ported to the other languages. Its term rewriting features are especially useful for CAS applications: http://reference.wolfram.com/mathematica/guide/Rules.html

5. `Prolog`. Its approach to pattern matching (unification) is in general much slower than what ML would do, but in some cases might be extremely useful. Fortunately, Prolog is easy to embed into another languages (see `Schelog`).

• Thanks, that's really helpful! I suppose I just need to examine the languages now. The mathematica suggestion is really interesting. Maybe I can learn from that, try my own rule system in some new suitable programming language and in the end implement my result in a graphical Python application. – Gerenuk May 10 '12 at 11:53
• When look at point 1) 2) and 3): seems I would chose Haskell. Would be interesting to learn anyway. Will it be at least just as good as using ML or as using Lisp with a library? Lisp has nice data structures, but no real advantage for pattern matching apart from libraries just as for any language? Points 4) and 5) are interesting in a different way :) – Gerenuk May 10 '12 at 16:58
• @Gerenuk, yes, out-of-box Haskell is the most powerful and equipped for your task. Lisp, OTOH, is the most flexible, because of its unique metaprogramming functionality. But you can still do quite a lot of this stuff in Haskell too, using the Template Haskell extension. So yes, it is a reasonable choice. – SK-logic May 10 '12 at 17:39

Can you suggest a programming language I could experiment with to test this approach (ideally not too experimental language)?

You are looking for a language but I think your question should be which type of programming language.

Having worked with Object-oriented (Imperative), Logic, Functional and Declarative programming languages, I would suggest something in the functional family.

If you want don't want to spend time parsing the input, and understand or can learn s-expressions, then I would suggest LISP. If you want something that also has types, which means you might have to either parse the input or enter the data in a form much closer to what the data structure definition then I would suggest maybe OCaml, Scheme or F#.

For why you should use a functional language over an object-oriented language see: OCaml for the Masses

As a general introduction to writing expression evaluator of algebraic data types in functional languages see Write Yourself a Scheme in 48 Hours

• Well, pattern matching is common in the functional languages, but it is not bound to them. It is perfectly possible to implement pattern matching in an otherwise fully imperative and OO language. – SK-logic May 10 '12 at 11:34

The kind of tree pattern matching you need is not provided out-of-the-box by any of the programming languages mentioned before. For example, if you want to try to factorize a sum of many terms each consisting of an arbitrary number of factors, your patterns need to be non-linear (to find the common factors) and allow segment assignment (to preserve everything else). Although widely available in string pattern matching, these features are strangely absent in most tree pattern matching implementations.

You can look at Tom (http://tom.loria.fr/wiki/index.php5/Main_Page), Egison (http://www.egison.org/) and at my pet-language Bracmat. (Search for that one on GitHub, I'm out of links as I am new at stackexchange). Bracmat is far beyond the experimental stage. Although I use it professionally mostly for natural language processing, it started as a small computer algebra system back in 1988.

You can find Egison and Bracmat examples on rosettacode.