node unifier

unifier.js

////////////////////////////////////////////////////////////////////////////////
// Simple unifier.

/*******************************************************************************
 * Unifier two terms.
 * term1: result of parse()
 * term2: result of parse()
 * frame: (optional) use an existing unification frame
 */
var unify = exports.unify = function(config){
  var exp1 = config.exp1, exp2 = config.exp2;
  var frame = config.frame || {};
  var isConstant = config.isConstant || isConstant_def
  var isFree = config.isFree || isFree_def;
  return {
    frame: frame,
    result:resolve(go(exp1,exp2))
  };

  /*****************************************************************************
   * Main unification logic.
   */
  function go(exp1,exp2){
    if(isConstant(exp1) && isConstant(exp2) && equal(exp1,exp2)){
      return exp1;
    } else if (isFree(exp1) && isFree(exp2)) {
      return extendWithFree(exp1,exp2);
    } else if (isGroup(exp1) && isGroup(exp2)) {
      return zipWith(exp1,exp2,go);
    } else if (isFree(exp1) || isFree(exp2)) {
      var free = isFree(exp1)? exp1 : exp2;
      var constantGroup = !isFree(exp1)? exp1 : exp2;
      return extendWithConstantOrGroup(free,constantGroup);
    }  else {
      throw [
        JSON.stringify(exp1),
        '  does not match ',
        JSON.stringify(exp2),
        '  with frame ',
        JSON.stringify(frame)
      ].join('\n');
    }
  }

  /*****************************************************************************
   * Extend a free variable with another.
   */
  function extendWithFree(free1,free2){
    if(frame[free1] || frame[free2]){
      if(frame[free1] && frame[free2]){
        if(frame[free1]===frame[free2]){
          return free1;
        } else {
          throw [
            'free variables ',free1,'  and ',free2,'  do not match'
          ].join('\n');
        }
      } else {
        var bound = frame[free1]? free1 : free2;
        var unbound = !frame[free1] ? free1 : free2;
        frame[unbound] = frame[bound];
        return free1;
      }
    } else {
      var box = {free:free1};
      frame[free1] = box;
      frame[free2] = box;
      return free1;
    }
  }

  /*****************************************************************************
   * Extend a free variable with a constant or group.
   */
  function extendWithConstantOrGroup(free,constant){
    if(frame[free]){
      if(frame[free].contents){
        if(equal(frame[free].contents,constant)){
          return free;
        } else {
          return go(frame[free].contents,constant);
        }
      } else if(frame[free].free) {
        delete frame[free].free;
        frame[free].contents = constant;
        return free;
      }
    } else {
      frame[free] = { contents: constant };
      return free;
    }
  }

  /*****************************************************************************
   * Resolve the free variables in an expression to their referents.
   */
  function resolve(expr){
    if(isGroup(expr)){
      return expr.map(resolve);
    } else if(isConstant(expr)) {
      return expr;
    } else if(isFree(expr)){
      if(frame[expr]) {
        if(frame[expr].contents) {
          var contents = frame[expr].contents;
          occursCheck(contents,expr,contents);
          return resolve(contents)
        }
        else
          return frame[expr].free;
      } else {
        return expr;
      }
    }
  }

  /*****************************************************************************
   * Simple occurs check.
   */
  function occursCheck(toplevel,free,expr){
    if(isGroup(expr)){
      return expr.map(function(e){return occursCheck(toplevel,free,e);});
    } else if(isFree(expr)) {
      if(expr == free){
        throw [
          JSON.stringify(free),
          '  occurs in ',
          JSON.stringify(toplevel),
          '  cannot construct infinite expression'
        ].join('\n');
      }
    }
  }
}

/*****************************************************************************
 * Pretty print an expression to a string.
 */
var prettify = exports.prettify = function(expr){
  return go(expr,false);
  function go(expr,parens){
    if(!expr){
      return '<undefined>';
    }
    else if(isGroup(expr)) {
      return (
        (parens?'(':'') +
          expr.map(function(x){ return go(x,true); }).join(' ') +
          (parens?')':'')
      );
    }
    else
      return expr;
  }
}

/*****************************************************************************
 * Parse a string into an expression.
 */
var parse = exports.parse = function(expr){
  return go(expr,0)[0];
  function go(expr,i){
    var len = expr.length;
    var current = '';
    var exprs = [];
    for(; i < len; i++) {
      if(expr[i]==' ')      { if(current) exprs.push(current);
                              current = '';
                            }
      else if(expr[i]=='(') { if(current) exprs.push(current);
                              current = '';
                              var ret = go(expr,i+1);
                              exprs.push(ret[0]);
                              i = ret[1];
                            }
      else if(expr[i]==')') { break; }
      else                  { current += expr[i];}
    }
    if(current) exprs.push(current);
    if(exprs.length == 1) exprs = exprs[0];
    return [exprs,i];
  }
}

/*****************************************************************************
 * Is an expresion a constant?
 */
function isConstant_def(x){
  return typeof x == 'string' &&
    !x.match(/^[a-z]+/);
}

