Source

pymathema / src / pymathema / evaluation.py

Full commit
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
'''
Created on Oct 30, 2010

@author: T. Michael Keesey
'''
from xml.dom.minidom import getDOMImplementation
from decimal import Decimal
import math
from fractions import Fraction

MATHML_NS_URI = "http://www.w3.org/1998/Math/MathML"

XSI_NS_URI = "http://www.w3.org/1999/XMLSchema-instance"

def checkSepNode(node):
    '''Checks that a <cn> node contains two numbers separated by a <sep> element.
    '''
    if node.childNodes.length != 3:
        raise EvaluationError("Expected two text nodes separated by a <sep> element in this type of <cn> element. Found " + str(node.childNodes.length) + " child node(s).")
    if node.firstChild.nodeType != 3 and node.firstChild.nodeType != 4:
        raise EvaluationError("First child node should be a text node for this type of <cn> element.")
    if node.childNodes.item(1).nodeType != 1:
        raise EvaluationError("Second child node should be an element node for this type of <cn> element.")
    if node.childNodes.item(1).namespaceURI != MATHML_NS_URI:
        raise EvaluationError("Second child node should be a MathML element for this type of <cn> element.")
    if node.childNodes.item(1).localName != "sep":
        raise EvaluationError("Second child node should be a <sep> element for this type of <cn> element.")
    if node.lastChild.nodeType != 3 and node.lastChild.nodeType != 4:
        raise EvaluationError("Last child node should be a text node for this type of <cn> element.")

def createMathMLDoc():
    mathml = getDOMImplementation().createDocument(MATHML_NS_URI, "math", None)
    schemaLocation = MATHML_NS_URI + " http://www.w3.org/Math/XMLSchema/mathml2/mathml2.xsd"
    mathml.documentElement.setAttributeNS(XSI_NS_URI, "schemaLocation", schemaLocation)
    return mathml

def extractText(node):
    '''Extracts all text within an XML node.
    '''
    if node.nodeType == 1:
        s = u""
        for i in range(node.childNodes.length):
            s += extractText(node.childNodes.item(i))
        return s;
    return unicode(node.nodeValue)

def nodeHasQName(node, uri, localName):
    '''Checks if an XML node has a specified qualified name.
    '''
    return node.namespaceURI == uri and node.localName == localName

class EvaluationError(Exception):
    '''Indicates an error in evaluating a MathML node.
    
    Such errors can be fixed by fixing the MathML.
    '''
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return repr(self.value)

class ImplementationError(Exception):
    '''Indicates an error caused by incomplete implementation of MathML.
    
    Such errors cannot be fixed  except by newer releases of pymathema which address the issue.
    '''
    def __init__(self, value):
        self.value = value
        
    def __str__(self):
        return repr(self.value)
    
def opEq(entities):
    '''Checks whether all elements in a collection are equal.
    '''
    n = len(entities)
    for i in range(n - 1):
        if entities[i] != entities[i + 1]:
            return False
    return True

def opGEq(entities):
    '''Checks whether each element in a collection is greater than or equal to the subsequent one.
    '''
    n = len(entities)
    for i in range(n - 1):
        if not(entities[i] >= entities[i + 1]):
            return False
    return True

def opGT(entities):
    '''Checks whether each element in a collection is greater than the subsequent one.
    '''
    n = len(entities)
    for i in range(n - 1):
        if not(entities[i] > entities[i + 1]):
            return False
    return True

def opIn(entities):
    '''Checks whether each element in a collection is a member of the subsequent one.
    '''
    n = len(entities)
    for i in range(n - 1):
        if not(entities[i] in entities[i + 1]):
            return False
    return True

def opIntersect(sets):
    '''Finds the intersection of any number of sets.
    '''
    result = set()
    for s in sets:
        result &= s
        if len(result) == 0:
            return frozenset()
    return frozenset(result)

def opLEq(entities):
    '''Checks whether each element in a collection is less than or equal to the subsequent one.
    '''
    n = len(entities)
    for i in range(n - 1):
        if not(entities[i] <= entities[i + 1]):
            return False
    return True

