sbool lispMatch_debug;

static Map<S, Lisp> lispMatch(Lisp pat, Lisp input, S... variables) {

  ret lispMatch(pat, input, asSet(variables));

}

static Map<S, Lisp> lispMatch(Lisp pat, Lisp input, Collection<S> variables) {

  new Map<S, Lisp> matches;

  ret lispMatch_sub(pat, input, variables, matches) ? matches : null;

}

static bool lispMatch_sub(Lisp pat, Lisp nl, Collection<S> variables, Map<S, Lisp> m) {

  if (pat == null || nl == null) ret false;

  if (pat.isLeaf() && variables.contains(pat.head)) {

    if (lispMatch_debug) print("Var: " + pat.head + " => " + nl);

    ret lispMatch_putMatch(m, pat.head, nl);

  }

  if (neq(pat.head, nl.head)) ret false;

  // heads identical, proceed to children

  int n = pat.size();

  if (n != nl.size()) ret false;

  for (int i = 0; i < n; i++) {

    if (lispMatch_debug) print("Sub " + i + ": " + pat.get(i) + " => " + nl.get(i));

    if (!lispMatch_sub(pat.get(i), nl.get(i), variables, m))

      false;

  }

  true;

}

static bool lispMatch_putMatch(Map<S, Lisp> matches, S key, Lisp val) {

  if (matches.containsKey(key)) {

    if (neq(matches.get(key), val))

      false;

      //fail("multi-matching not implemented");

  } else

    matches.put(key, val);

  true;

}