Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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[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;
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;
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