sympy/core/basic.py

   1 """Base class for all objects in sympy"""
   2
   3 type_class = type
   4
   5 import decimal
   6 from basic_methods import BasicMeths, cache_it, cache_it_immutable, BasicType
   7
   8 class MemoizerArg:
   9     """ See Memoizer.
  10     """
  11
  12     def __init__(self, allowed_types, converter = None, name = None):
  13         self._allowed_types = allowed_types
  14         self.converter = converter
  15         self.name = name
  16
  17     def fix_allowed_types(self, have_been_here={}):
  18         i = id(self)
  19         if have_been_here.get(i): return
  20         allowed_types = self._allowed_types
  21         if isinstance(allowed_types, str):
  22             self.allowed_types = getattr(Basic, allowed_types)
  23         elif isinstance(allowed_types, (tuple, list)):
  24             new_allowed_types = []
  25             for t in allowed_types:
  26                 if isinstance(t, str):
  27                     t = getattr(Basic, t)
  28                 new_allowed_types.append(t)
  29             self.allowed_types = tuple(new_allowed_types)
  30         else:
  31             self.allowed_types = allowed_types
  32         have_been_here[i] = True
  33         return
  34
  35     def process(self, obj, func, index = None):
  36         if isinstance(obj, self.allowed_types):
  37             if self.converter is not None:
  38                 obj = self.converter(obj)
  39             return obj
  40         func_src = '%s:%s:function %s' % (func.func_code.co_filename, func.func_code.co_firstlineno, func.func_name)
  41         if index is None:
  42             raise ValueError('%s return value must be of type %r but got %r' % (func_src, self.allowed_types, obj))
  43         if isinstance(index, (int,long)):
  44             raise ValueError('%s %s-th argument must be of type %r but got %r' % (func_src, index, self.allowed_types, obj))
  45         if isinstance(index, str):
  46             raise ValueError('%s %r keyword argument must be of type %r but got %r' % (func_src, index, self.allowed_types, obj))
  47         raise NotImplementedError(`index,type(index)`)
  48
  49 class Memoizer:
  50     """ Memoizer function decorator generator.
  51
  52     Features:
  53       - checks that function arguments have allowed types
  54       - optionally apply converters to arguments
  55       - cache the results of function calls
  56       - optionally apply converter to function values
  57
  58     Usage:
  59
  60       @Memoizer(<allowed types for argument 0>,
  61                 MemoizerArg(<allowed types for argument 1>),
  62                 MemoizerArg(<allowed types for argument 2>, <convert argument before function call>),
  63                 MemoizerArg(<allowed types for argument 3>, <convert argument before function call>, name=<kw argument name>),
  64                 ...
  65                 return_value_converter = <None or converter function, usually makes a copy>
  66                 )
  67       def function(<arguments>, <kw_argumnets>):
  68           ...
  69
  70     Details:
  71       - if allowed type is string object then there Basic must have attribute
  72         with the string name that is used as the allowed type --- this is needed
  73         for applying Memoizer decorator to Basic methods when Basic definition
  74         is not defined.
  75
  76     Restrictions:
  77       - arguments must be immutable
  78       - when function values are mutable then one must use return_value_converter to
  79         deep copy the returned values
  80
  81     Ref: http://en.wikipedia.org/wiki/Memoization
  82     """
  83
  84     def __init__(self, *arg_templates, **kw_arg_templates):
  85         new_arg_templates = []
  86         for t in arg_templates:
  87             if not isinstance(t, MemoizerArg):
  88                 t = MemoizerArg(t)
  89             new_arg_templates.append(t)
  90         self.arg_templates = tuple(new_arg_templates)
  91         return_value_converter = kw_arg_templates.pop('return_value_converter', None)
  92         self.kw_arg_templates = kw_arg_templates.copy()
  93         for template in self.arg_templates:
  94             if template.name is not None:
  95                 self.kw_arg_templates[template.name] = template
  96         if return_value_converter is None:
  97             self.return_value_converter = lambda obj: obj
  98         else:
  99             self.return_value_converter = return_value_converter
 100
 101     def fix_allowed_types(self, have_been_here={}):
 102         i = id(self)
 103         if have_been_here.get(i): return
 104         for t in self.arg_templates:
 105             t.fix_allowed_types()
 106         for k,t in self.kw_arg_templates.items():
 107             t.fix_allowed_types()
 108         have_been_here[i] = True
 109
 110     def __call__(self, func):
 111         cache = {}
 112         value_cache = {}
 113         def wrapper(*args, **kw_args):
 114             kw_items = tuple(kw_args.items())
 115             try:
 116                 return self.return_value_converter(cache[args,kw_items])
 117             except KeyError:
 118                 pass
 119             self.fix_allowed_types()
 120             new_args = tuple([template.process(a,func,i) for (a, template, i) in zip(args, self.arg_templates, range(len(args)))])
 121             assert len(args)==len(new_args)
 122             new_kw_args = {}
 123             for k, v in kw_items:
 124                 template = self.kw_arg_templates[k]
 125                 v = template.process(v, func, k)
 126                 new_kw_args[k] = v
 127             new_kw_items = tuple(new_kw_args.items())
 128             try:
 129                 return self.return_value_converter(cache[new_args, new_kw_items])
 130             except KeyError:
 131                 r = func(*new_args, **new_kw_args)
 132                 try:
 133                     try:
 134                         r = value_cache[r]
 135                     except KeyError:
 136                         value_cache[r] = r
 137                 except TypeError:
 138                     pass
 139                 cache[new_args, new_kw_items] = cache[args, kw_items] = r
 140                 return self.return_value_converter(r)
 141         return wrapper
 142
 143 #####
 144
 145 class Basic(BasicMeths):
 146     """
 147     Base class for all objects in sympy.
 148
 149     Conventions
 150     ===========
 151
 152     1)
 153     When you want to access parameters of some instance, always use [].
 154     Example:
 155
 156     In [2]: cot(x)[:]
 157     Out[2]: (x,)
 158
 159     In [3]: cot(x)[0]
 160     Out[3]: x
 161
 162     In [4]: (x*y)[:]
 163     Out[4]: (x, y)
 164
 165     In [5]: (x*y)[1]
 166     Out[5]: y
 167
 168
 169     2) Never use internal methods or variables (the ones prefixed with "_").
 170     Example:
 171
 172     In [6]: cot(x)._args    #don't use this, use cot(x)[:] instead
 173     Out[6]: (x,)
 174
 175
 176     """
 177
 178     def __new__(cls, *args, **assumptions):
 179         obj = object.__new__(cls)
 180         obj.assume(**assumptions)
 181         obj._mhash = None # will be set by BasicMeths.__hash__ method.
 182         obj._args = args  # all items in args must be Basic objects
 183         return obj
 184
 185     @staticmethod
 186     def sympify(a, sympify_lists=False):
 187         """Converts an arbitrary expression to a type that can be used
 188            inside sympy. For example, it will convert python int's into
 189            instance of sympy.Rational, floats into intances of sympy.Real,
 190            etc. It is also able to coerce symbolic expressions which does
 191            inherit after Basic. This can be useful in cooperation with SAGE.
 192
 193            It currently accepts as arguments:
 194                - any object defined in sympy (except maybe matrices [TODO])
 195                - standard numeric python types: int, long, float, Decimal
 196                - strings (like "0.09" or "2e-19")
 197
 198            If sympify_lists is set to True then sympify will also accept
 199            lists, tuples and sets. It will return the same type but with
 200            all of the entries sympified.
 201
 202            If the argument is already a type that sympy understands, it will do
 203            nothing but return that value. This can be used at the begining of a
 204            function to ensure you are working with the correct type.
 205
 206            >>> from sympy import *
 207
 208            >>> sympify(2).is_integer
 209            True
 210            >>> sympify(2).is_real
 211            True
 212
 213            >>> sympify(2.0).is_real
 214            True
 215            >>> sympify("2.0").is_real
 216            True
 217            >>> sympify("2e-45").is_real
 218            True
 219
 220         """
 221         if isinstance(a, BasicType):
 222             return a
 223         if isinstance(a, Basic):
 224             return a
 225         elif isinstance(a, bool):
 226             raise NotImplementedError("bool support")
 227         elif isinstance(a, (int, long)):
 228             return Basic.Integer(a)
 229         elif isinstance(a, (float, decimal.Decimal)):
 230             return Basic.Real(a)
 231         elif isinstance(a, complex):
 232             real, imag = map(Basic.sympify, (a.real, a.imag))
 233             ireal, iimag = int(real), int(imag)
 234
 235             if ireal + iimag*1j == a:
 236                 return ireal + iimag*Basic.ImaginaryUnit()
 237             return real + Basic.ImaginaryUnit() * imag
 238         elif isinstance(a, (list,tuple)) and len(a) == 2:
 239             return Basic.Interval(*a)
 240         elif isinstance(a, (list,tuple,set)) and sympify_lists:
 241             return type(a)([Basic.sympify(x, True) for x in a])
 242         else:
 243             # XXX this is here because of cyclic-import issues
 244             from sympy.matrices import Matrix
 245
 246             if isinstance(a, Matrix):
 247                 raise NotImplementedError('matrix support')
 248
 249             if not isinstance(a, str):
 250                 # At this point we were given an arbitrary expression
 251                 # which does not inherit after Basic. This may be
 252                 # SAGE's expression (or something alike) so take
 253                 # its normal form via str() and try to parse it.
 254                 a = str(a)
 255
 256             try:
 257                 return parser.Expr(a).tosymbolic()
 258             except:
 259                 pass
 260         raise ValueError("%r is NOT a valid SymPy expression" % a)
 261
 262     @Memoizer('Basic', MemoizerArg((type, type(None), tuple), name='type'), return_value_converter = lambda obj: obj.copy())
 263     def atoms(self, type=None):
 264         """Returns the atoms that form current object.
 265
 266         Example:
 267         >>> from sympy import *
 268         >>> x = Symbol('x')
 269         >>> y = Symbol('y')
 270         >>> (x+y**2+ 2*x*y).atoms()
 271         set([2, x, y])
 272
 273         You can also filter the results by a given type(s) of object
 274         >>> (x+y+2+y**2*sin(x)).atoms(type=Symbol)
 275         set([x, y])
 276
 277         >>> (x+y+2+y**2*sin(x)).atoms(type=Number)
 278         set([2])
 279
 280         >>> (x+y+2+y**2*sin(x)).atoms(type=(Symbol, Number))
 281         set([2, x, y])
 282         """
 283         result = set()
 284         if type is not None and not isinstance(type, (type_class, tuple)):
 285             type = Basic.sympify(type).__class__
 286         if isinstance(self, Atom):
 287             if type is None or isinstance(self, type):
 288                 result.add(self)
 289         else:
 290             for obj in self:
 291                 result = result.union(obj.atoms(type=type))
 292         return result
 293
 294     def is_hypergeometric(self, arg):
 295         from sympy.simplify import hypersimp
 296         return hypersimp(self, arg, simplify=False) is not None
 297
 298     def is_fraction(self, syms):
 299         p, q = self.as_numer_denom()
 300
 301         if p.is_polynomial(*syms):
 302             if q.is_polynomial(*syms):
 303                 return True
 304
 305         return False
 306
 307     def _eval_is_polynomial(self, syms):
 308         return
 309
 310     def is_polynomial(self, *syms):
 311         if syms:
 312             syms = map(Basic.sympify, syms)
 313         else:
 314             syms = list(self.atoms(type=Basic.Symbol))
 315
 316         if not syms: # constant polynomial
 317             return True
 318         else:
 319             return self._eval_is_polynomial(syms)
 320
 321     def as_polynomial(self, *syms, **kwargs):
 322         return Basic.Polynomial(self, var=(syms or None), **kwargs)
 323
 324     def _eval_subs(self, old, new):
 325         if self==old:
 326             return new
 327         return self
 328
 329     @cache_it_immutable
 330     def subs(self, old, new):
 331         """Substitutes an expression old -> new."""
 332         old = Basic.sympify(old)
 333         new = Basic.sympify(new)
 334
 335         # TODO This code is a start for issue 264. Currently, uncommenting
 336         #      this code will break A LOT of tests!
 337         #
 338         #if not old.is_dummy:
 339         #    exclude = ['dummy', 'comparable']
 340         #    for x in self._assume_defined:
 341         #        if x in exclude: continue
 342         #        old_val = getattr(old, 'is_' + x)
 343         #        if old_val is not None and old_val != getattr(new, 'is_' + x):
 344         #            raise ValueError("Cannot substitute '%s' for '%s' because assumptions do not match" % (str(new), str(old)))
 345
 346         return self._eval_subs(old, new)
 347
 348     def _seq_subs(self, old, new):
 349         if self==old:
 350             return new
 351         return self.__class__(*[s.subs(old, new) for s in self._args])
 352
 353     def has(self, *patterns):
 354         """
 355         Return True if self has any of the patterns.
 356         """
 357         if len(patterns)>1:
 358             for p in patterns:
 359                 if self.has(p):
 360                     return True
 361             return False
 362         elif not patterns:
 363             raise TypeError("has() requires at least 1 argument (got none)")
 364         p = Basic.sympify(patterns[0])
 365         if isinstance(p, Basic.Symbol) and not isinstance(p, Basic.Wild): # speeds up
 366             return p in self.atoms(p.__class__)
 367         if isinstance(p, BasicType):
 368             #XXX hack, this is very fragile:
 369             if str(self).find(str(p.__name__)) == -1:
 370                 #didn't find p in self
 371                 return False
 372             else:
 373                 return True
 374         if p.matches(self) is not None:
 375             return True
 376         for e in self._args:
 377             if e.has(p):
 378                 return True
 379         return False
 380
 381     def _eval_derivative(self, s):
 382         return
 383
 384     def _eval_integral(self, s):
 385         return
 386
 387     def _eval_defined_integral(self, s, a, b):
 388         return
 389
 390     def _eval_apply(self, *args, **assumptions):
 391         return
 392
 393     def _eval_fapply(self, *args, **assumptions):
 394         return
 395
 396     def _eval_fpower(b, e):
 397         return
 398
 399     def _eval_apply_power(self,b,e):
 400         return
 401
 402     def _eval_apply_evalf(self,*args):
 403         return
 404
 405     def _eval_eq_nonzero(self, other):
 406         return
 407
 408     def _eval_apply_subs(self, *args):
 409         return
 410
 411     def _calc_apply_positive(self, *args):
 412         return
 413
 414     def _calc_apply_real(self, *args):
 415         return
 416
 417     def _eval_conjugate(self):
 418         if self.is_real:
 419             return self
 420
 421     def conjugate(self):
 422         return S.Conjugate(self)
 423
 424     def subs_dict(self, old_new_dict):
 425         r = self
 426         for old,new in old_new_dict.items():
 427             r = r.subs(old,new)
 428         return r
 429
 430     #@classmethod
 431     def matches(pattern, expr, repl_dict={}, evaluate=False):
 432         """
 433         Helper method for match() - switches the pattern and expr.
 434
 435         Can be used to solve linear equations:
 436           >>> from sympy import Symbol, Wild
 437           >>> a,b = map(Symbol, 'ab')
 438           >>> x = Wild('x')
 439           >>> (a+b*x).matches(0)
 440           {x_: -a/b}
 441
 442         """
 443         from sympy.core.mul import Mul
 444         from sympy.core.power import Pow
 445
 446         # weed out negative one prefixes
 447         sign = 1
 448         if isinstance(pattern,Mul) and pattern[0] == -1:
 449           pattern = -pattern; sign = -sign
 450         if isinstance(expr, Mul) and expr[0] == -1:
 451           expr = -expr; sign = -sign
 452
 453         if evaluate:
 454             pat = pattern
 455             for old,new in repl_dict.items():
 456                 pat = pat.subs(old, new)
 457             if pat!=pattern:
 458                 return pat.matches(expr, repl_dict)
 459         expr = Basic.sympify(expr)
 460         if not isinstance(expr, pattern.__class__):
 461             from sympy.core.numbers import Rational
 462             # if we can omit the first factor, we can match it to sign * one
 463             if isinstance(pattern, Mul) and Mul(*pattern[1:]) == expr:
 464                return pattern[0].matches(Rational(sign), repl_dict, evaluate)
 465             # two-factor product: if the 2nd factor matches, the first part must be sign * one
 466             if isinstance(pattern, Mul) and len(pattern[:]) == 2:
 467                dd = pattern[1].matches(expr, repl_dict, evaluate)
 468                if dd == None: return None
 469                dd = pattern[0].matches(Rational(sign), dd, evaluate)
 470                return dd
 471             return None
 472
 473         if len(pattern._args[:])==0:
 474             if pattern==expr:
 475                 return repl_dict
 476             return None
 477         d = repl_dict.copy()
 478
 479         # weed out identical terms
 480         pp = list(pattern._args[:])
 481         ee = list(expr._args[:])
 482         for p in pattern:
 483           for e in expr:
 484             if e == p:
 485               if e in ee: ee.remove(e)
 486               if p in pp: pp.remove(p)
 487
 488         # only one symbol left in pattern -> match the remaining expression
 489         from sympy.core.symbol import Wild
 490         if len(pp) == 1 and isinstance(pp[0], Wild):
 491           if len(ee) == 1: d[pp[0]] = sign * ee[0]
 492           else: d[pp[0]] = sign * (type(expr)(*ee))
 493           return d
 494
 495         if len(ee) != len(pp):
 496             return None
 497
 498         i = 0
 499         for p,e in zip(pp, ee):
 500             if i == 0 and sign != 1:
 501               try: e = sign * e
 502               except TypeError: return None
 503             d = p.matches(e, d, evaluate=not i)
 504             i += 1
 505             if d is None:
 506                 return None
 507         return d
 508
 509     def match(self, pattern):
 510         """
 511         Pattern matching.
 512
 513         Wild symbols match all.
 514
 515         Return None when expression (self) does not match
 516         with pattern. Otherwise return a dictionary such that
 517
 518           pattern.subs_dict(self.match(pattern)) == self
 519
 520         """
 521         pattern = Basic.sympify(pattern)
 522         return pattern.matches(self, {})
 523
 524     def solve4linearsymbol(eqn, rhs, symbols = None):
 525         """ Solve equation
 526           eqn == rhs
 527         with respect to some linear symbol in eqn.
 528         Returns (symbol, solution). If eqn is nonlinear
 529         with respect to all symbols, then return
 530         trivial solution (eqn, rhs).
 531         """
 532         if isinstance(eqn, Basic.Symbol):
 533             return (eqn, rhs)
 534         if symbols is None:
 535             symbols = eqn.atoms(type=Basic.Symbol)
 536         if symbols:
 537             # find  symbol
 538             for s in symbols:
 539                 deqn = eqn.diff(s)
 540                 if isinstance(deqn.diff(s), Basic.Zero):
 541                     # eqn = a + b*c, a=eqn(c=0),b=deqn(c=0)
 542                     return s, (rhs - eqn.subs(s,0))/deqn.subs(s,0)
 543         # no linear symbol, return trivial solution
 544         return eqn, rhs
 545
 546     def _calc_splitter(self, d):
 547         if d.has_key(self):
 548             return d[self]
 549         r = self.__class__(*[t._calc_splitter(d) for t in self])
 550         if d.has_key(r):
 551             return d[r]
 552         s = d[r] = Basic.Temporary()
 553         return s
 554
 555     def splitter(self):
 556         d = {}
 557         r = self._calc_splitter(d)
 558         l = [(s.dummy_index,s,e) for e,s in d.items()]
 559         l.sort()
 560         return [(s,e) for i,s,e in l]
 561
 562     @cache_it_immutable
 563     def count_ops(self, symbolic=True):
 564         """ Return the number of operations in expressions.
 565
 566         Examples:
 567         >>> (1+a+b**2).count_ops()
 568         POW + 2 * ADD
 569         >>> (sin(x)*x+sin(x)**2).count_ops()
 570         ADD + MUL + POW + 2 * SIN
 571         """
 572         return Basic.Integer(len(self[:])-1) + sum([t.count_ops(symbolic=symbolic) for t in self])
 573
 574     def doit(self, **hints):
 575         """Evaluate objects that are not evaluated by default like limits,
 576            integrals, sums and products. All objects of this kind will be
 577            evaluated unless some species were excluded via 'hints'.
 578
 579            >>> from sympy import *
 580            >>> x, y = symbols('xy')
 581
 582            >>> 2*Integral(x, x)
 583            2*Integral(x, x)
 584
 585            >>> (2*Integral(x, x)).doit()
 586            x**2
 587
 588         """
 589         terms = [ term.doit(**hints) for term in self ]
 590         return self.__class__(*terms, **self._assumptions)
 591
 592     ###########################################################################
 593     ################# EXPRESSION REPRESENTATION METHODS #######################
 594     ###########################################################################
 595
 596     def _eval_expand_basic(self, *args):
 597         if isinstance(self, Atom):
 598             return self
 599         terms = [ term._eval_expand_basic(*args) for term in self._args ]
 600         return self.__class__(*terms, **self._assumptions)
 601
 602     def _eval_expand_power(self, *args):
 603         if isinstance(self, Atom):
 604             return self
 605         terms = [ term._eval_expand_power(*args) for term in self._args ]
 606         return self.__class__(*terms, **self._assumptions)
 607
 608     def _eval_expand_complex(self, *args):
 609         if isinstance(self, Atom):
 610             return self
 611         terms = [ term._eval_expand_complex(*args) for term in self._args ]
 612         return self.__class__(*terms, **self._assumptions)
 613
 614     def _eval_expand_trig(self, *args):
 615         if isinstance(self, Atom):
 616             return self
 617         terms = [ term._eval_expand_trig(*args) for term in self._args ]
 618         return self.__class__(*terms, **self._assumptions)
 619
 620     def _eval_expand_func(self, *args):
 621         if isinstance(self, Atom):
 622             return self
 623         terms = [ term._eval_expand_func(*args) for term in self._args ]
 624         return self.__class__(*terms, **self._assumptions)
 625
 626     def expand(self, *args, **hints):
 627         """Expand an expression based on different hints. Currently
 628            supported hints are basic, power, complex, trig and func.
 629         """
 630         obj = self
 631
 632         for hint in hints:
 633             if hints[hint] == True:
 634                 func = getattr(obj, '_eval_expand_'+hint, None)
 635
 636                 if func is not None:
 637                     obj = func(*args)
 638
 639         if hints.get('basic', True):
 640             obj = obj._eval_expand_basic()
 641
 642         return obj
 643
 644     def _eval_rewrite(self, pattern, rule, **hints):
 645         if isinstance(self, Atom):
 646             return self
 647         terms = [ t._eval_rewrite(pattern, rule, **hints) for t in self._args ]
 648         return self.__class__(*terms, **self._assumptions)
 649
 650     def rewrite(self, *args, **hints):
 651         """Rewrites expression containing applications of functions
 652            of one kind in terms of functions of different kind. For
 653            example you can rewrite trigonometric functions as complex
 654            exponentials or combinatorial functions as gamma function.
 655
 656            As a pattern this function accepts a list of functions to
 657            to rewrite (instances of DefinedFunction class). As rule
 658            you can use string or a destinaton function instance (in
 659            this cas rewrite() will use tostr() method).
 660
 661            There is also possibility to pass hints on how to rewrite
 662            the given expressions. For now there is only one such hint
 663            defined called 'deep'. When 'deep' is set to False it will
 664            forbid functions to rewrite their contents.
 665
 666            >>> from sympy import *
 667            >>> x, y = symbols('xy')
 668
 669            >>> sin(x).rewrite(sin, exp)
 670            -1/2*I*(-exp(-I*x) + exp(I*x))
 671
 672         """
 673         if isinstance(self, Atom) or not args:
 674             return self
 675         else:
 676             pattern, rule = args[:-1], args[-1]
 677
 678             if not isinstance(rule, str):
 679                 rule = rule.tostr()
 680
 681             rule = '_eval_rewrite_as_' + rule
 682
 683             if not pattern:
 684                 return self._eval_rewrite(None, rule, **hints)
 685             else:
 686                 if isinstance(pattern[0], (tuple, list)):
 687                     pattern = pattern[0]
 688
 689                 pattern = [ p.__class__ for p in pattern if self.has(p) ]
 690
 691                 if pattern:
 692                     return self._eval_rewrite(tuple(pattern), rule, **hints)
 693                 else:
 694                     return self
 695
 696     def as_coefficient(self, expr):
 697         """Extracts symbolic coefficient at the given expression. In
 698            other words, this functions separates 'self' into product
 699            of 'expr' and 'expr'-free coefficient. If such separation
 700            is not possible it will return None.
 701
 702            >>> from sympy import *
 703            >>> x, y = symbols('xy')
 704
 705            >>> E.as_coefficient(E)
 706            1
 707            >>> (2*E).as_coefficient(E)
 708            2
 709
 710            >>> (2*E + x).as_coefficient(E)
 711            >>> (2*sin(E)*E).as_coefficient(E)
 712
 713            >>> (2*pi*I).as_coefficient(pi*I)
 714            2
 715
 716            >>> (2*I).as_coefficient(pi*I)
 717
 718         """
 719         if isinstance(expr, Basic.Add):
 720             return None
 721         else:
 722             w = Basic.Wild('w')
 723
 724             coeff = self.match(w * expr)
 725
 726             if coeff is not None:
 727                 if isinstance(expr, Basic.Mul):
 728                     expr = expr[:]
 729                 else:
 730                     expr = [expr]
 731
 732                 if coeff[w].has(*expr):
 733                     return None
 734                 else:
 735                     return coeff[w]
 736             else:
 737                 return None
 738
 739     def as_independent(self, *deps):
 740         """Returns a pair with separated parts of a given expression
 741            independent of specified symbols in the first place and
 742            dependend on them in the other. Both parts are valid
 743            SymPy expressions.
 744
 745            >>> from sympy import *
 746            >>> x, y = symbols('xy')
 747
 748            >>> (x*sin(x)*cos(y)).as_independent(x)
 749            (cos(y), x*sin(x))
 750
 751         """
 752         indeps, depend = [], []
 753
 754         if isinstance(self, (Basic.Add, Basic.Mul)):
 755             terms = self[:]
 756         else:
 757             terms = [ self ]
 758
 759         for term in terms:
 760             if term.has(*deps):
 761                 depend.append(term)
 762             else:
 763                 indeps.append(term)
 764
 765         return Basic.Mul(*indeps), Basic.Mul(*depend)
 766
 767     def as_real_imag(self):
 768         """Performs complex expansion on 'self' and returns a tuple
 769            containing collected both real and imaginary parts. This
 770            method can't be confused with re() and im() functions,
 771            which does not perform complex expansion at evaluation.
 772
 773            However it is possible to expand both re() and im()
 774            functions and get exactly the same results as with
 775            a single call to this function.
 776
 777            >>> from sympy import *
 778
 779            >>> x, y = symbols('xy', real=True)
 780
 781            >>> (x + y*I).as_real_imag()
 782            (x, y)
 783
 784            >>> z, w = symbols('zw')
 785
 786            >>> (z + w*I).as_real_imag()
 787            (-im(w) + re(z), re(w) + im(z))
 788
 789         """
 790         expr = self.expand(complex=True)
 791
 792         if not isinstance(expr, Basic.Add):
 793             expr = [expr]
 794
 795         re_part, im_part = [], []
 796
 797         for term in expr:
 798             coeff = term.as_coefficient(S.ImaginaryUnit)
 799
 800             if coeff is None:
 801                 re_part.append(term)
 802             else:
 803                 im_part.append(coeff)
 804
 805         return (Basic.Add(*re_part), Basic.Add(*im_part))
 806
 807     def as_powers_dict(self):
 808         return { self : S.One }
 809
 810     def as_base_exp(self):
 811         # a -> b ** e
 812         return self, Basic.One()
 813
 814     def as_coeff_terms(self, x=None):
 815         # a -> c * t
 816         if x is not None:
 817             if not self.has(x):
 818                 return self, []
 819         return Basic.One(), [self]
 820
 821     def as_indep_terms(self, x):
 822         coeff, terms = self.as_coeff_terms()
 823         indeps = [coeff]
 824         new_terms = []
 825         for t in terms:
 826             if t.has(x):
 827                 new_terms.append(x)
 828             else:
 829                 indeps.append(x)
 830         return Basic.Mul(*indeps), Basic.Mul(*new_terms)
 831
 832     def as_coeff_factors(self, x=None):
 833         # a -> c + f
 834         if x is not None:
 835             if not self.has(x):
 836                 return self, []
 837         return Basic.Zero(), [self]
 838
 839     def as_numer_denom(self):
 840         # a/b -> a,b
 841         base, exp = self.as_base_exp()
 842         coeff, terms = exp.as_coeff_terms()
 843         if coeff.is_negative:
 844             # b**-e -> 1, b**e
 845             return Basic.One(), base ** (-exp)
 846         return self, Basic.One()
 847
 848     def as_expr_orders(self):
 849         """ Split expr + Order(..) to (expr, Order(..)).
 850         """
 851         l1 = []
 852         l2 = []
 853         if isinstance(self, Basic.Add):
 854             for f in self:
 855                 if isinstance(f, Basic.Order):
 856                     l2.append(f)
 857                 else:
 858                     l1.append(f)
 859         elif isinstance(self, Basic.Order):
 860             l2.append(self)
 861         else:
 862             l1.append(self)
 863         return Basic.Add(*l1), Basic.Add(*l2)
 864
 865     def normal(self):
 866         n, d = self.as_numer_denom()
 867         if isinstance(d, Basic.One):
 868             return n
 869         return n/d
 870
 871     ###################################################################################
 872     ##################### DERIVATIVE, INTEGRAL, FUNCTIONAL METHODS ####################
 873     ###################################################################################
 874
 875     def diff(self, *symbols, **assumptions):
 876         new_symbols = []
 877         for s in symbols:
 878             s = Basic.sympify(s)
 879             if isinstance(s, Basic.Integer) and new_symbols:
 880                 last_s = new_symbols.pop()
 881                 i = int(s)
 882                 new_symbols += [last_s] * i
 883             elif isinstance(s, Basic.Symbol):
 884                 new_symbols.append(s)
 885             else:
 886                 raise TypeError(".diff() argument must be Symbol|Integer instance (got %s)" % (s.__class__.__name__))
 887         ret = Basic.Derivative(self, *new_symbols, **assumptions)
 888         return ret
 889
 890     def fdiff(self, *indices):
 891         return Basic.FApply(Basic.FDerivative(*indices), self)
 892
 893     def integral(self, *symbols, **assumptions):
 894         new_symbols = []
 895         for s in symbols:
 896             s = Basic.sympify(s)
 897             if isinstance(s, Basic.Integer) and new_symbols:
 898                 last_s = new_symbols[-1]
 899                 i = int(s)
 900                 new_symbols += [last_s] * (i-1)
 901             elif isinstance(s, (Basic.Symbol, Basic.Equality)):
 902                 new_symbols.append(s)
 903             else:
 904                 raise TypeError(".integral() argument must be Symbol|Integer|Equality instance (got %s)" % (s.__class__.__name__))
 905         return Basic.Integral(self, *new_symbols, **assumptions)
 906
 907     def __call__(self, *args):
 908         return Basic.Apply(self, *args)
 909
 910     def _eval_evalf(self):
 911         return
 912
 913     def _seq_eval_evalf(self):
 914         return self.__class__(*[s.evalf() for s in self])
 915
 916     def __float__(self):
 917         result = self.evalf(precision=16)
 918
 919         if isinstance(result, Basic.Number):
 920             return float(result)
 921         else:
 922             raise ValueError("Symbolic value, can't compute")
 923
 924     def evalf(self, precision=None):
 925         if precision is None:
 926             r = self._eval_evalf()
 927         else:
 928             old_precision = Basic.set_precision(precision)
 929             r = self._eval_evalf()
 930             Basic.set_precision(old_precision)
 931         if r is None:
 932             r = self
 933         return r
 934
 935     ###################################################################################
 936     ##################### SERIES, LEADING TERM, LIMIT, ORDER METHODS ##################
 937     ###################################################################################
 938
 939     def series(self, x, n = 6):
 940         """
 941         Usage
 942         =====
 943             Return the Taylor series around 0 of self with respect to x until
 944             the n-th term (default n is 6).
 945
 946         Notes
 947         =====
 948             For computing power series, use oseries() method.
 949         """
 950         x = Basic.sympify(x)
 951         o = Basic.Order(x**n,x)
 952         r = self.oseries(o)
 953         if r==self:
 954             return self
 955         return r + o
 956
 957     @cache_it_immutable
 958     def oseries(self, order, _cache={}):
 959         """
 960         Return the series of an expression upto given Order symbol.
 961         """
 962         if _cache.has_key((self, order)):
 963             raise RuntimeError('Detected recursion while computing oseries(%s, %s)' % (self, order))
 964         order = Basic.Order(order)
 965         _cache[(self, order)] = 1
 966         if isinstance(order, Basic.Zero):
 967             del _cache[(self, order)]
 968             return self
 969         o = self.is_order
 970         if o is not None:
 971             if o.contains(order):
 972                 del _cache[(self, order)]
 973                 return self
 974         if order.contains(self):
 975             del _cache[(self, order)]
 976             return Basic.Zero()
 977         if len(order.symbols)>1:
 978             r = self
 979             for s in order.symbols:
 980                 o = Basic.Order(order.expr, s)
 981                 r = r.oseries(o)
 982             del _cache[(self, order)]
 983             return r
 984         x = order.symbols[0]
 985         if not self.has(x):
 986             del _cache[(self, order)]
 987             return self
 988         obj = self._eval_oseries(order)
 989         if obj is not None:
 990             obj2 = obj.expand(trig=True)
 991             if obj2 != obj:
 992                 r = obj2.oseries(order)
 993                 del _cache[(self, order)]
 994                 return r
 995             del _cache[(self, order)]
 996             return obj2
 997         del _cache[(self, order)]
 998         raise NotImplementedError('(%s).oseries(%s)' % (self, order))
 999
