sympy/core/assumptions.py

   1 from facts import FactRules
   2
   3
   4 class CycleDetected(Exception):
   5     """(internal) used to detect cycles when evaluating assumptions
   6        through prerequisites
   7     """
   8     pass
   9
  10
  11 class AssumeMeths(object):
  12     """ Define default assumption methods.
  13
  14     AssumeMeths should be used to derive Basic class only.
  15
  16     All symbolic objects have assumption attributes that can be accessed via
  17     .is_<assumption name> attribute.
  18
  19     Assumptions determine certain properties of symbolic objects. Assumptions
  20     can have 3 possible values: True, False, None.  None is returned when it is
  21     impossible to say something about the property. For example, a Symbol is
  22     not know beforehand to be positive.
  23
  24     By default, all symbolic values are in the largest set in the given context
  25     without specifying the property. For example, a symbol that has a property
  26     being integer, is also real, complex, etc.
  27
  28     Here follows a list of possible assumption names:
  29
  30         - commutative   - object commutes with any other object with
  31                           respect to multiplication operation.
  32         - real          - object can have only values from the set
  33                           of real numbers
  34         - integer       - object can have only values from the set
  35                           of integers
  36         - bounded       - object absolute value is bounded
  37         - positive      - object can have only positive values
  38         - negative      - object can have only negative values
  39         - nonpositive      - object can have only nonpositive values
  40         - nonnegative      - object can have only nonnegative values
  41         - comparable    - object.evalf() returns Number object.
  42         - irrational    - object value cannot be represented exactly by Rational
  43         - unbounded     - object value is arbitrarily large
  44         - infinitesimal - object value is infinitesimal
  45
  46
  47     Example rules:
  48
  49       positive=T            ->  nonpositive=F, real=T
  50       real=T & positive=F   ->  nonpositive=T
  51
  52       unbounded=F|T         ->  bounded=not unbounded   XXX ok?
  53       irrational=T          ->  real=T
  54
  55
  56     Implementation note: assumption values are stored in
  57     ._assumption dictionary or are returned by getter methods (with
  58     property decorators) or are attributes of objects/classes.
  59
  60     Examples:
  61
  62         - True, when we are sure about a property. For example, when we are
  63         working only with real numbers:
  64         >>> from sympy import *
  65         >>> Symbol('x', real = True)
  66         x
  67
  68         - False
  69
  70         - None (if you don't know if the property is True or false)
  71     """
  72
  73     __slots__ = ['_assumptions',    # assumptions
  74                  '_a_inprogress',   # already-seen requests (when deducing
  75                                     # through prerequisites -- see CycleDetected)
  76                 ]
  77
  78
  79     # This are the rules under which our assumptions function
  80     #
  81     # References
  82     # ----------
  83     #
  84     # negative,     -- http://en.wikipedia.org/wiki/Negative_number
  85     # nonnegative
  86     #
  87     # even, odd     -- http://en.wikipedia.org/wiki/Parity_(mathematics)
  88     # imaginary     -- http://en.wikipedia.org/wiki/Imaginary_number
  89     # composite     -- http://en.wikipedia.org/wiki/Composite_number
  90     # finite        -- http://en.wikipedia.org/wiki/Finite
  91     # infinitesimal -- http://en.wikipedia.org/wiki/Infinitesimal
  92     # irrational    -- http://en.wikipedia.org/wiki/Irrational_number
  93     # ...
  94
  95     _assume_rules = FactRules([
  96
  97         'integer        ->  rational',
  98         'rational       ->  real',
  99         'real           ->  complex',
 100         'imaginary      ->  complex',
 101         'complex        ->  commutative',
 102
 103         'odd            ==  integer & !even',
 104         'even           ==  integer & !odd',
 105
 106         'real           ==  negative | zero | positive',
 107
 108         'positive       ->  real & !negative & !zero',
 109         'negative       ->  real & !positive & !zero',
 110
 111         'nonpositive    ==  real & !positive',
 112         'nonnegative    ==  real & !negative',
 113
 114         'zero           ->  infinitesimal & even',
 115
 116         'prime          ->  integer & positive',
 117         'composite      ==  integer & positive & !prime',
 118
 119         'irrational     ==  real & !rational',
 120
 121         'imaginary      ->  !real',
 122
 123
 124         '!bounded     ==  unbounded',
 125         '!commutative ==  noncommutative',
 126         '!complex       ==  noncomplex',
 127         'noninteger     ==  real & !integer',
 128         '!zero        ==  nonzero',
 129         '!homogeneous ==  inhomogeneous',
 130
 131         # XXX do we need this ?
 132         'finite     ->  bounded',       # XXX do we need this?
 133         'finite     ->  !zero',         # XXX wrong?
 134         'infinitesimal ->  !finite',    # XXX is this ok?
 135
 136         # TODO we should remove this (very seldomly used, but affect performance):
 137         'nni    ==  integer & nonnegative',
 138         'npi    ==  integer & nonpositive',
 139         'pi     ==  integer & positive',
 140         'ni     ==  integer & negative',
 141     ])
 142
 143     _assume_defined = _assume_rules.defined_facts.copy()
 144     _assume_defined.add('comparable')
 145     _assume_defined = frozenset(_assume_defined)
 146
 147
 148
 149     ###################################
 150     # positive/negative from .evalf() #
 151     ###################################
 152
 153     # properties that indicate ordering on real axis
 154     _real_ordering = set(['negative', 'nonnegative', 'positive', 'nonpositive'])
 155
 156     # what can be said from cmp(x.evalf(),0)
 157     # NOTE: if x.evalf() is zero we can say nothing
 158     _real_cmp0_table= {
 159             'positive': {1: True,  -1: False, 0: None},
 160             'negative': {1: False, -1: True,  0: None},
 161             }
 162
 163     # because we can say nothing if x.evalf() is zero, nonpositive is the same
 164     # as negative
 165     _real_cmp0_table['nonpositive'] = _real_cmp0_table['negative']
 166     _real_cmp0_table['nonnegative'] = _real_cmp0_table['positive']
 167
 168     def __getstate__(self, cls=None):
 169         if cls is None:
 170             # This is the case for the instance that gets pickled
 171             cls = self.__class__
 172
 173         d = {}
 174         # Get all data that should be stored from super classes
 175         for c in cls.__bases__:
 176             if hasattr(c, "__getstate__"):
 177                 d.update(c.__getstate__(self, c))
 178
 179         # Get all information that should be stored from cls and return the dic
 180         for name in cls.__slots__:
 181             if hasattr(self, name):
 182                 d[name] = getattr(self, name)
 183         return d
 184
 185     def __setstate__(self, d):
 186         # All values that were pickled are now assigned to a fresh instance
 187         for name, value in d.iteritems():
 188             try:
 189                 setattr(self, name, value)
 190             except:
 191                 pass
 192
 193
 194
 195     def _what_known_about(self, k):
 196         """tries hard to give an answer to: what is known about fact `k`
 197
 198            This function is called when a request is made to see what a fact
 199            value is.
 200
 201            If we are here, it means that the asked-for fact is not known, and
 202            we should try to find a way to find it's value.
 203
 204            For this we use several techniques:
 205
 206            1. _eval_is_<fact>
 207            ------------------
 208
 209            first fact-evalation function is tried,  for example
 210            _eval_is_integer
 211
 212
 213            2. relations
 214            ------------
 215
 216            if the first step did not succeeded (no such function, or its return
 217            is None) then we try related facts. For example
 218
 219                        means
 220              rational   -->   integer
 221
 222            another example is joined rule:
 223
 224              integer & !odd  --> even
 225
 226            so in the latter case if we are looking at what 'even' value is,
 227            'integer' and 'odd' facts will be asked.
 228
 229
 230            3. evalf() for comparable
 231            -------------------------
 232
 233            as a last resort for comparable objects we get their numerical value
 234            -- this helps to determine facts like 'positive' and 'negative'
 235
 236
 237
 238            In all cases when we settle on some fact value, it is given to
 239            _learn_new_facts to deduce all its implications, and also the result
 240            is cached in ._assumptions for later quick access.
 241         """
 242
 243         # 'defined' assumption
 244         if k not in self._assume_defined:
 245             raise AttributeError('undefined assumption %r' % (k))
 246
 247         assumptions = self._assumptions
 248
 249         seen = self._a_inprogress
 250         #print '%s=?\t%s %s' % (name, self,seen)
 251         if k in seen:
 252             raise CycleDetected
 253
 254         seen.append(k)
 255
 256         try:
 257             # First try the assumption evaluation function if it exists
 258             if hasattr(self, '_eval_is_'+k):
 259                 #print 'FWDREQ: %s\t%s' % (self, k)
 260                 try:
 261                     a = getattr(self,'_eval_is_'+k)()
 262
 263                 # no luck - e.g. is_integer -> ... -> is_integer
 264                 except CycleDetected:
 265                     #print 'CYC'
 266                     pass
 267
 268                 else:
 269                     if a is not None:
 270                         self._learn_new_facts( ((k,a),) )
 271                         return a
 272
 273
 274
 275             # Try assumption's prerequisites
 276             for pk in self._assume_rules.prereq.get(k,()):
 277                 #print 'pk: %s' % pk
 278                 if hasattr(self, '_eval_is_'+pk):
 279                     # cycle
 280                     if pk in seen:
 281                         continue
 282
 283                     #print 'PREREQ: %s\t%s <- %s' % (self, k, pk)
 284                     a = getattr(self,'is_'+pk)
 285
 286                     if a is not None:
 287                         self._learn_new_facts( ((pk,a),) )
 288                         # it is possible that we either know or don't know k at
 289                         # this point
 290                         try:
 291                             return self._assumptions[k]
 292                         except KeyError:
 293                             pass
 294         finally:
 295             seen.pop()
 296
 297
 298         # For positive/negative try to ask evalf
 299         if k in self._real_ordering:
 300             if self.is_comparable:
 301                 v = self.evalf()
 302
 303                 c = cmp(v, 0)
 304                 a = self._real_cmp0_table[k][c]
 305
 306                 if a is not None:
 307                     self._learn_new_facts( ((k,a),) )
 308                     return a
 309
 310         # No result -- unknown
 311         # cache it  (NB ._learn_new_facts(k, None) to learn other properties,
 312         # and because assumptions may not be detached)
 313         self._learn_new_facts( ((k,None),) )
 314         return None
 315
 316
 317     def _learn_new_facts(self, facts):
 318         """Learn new facts about self.
 319
 320            *******************************************************************
 321            * internal routine designed to be used only from assumptions core *
 322            *******************************************************************
 323
 324            Given new facts and already present knowledge (._assumptions) we ask
 325            inference engine to derive full set of new facts which follow from
 326            this combination.
 327
 328            The result is stored back into ._assumptions
 329         """
 330         # no new facts
 331         if not facts:
 332             return
 333
 334         default_assumptions = type(self).default_assumptions
 335         base = self._assumptions
 336
 337         # ._assumptions were shared with the class
 338         if base is default_assumptions:
 339             base = base.copy()
 340             self._assumptions = base
 341             self._assume_rules.deduce_all_facts(facts, base)
 342
 343         else:
 344             # NOTE it modifies base inplace
 345             self._assume_rules.deduce_all_facts(facts, base)
 346
 347
 348
 349     def _assume_hashable_content(self):
 350         d = self._assumptions
 351         keys = d.keys()
 352         keys.sort()
 353         return tuple([(k+'=', d[k]) for k in keys])
 354