How does a system like Wolfram Alpha or Mathematica solve equations?

Question

I'm building a web-based programming language partially inspired by Prolog and Haskell (don't laugh).

It already has quite a bit of functionality, you can check out the prototype at http://www.lastcalc.com/. You can see the source here and read about the architecture here. Remember it's a prototype.

Currently LastCalc cannot simplify expressions or solve equations. Rather than hard-coding this in Java, I would like to enhance the fundamental language such that it can be extended to do these things using nothing but the language itself (as with Prolog). Unlike Prolog, LastCalc has a more powerful search algorithm, Prolog is "depth-first search with backtracking", LastCalc currently uses a heuristic best-first search.

Before delving into this I want to understand more about how other systems solve this problem, particularly Mathematica / Wolfram Alpha.

I assume the idea, at least in the general case, is that you give the system a bunch of rules for manipulation of equations (like a*(b+c) = a*b + a+c) specify the goal (eg. isolate variable x) and then let it loose.

So, my questions are:

• Is my assumption correct?
• What is the search strategy for applying rules? eg. depth first, breadth first, depth first with iterative deepening, some kind of best first?
• If it is "best first", what heuristics are used to determine whether it is likely that a particular rule application has got us closer to our goal?

I'd also appreciate any other advice (except for "give up" - I regularly ignore that piece of advice and doing so has served me well ;).

Answer 1

I dealt with such questions myself some time ago. I then found this document about simplification of expressions. It is titled Rule-based Simplification of Expressions and shows some details about simplification in Mupad, which later became a part of Matlab.

According to this document, your assumption is correct. There is a set of rules for manipulation of expressions. A heuristic quality metric is is used as a target function for simplification.