Instantly share code, notes, and snippets.

# hdon/aljebr.formats.js Created Dec 5, 2014

Javascript library for working with algebra and descendent calculuses
 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; var l='', r=''; if ('object' != typeof expression) { return expression; } if (expression.length != 3) throw new Error('Only binary operators are supported'); switch (expression) { 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, expression) + operator + recurse(expression, expression) + r; } return recurse(expression, 'none'); } exports.serializeExpression = serializeExpression;
 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 != predExpr) 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; ipredicate 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
 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;
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.