/*****************************************************************************
 * Is an expression a group?
 */
function isGroup(x){
  return x._unifier_isArray();
}

/*****************************************************************************
 * Is an expression a free variable?
 */
function isFree_def(x){
  return !isConstant_def(x) && !isGroup(x);
}

////////////////////////////////////////////////////////////////////////////////
// Simple testing library

/*******************************************************************************
 * Simple testing object.
 */
function Tester(name){
  this.name = name;
  this.ran = 0;
}

/*******************************************************************************
 * Run a simple comparison test.
 */
Tester.prototype.test = function(d,x,y){
  if(arguments.length == 0)
    console.log(this.name + '_test: ' + 'OK.');
  if(!x || !y || !equal(x,y)){
    throw [this.name + ':',
           d,
           "  failed because ",
           JSON.stringify(x) || "(empty string)",
           "  didn\'t match",
           JSON.stringify(y)]
      .join("\n");
  }
};

/*******************************************************************************
 * Get a function that runs the test (for convenience).
 */
Tester.prototype.getTester = function(){
  var self = this;
  return function(x,y,z){ self.test(x,y,z); self.ran++; };
};

/*******************************************************************************
 * Just print a message indicating completion.
 */
Tester.prototype.finish = function(){
  console.log(this.name + ': OK, ' + this.ran + ' tests completed.');
};

////////////////////////////////////////////////////////////////////////////////
// Tests

/*******************************************************************************
 * Test the parser.
 */
exports.parse_test = function(){
  var tester = new Tester('parse_test'), test = tester.getTester();
  function t(a,b){test(JSON.stringify(a),parse(a),b)}
  t('a b'                  , ['a','b']);
  t('a'                    , 'a');
  t('(a)'                  , 'a');
  t('((a))'                , 'a');
  t('((a)) b'              , ['a','b']);
  t('((a))b'               , ['a','b']);
  t('(((a))b)c'            , [['a','b'],'c']);
  t('a(b)((c))'            , ['a','b','c']);
  t('(a(b)((c)))d'         , [['a','b','c'],'d']);
  t('((a) )  b'            , ['a','b']);
  t('((a) ) b'             , ['a','b']);
  t('(((a) ) b) c'         , [['a','b'],'c']);
  t('a(b) ((c) ) '         , ['a','b','c']);
  t('(a(b) ((c) ) ) d'     , [['a','b','c'],'d']);
  t(' ( (a) )  b'          , ['a','b']);
  t(' ( (a) ) b'           , ['a','b']);
  t(' ( ( (a) ) b) c'      , [['a','b'],'c']);
  t('a (b)  ( (c) ) '      , ['a','b','c']);
  t(' (a (b)  ( (c) ) ) d' , [['a','b','c'],'d']);
  tester.finish();
}

/*******************************************************************************
 * Test the unifier.
 */
exports.unify_test = function(){
  var tester = new Tester('unify_test'), test = tester.getTester();
  function up(a,b,out){ return test(JSON.stringify(a) + ' = ' + JSON.stringify(b),
                             prettify(unify({
                               exp1: parse(a),
                               exp2: parse(b)
                             }).result),out); };
  up('a'      , 'a'                , 'a');
  up('a'      , 'z'                , 'a');
  up('a b'    , 'x y'              , 'a b');
  up('a b c'  , 'x y y'            , 'a b b');
  up('A'      , 'A'                , 'A');
  up('a'      , 'A'                , 'A');
  up('A'      , 'a'                , 'A');
  up('a b'    , 'A b'              , 'A b');
  up('a b'    , 'A a'              , 'A A');
  up('a a'    , 'x A'              , 'A A');
  up('a a a'  , 'x A x'            , 'A A A');
  up('a a x'  , 'A k (k k)'        , 'A A (A A)');
  up('x A y'  , 'y z A'            , 'A A A');
  up('x x'    , '(A y C) (A B z)'  , '(A B C) (A B C)');
  up('Map String value -> List (Map String value)',
     'Map key Int -> List (Map key Int)',
     'Map String Int -> List (Map String Int)');
  
  // Should fail with error
  // up('x y A' , 'x B y'            , '');
  
  // Should fail with occurs check
  // up('x'      , 'x x'              , '∞');
  
  tester.finish();
}

////////////////////////////////////////////////////////////////////////////////
// Utilities
//

/*****************************************************************************
 * Is an object an array? The answer is no.
 */
Object.prototype._unifier_isArray = function(){
  return false;
};

/*****************************************************************************
 * Is an array an array? The answer is “oui, monsieur!”
 */
Array.prototype._unifier_isArray = function(){
  return true;
};

/*****************************************************************************
 * Zip two lists with a cons function.
 */
function zipWith(ys,xs,cons){
  var len = Math.max(xs.length,ys.length);
  var accum = [];
  for(var i = 0; i < len; i++){
    accum.push(cons(ys[i],xs[i]));
  }
  return accum;
};

/*****************************************************************************
 * Are two objects structurally equal?
 */
function equal(a,o){
  return JSON.stringify(a) == JSON.stringify(o);
}