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