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         elif hasattr(a, "_sympy_"):
 243             # the "a" implements _sympy_() method, that returns a SymPy
 244             # expression (by definition), so we just use it
 245             return a._sympy_()
 246         else:
 247             # XXX this is here because of cyclic-import issues
 248             from sympy.matrices import Matrix
 249
 250             if isinstance(a, Matrix):
 251                 raise NotImplementedError('matrix support')
 252
 253             if not isinstance(a, str):
 254                 # At this point we were given an arbitrary expression
 255                 # which does not inherit from Basic and doesn't implement
 256                 # _sympy_ (which is a canonical and robust way to convert
 257                 # anything to SymPy expression).
 258                 #
 259                 # As a last chance, we try to take "a"'s  normal form via str()
 260                 # and try to parse it. If it fails, then we have no luck and
 261                 # return an exception
 262                 a = str(a)
 263
 264             try:
 265                 return parser.Expr(a).tosymbolic()
 266             except:
 267                 pass
 268         if a.strip() != a:
 269             return Basic.sympify(a.strip())
 270         raise ValueError("%r is NOT a valid SymPy expression" % a)
 271
 272     @Memoizer('Basic', MemoizerArg((type, type(None), tuple), name='type'), return_value_converter = lambda obj: obj.copy())
 273     def atoms(self, type=None):
 274         """Returns the atoms that form current object.
 275
 276         Example:
 277         >>> from sympy import *
 278         >>> x = Symbol('x')
 279         >>> y = Symbol('y')
 280         >>> (x+y**2+ 2*x*y).atoms()
 281         set([2, x, y])
 282
 283         You can also filter the results by a given type(s) of object
 284         >>> (x+y+2+y**2*sin(x)).atoms(type=Symbol)
 285         set([x, y])
 286
 287         >>> (x+y+2+y**2*sin(x)).atoms(type=Number)
 288         set([2])
 289
 290         >>> (x+y+2+y**2*sin(x)).atoms(type=(Symbol, Number))
 291         set([2, x, y])
 292         """
 293         result = set()
 294         if type is not None and not isinstance(type, (type_class, tuple)):
 295             type = Basic.sympify(type).__class__
 296         if isinstance(self, Atom):
 297             if type is None or isinstance(self, type):
 298                 result.add(self)
 299         else:
 300             for obj in self:
 301                 result = result.union(obj.atoms(type=type))
 302         return result
 303
 304     def is_hypergeometric(self, arg):
 305         from sympy.simplify import hypersimp
 306         return hypersimp(self, arg, simplify=False) is not None
 307
 308     @property
 309     def is_number(self):
 310         """Returns True if self is a number (like 1, or 1+log(2)), and False
 311         otherwise (e.g. 1+x)."""
 312         return len(self.atoms(Basic.Symbol)) == 0
 313
 314     def is_fraction(self, syms):
 315         p, q = self.as_numer_denom()
 316
 317         if p.is_polynomial(*syms):
 318             if q.is_polynomial(*syms):
 319                 return True
 320
 321         return False
 322
 323     def _eval_is_polynomial(self, syms):
 324         return
 325
 326     def is_polynomial(self, *syms):
 327         if syms:
 328             syms = map(Basic.sympify, syms)
 329         else:
 330             syms = list(self.atoms(type=Basic.Symbol))
 331
 332         if not syms: # constant polynomial
 333             return True
 334         else:
 335             return self._eval_is_polynomial(syms)
 336
 337     def as_polynomial(self, *syms, **kwargs):
 338         return Basic.Polynomial(self, var=(syms or None), **kwargs)
 339
 340     def _eval_subs(self, old, new):
 341         if self==old:
 342             return new
 343         return self
 344
 345     @cache_it_immutable
 346     def subs(self, old, new):
 347         """Substitutes an expression old -> new."""
 348         old = Basic.sympify(old)
 349         new = Basic.sympify(new)
 350
 351         # TODO This code is a start for issue 264. Currently, uncommenting
 352         #      this code will break A LOT of tests!
 353         #
 354         #if not old.is_dummy:
 355         #    exclude = ['dummy', 'comparable']
 356         #    for x in self._assume_defined:
 357         #        if x in exclude: continue
 358         #        old_val = getattr(old, 'is_' + x)
 359         #        if old_val is not None and old_val != getattr(new, 'is_' + x):
 360         #            raise ValueError("Cannot substitute '%s' for '%s' because assumptions do not match" % (str(new), str(old)))
 361
 362         #print self, old, new
 363         return self._eval_subs(old, new)
 364
 365     def _seq_subs(self, old, new):
 366         if self==old:
 367             return new
 368         #new functions are initialized differently, than old functions
 369         from sympy.core.function import FunctionClass
 370         if isinstance(self.func, FunctionClass):
 371             args = self[:]
 372         else:
 373             args = (self.func,)+self[:]
 374         return self.__class__(*[s.subs(old, new) for s in args])
 375
 376     def has(self, *patterns):
 377         """
 378         Return True if self has any of the patterns.
 379         """
 380         if len(patterns)>1:
 381             for p in patterns:
 382                 if self.has(p):
 383                     return True
 384             return False
 385         elif not patterns:
 386             raise TypeError("has() requires at least 1 argument (got none)")
 387         p = Basic.sympify(patterns[0])
 388         if isinstance(p, Basic.Symbol) and not isinstance(p, Basic.Wild): # speeds up
 389             return p in self.atoms(p.__class__)
 390         if isinstance(p, BasicType):
 391             #XXX hack, this is very fragile:
 392             if str(self).find(str(p.__name__)) == -1:
 393                 #didn't find p in self
 394                 return False
 395             else:
 396                 return True
 397         if p.matches(self) is not None:
 398             return True
 399         if not False:
 400             args = self[:]
 401         else:
 402             args = (self.func,)+self[:]
 403         for e in args:
 404             if e.has(p):
 405                 return True
 406         return False
 407
 408     def _eval_derivative(self, s):
 409         return
 410
 411     def _eval_integral(self, s):
 412         return
 413
 414     def _eval_defined_integral(self, s, a, b):
 415         return
 416
 417     def _eval_fapply(self, *args, **assumptions):
 418         return
 419
 420     def _eval_fpower(b, e):
 421         return
 422
 423     def _eval_apply_power(self,b,e):
 424         return
 425
 426     def _eval_apply_evalf(self,*args):
 427         return
 428
 429     def _eval_eq_nonzero(self, other):
 430         return
 431
 432     @classmethod
 433     def _eval_apply_subs(cls, *args):
 434         return
 435
 436     def _calc_apply_positive(self, *args):
 437         return
 438
 439     def _calc_apply_real(self, *args):
 440         return
 441
 442     def _eval_conjugate(self):
 443         if self.is_real:
 444             return self
 445
 446     def conjugate(self):
 447         from sympy.functions.elementary.complexes import conjugate as c
 448         return c(self)
 449
 450     def subs_dict(self, old_new_dict):
 451         r = self
 452         for old,new in old_new_dict.items():
 453             r = r.subs(old,new)
 454         return r
 455
 456     #@classmethod
 457     def matches(pattern, expr, repl_dict={}, evaluate=False):
 458         """
 459         Helper method for match() - switches the pattern and expr.
 460
 461         Can be used to solve linear equations:
 462           >>> from sympy import Symbol, Wild
 463           >>> a,b = map(Symbol, 'ab')
 464           >>> x = Wild('x')
 465           >>> (a+b*x).matches(0)
 466           {x_: -a/b}
 467
 468         """
 469         from sympy.core.mul import Mul
 470         from sympy.core.power import Pow
 471
 472         # weed out negative one prefixes
 473         sign = 1
 474         if isinstance(pattern,Mul) and pattern[0] == -1:
 475           pattern = -pattern; sign = -sign
 476         if isinstance(expr, Mul) and expr[0] == -1:
 477           expr = -expr; sign = -sign
 478
 479         if evaluate:
 480             pat = pattern
 481             for old,new in repl_dict.items():
 482                 pat = pat.subs(old, new)
 483             if pat!=pattern:
 484                 return pat.matches(expr, repl_dict)
 485         expr = Basic.sympify(expr)
 486         if not isinstance(expr, pattern.__class__):
 487             from sympy.core.numbers import Rational
 488             # if we can omit the first factor, we can match it to sign * one
 489             if isinstance(pattern, Mul) and Mul(*pattern[1:]) == expr:
 490                return pattern[0].matches(Rational(sign), repl_dict, evaluate)
 491             # two-factor product: if the 2nd factor matches, the first part must be sign * one
 492             if isinstance(pattern, Mul) and len(pattern[:]) == 2:
 493                dd = pattern[1].matches(expr, repl_dict, evaluate)
 494                if dd == None: return None
 495                dd = pattern[0].matches(Rational(sign), dd, evaluate)
 496                return dd
 497             return None
 498
 499         if len(pattern[:])==0:
 500             if pattern==expr:
 501                 return repl_dict
 502             return None
 503         d = repl_dict.copy()
 504
 505         # weed out identical terms
 506         pp = list(pattern)
 507         ee = list(expr)
 508         for p in pattern:
 509           for e in expr:
 510             if e == p:
 511               if e in ee: ee.remove(e)
 512               if p in pp: pp.remove(p)
 513
 514         # only one symbol left in pattern -> match the remaining expression
 515         from sympy.core.symbol import Wild
 516         if len(pp) == 1 and isinstance(pp[0], Wild):
 517           if len(ee) == 1: d[pp[0]] = sign * ee[0]
 518           else: d[pp[0]] = sign * (type(expr)(*ee))
 519           return d
 520
 521         if len(ee) != len(pp):
 522             return None
 523
 524         i = 0
 525         for p,e in zip(pp, ee):
 526             if i == 0 and sign != 1:
 527               try: e = sign * e
 528               except TypeError: return None
 529             d = p.matches(e, d, evaluate=not i)
 530             i += 1
 531             if d is None:
 532                 return None
 533         return d
 534
 535     def match(self, pattern):
 536         """
 537         Pattern matching.
 538
 539         Wild symbols match all.
 540
 541         Return None when expression (self) does not match
 542         with pattern. Otherwise return a dictionary such that
 543
 544           pattern.subs_dict(self.match(pattern)) == self
 545
 546         """
 547         pattern = Basic.sympify(pattern)
 548         return pattern.matches(self, {})
 549
 550     def solve4linearsymbol(eqn, rhs, symbols = None):
 551         """ Solve equation
 552           eqn == rhs
 553         with respect to some linear symbol in eqn.
 554         Returns (symbol, solution). If eqn is nonlinear
 555         with respect to all symbols, then return
 556         trivial solution (eqn, rhs).
 557         """
 558         if isinstance(eqn, Basic.Symbol):
 559             return (eqn, rhs)
 560         if symbols is None:
 561             symbols = eqn.atoms(type=Basic.Symbol)
 562         if symbols:
 563             # find  symbol
 564             for s in symbols:
 565                 deqn = eqn.diff(s)
 566                 if isinstance(deqn.diff(s), Basic.Zero):
 567                     # eqn = a + b*c, a=eqn(c=0),b=deqn(c=0)
 568                     return s, (rhs - eqn.subs(s,0))/deqn.subs(s,0)
 569         # no linear symbol, return trivial solution
 570         return eqn, rhs
 571
 572     def _calc_splitter(self, d):
 573         if d.has_key(self):
 574             return d[self]
 575         r = self.__class__(*[t._calc_splitter(d) for t in self])
 576         if d.has_key(r):
 577             return d[r]
 578         s = d[r] = Basic.Temporary()
 579         return s
 580
 581     def splitter(self):
 582         d = {}
 583         r = self._calc_splitter(d)
 584         l = [(s.dummy_index,s,e) for e,s in d.items()]
 585         l.sort()
 586         return [(s,e) for i,s,e in l]
 587
 588     @cache_it_immutable
 589     def count_ops(self, symbolic=True):
 590         """ Return the number of operations in expressions.
 591
 592         Examples:
 593         >>> (1+a+b**2).count_ops()
 594         POW + 2 * ADD
 595         >>> (sin(x)*x+sin(x)**2).count_ops()
 596         ADD + MUL + POW + 2 * SIN
 597         """
 598         return Basic.Integer(len(self[:])-1) + sum([t.count_ops(symbolic=symbolic) for t in self])
 599
 600     def doit(self, **hints):
 601         """Evaluate objects that are not evaluated by default like limits,
 602            integrals, sums and products. All objects of this kind will be
 603            evaluated unless some species were excluded via 'hints'.
 604
 605            >>> from sympy import *
 606            >>> x, y = symbols('xy')
 607
 608            >>> 2*Integral(x, x)
 609            2*Integral(x, x)
 610
 611            >>> (2*Integral(x, x)).doit()
 612            x**2
 613
 614         """
 615         terms = [ term.doit(**hints) for term in self ]
 616         return self.__class__(*terms, **self._assumptions)
 617
 618     ###########################################################################
 619     ################# EXPRESSION REPRESENTATION METHODS #######################
 620     ###########################################################################
 621
 622     def _eval_expand_basic(self, *args):
 623         if isinstance(self, Atom):
 624             return self
 625         sargs = self[:]
 626         terms = [ term._eval_expand_basic(*args) for term in sargs ]
 627         return self.__class__(*terms, **self._assumptions)
 628
 629     def _eval_expand_power(self, *args):
 630         if isinstance(self, Atom):
 631             return self
 632         if not isinstance(self, Basic.Apply):
 633             sargs = self[:]
 634         else:
 635             sargs = (self.func,)+self[:]
 636         terms = [ term._eval_expand_power(*args) for term in sargs ]
 637         return self.__class__(*terms, **self._assumptions)
 638
 639     def _eval_expand_complex(self, *args):
 640         if isinstance(self, Atom):
 641             return self
 642         sargs = self[:]
 643         terms = [ term._eval_expand_complex(*args) for term in sargs ]
 644         return self.__class__(*terms, **self._assumptions)
 645
 646     def _eval_expand_trig(self, *args):
 647         if isinstance(self, Atom):
 648             return self
 649         sargs = self[:]
 650         terms = [ term._eval_expand_trig(*args) for term in sargs ]
 651         return self.__class__(*terms, **self._assumptions)
 652
 653     def _eval_expand_func(self, *args):
 654         if isinstance(self, Atom):
 655             return self
 656         sargs = self[:]
 657         terms = [ term._eval_expand_func(*args) for term in sargs ]
 658         return self.__class__(*terms, **self._assumptions)
 659
 660     def expand(self, *args, **hints):
 661         """Expand an expression based on different hints. Currently
 662            supported hints are basic, power, complex, trig and func.
 663         """
 664         obj = self
 665
 666         for hint in hints:
 667             if hints[hint] == True:
 668                 func = getattr(obj, '_eval_expand_'+hint, None)
 669
 670                 if func is not None:
 671                     obj = func(*args)
 672
 673         if hints.get('basic', True):
 674             obj = obj._eval_expand_basic()
 675
 676         return obj
 677
 678     def _eval_rewrite(self, pattern, rule, **hints):
 679         if isinstance(self, Atom):
 680             return self
 681         sargs = self[:]
 682         terms = [ t._eval_rewrite(pattern, rule, **hints) for t in sargs ]
 683         return self.__class__(*terms, **self._assumptions)
 684
 685     def rewrite(self, *args, **hints):
 686         """Rewrites expression containing applications of functions
 687            of one kind in terms of functions of different kind. For
 688            example you can rewrite trigonometric functions as complex
 689            exponentials or combinatorial functions as gamma function.
 690
 691            As a pattern this function accepts a list of functions to
 692            to rewrite (instances of DefinedFunction class). As rule
 693            you can use string or a destinaton function instance (in
 694            this cas rewrite() will use tostr() method).
 695
 696            There is also possibility to pass hints on how to rewrite
 697            the given expressions. For now there is only one such hint
 698            defined called 'deep'. When 'deep' is set to False it will
 699            forbid functions to rewrite their contents.
 700
 701            >>> from sympy import *
 702            >>> x, y = symbols('xy')
 703
 704            >>> sin(x).rewrite(sin, exp)
 705            -1/2*I*(-exp(-I*x) + exp(I*x))
 706
 707         """
 708         if isinstance(self, Atom) or not args:
 709             return self
 710         else:
 711             pattern, rule = args[:-1], args[-1]
 712
 713             if not isinstance(rule, str):
 714                 # XXX move me out of here (cyclic imports)
 715                 from function import FunctionClass
 716
 717                 if rule == Basic.tan:
 718                     rule = "tan"
 719                 elif rule == Basic.exp:
 720                     rule = "exp"
 721                 elif isinstance(rule, FunctionClass):   # new-style functions
 722                     #print rule
 723                     rule = rule.__name__  # XXX proper attribute for name?
 724                     #print rule
 725                 else:
 726                     rule = rule.tostr()
 727
 728             rule = '_eval_rewrite_as_' + rule
 729
 730             if not pattern:
 731                 return self._eval_rewrite(None, rule, **hints)
 732             else:
 733                 if isinstance(pattern[0], (tuple, list)):
 734                     pattern = pattern[0]
 735
 736                 pattern = [ p.__class__ for p in pattern if self.has(p) ]
 737
 738                 if pattern:
 739                     return self._eval_rewrite(tuple(pattern), rule, **hints)
 740                 else:
 741                     return self
 742
 743     def as_coefficient(self, expr):
 744         """Extracts symbolic coefficient at the given expression. In
 745            other words, this functions separates 'self' into product
 746            of 'expr' and 'expr'-free coefficient. If such separation
 747            is not possible it will return None.
 748
 749            >>> from sympy import *
 750            >>> x, y = symbols('xy')
 751
 752            >>> E.as_coefficient(E)
 753            1
 754            >>> (2*E).as_coefficient(E)
 755            2
 756
 757            >>> (2*E + x).as_coefficient(E)
 758            >>> (2*sin(E)*E).as_coefficient(E)
 759
 760            >>> (2*pi*I).as_coefficient(pi*I)
 761            2
 762
 763            >>> (2*I).as_coefficient(pi*I)
 764
 765         """
 766         if isinstance(expr, Basic.Add):
 767             return None
 768         else:
 769             w = Basic.Wild('w')
 770
 771             coeff = self.match(w * expr)
 772
 773             if coeff is not None:
 774                 if isinstance(expr, Basic.Mul):
 775                     expr = expr[:]
 776                 else:
 777                     expr = [expr]
 778
 779                 if coeff[w].has(*expr):
 780                     return None
 781                 else:
 782                     return coeff[w]
 783             else:
 784                 return None
 785
 786     def as_independent(self, *deps):
 787         """Returns a pair with separated parts of a given expression
 788            independent of specified symbols in the first place and
 789            dependend on them in the other. Both parts are valid
 790            SymPy expressions.
 791
 792            >>> from sympy import *
 793            >>> x, y = symbols('xy')
 794
 795            >>> (x*sin(x)*cos(y)).as_independent(x)
 796            (cos(y), x*sin(x))
 797
 798         """
 799         indeps, depend = [], []
 800
 801         if isinstance(self, (Basic.Add, Basic.Mul)):
 802             terms = self[:]
 803         else:
 804             terms = [ self ]
 805
 806         for term in terms:
 807             if term.has(*deps):
 808                 depend.append(term)
 809             else:
 810                 indeps.append(term)
 811
 812         return Basic.Mul(*indeps), Basic.Mul(*depend)
 813
 814     def as_real_imag(self):
 815         """Performs complex expansion on 'self' and returns a tuple
 816            containing collected both real and imaginary parts. This
 817            method can't be confused with re() and im() functions,
 818            which does not perform complex expansion at evaluation.
 819
 820            However it is possible to expand both re() and im()
 821            functions and get exactly the same results as with
 822            a single call to this function.
 823
 824            >>> from sympy import *
 825
 826            >>> x, y = symbols('xy', real=True)
 827
 828            >>> (x + y*I).as_real_imag()
 829            (x, y)
 830
 831            >>> z, w = symbols('zw')
 832
 833            >>> (z + w*I).as_real_imag()
 834            (-im(w) + re(z), im(z) + re(w))
 835
 836         """
 837         expr = self.expand(complex=True)
 838
 839         if not isinstance(expr, Basic.Add):
 840             expr = [expr]
 841
 842         re_part, im_part = [], []
 843
 844         for term in expr:
 845             coeff = term.as_coefficient(S.ImaginaryUnit)
 846
 847             if coeff is None:
 848                 re_part.append(term)
 849             else:
 850                 im_part.append(coeff)
 851
 852         return (Basic.Add(*re_part), Basic.Add(*im_part))
 853
 854     def as_powers_dict(self):
 855         return { self : S.One }
 856
 857     def as_base_exp(self):
 858         # a -> b ** e
 859         return self, Basic.One()
 860
 861     def as_coeff_terms(self, x=None):
 862         # a -> c * t
 863         if x is not None:
 864             if not self.has(x):
 865                 return self, []
 866         return Basic.One(), [self]
 867
 868     def as_indep_terms(self, x):
 869         coeff, terms = self.as_coeff_terms()
 870         indeps = [coeff]
 871         new_terms = []
 872         for t in terms:
 873             if t.has(x):
 874                 new_terms.append(x)
 875             else:
 876                 indeps.append(x)
 877         return Basic.Mul(*indeps), Basic.Mul(*new_terms)
 878
 879     def as_coeff_factors(self, x=None):
 880         # a -> c + f
 881         if x is not None:
 882             if not self.has(x):
 883                 return self, []
 884         return Basic.Zero(), [self]
 885
 886     def as_numer_denom(self):
 887         # a/b -> a,b
 888         base, exp = self.as_base_exp()
 889         coeff, terms = exp.as_coeff_terms()
 890         if coeff.is_negative:
 891             # b**-e -> 1, b**e
 892             return Basic.One(), base ** (-exp)
 893         return self, Basic.One()
 894
 895     def as_expr_orders(self):
 896         """ Split expr + Order(..) to (expr, Order(..)).
 897         """
 898         l1 = []
 899         l2 = []
 900         if isinstance(self, Basic.Add):
 901             for f in self:
 902                 if isinstance(f, Basic.Order):
 903                     l2.append(f)
 904                 else:
 905                     l1.append(f)
 906         elif isinstance(self, Basic.Order):
 907             l2.append(self)
 908         else:
 909             l1.append(self)
 910         return Basic.Add(*l1), Basic.Add(*l2)
 911
 912     def normal(self):
 913         n, d = self.as_numer_denom()
 914         if isinstance(d, Basic.One):
 915             return n
 916         return n/d
 917
 918     ###################################################################################
 919     ##################### DERIVATIVE, INTEGRAL, FUNCTIONAL METHODS ####################
 920     ###################################################################################
 921
 922     def diff(self, *symbols, **assumptions):
 923         new_symbols = []
 924         for s in symbols:
 925             s = Basic.sympify(s)
 926             if isinstance(s, Basic.Integer) and new_symbols:
 927                 last_s = new_symbols.pop()
 928                 i = int(s)
 929                 new_symbols += [last_s] * i
 930             elif isinstance(s, Basic.Symbol):
 931                 new_symbols.append(s)
 932             else:
 933                 raise TypeError(".diff() argument must be Symbol|Integer instance (got %s)" % (s.__class__.__name__))
 934         ret = Basic.Derivative(self, *new_symbols, **assumptions)
 935         return ret
 936
 937     def fdiff(self, *indices):
 938         return Basic.FApply(Basic.FDerivative(*indices), self)
 939
 940     def integral(self, *symbols, **assumptions):
 941         new_symbols = []
 942         for s in symbols:
 943             s = Basic.sympify(s)
 944             if isinstance(s, Basic.Integer) and new_symbols:
 945                 last_s = new_symbols[-1]
 946                 i = int(s)
 947                 new_symbols += [last_s] * (i-1)
 948             elif isinstance(s, (Basic.Symbol, Basic.Equality)):
 949                 new_symbols.append(s)
 950             else:
 951                 raise TypeError(".integral() argument must be Symbol|Integer|Equality instance (got %s)" % (s.__class__.__name__))
 952         return Basic.Integral(self, *new_symbols, **assumptions)
 953
 954     #XXX fix the removeme
 955     def __call__(self, *args, **removeme):
 956         return Basic.SingleValuedFunction(self[0])(*args)
 957         print self, args
 958         return Basic.Apply(self, *args)
 959
 960     def _eval_evalf(self):
 961         return
 962
 963     def _seq_eval_evalf(self):
 964         return self.__class__(*[s.evalf() for s in self])
 965
 966     def __float__(self):
 967         result = self.evalf(precision=16)
 968
 969         if isinstance(result, Basic.Number):
 970             return float(result)
 971         else:
 972             raise ValueError("Symbolic value, can't compute")
 973
 974     def evalf(self, precision=None):
 975         if precision is None:
 976             r = self._eval_evalf()
 977         else:
 978             old_precision = Basic.set_precision(precision)
 979             r = self._eval_evalf()
 980             Basic.set_precision(old_precision)
 981         if r is None:
 982             r = self
 983         return r
 984
 985     ###################################################################################
 986     ##################### SERIES, LEADING TERM, LIMIT, ORDER METHODS ##################
 987     ###################################################################################
 988
 989     def series(self, x, n = 6):
 990         """
 991         Usage
 992         =====
 993             Return the Taylor series around 0 of self with respect to x until
 994             the n-th term (default n is 6).
 995
 996         Notes
 997         =====
 998             This method is the most high level method and it returns the
 999             series including the O(x**n) term.
1000
1001             Internally, it executes a method oseries(), which takes an
1002             O instance as the only parameter and it is responsible for
1003             returning a series (without the O term) up to the given order.
1004         """
1005         x = Basic.sympify(x)
1006         o = Basic.Order(x**n,x)
1007         r = self.oseries(o)
1008         if r==self:
1009             return self
1010         return r + o
1011
1012     @cache_it_immutable
1013     def oseries(self, order, _cache={}):
1014         """
1015         Return the series of an expression upto given Order symbol (without the
1016         actual O term).
1017
1018         The general philosophy is this: simply start with the most simple
1019         taylor (laurent) term and calculate one be one and use
1020         order.contains(term) method to determine if your term is still
1021         significant and should be added to the series, or we should stop.
1022
1023         The _cache parameter is not meant to be used by a user. It is here only
1024         to detect an infinite recursion.
1025         """
1026         #is the _cache mechanism really necessary? I think it could be removed
1027         #completely, it's only slowing things down (well, probably negligibly).
1028         #python can also detect an infinite recursion, so I am for removing
1029         #_cache. --Ondrej
1030         if _cache.has_key((self, order)):
1031             raise RuntimeError('Detected recursion while computing oseries(%s, %s)' % (self, order))
1032         order = Basic.Order(order)
1033         _cache[(self, order)] = 1
1034         if isinstance(order, Basic.Zero):
1035             del _cache[(self, order)]
1036             return self
1037         if order.contains(self):
1038             del _cache[(self, order)]
1039             return Basic.Zero()
1040         if len(order.symbols)>1:
1041             r = self
1042             for s in order.symbols:
1043                 o = Basic.Order(order.expr, s)
1044                 r = r.oseries(o)
1045             del _cache[(self, order)]
1046             return r
1047         x = order.symbols[0]
1048         if not self.has(x):
1049             del _cache[(self, order)]
1050             return self
1051         obj = self._eval_oseries(order)
1052         if obj is not None:
1053             #obj2 = obj.expand(trig=True)
1054             obj2 = obj.expand()
1055             if obj2 != obj:
1056                 r = obj2.oseries(order)
1057                 del _cache[(self, order)]
1058                 return r
1059             del _cache[(self, order)]
1060             return obj
1061         del _cache[(self, order)]
1062         raise NotImplementedError('(%s).oseries(%s)' % (self, order))
1063
1064     def _eval_oseries(self, order):
1065         return
1066
1067     def _compute_oseries(self, arg, order, taylor_term, unevaluated_func, correction = 0):
1068         """
1069         compute series sum(taylor_term(i, arg), i=0..n-1) such
1070         that order.contains(taylor_term(n, arg)). Assumes that arg->0 as x->0.
1071         """
1072         x = order.symbols[0]
1073         ln = Basic.log
1074         o = Basic.Order(arg, x)
1075         if isinstance(o, Basic.Zero):
1076             return unevaluated_func(arg)
1077         if o.expr==1:
1078             e = ln(order.expr*x)/ln(x)
1079         else:
1080             e = ln(order.expr)/ln(o.expr)
1081         n = e.limit(x,0) + 1 + correction
1082         if n.is_unbounded:
1083             # requested accuracy gives infinite series,
1084             # order is probably nonpolynomial e.g. O(exp(-1/x), x).
1085             return unevaluated_func(arg)
1086         try:
1087             n = int(n)
1088         except TypeError:
1089             #well, the n is something more complicated (like 1+log(2))
1090             n = int(n.evalf()) + 1
1091         assert n>=0,`n`
1092         l = []
1093         g = None
1094         for i in xrange(n+2):
1095             g = taylor_term(i, arg, g)
1096             g = g.oseries(order)
1097             l.append(g)
1098         return Basic.Add(*l)
1099
1100     def limit(self, x, xlim, direction='<'):
1101         """ Compute limit x->xlim.
1102         """
1103         from sympy.series.limits_series import Limit
1104         return Limit(self, x, xlim, direction)
1105
1106     def inflimit(self, x): # inflimit has its own cache
1107         x = Basic.sympify(x)
1108         from sympy.series.limits_series import InfLimit
1109         return InfLimit(self, x)
1110
1111     @cache_it_immutable
1112     def as_leading_term(self, *symbols):
1113         if len(symbols)>1:
1114             c = self
1115             for x in symbols:
1116                 c = c.as_leading_term(x)
1117             return c
1118         elif not symbols:
1119             return self
1120         x = Basic.sympify(symbols[0])
1121         assert isinstance(x, Basic.Symbol),`x`
1122         if not self.has(x):
1123             return self
1124         expr = self.expand(trig=True)
1125         obj = expr._eval_as_leading_term(x)
1126         if obj is not None:
1127             return obj
1128         raise NotImplementedError('as_leading_term(%s, %s)' % (self, x))
1129
1130     def as_coeff_exponent(self, x):
1131         """ c*x**e -> c,e where x can be any symbolic expression.
1132         """
1133         x = Basic.sympify(x)
1134         wc = Basic.Wild()
1135         we = Basic.Wild()
1136         c, terms = self.as_coeff_terms()
1137         p  = wc*x**we
1138         d = self.match(p)
1139         if d is not None:
1140             return d[wc], d[we]
1141         return self, Basic.Zero()
1142
1143     def ldegree(self, x):
1144         x = Basic.sympify(x)
1145         c,e = self.as_leading_term(x).as_coeff_exponent(x)
1146         if not c.has(x):
1147             return e
1148         raise ValueError("cannot compute ldegree(%s, %s), got c=%s" % (self, x, c))
1149
1150     def leadterm(self, x):
1151         x = Basic.sympify(x)
1152         c,e = self.as_leading_term(x).as_coeff_exponent(x)
1153         if not c.has(x):
1154             return c,e
1155         raise ValueError("cannot compute ldegree(%s, %s), got c=%s" % (self, x, c))
1156
1157     ##########################################################################
1158     ##################### END OF BASIC CLASS #################################
1159     ##########################################################################
1160
1161 class Atom(Basic):
1162
1163     precedence = Basic.Atom_precedence
1164
1165     def _eval_derivative(self, s):
1166         if self==s: return Basic.One()
1167         return Basic.Zero()
1168
1169     def pattern_match(pattern, expr, repl_dict):
1170         if pattern==expr:
1171             return repl_dict
1172         return None
1173
1174     def as_numer_denom(self):
1175         return self, Basic.One()
1176
1177     def _calc_splitter(self, d):
1178         return self
1179
1180     def count_ops(self, symbolic=True):
1181         return Basic.Zero()
1182
1183     def doit(self, **hints):
1184         return self
1185
1186     def _eval_integral(self, s):
1187         if s==self:
1188             return self**2/2
1189         return self*s
1190
1191     def _eval_defined_integral(self, s, a, b):
1192         if s==self:
1193             return (b**2-a**2)/2
1194         return self*(b-a)
1195
1196     def _eval_is_polynomial(self, syms):
1197         return True
1198
1199     def _eval_oseries(self, order):
1200         # .oseries() method checks for order.contains(self)
1201         return self
1202
1203     def _eval_as_leading_term(self, x):
1204         return self
1205
1206
1207 class Singleton(Basic):
1208     """ Singleton object.
1209     """
1210
1211     def __new__(cls, *args, **assumptions):
1212         # if you need to overload __new__, then
1213         # use the same code as below to ensure
1214         # that only one instance of Singleton
1215         # class is created.
1216         obj = Singleton.__dict__.get(cls.__name__)
1217         if obj is None:
1218             obj = Basic.__new__(cls,*args,**assumptions)
1219             setattr(Singleton, cls.__name__, obj)
1220         return obj
1221
1222 class SingletonFactory:
1223     """
1224     A map between singleton classes and the corresponding instances.
1225     E.g. S.Exp == Basic.Exp()
1226     """
1227
1228     def __getattr__(self, clsname):
1229         if clsname == "__repr__":
1230             return lambda: "S"
1231         obj = Singleton.__dict__.get(clsname)
1232         if obj is None:
1233             cls = getattr(Basic, clsname)
1234             assert issubclass(cls, Singleton),`cls`
1235             obj = cls()
1236             setattr(self, clsname, obj)
1237         return obj
1238
1239 S = SingletonFactory()
1240
1241 import parser