25

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

Pete B.
  • 3,188
  • 6
  • 25
  • 38
sanity
  • 35,347
  • 40
  • 135
  • 226
  • 12
    Please people, do not broad this as too close... er, the other way around. This is interesting and answerable - and anyway, go find some of those "gimme teh codez" or "why does `"foo"[0] = 'b';` segfault?" questions, your CV would serve a much better purpose there. –  Sep 10 '13 at 20:07
  • Are you asking about solving equations, or parsing expressions? "solve 150sin(x)-gamma(x)=0" is one thing, "parse (((((x+1)-1)+1)-sin(x)-1))" is another thing, however the first may involve the second. – nanofarad Sep 10 '13 at 20:13
  • Good question. LastCalc is fairly weird in that everything it does, whether parsing, doing unit conversions, or (soon) simplifying expressions and solving equations, is just a series of transformations - the starting point being a list of tokens. However, parsing isn't a challenge, so please focus on solving, not parsing. – sanity Sep 10 '13 at 20:21
  • 2
    To the person who voted to close due to "too broad". I can see how it might appear to be very broad superficially, but actually I think this question is answerable, and actually I expect the answer to be fairly concise. Wolfram Alpha might be very sophisticated, but I suspect the core principles on which its equation manipulation works are relatively simple and explainable. – sanity Sep 10 '13 at 20:24
  • 1
    Reading you Question, I found this document http://www.math.wpi.edu/IQP/BVCalcHist/calctoc.html searching about it. Maybe it will help. There is an implementation of a CAS and it talks about simplification of equations. – Jean Waghetti Sep 10 '13 at 21:00
  • If you haven't already done so research the topic of *term-rewriting*. – High Performance Mark Sep 11 '13 at 07:57

2 Answers2

10

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.

Rubydesic
  • 3,386
  • 12
  • 27
Marc Hauptmann
  • 688
  • 5
  • 18
2

Wolfram alpha is developed by Mathematica

  • mathematica is stephen wolphram's brainchild. Mathematica 1.0 was released in 1988. mathematica is much like maple and they both rely heavily on older software libraries like LaPack.
  • The libraries that these programs are, based on, and often simply, legacy software. They've been around, and modified, for a very long time.

If you would like to know about the background programs running, sagemath is a free open source alternative; you could possible reverse engineer the solutions to your questions:

SageMath.org

useslessone
  • 69
  • 1
  • 4