def opLT(entities):
    '''Checks whether each element in a collection is less than the subsequent one.
    '''
    n = len(entities)
    for i in range(n - 1):
        if not(entities[i] < entities[i + 1]):
            return False
    return True

def opNEq(entities):
    '''Checks whether any two elements of a collection are equal.
    
    Returns False if so.
    '''
    n = len(entities)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if entities[i] == entities[j]:
                return False
    return True

def opNotIn(entities):
    '''Checks whether each element in a collection is not a member of the subsequent one.
    '''
    n = len(entities)
    for i in range(n - 1):
        if entities[i] in entities[i + 1]:
            return False
    return True

def opUnion(sets):
    '''Finds the union of any number of sets.
    '''
    result = set()
    for s in sets:
        result |= s
    return frozenset(result)

class CompositeOperation(object):
    '''An operation formed by the composition of other operations.
    '''
    def __init__(self, operations):
        self.operations = operations
    def __call__(self, args):
        operations = list(self.operations)
        operations.reverse()
        for op in operations:
            args = [op.__call__(args)]
        return args[0]

class MathMLEvaluator(object):
    '''Base class for evaluating MathML elements.
    '''
    def __init__(self):
        self.methodTable = self.createMethodTable()
        self.valueTable = self.createValueTable()
        self.cnTypeTable = self.createCNTypeTable()
        self.definitionURLTable = {}
        self.ciTable = {}
        self.declareTypeTable = {}
        self.defaultDomainOfApplication = frozenset()
        self.dom = getDOMImplementation()
        self.doc = self.dom.createDocument(MATHML_NS_URI, "math", None)
    def findDefinitionURLs(self, value):
        urls = set()
        for (url, definedValue) in self.definitionURLTable.iteritems():
            if value == definedValue:
                urls.add(url)
        return frozenset(urls)
    def universalPowerSet(self, exponent = 2, domainOfApplication = None):
        '''Finds the universal power set (using domainOfApplication) to a given exponent.
        
        If domainOfApplication is not specified, then self.defaultDomainOfApplication is used.
        '''
        if domainOfApplication is None:
            domainOfApplication = self.defaultDomainOfApplication
        if exponent < 1:
            return frozenset()
        if exponent == 1:
            return frozenset(domainOfApplication)
        result = set()
        if exponent == 2:
            for a in domainOfApplication:
                for b in domainOfApplication:
                    result.add((a, b))
        else:
            base = self.universalPowerSet(exponent - 1)
            for baseTuple in base:
                for element in domainOfApplication:
                    result |= frozenset(list(baseTuple) + [element])
        return frozenset(result)
    def addDeclareType(self, type, factoryMethod):
        '''Adds a declaration type by associating a type name with a factory method.
        
        Example:
        
        _elementIndex = 0
        
        def createElement():
            _elementIndex += 1
            return _elementIndex
            
        evaluator.addDeclareType("myType", createElement)
        
        The following MathML will evaluate to 1 the first time it is evaluated:
        
        <declare type="myType">
            <ci>myVar</ci>
        </declare>
        
        Note that the <declare> element must have only one child element. If it has two, the second one
        will determine the value, not the factory method associated with the type.
        '''
        self.declareTypeTable[type] = factoryMethod
    def addDefinition(self, definitionURL, value):
        '''Adds a definition by associating a URL with a value.
        
        Example:
        
        evaluator.addDefinition('#zero', 0)
        
        The following MathML will evaluate to 0:
        
        <csymbol definitionURL="#zero"/>
        '''
        self.definitionURLTable[definitionURL] = value
    def createCNTypeTable(self):
        '''Creates and returns the dictionary used to evaluate <cn> elements.
        
        Keys correspond to the @type attribute and values indicate evaluation operations.
        This may be overridden to provide an alternate implementation of numbers.
        '''
        return {"real" : self.evaluateCNReal, "integer" : self.evaluateCNInteger, "rational" : self.evaluateCNRational, "complex-cartesian" : self.evaluateCNComplexCartesian, "complex-polar" : self.evaluateCNComplexPolar, "constant" : self.evaluateCNConstant }    
    def createMethodTable(self):
        '''Creates and returns the meta-dictionary used to evaluate structural MathML elements.
        
        Within the meta-dictionary, keys correspond to namespace URIs, and values are namespace dictionaries.
        
        Within namespace dictionaries, keys correspond to element local names and values indicate evaluation operations.
        '''
        return {"http://www.w3.org/1998/Math/MathML" :
                    {"apply": self.evaluateApply,
                     "ci" : self.evaluateCI,
                     "cn" : self.evaluateCN,
                     "csymbol" : self.evaluateDefined,
                     "declare" : self.evaluateDeclare,
                     "list" : self.evaluateList,
                     "math" : self.evaluateMath,
                     "piecewise" : self.evaluatePiecewise,
                     "set" : self.evaluateSet}}
    def createValueTable(self):
        '''Creates and returns the dictionary used to evaluate fixed-value MathML elements.
        
        Within the meta-dictionary, keys correspond to namespace URIs, and values are namespace dictionaries.
        
        Within namespace dictionaries, keys correspond to element local names and values indicate the associated fixed values.
        '''
        return {"http://www.w3.org/1998/Math/MathML" :
                    {"and" : lambda a: set(x for x in a) == frozenset([True]),
                     "compose" : CompositeOperation,
                     "emptyset" : frozenset(),
                     "eq" : opEq,
                     "false" : False,
                     "geq" : opGEq,
                     "gt" : opGT,
                     "implies" : lambda a: not a[0] or a[1],
                     "in" : opIn,
                     "intersect" : opIntersect,
                     "leq" : opLEq,
                     "lt" : opLT,
                     "not" : lambda a: not a[0],
                     "notin" : opNotIn,
                     "notprsubset" : lambda a: not opLT(a),
                     "notsubset" : lambda a: not opLEq(a),
                     "neq" : opNEq,
                     "or" : lambda a: True in a,
                     "prsubset" : opLT,
                     "selector" : lambda a: a[0][a[1]],
                     "setdiff" : lambda a: a[0] - a[1],
                     "subset" : opLEq,
                     "true" : True,
                     "union" : opUnion,
                     "xor" : lambda a: bool(a[0]) != bool(a[1])}}
    def evaluate(self, node):
        '''Determines the value of a MathML element.
        '''
        if (node.namespaceURI in self.valueTable):
            table = self.valueTable[node.namespaceURI]
            if (node.localName in table):
                return table[node.localName]
        if not(node.namespaceURI in self.methodTable):
            raise EvaluationError("Unrecognized namespace URI: " + str(node.namespaceURI) + "::" + str(node.localName))
        table = self.methodTable[node.namespaceURI]
        if not(node.localName in table):
            raise EvaluationError("Unrecognized node name: " + str(node.nodeName))
        method = table[node.localName]
        return method(node)
    def evaluateApply(self, node):
        '''Determines the value of a MathML <apply> element.
        '''
        n = node.childNodes.length
        if n < 1:
            raise EvaluationError("An <apply> element must have at least two child elements.")
        operation = self.evaluate(node.firstChild) 
        args = []
        for i in range(1, n):
            args.append(self.evaluate(node.childNodes.item(i)))
        args = tuple(args)
        if hasattr(operation, "__call__"):
            return operation(args)
        return args in operation
    def evaluateConditions(self, nodes):
        '''Determines the whether a series of MathML <condition> elements describe a condition that holds.
        '''
        for node in nodes:
            if self.evaluate(node.firstChild) != True:
                return False
        return True
    def evaluateBVarSet(self, node):
        '''Determines the value of a MathML <set> element which includes a <bvar> expression.
        '''
        #:TODO: Add domainofapplication
        #:TODO: Optimize
        bVarNodes = []
        bVarNames = []
        #Gather nodes of certain types into collections.
        conditionNodes = []
        valueNodes = []
        for i in range(0, node.childNodes.length):
            childNode = node.childNodes.item(i)
            if nodeHasQName(childNode, MATHML_NS_URI, "bvar"):
                bVarNodes.append(childNode)
                bVarNames.append(extractText(childNode))
            elif nodeHasQName(childNode, MATHML_NS_URI, "condition"):
                conditionNodes.append(childNode)
            else:
                valueNodes.append(childNode)
        #Grab value nodes from <bvar> elements.
        bVarNum = len(bVarNodes)
        if bVarNum == 0:
            raise EvaluationError("No <bvar> elements found.")
        if len(valueNodes) == 0:
            for n in bVarNodes:
                valueNodes.append(n.firstChild.cloneNode(True))
        valueNode = None
        #Create the value node.
        if len(valueNodes) == 1:
            valueNode = valueNodes[0]
        else:
            valueNode = self.doc.createElementNS(MATHML_NS_URI, "list")
            for n in valueNodes:
                valueNode.appendChild(n.cloneNode(True))
        #Initiate result.
        result = set()
        #Go through all possible values and see if they fulfill all conditions.
        for possibility in self.universalPowerSet(bVarNum):
            if bVarNum == 1:
                self.ciTable[bVarNames[0]] = possibility
            else:
                for i in range(bVarNum):
                    self.ciTable[bVarNames[i]] = possibility[i]
            if self.evaluateConditions(conditionNodes):
                result.add(self.evaluate(valueNode))
        # Prepare and return results.
        return frozenset(result)
    def evaluateCI(self, node):
        '''Determines the value of a MathML <ci> element.
        '''
        identifier = extractText(node)
        if not(identifier in self.ciTable):
            raise EvaluationError("Unrecognized identifier: \"" + identifier + '".')
        return self.ciTable[identifier]
    def evaluateCN(self, node):
        '''Determines the value of a MathML <cn> element.
        '''
        if node.hasAttribute("definitionURL"):
            return self.evaluateDefined(node)
        type = node.getAttribute("type") if node.hasAttribute("type") else "real"
        if not(type in self.cnTypeTable):
            raise EvaluationError("Unrecognized content number (cn) type: " + type)
        method = self.cnTypeTable[type]
        return method(node)
    def evaluateCNComplexCartesian(self, node):
        '''Determines the value of a MathML <cn type="complex-cartesian"> element.
        '''
        checkSepNode(node)
        return complex(float(node.firstChild.nodeValue), float(node.lastChild.nodeValue))
    def evaluateCNComplexPolar(self, node):
        '''Determines the value of a MathML <cn type="complex-polar"> element.
        '''
        checkSepNode(node)
        r = float(node.firstChild.nodeValue)
        theta = float(node.lastChild.nodeValue)
        return complex(r * math.cos(theta), r * math.sin(theta))
    def evaluateCNConstant(self, node):
        '''Determines the value of a MathML <cn type="constant"> element.
        '''
        #:TODO:
        raise ImplementationError("Constant numbers have not yet been implemented.")
    def evaluateCNInteger(self, node):
        '''Determines the value of a MathML <cn type="integer"> element.
        '''
        base = int(node.getAttribute("base")) if node.hasAttribute("base") else 10
        if node.childNodes.length != 1:
            raise EvaluationError("Expected single text node child for <cn type=\"integer\"> element. Found: " + str(node.childNodes.length))
        if node.firstChild.nodeType != 3 and node.firstChild.nodeType != 4:
            raise EvaluationError("Child node should be a text node for <cn type=\"integer\"> element.")
        return int(node.firstChild.nodeValue, base)
    def evaluateCNRational(self, node):
        '''Determines the value of a MathML <cn type="rational"> element.
        '''
        checkSepNode(node)
        base = int(node.getAttribute("base")) if node.hasAttribute("base") else 10
        return Fraction(int(node.firstChild.nodeValue, base), int(node.lastChild.nodeValue, base))
    def evaluateCNReal(self, node):
        '''Determines the value of a MathML <cn type="real"> element.
        '''
        if node.childNodes.length != 1:
            raise EvaluationError("Expected single text node child for <cn type=\"real\"> element. Found: " + str(node.childNodes.length))
        return Decimal(node.firstChild.nodeValue)
    def evaluateDeclare(self, node):
        '''Determines the value of a MathML <declare> element.
        '''
        if (node.childNodes.length == 1):
            if not node.hasAttribute("type"):
                raise EvaluationError("If a <declare> element has only one child element, then it must also have a @type attribute.")
            type = node.getAttribute("type")
            if not(type in self.declareTypeTable):
                raise EvaluationError("Unknown declaration type: \"" + type + "\".")
            value = self.declareTypeTable[type]()
        elif (node.childNodes.length == 2):
            value = self.evaluate(node.childNodes.item(1))
        else:
            raise EvaluationError("Expected one or two child elements for <declare> element. Found: " + str(node.childNodes.length))
        idNode = node.childNodes.item(0)
        if idNode.namespaceURI != MATHML_NS_URI:
            raise EvaluationError("First child node should be a MathML element in <declare> elements.")
        defined = False
        if idNode.hasAttribute("definitionURL"):
            defined = True
            self.addDefinition(idNode.getAttribute("definitionURL"), value)
        if idNode.localName == "ci":
            defined = True
            self.ciTable[extractText(idNode)] = value
        if not defined:
            raise EvaluationError("A <ci> element or an element with a @definitionURL attribute must be the first child element in a <declare> element.")
        return value
    def evaluateDefined(self, node):
        '''Determines the value of a MathML element with a @definitionURL attribute (for example, a <csymbol> element).
        '''
        return self.definitionURLTable[node.getAttribute("definitionURL")]
    def evaluateDefinitionURL(self, url):
        '''Determines the value of a defined URL.
        '''
        return self.definitionURLTable[url]
    def evaluateList(self, node):
        '''Determines the value of a MathML <list> element.
        '''
        result = list()
        for n in node.childNodes:
            result.append(self.evaluate(n))
        return tuple(result)
    def evaluateMath(self, node):
        '''Determines the value of a MathML <math> element.
        
        There is no canonical meaning for a <math> element. This function evaluates all child nodes
        and then returns self.definitionURLTable, a dictionary mapping URLs to values, as specified
        by <declare> elements.
        '''
        for n in node.childNodes:
            self.evaluate(n)
        return self.definitionURLTable;
    def evaluatePiecewise(self, node):
        '''Determines the value of a MathML <piecewise> element.
        '''
        n = node.childNodes.length
        if n < 2:
            raise EvaluationError("A <piecewise> element must have at least two child elements.")
        for i in range(n - 1):
            piece = node.childNodes.item(i)
            if piece.namespaceURI != MATHML_NS_URI or piece.localName != "piece":
                raise EvaluationError("All child elements of a <piecewise> element must be <piece> elements, except for the last one.")
            if piece.childNodes.length != 2:
                raise EvaluationError("All <piece> elements must have exactly two child elements.")
        otherwise = node.childNodes.item(n - 1)
        if otherwise.namespaceURI != MATHML_NS_URI or otherwise.localName != "otherwise":
            raise EvaluationError("The last child element of a <piecewise> element must be an <otherwise> element.")
        if otherwise.childNodes.length != 1:
            raise EvaluationError("All <otherwise> elements must have exactly one child element.")
        for i in range(n - 1):
            if self.evaluate(node.childNodes.item(i).lastChild) == True:
                return self.evaluate(node.childNodes.item(i).firstChild)
        return self.evaluate(otherwise.firstChild)
    def evaluateSet(self, node):
        '''Determines the value of a MathML <set> element.
        '''
        if node.childNodes.length > 0 and nodeHasQName(node.firstChild, MATHML_NS_URI, "bvar"):
            return self.evaluateBVarSet(node)
        result = set()
        for n in node.childNodes:
            result |= frozenset([self.evaluate(n)])
        return frozenset(result)