Lisa/Logical Implementation

type MatchConstraint = Map[String, Any]
def unifyMatch(pattern1: Any, pattern2:Any, givenConstraints: MatchConstraint): Option[MatchConstraint] = {
  // 为了方便期间，使用了本地可变状态。
    val constraints = collection.mutable.Map.from(givenConstraints)
    // 表示匹配成功后该返回的结果
    def succeed = Some(constraints.toMap)

  // 检测当前的表达式是不是依赖于该符号，这是简单的树遍历。
    def dependsOn(name: String, exp: Any): Boolean = exp match {
        case Symbol(`name`) => true
        case Symbol(symbol) => constraints.get(symbol).exists(dependsOn(name, _))
        case list: List[_] => list.exists(dependsOn(name, _))
        case _ => false
    }

    def extend(name: String, exp: Any): Option[MatchConstraint] = {
      // 忽略匹配
        if(name == "_") succeed
        else constraints.get(name) match {
            case Some(x) => matchOne(exp, x) // 如果已经有该变量的限制了，则限制的值应当于当前值归一匹配。
            case _ => exp match {
              // 如果当前要扩展的值是一个变量
                case Symbol(symbol) => constraints.get(symbol) match {
                    case Some(x) => matchOne(Symbol(name), x) // 环境中有关于该变量的限制，则同上。
                    case _ => 
                        constraints.update(name, exp) // 否则就新增一个限制
                        succeed
                }
                case _ =>
                    if (dependsOn(name, exp)) None // 如果当前要扩展的表达式依赖于自身，我们无法求解一个不动点方程，故放弃。
                    else {
                        constraints.update(name, exp)
                        succeed
                    }
            }
        }
    }

  // 将一个表达式和另一个表达式做归一匹配
    def matchOne(pattern1: Any, pattern2: Any): Option[MatchConstraint] = {
        if(pattern1 == pattern2) succeed // 如果两者相等，yataze！
        else pattern1 match {
            case Symbol(name) => extend(name, pattern2) // 如果是一个变量，则扩展该变量的限制。
            case _ => pattern2 match {
                case Symbol(name) => extend(name, pattern1)
                case list1: List[_] => pattern2 match {
                    case list2: List[_] => matchMany(list1, list2) // 如果要匹配的是俩列表，则匹配两个列表。
                    case _ => None
                }
                case _ => None
            }
        }
    }

    // 匹配两个列表
    def matchMany(pattern1: List[Any], pattern2: List[Any]): Option[MatchConstraint] = {
        pattern1 match {
            case Nil => if (pattern2.isEmpty) succeed else None // 如果其中一个空了，另一个也得是空的
            case (Symbol("...") :: (sym@Symbol(_)) :: Nil) :: xs => // 匹配任意长度的变量 这里是(... x)，你可以定义自己的任意长度匹配的表现形式。
          if (xs.isEmpty) matchOne(sym, pattern2)
          else None
            case otherwise :: xs => pattern2 match {
          case (Symbol("...") :: (sym@Symbol(_)) :: Nil) :: xs => // 对pattern做相同对任意长参数检查
            if (xs.isEmpty) matchOne(pattern1, sym)
            else None
                case y :: ys => for {
                    _ <- matchOne(otherwise, y)
                    tailMatch <- matchMany(xs, ys)
                } yield tailMatch // 否则就先匹配头，再匹配剩下的
                case _ => None // 第二个是空，第一个却不是空，这不可能匹配成功。
            }
        }
    }

    matchOne(pattern1, pattern2) // 最后启动匹配
}

type ConstraintType = Map[String, Any]
type MatcherFunction = (LazyList[ConstraintType], LogicalContext) => LazyList[ConstraintType]
trait Matcher extends MatcherFunction

def and(that: Matcher): Matcher = (in, lc) => {
    val thisOut = this(in, lc)
    that(thisOut, lc)
}

def or(that: Matcher): Matcher = (in, lc) => {
    val thisOut = this(in, lc)
    thisOut #::: that(in, lc)
}

def not: Matcher = (in, lc) => {
    in.filter(frame => this(LazyList(frame), lc).isEmpty)
}