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
    
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
1  
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
add comment

3 Answers

up vote 7 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
add comment

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
    
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
add comment

All the high-level programming languages I know enable doing this pretty simply. I recommend using an Object Oriented language e.g. C# or Java. However, you could do this in C++, C or even Assembly.

share|improve this answer
    
Pattern matching? In Java? In C? Are you kidding?!? –  SK-logic May 10 '12 at 10:56
    
Matching tree nodes. And I said in can be done in C - I did not recommend C. There are built in libraries for XML which could be used in C# or Java for matching and replacing sub-trees. –  Danny Varod May 10 '12 at 11:18
4  
Well, it can be done in Brainfuck or on a Turing machine too. But it is a pain. And there are no pattern matching libraries for Java or C# at all. Please take a look at any proper pattern matching before suggesting something totally unusable. E.g., see Mathematica (and its term rewriting features), or any ML dialect, or Prolog with its built-in unification. –  SK-logic May 10 '12 at 11:26
    
I coded in Scheme and LISP, their main advantage is their dynamic typing. However, if you model the mathematical operators as classes with a solve method one the base type, then the static classes can be useful and enable you to do anything you could do in the above. –  Danny Varod May 10 '12 at 12:30
1  
Plain Scheme and Lisp are not that useful for such tasks - you'll need some form of pattern matching any way. It is not possible to simulate an efficient pattern matching in a pure OOP, without any metaprogramming. What you suggest is a trivial visitor, which is not useful for anything complicated. See this for example: docs.racket-lang.org/reference/match.html –  SK-logic May 10 '12 at 12:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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