Source Code for Module sympycore.basealgebra.algebra

  1  """ Provides BasicAlgebra class. 
  2  """ 
  3   
  4  __docformat__ = "restructuredtext" 
  5  __all__ = ['Algebra', 'SymbolicEquality'] 
  6   
  7  from ..core import classes, Expr 
  8  from ..utils import LT, GT, LE, GE, NE, EQ 
  9   
 10  symbolic_comparison_map = dict( 
 11      equality = dict(__eq__=EQ, __ne__=NE), 
 12      inequality = dict(__lt__=LT,__le__=LE, __gt__=GT,__ge__=GE) 
 13      ) 
 14   
 15 -class SymbolicEquality: 
 16      """ Contex for logical operations. 
 17   
 18      In the ``SymbolicEquality(<Algebra class>)`` context relational 
 19      operations return ``Logic`` instances instead of computing 
 20      lexicographic value of relational operations. 
 21   
 22      For example, 
 23   
 24      >>> x = Calculus('x') 
 25      >>> with SymbolicEquality(Calculus): 
 26      >>>     print x==x 
 27      ...      
 28      ...      
 29      x==x 
 30      >>> print x==x 
 31      True 
 32   
 33      Add ``from __future__ import with_statement`` to the header of 
 34      python file when using Python version 2.5. 
 35       
 36      """ 
 37   
 38 -    def __init__(self, *classes): 
 39          self.classes = classes 
 40   
 41 -    def __enter__(self): 
 42          for cls in self.classes: 
 43              cls.enable_symbolic_comparison() 
 44   
 45 -    def __exit__(self, type, value, tb): 
 46          for cls in self.classes: 
 47              cls.disable_symbolic_comparison() 
 48          return tb is None 
 49   
 50   
 51 -class Algebra(Expr): 
 52      """ Represents an element of an algebraic structure. 
 53   
 54      This class collects implementation specific methods of algebra 
 55      classes. 
 56       
 57      For implemented algebras, see: 
 58   
 59        Verbatim 
 60        CollectingField 
 61       
 62      New algebras may need to redefine the following methods:: 
 63       
 64        __new__(cls, ...) 
 65        convert(cls, obj, typeerror=True) 
 66        convert_coefficient(cls, obj, typeerror=True) 
 67        convert_exponent(cls, obj, typeerror=True) 
 68        as_verbatim(self) 
 69        as_algebra(self, cls) 
 70   
 71      and the following properties:: 
 72   
 73        args(self) 
 74        func(self) 
 75   
 76      """ 
 77      #__slots__ = ['_str_value'] 
 78   
 79      _str_value = None 
 80   
 81      coefftypes = (int, long) 
 82      exptypes = (int, long) 
 83   
 84 -    def __str__(self): 
 85          s = self._str_value 
 86          if s is None: 
 87              s = self._str_value = str(self.as_verbatim()) 
 88          return s 
 89   
 90 -    def __repr__(self): 
 91          return '%s(%r)' % (self.__class__.__name__, str(self)) 
 92   
 93 -    def __nonzero__(self): 
 94          return not not self.data 
 95   
 96      @classmethod 
 97 -    def enable_symbolic_comparison(cls, name = 'equality'): 
 98          """ Enable returning Logic instances from relational methods. 
 99          """ 
