Function get_class returns a class from a given string. It makes use of get_mod_func --- sympy/utilities/source.py | 26 ++++++++++++++++++++++++++ 1 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/sympy/utilities/source.py b/sympy/utilities/source.py index 56ca7f7..1470759 100644 --- a/sympy/utilities/source.py +++ b/sympy/utilities/source.py @@ -10,3 +10,29 @@ def source(object): """ print 'In file: %s' % inspect.getsourcefile(object) print inspect.getsource(object) + +def get_class(lookup_view): + """ + Convert a string version of a class name to the object. + + This is used by the query method + """ + if isinstance(lookup_view, str): + # Bail early for non-ASCII strings (they can't be functions). + lookup_view = lookup_view.encode('ascii') + mod_name, func_name = get_mod_func(lookup_view) + if func_name != '': + lookup_view = getattr(__import__(mod_name, {}, {}, ['']), func_name) + if not callable(lookup_view): + raise AttributeError("'%s.%s' is not a callable." % (mod_name, func_name)) + return lookup_view + + +def get_mod_func(callback): + # Converts 'sympy.core.query.QueryIntegerHandler' to + # ['sympy.core.query', 'QueryIntegerHandler'] + try: + dot = callback.rindex('.') + except ValueError: + return callback, '' + return callback[:dot], callback[dot+1:] \ No newline at end of file -- 1.6.1.2
This is a very naive implementation. It constructs EVERY possible query with propositions from self.defined_facts and tries every one to see if it succeeds.
It has unacceptable slow performance. This is implemented just as workaround for the new assumption system, but eventually a complete backward-chaining algorithm should be implemented. --- sympy/core/facts.py | 42 ++++++++++++++++++++++++++++++++++ sympy/core/tests/test_assumptions.py | 28 +++++++++++++++++++++- sympy/core/tests/test_facts.py | 10 ++++++++ 3 files changed, 79 insertions(+), 1 deletions(-)
diff --git a/sympy/core/facts.py b/sympy/core/facts.py index 2e9d666..27bf0c6 100644 --- a/sympy/core/facts.py +++ b/sympy/core/facts.py @@ -817,6 +817,48 @@ def __init__(self, rules): # TODO: add proper support for U (None), i.e. # integer=U -> rational=U ??? (XXX i'm not sure)
+ def bc_ask(self, goal, theta={}): + """Backward-chaining algorithm. Backward-chaining reasoners process + queries and return proofs for the answers they provide. + + This is a very naive implementation. It constructs EVERY possible query + with propositions from self.defined_facts and tries every one to see + if it succeeds. + + It has unacceptable slow performance. This is implemented just as + workaround for the new assumption system. Do *NOT* commit to the + main repo + """ + + if len(goal.keys()) > 1: + raise NotImplementedError + + key = goal.keys()[0] + _facts = [] + from sympy.utilities.iterables import subsets, variations + for k in range(len(self.defined_facts)): + k_subsets = list(subsets(self.defined_facts, k)) + for k_sub in k_subsets: + if not key in k_sub: + # it won't be of any use if goal is in answers + for _pos in variations([True, False], len(k_sub), repetition=True): + _res = dict() + for k, i in enumerate(k_sub): + _res[i] = _pos[k] + _facts.append(_res) + + answers = [] + for _f in _facts: + try: + _deduced = self.deduce_all_facts(_f) + + if _deduced.has_key(key) and _deduced[key] == goal[key]: + answers.append(_f) + except AssertionError: + pass + + return answers +
def deduce_all_facts(self, facts, base=None): """Deduce all facts from known facts ({} or [] of (k,v)) diff --git a/sympy/core/tests/test_assumptions.py b/sympy/core/tests/test_assumptions.py index cb1c0d5..a4d7ca8 100644 --- a/sympy/core/tests/test_assumptions.py +++ b/sympy/core/tests/test_assumptions.py @@ -1,4 +1,30 @@ -from sympy.core import Symbol, S, Rational, Integer +from sympy.core.assumptions import Assume +from sympy.core import Symbol + +def test_assume(): + x = Symbol('x') + assump = Assume(x, 'integer') + assert assump.expr == x + assert assump.key == 'integer' + assert assump.bool_key == True + +def test_assume_False(): + x = Symbol('x') + assump = Assume(x, 'integer', False) + assert assump.expr == x + assert assump.key == 'integer' + assert assump.bool_key == False + +def test_assume_equal(): + x = Symbol('x') + assert Assume(x, 'positive') == Assume(x, 'positive') + assert Assume(x, 'positive') != Assume(x, 'positive', False) + assert Assume(x, 'positive', False) == Assume(x, 'positive', False) + +### Also check the old assumption system until it is completely +### removed + +from sympy.core import S, Rational, Integer from sympy.utilities.pytest import XFAIL, raises
variations is a routine that calculates all possible variations of size n (with or without repetition) of a given set. --- sympy/utilities/iterables.py | 36 +++++++++++++++++++++++++++++++ sympy/utilities/tests/test_iterables.py | 6 ++++- 2 files changed, 41 insertions(+), 1 deletions(-)
diff --git a/sympy/utilities/iterables.py b/sympy/utilities/iterables.py index 6179622..61879a6 100644 --- a/sympy/utilities/iterables.py +++ b/sympy/utilities/iterables.py @@ -173,3 +173,39 @@ def recursion(result, M, k): for elem in recursion([item], M[i + 1:], k - 1): yield elem
+ +def cartes(seq0, seq1, modus='pair'): + """ return the Cartesian Product of two sequences """ + if modus == 'pair': + return [[item0, item1] for item0 in seq0 for item1 in seq1] + elif modus == 'triple': + return [item0 + [item1] for item0 in seq0 for item1 in seq1] + +def variations(seq, n, repetition=False): + """Returns all the variations of the list of size n. + + variations(seq, n, True) will return all the variations of the list of + size n with repetitions + + variations(seq, n, False) will return all the variations of the list of + size n without repetitions + """ + def setrep(seq): # remove sets with duplicates (repetition is relevant) + def delrep(seq): # remove duplicates while maintaining order + result = [] + for item in seq: + if item not in result: + result.append(item) + return result + return [item for item in seq if item == delrep(item)] + + if n == 1: + return [[item] for item in seq] + result = range(len(seq)) + cartesmodus = 'pair' + for i in range(n-1): + result = cartes(result, range(len(seq)), cartesmodus) + if not repetition: + result = setrep(result) + cartesmodus = 'triple' + return [[seq[index] for index in indices] for indices in result] diff --git a/sympy/utilities/tests/test_iterables.py b/sympy/utilities/tests/test_iterables.py index 1eea497..959c900 100644 --- a/sympy/utilities/tests/test_iterables.py +++ b/sympy/utilities/tests/test_iterables.py @@ -1,6 +1,6 @@ from sympy import symbols from sympy.utilities.iterables import postorder_traversal, \ - preorder_traversal, flatten, subsets + preorder_traversal, flatten, subsets, variations
1. Can't assume relations. It is not possible to specify relations between different objects. For example, you can assume that x>0 and y>0, but you can't assume x>y
2. Verbose code splitted across multiple classes. Each class must override query methods (.is_*).
3. Extensibility. To add new assumptions you have to add code to the core
The assumption system implemented in this series of patches relies on these principles:
1. Assumptions are separate from objects. Assumptions are instances of Assume, which is a class that holds a reference to the expression and to the 'key' (what it assumes)
2. Queries out of the core. No more .is_* methods. Specific queries are implemented as subclasses of QueryHandler, and the query function calls the appropriate subclass of QueryHandler
query -> QueryHandler -> QueryNegativeHandler -> QueryIntegerHandler -> QueryBoundedHandler ... That way, creating new queries is a matter of subclassing QueryHandler and override the apropriate methods.
In this patch, two fundamental objects were created for this task:
- sympy.core.assumptions.Assume, which takes track of the object's assumptions.
- a query method: sympy.query.query, which replaces the old expr.is_* syntax. Also the relevat handlers were created to resolve some queries, in sympy.queries.handlers
diff --git a/doc/src/modules.txt b/doc/src/modules.txt index 0232b4d..d13a655 100644 --- a/doc/src/modules.txt +++ b/doc/src/modules.txt @@ -27,6 +27,7 @@ access any SymPy module, or use this contens: modules/geometry.txt modules/galgebra/GA/GAsympy.txt modules/statistics.txt + modules/query.txt modules/concrete.txt modules/solvers.txt
diff --git a/doc/src/modules/query.txt b/doc/src/modules/query.txt new file mode 100644 index 0000000..df9aaa1 --- /dev/null +++ b/doc/src/modules/query.txt @@ -0,0 +1,85 @@ +Query module +============ + +This module is responsible for inferring properties from objects + +Supported queries +----------------- + + - *bounded* + - *commutative* + - *comparable* + - *complex* + - *composite* + - *even* + - *finite* + - *imaginary* + - *infinitesimal* + - *integer* + - *irrational* + - *rational* + - *nonnegative* + - *noninteger* + - *nonpositive* + - *nonzero* + - *negative* + - *positive* + - *prime* + - *real* + - *odd* + - *unbounded* + - *zero* + +Examples +-------- + >>> from sympy import Symbol, Assume, query + >>> query(2, 'integer') + True + >>> query(2, 'rational') + True + >>> query(1.5, 'integer') + Flase + >>> x = Symbol('x') + >>> query(x, 'integer', Assume(x, 'even')) + True + +You can find more examples in the in the form of test under directory sympy/query/tests/ + + + +Design +------ +Each time query is called, the appropriate Handler for the current key is called. This is +always a subclass of sympy.query.QueryHandler. It's classmethods have the name's of the classes +it supports. For example, + +For example, a (simplified) QueryHandler for the query 'positive' would look like this:: + + class QueryPositiveHandler(CommonHandler): + + def Mul(self): + # return True if all argument's in self.expr.args are positive + ... + + def Add(self): + for arg in self.expr.args: + if query(arg, self.key, self.assumptions) != True: + break + else: + # if all argument's are positive + return True + ... + +So that the .Mul() method would be called when self.expr is an instance of Mul, the Add method +would be called when self.expr is an instance of Add and so on. + + +Extensibility +------------- +You can define your own queries by subclassing sympy.query.QueryHandler and passing +to query a a qdict argument consting of the query's string and the appropriate +handler. For example:: + + query(expr, 'my_query', qdict={'my_query': MyQueryHandler}) + +would call MyQueryHandler to resolve the query 'my_query' \ No newline at end of file -- 1.6.1.2
On Mon, Mar 16, 2009 at 8:13 AM, Fabian Seoane <fab...@fseoane.net> wrote:
> this introduces my work on the new assumption system. The old assumption is left
> untouched until we migrate all the code the new assumption system.
On Mon, Mar 16, 2009 at 8:13 AM, Fabian Seoane <fab...@fseoane.net> wrote:
> variations is a routine that calculates all possible variations > of size n (with or without repetition) of a given set. > --- > sympy/utilities/iterables.py | 36 +++++++++++++++++++++++++++++++ > sympy/utilities/tests/test_iterables.py | 6 ++++- > 2 files changed, 41 insertions(+), 1 deletions(-)
> diff --git a/sympy/utilities/iterables.py b/sympy/utilities/iterables.py > index 6179622..61879a6 100644 > --- a/sympy/utilities/iterables.py > +++ b/sympy/utilities/iterables.py > @@ -173,3 +173,39 @@ def recursion(result, M, k): > for elem in recursion([item], M[i + 1:], k - 1): > yield elem
> + > +def cartes(seq0, seq1, modus='pair'): > + """ return the Cartesian Product of two sequences """ > + if modus == 'pair': > + return [[item0, item1] for item0 in seq0 for item1 in seq1] > + elif modus == 'triple': > + return [item0 + [item1] for item0 in seq0 for item1 in seq1] > + > +def variations(seq, n, repetition=False): > + """Returns all the variations of the list of size n. > + > + variations(seq, n, True) will return all the variations of the list of > + size n with repetitions
On Mon, Mar 16, 2009 at 8:13 AM, Fabian Seoane <fab...@fseoane.net> wrote:
> Function get_class returns a class from a given string. It makes use > of get_mod_func > --- > sympy/utilities/source.py | 26 ++++++++++++++++++++++++++ > 1 files changed, 26 insertions(+), 0 deletions(-)
> diff --git a/sympy/utilities/source.py b/sympy/utilities/source.py > index 56ca7f7..1470759 100644 > --- a/sympy/utilities/source.py > +++ b/sympy/utilities/source.py > @@ -10,3 +10,29 @@ def source(object): > """ > print 'In file: %s' % inspect.getsourcefile(object) > print inspect.getsource(object) > + > +def get_class(lookup_view): > + """ > + Convert a string version of a class name to the object. > + > + This is used by the query method > + """ > + if isinstance(lookup_view, str): > + # Bail early for non-ASCII strings (they can't be functions). > + lookup_view = lookup_view.encode('ascii') > + mod_name, func_name = get_mod_func(lookup_view) > + if func_name != '': > + lookup_view = getattr(__import__(mod_name, {}, {}, ['']), func_name) > + if not callable(lookup_view): > + raise AttributeError("'%s.%s' is not a callable." % (mod_name, func_name)) > + return lookup_view > + > + > +def get_mod_func(callback): > + # Converts 'sympy.core.query.QueryIntegerHandler' to > + # ['sympy.core.query', 'QueryIntegerHandler'] > + try: > + dot = callback.rindex('.') > + except ValueError: > + return callback, '' > + return callback[:dot], callback[dot+1:]
Could there be tests for both of the functions above? It's not exactly clear what they are doing from the docstrings. Also code like this is really hackish:
On Mon, Mar 16, 2009 at 8:13 AM, Fabian Seoane <fab...@fseoane.net> wrote:
> This is a very naive implementation. It constructs EVERY possible query
> with propositions from self.defined_facts and tries every one to see
> if it succeeds.
> It has unacceptable slow performance. This is implemented just as
> workaround for the new assumption system, but eventually a complete
> backward-chaining algorithm should be implemented.
> ---
> sympy/core/facts.py | 42 ++++++++++++++++++++++++++++++++++
> sympy/core/tests/test_assumptions.py | 28 +++++++++++++++++++++-
> sympy/core/tests/test_facts.py | 10 ++++++++
> 3 files changed, 79 insertions(+), 1 deletions(-)
> diff --git a/sympy/core/facts.py b/sympy/core/facts.py
> index 2e9d666..27bf0c6 100644
> --- a/sympy/core/facts.py
> +++ b/sympy/core/facts.py
> @@ -817,6 +817,48 @@ def __init__(self, rules):
> # TODO: add proper support for U (None), i.e.
> # integer=U -> rational=U ??? (XXX i'm not sure)
> + def bc_ask(self, goal, theta={}):
> + """Backward-chaining algorithm. Backward-chaining reasoners process
> + queries and return proofs for the answers they provide.
> +
> + This is a very naive implementation. It constructs EVERY possible query
> + with propositions from self.defined_facts and tries every one to see
> + if it succeeds.
> +
> + It has unacceptable slow performance. This is implemented just as
> + workaround for the new assumption system. Do *NOT* commit to the
> + main repo
> + """
> +
> + if len(goal.keys()) > 1:
> + raise NotImplementedError
> +
> + key = goal.keys()[0]
> + _facts = []
> + from sympy.utilities.iterables import subsets, variations
> + for k in range(len(self.defined_facts)):
> + k_subsets = list(subsets(self.defined_facts, k))
> + for k_sub in k_subsets:
> + if not key in k_sub:
> + # it won't be of any use if goal is in answers
> + for _pos in variations([True, False], len(k_sub), repetition=True):
> + _res = dict()
> + for k, i in enumerate(k_sub):
> + _res[i] = _pos[k]
> + _facts.append(_res)
> +
> + answers = []
> + for _f in _facts:
> + try:
> + _deduced = self.deduce_all_facts(_f)
> +
> + if _deduced.has_key(key) and _deduced[key] == goal[key]:
> + answers.append(_f)
> + except AssertionError:
> + pass
> +
> + return answers
> +
> def deduce_all_facts(self, facts, base=None):
> """Deduce all facts from known facts ({} or [] of (k,v))
> diff --git a/sympy/core/tests/test_assumptions.py b/sympy/core/tests/test_assumptions.py
> index cb1c0d5..a4d7ca8 100644
> --- a/sympy/core/tests/test_assumptions.py
> +++ b/sympy/core/tests/test_assumptions.py
> @@ -1,4 +1,30 @@
> -from sympy.core import Symbol, S, Rational, Integer
> +from sympy.core.assumptions import Assume
> +from sympy.core import Symbol
> +
> +def test_assume():
> + x = Symbol('x')
> + assump = Assume(x, 'integer')
> + assert assump.expr == x
> + assert assump.key == 'integer'
> + assert assump.bool_key == True
> +
> +def test_assume_False():
> + x = Symbol('x')
> + assump = Assume(x, 'integer', False)
> + assert assump.expr == x
> + assert assump.key == 'integer'
> + assert assump.bool_key == False
> +
> +def test_assume_equal():
> + x = Symbol('x')
> + assert Assume(x, 'positive') == Assume(x, 'positive')
> + assert Assume(x, 'positive') != Assume(x, 'positive', False)
> + assert Assume(x, 'positive', False) == Assume(x, 'positive', False)
> +
> +### Also check the old assumption system until it is completely
> +### removed
^^^^ I think those Assume tests should go to the next patch.
I want to play with this a bit more in the coming days in your branch. Probably more docstrings could be written, if I find time, I'll write some and send a patch.
On Mon, Mar 16, 2009 at 8:13 AM, Fabian Seoane <fab...@fseoane.net> wrote:
> The old assumption system had some limitations:
> 1. Can't assume relations. It is not possible to specify relations between different > objects. For example, you can assume that x>0 and y>0, but you can't > assume x>y
> 2. Verbose code splitted across multiple classes. Each class must override > query methods (.is_*).
> 3. Extensibility. To add new assumptions you have to add code to > the core
> The assumption system implemented in this series of patches relies on these > principles:
> 1. Assumptions are separate from objects. Assumptions are instances of Assume, which is > a class that holds a reference to the expression and to the 'key' (what it assumes)
> 2. Queries out of the core. No more .is_* methods. Specific queries are implemented > as subclasses of QueryHandler, and the query function calls the appropriate > subclass of QueryHandler
> query -> QueryHandler -> QueryNegativeHandler > -> QueryIntegerHandler > -> QueryBoundedHandler > ... > That way, creating new queries is a matter of subclassing QueryHandler and override > the apropriate methods.
> In this patch, two fundamental objects were created for this task:
> - sympy.core.assumptions.Assume, which takes track of the > object's assumptions.
> - a query method: sympy.query.query, which replaces the old > expr.is_* syntax. Also the relevat handlers were created to resolve > some queries, in sympy.queries.handlers
Ondrej Certik wrote: > On Mon, Mar 16, 2009 at 8:13 AM, Fabian Seoane <fab...@fseoane.net> wrote:
>> Function get_class returns a class from a given string. It makes use >> of get_mod_func >> --- >> sympy/utilities/source.py | 26 ++++++++++++++++++++++++++ >> 1 files changed, 26 insertions(+), 0 deletions(-)
>> diff --git a/sympy/utilities/source.py b/sympy/utilities/source.py >> index 56ca7f7..1470759 100644 >> --- a/sympy/utilities/source.py >> +++ b/sympy/utilities/source.py >> @@ -10,3 +10,29 @@ def source(object): >> """ >> print 'In file: %s' % inspect.getsourcefile(object) >> print inspect.getsource(object) >> + >> +def get_class(lookup_view): >> + """ >> + Convert a string version of a class name to the object. >> + >> + This is used by the query method >> + """ >> + if isinstance(lookup_view, str): >> + # Bail early for non-ASCII strings (they can't be functions). >> + lookup_view = lookup_view.encode('ascii') >> + mod_name, func_name = get_mod_func(lookup_view) >> + if func_name != '': >> + lookup_view = getattr(__import__(mod_name, {}, {}, ['']), func_name) >> + if not callable(lookup_view): >> + raise AttributeError("'%s.%s' is not a callable." % (mod_name, func_name)) >> + return lookup_view >> + >> + >> +def get_mod_func(callback): >> + # Converts 'sympy.core.query.QueryIntegerHandler' to >> + # ['sympy.core.query', 'QueryIntegerHandler'] >> + try: >> + dot = callback.rindex('.') >> + except ValueError: >> + return callback, '' >> + return callback[:dot], callback[dot+1:]
> Could there be tests for both of the functions above? It's not exactly > clear what they are doing from the docstrings. Also code like this is > really hackish:
yeah, I know it looks hackish, but it is copied from a similar utility in the django codebase, so i'm quite sure that there isn't a better way of doing it
It sure lacks docstrings and tests, so I'll send a reworked patch or this and the other modules soon.
|