1000     def _eval_oseries(self, order):
1001         return
1002
1003     def _compute_oseries(self, arg, order, taylor_term, unevaluated_func, correction = 0):
1004         """
1005         compute series sum(taylor_term(i, arg), i=0..n-1) such
1006         that order.contains(taylor_term(n, arg)). Assumes that arg->0 as x->0.
1007         """
1008         x = order.symbols[0]
1009         ln = Basic.Log()
1010         o = Basic.Order(arg, x)
1011         if isinstance(o, Basic.Zero):
1012             return unevaluated_func(arg)
1013         if o.expr==1:
1014             e = ln(order.expr*x)/ln(x)
1015         else:
1016             e = ln(order.expr)/ln(o.expr)
1017         n = e.limit(x,0) + 1 + correction
1018         if n.is_unbounded:
1019             # requested accuracy gives infinite series,
1020             # order is probably nonpolynomial e.g. O(exp(-1/x), x).
1021             return unevaluated_func(arg)
1022         n = int(n)
1023         assert n>=0,`n`
1024         l = []
1025         g = None
1026         for i in xrange(n+2):
1027             g = taylor_term(i, arg, g)
1028             g = g.oseries(order)
1029             l.append(g)
1030         return Basic.Add(*l)
1031
1032     def limit(self, x, xlim, direction='<'):
1033         """ Compute limit x->xlim.
1034         """
1035         return Basic.Limit(self, x, xlim, direction)
1036
1037     def inflimit(self, x): # inflimit has its own cache
1038         x = Basic.sympify(x)
1039         return Basic.InfLimit(self, x)
1040
1041     @cache_it_immutable
1042     def as_leading_term(self, *symbols):
1043         if len(symbols)>1:
1044             c = self
1045             for x in symbols:
1046                 c = c.as_leading_term(x)
1047             return c
1048         elif not symbols:
1049             return self
1050         x = Basic.sympify(symbols[0])
1051         assert isinstance(x, Basic.Symbol),`x`
1052         if not self.has(x):
1053             return self
1054         expr = self.expand(trig=True)
1055         obj = expr._eval_as_leading_term(x)
1056         if obj is not None:
1057             return obj
1058         raise NotImplementedError('as_leading_term(%s, %s)' % (self, x))
1059
1060     def as_coeff_exponent(self, x):
1061         """ c*x**e -> c,e where x can be any symbolic expression.
1062         """
1063         x = Basic.sympify(x)
1064         wc = Basic.Wild()
1065         we = Basic.Wild()
1066         c, terms = self.as_coeff_terms()
1067         p  = wc*x**we
1068         d = self.match(p)
1069         if d is not None:
1070             return d[wc], d[we]
1071         return self, Basic.Zero()
1072
1073     def ldegree(self, x):
1074         x = Basic.sympify(x)
1075         c,e = self.as_leading_term(x).as_coeff_exponent(x)
1076         if not c.has(x):
1077             return e
1078         raise ValueError("cannot compute ldegree(%s, %s), got c=%s" % (self, x, c))
1079
1080     def leadterm(self, x):
1081         x = Basic.sympify(x)
1082         c,e = self.as_leading_term(x).as_coeff_exponent(x)
1083         if not c.has(x):
1084             return c,e
1085         raise ValueError("cannot compute ldegree(%s, %s), got c=%s" % (self, x, c))
1086
1087     ##########################################################################
1088     ##################### END OF BASIC CLASS #################################
1089     ##########################################################################
1090
1091 class Atom(Basic):
1092
1093     precedence = Basic.Atom_precedence
1094
1095     def _eval_derivative(self, s):
1096         if self==s: return Basic.One()
1097         return Basic.Zero()
1098
1099     def pattern_match(pattern, expr, repl_dict):
1100         if pattern==expr:
1101             return repl_dict
1102         return None
1103
1104     def as_numer_denom(self):
1105         return self, Basic.One()
1106
1107     def _calc_splitter(self, d):
1108         return self
1109
1110     def count_ops(self, symbolic=True):
1111         return Basic.Zero()
1112
1113     def doit(self, **hints):
1114         return self
1115
1116     def _eval_integral(self, s):
1117         if s==self:
1118             return self**2/2
1119         return self*s
1120
1121     def _eval_defined_integral(self, s, a, b):
1122         if s==self:
1123             return (b**2-a**2)/2
1124         return self*(b-a)
1125
1126     def _eval_is_polynomial(self, syms):
1127         return True
1128
1129     def _eval_oseries(self, order):
1130         # .oseries() method checks for order.contains(self)
1131         return self
1132
1133     def _eval_as_leading_term(self, x):
1134         return self
1135
1136
1137 class Singleton(Basic):
1138     """ Singleton object.
1139     """
1140
1141     def __new__(cls, *args, **assumptions):
1142         # if you need to overload __new__, then
1143         # use the same code as below to ensure
1144         # that only one instance of Singleton
1145         # class is created.
1146         obj = Singleton.__dict__.get(cls.__name__)
1147         if obj is None:
1148             obj = Basic.__new__(cls,*args,**assumptions)
1149             setattr(Singleton, cls.__name__, obj)
1150         return obj
1151
1152 class SingletonFactory:
1153     """
1154     A map between singleton classes and the corresponding instances.
1155     E.g. S.Exp == Basic.Exp()
1156     """
1157
1158     def __getattr__(self, clsname):
1159         if clsname == "__repr__":
1160             return lambda: "S"
1161         obj = Singleton.__dict__.get(clsname)
1162         if obj is None:
1163             cls = getattr(Basic, clsname)
1164             assert issubclass(cls, Singleton),`cls`
1165             obj = cls()
1166             setattr(self, clsname, obj)
1167         return obj
1168
1169 S = SingletonFactory()
1170
1171 import parser