Programming Language Sumi DEMO

match1:(pattern, datum, binding) {
  variablep:(pattern) {
    (pattern instanceof String||typeof(pattern) == "string")
    && pattern.charAt(0) == "$"
    && pattern != "..."
  }
  atom:(pattern){pattern == null || typeof(pattern) == "string"|| (pattern instanceof String)}
  consp:(list){list instanceof Array}
  if (variablep(pattern)) {
    if (pattern in binding) {
      return match1(binding[pattern], datum, binding);
    } else {
      binding[pattern] = datum;
      return binding;
    }
  }
  if (atom(pattern) && atom(datum)) {
    if (pattern+"" == datum+"") {return binding}
    return null
  }
  if (pattern instanceof XOX && datum instanceof XOX ||
      pattern instanceof XOY && datum instanceof XOY) {
    if(pattern.op != datum.op) {return null}
    result : match1(pattern.exp1,datum.exp1,binding)
    if (result == null) {return null;}
    return match1(pattern.exp2, datum.exp2, binding)
  }
  if (pattern instanceof XPXP && datum instanceof XPXP) {
    if (pattern.left != datum.left) {return null}
    if (pattern.right != datum.right) {return null}
    result: match1(pattern.exp1,datum.exp1,binding)
    if (result == null) {return null}
    return match1(pattern.exp2, datum.exp2, binding)
  }
  if (pattern instanceof PXP && datum instanceof PXP) {
    if (pattern.left != datum.left) {return null}
    if (pattern.right != datum.right) {return null}
    return match1(pattern.exp,datum.exp,binding)
  }
  if (pattern instanceof XO && datum instanceof XO ||
      pattern instanceof OY && datum instanceof OY) {
    if(pattern.op != datum.op) {return null}
    return match1(pattern.exp,datum.exp,binding)
  }
  if (consp(pattern) && consp(datum)) {
    result : binding
    for (i : 0; i < pattern.length; i++) {
      if (pattern[i] == "...") {
        return match1(pattern[i + 1], datum.slice(i, datum.length), binding);
      }
      result = match1(pattern[i], datum[i], binding);
      if (result == null) {return null}
    }
    if (datum.length > pattern.length) {return null}
    return result
  }
  return null
}
#print(match1(["aaa";qq($b);"$ccc"],["aaa";"bbb";["ccc";"ddd"]],{})+"\n")
#print(match1(qq(aa + $b),qq(aa+cc*dd),{})+"\n")
#print(match1(
#  qq($f($arg){$body}),
#  qq(a.b(a,b,c){a+b*d}),{}
#)+"\n")
#
#print(match1(
#  qq(if($arg){$a}else{$b}),
#  qq(if(a==b){a}else{b}c),{}
#)+"\n")

filter:(tree,rule,f) {
  rep:(tree){
    rc:match1(rule, tree,{})
    if(rc != null) {return f(rule,rc)}
    if(tree instanceof XOX) {return new XOX(rep(tree.exp1),tree.op,rep(tree.exp2)) }
    if(tree instanceof XOY) {return new XOY(rep(tree.exp1),tree.op,rep(tree.exp2)) }
    if(tree instanceof XO) {return new XO(rep(tree.exp),tree.op)}
    if(tree instanceof OY) {return new OY(tree.op,rep(tree,exp))}
    if(tree instanceof PXP) {return new PXP(tree.left,rep(tree.exp),tree.right)}
    if(tree instanceof XPXP) {return new XPXP(rep(tree.exp1), tree.left,rep(tree.exp2),tree.right)}
    return tree
  }
  rep(tree)
}

rc1:filter(qq(a+b*c),qq($a+$b),(t,r){return qq{add(uq{r.$a},uq{r.$b})} } )
rc2:filter(rc1,qq($a*$b),(t,r){return qq{mul(uq{r.$a},uq{r.$b})} } )