Javascript library for working with algebra and descendent calculuses
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var util = require('./util') | |
, KeyValueStore = util.KeyValueStore | |
, aljebr = require('./aljebr') | |
; | |
function serializeExpression(expression) | |
{ | |
var eqNesting = 0; | |
function recurse(expression, parentOperator) | |
{ | |
var needParens = false; | |
var operator = expression[0]; | |
var l='', r=''; | |
if ('object' != typeof expression) | |
{ | |
return expression; | |
} | |
if (expression.length != 3) | |
throw new Error('Only binary operators are supported'); | |
switch (expression[0]) | |
{ | |
case '=': | |
needParens = eqNesting++ > 0; | |
break; | |
case '+': | |
needParens = parentOperator == '*'; | |
break; | |
case '*': | |
break; | |
default: | |
throw new Error('"'+operator+'" operator is unsupported'); | |
} | |
if (needParens) | |
{ | |
l = '('; | |
r = ')'; | |
} | |
return l + | |
recurse(expression[1], expression[0]) + | |
operator + | |
recurse(expression[2], expression[0]) + | |
r; | |
} | |
return recurse(expression, 'none'); | |
} | |
exports.serializeExpression = serializeExpression; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var util = require('./util') | |
, deepCopy = util.deepCopy | |
, KeyValueStore = util.KeyValueStore | |
//, db = require('../db') | |
; | |
function isValidOperatorExpression(expression) | |
{ | |
/* All operator expressions are Arrays with at least an operator and one | |
* operand. Simpler types of expressions include variables and constants, | |
* and will fail this test. | |
*/ | |
return 'object' == typeof expression && | |
expression instanceof Array && | |
expression.length >= 2; | |
} | |
function assertValidOperatorExpression(expression) | |
{ | |
if (!isValidOperatorExpression(expression)) | |
throw new Error('Expected valid operator expression'); | |
} | |
/* This function derives one expression from another, by means of | |
* substitution. | |
* | |
* NOTE: I couldn't find the correct vernacular for the various | |
* parts of substitution anatomy, so please bear with me as I present my | |
* own: | |
* "subject" The subject is expression we wish to replace via | |
* substitution. | |
* "substitute" This is what replaces the subject in the resulting | |
* algebraic expression. | |
* "predicate" This is side of the substitution equation to which the | |
* subject conforms. | |
* "object" This is the side of the equation opposite the predicate, | |
* from which the substitute is formed, via the correspondance | |
* between the subject and the predicate. | |
*/ | |
function substitute(subjExpr, predExpr, objExpr) | |
{ | |
var varMap = {} | |
; | |
subjExpr = referentialEqualityForCSEs(subjExpr); | |
/* This function evaluates algebraic substitution correspondance from the | |
* subject expression 'subjExpr' and the predicate expression 'predExpr'. | |
* TODO does it do more? what does it return? | |
*/ | |
function calculateCorrespondence(subjExpr, predExpr) | |
{ | |
var cachedOperand; | |
assertValidOperatorExpression(subjExpr); | |
assertValidOperatorExpression(predExpr); | |
/* Compare operand count */ | |
if (subjExpr.length != predExpr.length) | |
return false; | |
/* Compare operator */ | |
if (subjExpr[0] != predExpr[0]) | |
return false; | |
/* Compare operands individually */ | |
for (i = 1; i < predExpr.length; i++) | |
{ | |
/* If the predicate expression's operand is an operator expression, | |
* then the subject expression's corresponding operand must also be | |
* an operator expression. Then we recurse. | |
*/ | |
if ('object' == typeof predExpr[i]) | |
{ | |
if ('object' != typeof subjExpr[i]) | |
return false; | |
if (!calculateCorrespondence(subjExpr[i], predExpr[i])) | |
return false; | |
} | |
/* If the predicate expression's operand is a variable expression, | |
* then the subject expression's corresponding operand can be | |
* anything, but we have to cache it, or verify that it matches what | |
* is already in the cache. | |
*/ | |
else if ('string' == typeof predExpr[i]) | |
{ | |
cachedOperand = varMap[predExpr[i]]; | |
if (cachedOperand == void 0) | |
{ | |
varMap[predExpr[i]] = subjExpr[i]; | |
} | |
else | |
{ | |
if (subjExpr[i] != cachedOperand) | |
return false; | |
} | |
} | |
} | |
return true; | |
} | |
if (!calculateCorrespondence(subjExpr, predExpr)) | |
return false; | |
subsExpr = deepCopy(objExpr); | |
function calculateObjectExpression(subsExpr) | |
{ | |
var subjExpr, i; | |
if ('object' == typeof subsExpr) | |
{ | |
for (i=1; i<subsExpr.length; i++) | |
subsExpr[i] = calculateObjectExpression(subsExpr[i]); | |
} | |
else if ('string' == typeof subsExpr) | |
{ | |
/* We have a variable expression. Use the subject->predicate mapping | |
* to resolve these variables to their corresponding subject | |
* subexpressions. | |
*/ | |
subjExpr = varMap[subsExpr]; | |
if (subjExpr === void 0) | |
throw new Error('Object expression contained a variable not specified in the predicate expression'); | |
return subjExpr; | |
} | |
else throw new Error('Object expressions presently only support operator and variable expressions.'); | |
return subsExpr; | |
} | |
return calculateObjectExpression(subsExpr); | |
} | |
function derive(expression, selector, equation) | |
{ | |
var resultExpression, selectedExpression, subexpressionMap, i, | |
equationExpression, expressionCursor, equationCursor; | |
/* Deep-copy the original expression */ | |
expression = deepCopy(expression); | |
/* Identify the selected expression */ | |
selectedExpression = expression; | |
while (i < selector.length) | |
{ | |
selectedExpression = selectedExpression[selector[i++]]; | |
} | |
/* Try both sides of the equation, if necessary. */ | |
for (i = 1; i < 2; i++) | |
{ | |
isomap = evaluateIsomorphismAndMapExpressions() | |
equationExpression = equation[i]; | |
equationCursor = equationExpression; | |
expressionCursor = selectedExpression; | |
subexpressionMap = new KeyValueStore; | |
} | |
} | |
/* This function will return an expression identical to the 'expression' | |
* argument, except that common subexpressions will be pass Javascript's | |
* equality operator ("==") by representing common subexpressions with the | |
* same object. | |
* | |
* The 'expression' argument is unchanged, and no reference to it or any | |
* of its subexpressions will be found in the returned expression. | |
* | |
* Using this can offer higher efficiency and expressiveness when you are | |
* required to test for the formal equality of an expression's | |
* subexpressions. | |
* | |
* NOTE: You can also "undo" the effect of this function with deepCopy(). | |
* | |
* NOTE: We also use this function as a unique, magic key for | |
* our instances of KeyValueStore. | |
* | |
* TODO eliminate use of deepCopy() | |
*/ | |
function referentialEqualityForCSEs(expression) | |
{ | |
var subexpressionCache; | |
/* If this is a primitive value, it is already formally equal via | |
* Javascript's equality operator. | |
*/ | |
if ('object' != typeof expression) | |
return expression; | |
/* Let's be extra paranoid that we don't harm the original expression. */ | |
expression = deepCopy(expression); | |
function recurse(subexpression) | |
{ | |
var i, cacheCursor, cacheCursor2; | |
/* Paranoid sanity checks */ | |
if ('object' != typeof subexpression | |
|| !(subexpression instanceof Array)) | |
throw new Error('Encountered unexpected type') | |
for (i=1; i<subexpression.length; i++) | |
{ | |
/* If we find a non-primitive operand, we recurse, depth-first. */ | |
if ('object' == typeof subexpression[i]) | |
subexpression[i] = recurse(subexpression[i]) | |
} | |
/* Now that our operands have all been added to the cache and "unified" | |
* wherever possible, we will place ourselves in the cache, or, unify | |
* with the equivalent subexpression, should we find it already in the | |
* cache. | |
*/ | |
cacheCursor = subexpressionCache; | |
for (i=0; i<subexpression.length; i++) | |
{ | |
cacheCursor2 = cacheCursor.get(subexpression[i]); | |
if (cacheCursor2 === void 0) | |
break; | |
cacheCursor = cacheCursor2; | |
} | |
if (i == subexpression.length) | |
{ | |
/* We should be able to find our doppleganger now. */ | |
return cacheCursor.get(referentialEqualityForCSEs) | |
} | |
else | |
{ | |
/* We are not in the cache. Let's build ourselves into it. */ | |
for (i=i; i<subexpression.length; i++) | |
{ | |
cacheCursor = cacheCursor.put(subexpression[i], new KeyValueStore); | |
} | |
/* Use our unique magic key to identify our subexpression within the | |
* cache. | |
*/ | |
return cacheCursor.put(referentialEqualityForCSEs, subexpression); | |
} | |
} | |
subexpressionCache = new KeyValueStore; | |
return recurse(expression); | |
} | |
//['=', ['+', 'x', 'y'], ['+', 'y', 'x']] | |
exports.referentialEqualityForCSEs = referentialEqualityForCSEs; | |
exports.substitute = substitute; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function deepCopy(obj) | |
{ | |
var ret, k; | |
/* Functions have reference semantics which we cannot penetrate */ | |
if ('function' == typeof obj) | |
throw new Error('Cannot deepCopy() a function'); | |
/* Simply return primtive values; no reference semantics here */ | |
if ('object' != typeof obj) | |
return obj; | |
/* Arrays require a special case */ | |
if (obj instanceof Array) | |
{ | |
/* Recursively deepCopy() each array element */ | |
ret = obj.map(deepCopy); | |
} | |
else | |
{ | |
/* Create a new object, preserving the prototype of the original object */ | |
ret = Object.create(Object.getPrototypeOf(obj)); | |
/* Recursively deepCopy() each key-value pair in the object */ | |
Object.keys(obj).forEach(function(k){ ret[k] = deepCopy[obj[k]] }); | |
} | |
return ret; | |
} | |
function deepKey(o, k) | |
{ | |
} | |
/* This is a key-value store, like Object, but supporting reference | |
* semantics for keys. Access time is linear, with average case being | |
* O(n/2) and worst-case being O(n). | |
* | |
* TODO Is there faster way? The way it's implemented now, keys and | |
* values are really just a pair of values with no direction distinction. | |
* It might be more efficient if I simply committed to using an object | |
* factory that pins a UUID onto every object which I might need to use as | |
* a key. | |
*/ | |
function KeyValueStore() | |
{ | |
this.keys = []; | |
this.vals = []; | |
} | |
function KeyValueStore_get(key) | |
{ | |
var index; | |
index = this.keys.indexOf(key); | |
if (index < 0) | |
return void 0; | |
return this.vals[index]; | |
} | |
function KeyValueStore_put(key, val) | |
{ | |
var index; | |
index = this.keys.indexOf(key); | |
if (index < 0) | |
{ | |
index = this.keys.length; | |
} | |
this.keys[index] = key; | |
this.vals[index] = val; | |
return val; | |
} | |
function KeyValueStore_removeByKey(key) | |
{ | |
var index; | |
index = this.keys.indexOf(key); | |
if (index < 0) | |
{ | |
throw new Error('No such key'); | |
} | |
if (this.keys.length > 1) | |
{ | |
this.keys[index] = this.keys[this.keys.length-1]; | |
this.vals[index] = this.vals[this.vals.length-1]; | |
} | |
this.keys.length--; | |
return this.vals[index]; | |
} | |
function KeyValueStore_getLength() | |
{ | |
return this.keys.length; | |
} | |
KeyValueStore.prototype.get = KeyValueStore_get; | |
KeyValueStore.prototype.put = KeyValueStore_put; | |
KeyValueStore.prototype.removeByKey = KeyValueStore_removeByKey; | |
KeyValueStore.prototype.getLength = KeyValueStore_getLength; | |
exports.KeyValueStore = KeyValueStore; | |
exports.deepCopy = deepCopy; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment