Javascript library for working with algebra and descendent calculuses

aljebr.formats.js

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;

aljebr.js

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;

util.js

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;