PRolog Equation Solving System

[someone]

Hi,

If we want to improve our equation solver in the range of transcendental
equations, it might be interesting to look at PRESS [1]:

"PRESS (PRolog Equation Solving System) is a system for solving
symbolic, transcendental, non-differential equations."

[1]: http://dream.inf.ed.ac.uk/software/press/

[Aaron Meurer]

That's useful. It looks like the problems it solves are mostly of the
type that can already be solved by SymPy, but doing it this way would
have some advantages (e.g., it looks like it mostly solves things in a
way that would be useful for a "step-by-step" system). I think Harsh
at least should take a look. There are some latex files in the
pressdir/probs directory that have some examples of what it can do.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/53867f62.c9dd0e0a.684c.fffffd80SMTPIN_ADDED_BROKEN%40gmr-mx.google.com.
> For more options, visit https://groups.google.com/d/optout.

[Richard Fateman]

You could look at it, but I think that, unless it has been changed since

I last looked, it has nothing at all to offer vs. an algorithmic approach.

And some real problems in that it returns answers that are wrong, sometimes.

The authors of the program are assuming that the (human?) recipient would naturally check any

answer from some  computer program.

see

http://www.cs.berkeley.edu/~fateman/papers/solving.pdf

cheers

RJF

[Aaron Meurer]

How does it return invalid results? Does it not check if spurious
solutions were introduced through multiplying both sides of an
equation?

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/a8d25cb1-05c6-43b0-bc86-293689c3c533%40googlegroups.com.

[F. B.]

According to their website that code is copyrighted

Unless explicitly stated otherwise all material on this web site is copyright © The University of Edinburgh. 

[Aaron Meurer]

We wouldn't be able to use it directly anyway. The idea would be more
to look at their methodology, and maybe also the types of equations
that they can solve.

Also, don't confuse copyrighted with proprietary. SymPy is also
copyrighted (read the first line of the LICENSE file).

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/939f18b3-e5e1-4651-8bcf-2e3df7d67908%40googlegroups.com.

[Richard Fateman]

On Wednesday, May 28, 2014 9:16:46 PM UTC-7, Aaron Meurer wrote:

How does it return invalid results? Does it not check if spurious
solutions were introduced through multiplying both sides of an
equation?

yes.

Also, if one is inclined to say that computer programs "know" things, then

computer programs presumably are "ignorant of" things.

In which case I think one would say that this program is ignorant of

complex variables.  

 

[Aaron Meurer]

Ah, but the concept is sound, I think. One just needs to be more
careful in the implementation.

Given that this program was designed to solve "high school algebra,"
it's not surprising that the author chose to ignore complex variables,
for better or for worse.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/ebdacb2f-d41b-44cf-ba1d-9259ef825e1d%40googlegroups.com.

[Rathmann]

Interestingly, the problem that Richard Fateman uses to introduce his critique of Press (and other systems) doesn't look to be a happy one for Sympy.

from sympy.abc import x

from sympy import cos, solve

solve(cos(x)+cos(3*x)+cos(5*x), x)

<At least in my (not quite up to date) tree, this gives a hang/infinite loop>

If you do the high-school level cleverness by hand, and replace it with 

solve(cos(3*x)*(1+2*cos(2*x)), x)

[pi/6, pi/3, pi/2, 2*pi/3]

which is better, although missing a root at 5pi/6

[F. B.]

More than the logic contained in PRESS, I would get inspiration for the programming style.

The current sympy solve has a lot of manual dispatching through "IF" and recursion. The code is hard to read, and you also need a debugger to understand what happens to expressions. I would suggest to either use a logical style (like PROLOG rules, there is the logpy project which is trying to implement that paradigm in Python), or pattern dispatch (as in Wolfram Mathematica).

An example of a possible implementation of a solver using pattern dispatch:

@patterndispatch(cos(A), x, assumptions=Q.has(A, x) & Q.instanceof(x, Symbol))
def solve(f, x):
    return # solutions to cos(A) == 0, call solve(A - zeros of cos(), x)

@patterndispatch(cos(A)+B, x, assumptions=Q.has(A, x) & not Q.has(B, x) & Q.instanceof(x, Symbol)
def solve(f, x):
    # code

This would make the code a lot more readable, solutions would be mapped to very specific cases, and there would no need to manually create lots of IFs, because the @patterndispatch decorator would store and use the dispatching information properly (e.g. in a directed acyclic graph). This was the style pursued by Wolfram Mathematica and it proved very successful.

Alternatively, the logic programming style of PRESS could be implemented into SymPy by creating a dependence to LogPy.

I really believe that the code should become more readable. I would favour the introduction of a pattern dispatching decorator with joint assumptions.

[Aaron Meurer]

+1. I like your thoughts for extensions to the assumptions system.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/3ff4d2f1-7040-4b20-939e-e0836570ddb3%40googlegroups.com.

[Aaron Meurer]

It's getting stuck in the checking routine. Try check=False.

If you do rewrite(exp), you get some solutions.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/325f15d8-200a-4022-b21f-8286879941d1%40googlegroups.com.

[F. B.]

By the way, just some considerations about the Prolog approach to equation solving. In short, Prolog tries to determine the largest set that satisfies all given rules. I guess that if PRESS misses some rules, it will end up showing too many solutions, because the solution set has not been properly restricted. This is a serious shortcoming of logical programming, you have to write all necessary rules.

On the other hand a pattern dispatching system combined with an improved assumptions system would allow partial implementations of solver rules without this problem.

[F. B.]

I had a look at SymPy, it looks like this:

In [1]: solve(cos(3*x), x)
Out[1]:
⎡π  π⎤
⎢─, ─⎥
⎣6  2⎦

In [2]: solve(cos(n*x), x)
Out[2]:
⎡ π   3⋅π⎤
⎢───, ───⎥
⎣2⋅n  2⋅n⎦

It looks like the cos( ) solver just thinks that cos( ) can be zero at two points (pi/2 and 3*pi/2), then calls a solver to match its argument to those values.

cos(3*x) == 0 misses thus 5*pi/2, which divided by 3 would give 5*pi/6, the missing solution.

By the way, why did the solver implicitly assume that n != 0 ? If n == 0, there are no solutions to cos(n*x) == 0.

Is there any representation for periodic infinite sets in SymPy?

[Richard Fateman]

I suppose my objection to the PRESS program is not the "organization" per se,  It could be that knowledge

of mathematics can be encoded procedurally or functionally or as pattern matches or as rules.  Frankly,

I have my own bias, having worked with several of these.

What I object to is the mind set of the programmers that there is, essentially, no point in encoding

mathematics at all,  just some collection of mimicking what students might do in their flailing around

trying to answer certain kinds of examination questions.  

I suppose one could argue that there is no "there" there, and all of mathematics is just

pushing symbols around on paper,  and you just need more and more rules to achieve a higher and

higher grade on exam questions.  This is sometimes portrayed as a view that you start knowing

nothing and just "debug".   And maybe that is how infants learn, at least initially.

If those rules become "high level"  in some way perhaps there is a route to something that

could pass for knowledge, and might even answer unanticipated questions.  But the particular

PRESS rules are weak, and the fact that the answers cannot be checked is a hint that it

doesn't really contain the concepts of mathematics in a systematically complete way.

RJF

[Aaron Meurer]

These are all issues that Harsh should be addressing in his GSoC project.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/fc862b0e-800c-4e5e-a2dd-a3f4151a61fa%40googlegroups.com.