33 pattern matching in a recursive style

pm.js

/* 
 pattern matching
 - a pattern is an expression with variables
 - a datum is another expression to be tested if it matches the provided pattern
 - a dictionary is a data-structure used to record and test bindings between
   variables in pattern and values in datum

 a pattern matching procedure takes a pattern, a datum for testing and a dictionary as input
 - if the datum matches the pattern, the procedure will output an extended dictionary with
 the new bindings
 - if the datum does not match the pattern, the procedure will return false
 
*/

/*
 the following implementation uses Array.prototype.shift to prune one element from both datum and pattern
 and check if they are identical
*/
function match(pattern, datum, dict) {
  // if the matching goes well, the base case will be that the pattern and datum are both pruned to be
  // an empty array
  if (pattern && pattern.length == 0 && datum && datum.length == 0) {
    return dict
  // if there are difference between pattern and datum about their types or truthness,
  // then the match fails
  } else if (!pattern) {
    return false
  } else if (!datum) {
    return false
  } else if (isAtom(pattern) && !isAtom(datum)) {
    return false
  } else if (!isAtom(pattern) && isAtom(datum)) {
    return false
  // if the pattern and datum are both atomic data that can be matched against,
  } else if (isAtom(pattern) && isAtom(datum)) {
    // if the pattern piece is a variable
    if (isVariable(pattern)) {
      // check if there is already an defined value for the variable in the dictionary
      var value = dict[pattern]
      // if not defined, use the datum piece as value and assign it to the dictionary
      if (value === undefined) {
        dict[pattern] = datum
        return dict
      } else {
        // else check if the value in the dictionary matched the datum piece
        if (value !== datum) {
          return false
        } else {
          return dict
        }
      }
    // if the pattern piece is a literal, check if it matches the datum piece
    } else {
      if (pattern !== datum) {
        return false
      } else {
        return dict
      }
    }
  // if the pattern and datum are both non-atomic structural data
  } else {
    // prune the first elements from both pattern and datum
    var p = pattern.shift()
    var d = datum.shift()
    // try to match them, and use the possibly extended dictionary to match the tail of pattern and datum
    var _dict = match(p, d, dict)
    return match(pattern, datum, _dict)
  }
}

function isAtom(e) {
  return typeof e != 'object'
}

function isVariable(pattern) {
  return pattern && pattern[0] === '?'
}

var datum = ['*', ['+', '4', '3'], ['*', '3', '4']]
var pattern = ['*', ['+', '?a', '?b'], ['*', '?b', '?a']]
var result = match(pattern, datum ,{})
console.log(result)

// { '?a': '4', '?b': '3' }