100          logic_map = symbolic_comparison_map.get(name) 
101          if logic_map is None: 
102              raise ValueError('Unknown symbolic comparison name: %r. Valid names are %s'\ 
103                               % (name, ', '.join([repr(k) for k in symbolic_comparison_map]))) 
104          logic_map_name = '_%s_map' % (name) 
105          d = getattr(cls, logic_map_name, None) 
106          if d is None: 
107              d = {} 
108              setattr(cls, logic_map_name, d) 
109              for mthname, head in logic_map.items(): 
110                  d[mthname] = getattr(cls, mthname, None) 
111                  setattr(cls, mthname, lambda self, other, head=head: classes.Logic(head, (self, other))) 
112   
113      @classmethod 
114 -    def disable_symbolic_comparison(cls, name = 'equality'): 
115          """ Disable returning Logic instances from relational methods. 
116          """ 
117          logic_map = symbolic_comparison_map.get(name) 
118          if logic_map is None: 
119              raise ValueError('Unknown symbolic comparison name: %r. Valid names are %s'\ 
120                               % (name, ', '.join([repr(k) for k in symbolic_comparison_map]))) 
121          logic_map_name = '_%s_map' % (name) 
122          d = getattr(cls, logic_map_name, None) 
123          if d is None: 
124              return 
125          for mthname, mth in d.items(): 
126              if mth is None: 
127                  delattr(cls, mthname) 
128              else: 
129                  setattr(cls, mthname, mth) 
130          delattr(cls, logic_map_name) 
131   
132 -    def as_tree(self, tab='', level=0): 
133          return self.as_verbatim().as_tree(tab,level) 
134   
135      @classmethod 
136 -    def convert(cls, obj, typeerror=True): 
137          """ Convert obj to algebra element. 
138   
139          Set typeerror=False when calling from operation methods like __add__, 
140          __mul__, etc. 
141          """ 
142          # check if obj is already algebra element: 
143          if isinstance(obj, cls): 
144              return obj 
145   
146          # parse algebra expression from string: 
147          if isinstance(obj, (str, unicode, Verbatim)): 
148              return Verbatim.convert(obj).as_algebra(cls) 
149   
150          # check if obj belongs to coefficient algebra 
151          r = cls.convert_coefficient(obj, typeerror=False) 
152          if r is not NotImplemented: 
153              return cls.Number(r) 
154   
155          # as a last resort, convert from another algebra: 
156          if isinstance(obj, Algebra): 
157              return obj.as_algebra(cls) 
158   
159          if typeerror: 
160              raise TypeError('%s.convert: failed to convert %s instance'\ 
161                              ' to algebra'\ 
162                              % (cls.__name__, obj.__class__.__name__)) 
163          else: 
164              return NotImplemented 
165   
166      @classmethod 
167 -    def convert_exponent(cls, obj, typeerror=True): 
168          """ Convert obj to exponent algebra. 
169          """ 
170          if isinstance(obj, cls.exptypes) or isinstance(obj, cls): 
171              return obj 
172          if typeerror: 
173              raise TypeError('%s.convert_exponent: failed to convert %s instance'\ 
174                              ' to exponent algebra, expected int|long object'\ 
175                              % (cls.__name__, obj.__class__.__name__)) 
176          else: 
177              return NotImplemented 
178   
179      @classmethod 
180 -    def convert_coefficient(cls, obj, typeerror=True): 
181          """ Convert obj to coefficient algebra. 
182          """ 
183          if isinstance(obj, cls.coefftypes): 
184              return obj 
185          if typeerror: 
186              raise TypeError('%s.convert_coefficient: failed to convert %s instance'\ 
187                              ' to coefficient algebra, expected int|long object'\ 
188                              % (cls.__name__, obj.__class__.__name__)) 
189          else: 
190              return NotImplemented 
191   
192 -    def as_verbatim(self): 
193          raise NotImplementedError('%s must define as_verbatim method' #pragma NO COVER 
194                                    % (self.__class__.__name__))         #pragma NO COVER 
195   
196 -    def as_algebra(self, cls): 
197          """ Convert algebra to another algebra. 
198   
199          This method uses default conversation via verbatim algebra that 
200          might not be the most efficient. For efficiency, algebras should 
201          redefine this method to implement direct conversation. 
202          """ 
203          # todo: cache verbatim algebras 
204          if cls is classes.Verbatim: 
205              return self.as_verbatim() 
206          return self.as_verbatim().as_algebra(cls) 
207   
208      @classmethod 
209 -    def get_predefined_symbols(cls, name): 
210          return 
211   
212      @property 
213 -    def func(self): 
214          """ Returns a callable such that ``self.func(*self.args) == self``. 
215          """ 
216          raise NotImplementedError('%s must define property func'      #pragma NO COVER 
217                                    % (cls.__name__))                   #pragma NO COVER 
218   
219      @property 
220 -    def args(self): 
221          """ Returns a sequence such that ``self.func(*self.args) == self``. 
222          """ 
223          raise NotImplementedError('%s must define property args'      #pragma NO COVER 
224                                    % (cls.__name__))                   #pragma NO COVER 
225   
226      @classmethod 
227 -    def Symbol(cls, obj): 
228          """ Construct algebra symbol directly from obj. 
229          """ 
230          raise NotImplementedError('%s must define classmethod Symbol' #pragma NO COVER 
231                                    % (cls.__name__))                   #pragma NO COVER 
232   
233      @classmethod 
234 -    def Number(cls, num, denom=None): 
235          """ Construct algebra number directly from obj. 
236          """ 
237          raise NotImplementedError('%s must define classmethod Number' #pragma NO COVER 
238                                    % (cls.__name__))                   #pragma NO COVER 
239   
240      @property 
241 -    def symbols(self): 
242          """ Return a set of atomic subexpressions in a symbolic object. 
243          """ 
244          symbols = self._symbols 
245          if symbols is None: 
246              args = self.args 
247              if args: 
248                  symbols = set() 
249                  for arg in args: 
250                      symbols |= arg.symbols 
251              else: 
252                  symbols = set([self]) 
253              self._symbols = symbols 
254          return symbols 
255   
256 -    def has(self, obj): 
257          """ Return True if self contains atomic expression obj. 
258          """ 
259          convert = self.convert 
260          return convert(obj) in self.symbols 
261   
262 -    def match(self, pattern, *wildcards): 
263          """ 
264          Pattern matching. 
265   
266          Return None when expression (self) does not match with 
267          pattern. Otherwise return a dictionary such that 
268   
269          :: 
270   
271            pattern.subs_dict(self.match(pattern, *wildcards)) == self 
272   
273          Don't redefine this method, redefine ``matches(..)`` method instead. 
274   
275          :See: 
276            http://wiki.sympy.org/wiki/Generic_interface#Pattern_matching 
277          """ 
278          pattern = self.convert(pattern) 
279          wild_expressions = [] 
280          wild_predicates = [] 
281          for w in wildcards: 
282              if type(w) in [list, tuple]: 
283                  assert len(w)==2,`w` 
284                  s, func = w 
285              else: 
286                  s, func = w, True 
287              s = self.convert(s) 
288              wild_expressions.append(s) 
289              wild_predicates.append(func) 
290          if wild_expressions: 
291              wild_info = (wild_expressions, wild_predicates) 
292          else: 
293              wild_info = None 
294          return pattern.matches(self, {}, wild_info) 
295   
296 -    def matches(pattern, expr, repl_dict={}, wild_info=None): 
297          # check if pattern has a match and return it provided that 
298          # the match matches with expr: 
299          v = repl_dict.get(pattern) 
300          if v is not None: 
301              if v==expr: 
302                  return repl_dict 
303              return 
304          # check if pattern matches with expr: 
305          if pattern==expr: 
306              if wild_info and expr in wild_info[0]: 
307                  return 
308              return repl_dict 
309          if wild_info: 
310              wild_expressions, wild_predicates = wild_info 
311              # check if pattern is a wild expression 
312              if pattern in wild_expressions: 
313                  if expr in wild_expressions: 
314                      # wilds do not match other wilds 
315                      return 
316                  if expr.symbols.intersection(pattern.symbols): 
317                      # wild does not match expressions containing wild expressions 
318                      return 
319                  # wild pattern matches with expr only if predicate(expr) returns True 
320                  predicate = wild_predicates[wild_expressions.index(pattern)] 
321                  if (isinstance(predicate, bool) and predicate) or predicate(expr): 
322                      repl_dict = repl_dict.copy() 
323                      repl_dict[pattern] = expr 
324                      return repl_dict 
325              pattern_symbols = pattern.symbols 
326              for w in wild_expressions: 
327                  if w in pattern_symbols: 
328                      # _matches implements implementation specific matches, 
329                      # pattern should contain wild symbols, otherwise 
330                      # _matches would always return None 
331                      return pattern._matches(expr, repl_dict, wild_info) 
332          return 
333   
334      @classmethod 
335 -    def _matches_seq(cls, pattern_seq, expr_seq, repl_dict, wild_info): 
336          n = len(pattern_seq) 
337          m = len(expr_seq) 
338          if n!=m: 
339              return 
340          elif n==0: 
341              return repl_dict 
342          elif n==1: 
343              p = pattern_seq[0] 
344              if isinstance(p, cls): 
345                  return p.matches(expr_seq[0], repl_dict, wild_info) 
346              if p==expr_seq[0]: 
347                  return repl_dict 
348              return 
349          def matches(pattern, expr): 
350              if isinstance(pattern, cls): 
351                  return pattern.matches(expr, repl_dict, wild_info) 
352              if pattern==expr: 
353                  return repl_dict 
354              return 
355          def subs(expr, l): 
356              if isinstance(expr, cls): 
357                  return expr.subs(l) 
358              return expr 
359          for i in xrange(n): 
360              p = pattern_seq[i] 
361              e = expr_seq[i] 
362              r = matches(p, e) 
363              if r is not None: 
364                  new_pattern_seq = [subs(pattern_seq[j],r.items()) for j in xrange(n) if j!=i] 
365                  new_expr_seq = [expr_seq[j] for j in xrange(n) if j!=i] 
366                  r1 = cls._matches_seq(new_pattern_seq, new_expr_seq, r, wild_info) 
367                  if r1 is not None: 
368                      return r1 
369          return 
370   
371 -    def _matches(pattern, expr, repl_dict, wild_info): 
372          if pattern.func == expr.func: 
373              return pattern._matches_seq(pattern.args, expr.args, repl_dict, wild_info) 
374          return 
375   
376 -    def subs(self, subexpr, newexpr=None): 
377          """ Substitute a sub-expression with new expression. 
378           
379          There are two usage forms:: 
380           
381            obj.subs(subexpr, newexpr) 
382            obj.subs([(subexpr1, newexpr1), (subexpr2, newexpr2), ..]) 
383           
384          """ 
385          convert = self.convert 
386          if newexpr is None: 
387              r = self 
388              for s,n in subexpr: 
389                  r = r._subs(convert(s), convert(n)) 
390              return r 
391          return self._subs(convert(subexpr), convert(newexpr)) 
392   
393 -    def _subs(self, subexpr, newexpr): 
394          raise NotImplementedError('%s must define _subs method'     #pragma NO COVER 
395                                    % (self.__class__.__name__))      #pragma NO COVER 
396   
397   
398  from .verbatim import Verbatim 
399