|
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; |