Simple unifier

unifier.js

/*******************************************************************************
 * Unify two expressions.
 */
function unify(config){
  var exp1 = config.exp1, exp2 = config.exp2;
  var frame = config.frame || {};
  return config.returnFrame?
    [resolve(go(exp1,exp2)),frame] : resolve(go(exp1,exp2));
  function go(exp1,exp2){
    if(isConstant(exp1) && isConstant(exp2) && exp1.equal(exp2)){
      return exp1;
    } else if (isFree(exp1) && isFree(exp2)) {
      return extendWithFree(exp1,exp2);
    } else if (isGroup(exp1) && isGroup(exp2)) {
      return exp1.zipWith(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');
    }
  }
  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;
    }
  }
  function extendWithConstantOrGroup(free,constant){
    if(frame[free]){
      if(frame[free].contents){
        if(frame[free].contents.equal(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;
    }
  }
  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;
      }
    }
  }
  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');
      }
    }
  }
}

function search(db,exprStr){
  var results = [], expr = parse(exprStr);
  db.map(function(entry){
    var result;
    try {
      if(typeof entry != 'string') {
        // First, ensure that the conclusion of the rule matches the
        // query.
        // E.g. Query: (Person a)
        //      Conclusion: (Person x)
        var conclusion = parse(entry[0]);
        unify({exp1:conclusion,exp2:expr});
        // Second, search for an instantiation of the rule's body in
        // the DB.
        var body = entry[1];
        var dbSansThisRule = db;
        queryResult = search(dbSansThisRule,body)[0];
        // Third, unify to get the /frame/ for the unification of the
        // body and the result.
        var frame;
        var bod = unify({exp1:queryResult,exp2:parse(body),returnFrame:true});
        result = bod[0];
        frame = bod[1];
        // Finally, merely instantiate the conclusion against the
        // body's frame.
        result = unify({exp1:conclusion,exp2:conclusion,frame:frame});
      }
      else {
        result = unify({exp1:parse(entry),exp2:expr});
      }
    } catch (e){
      return false;
    }
    results.push(result);
  });
  return results.length? results : 'No.';
}

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

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

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

/*******************************************************************************
 * Pretty print an expression to a string.
 */
function prettify(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.
 */
function parse(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];
  }
}

////////////////////////////////////////////////////////////////////////////////
// Simple tester

function Tester(name){
  this.name = name;
}

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

Tester.prototype.getTester = function(){
  var self = this;
  return function(x,y,z){ self.test(x,y,z); };
};

Tester.prototype.finish = function(){
  console.log(this.name + ': OK.');
};


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

function parse_test(){
  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();
}

function unify_test(){
  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)
                             })),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();
}

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

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

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

/*******************************************************************************
 * Filter a list.
 */
Array.prototype.filter = function(pred){
  var len = this.length;
  var accum = [];
  for(var i = 0; i < len; i++){
    if(pred(this[i],i))
      accum.push(this[i]);
  }
  return accum;
};

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

parse_test();
unify_test();

console.log(search([
  ['MeetingsVisitor person','SupremeManager person'],
  ['BoredToTears poorSoul','MeetingsVisitor poorSoul'],
  'Programmer Janis',
  'Programmer Mihai',
  'SupremeManager Regis',
  'Programmer Chris',
],'BoredToTears who'));