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.

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).

share|improve this question

put on hold as off-topic by Snowman, MichaelT, GlenH7, amon, Bart van Ingen Schenau yesterday

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about what language, technology, or project one should take up next are off topic on Programmers, as they can only attract subjective opinions for answers. There are too many individual factors behind the question to create answers that will have lasting value. You may be able to get help in The Whiteboard, our chat room." – Snowman, MichaelT, GlenH7, Bart van Ingen Schenau
If this question can be reworded to fit the rules in the help center, please edit the question.

    
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
5  
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

3 Answers 3

up vote 12 down vote accepted

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).

share|improve this answer
    
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

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.

share|improve this answer

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

share|improve this answer
1  
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

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