1

每当我不得不在 Scala 中创建 AST 时，我都会使用抽象的密封特征/案例类模式。到目前为止它工作得非常好，让编译器检查模式匹配是一个很大的胜利。

但是现在我遇到了一个我无法解决的问题。如果我有 2 种语言，其中一种是另一种的子集，该怎么办？作为一个简单的例子，考虑一个 lambda 演算，其中每个变量都是绑定的，以及另一种相关的语言，其中变量可以是绑定的或自由的。

第一语言：

  abstract sealed class Expression

  case class Variable(val scope: Lambda, val name:String) extends Expression

  case class Lambda(val v: Variable, val inner: Expression) extends Expression

  case class Application(val function: Expression, val input: Expression) extends Expression

第二语言：

  abstract sealed class Expression

  case class Variable(val name:String) extends Expression

  case class Lambda(val v: Variable, val inner: Expression) extends Expression

  case class Application(val function: Expression, val input: Expression) extends Expression

唯一的变化是从变量中删除范围。

如您所见，有很多冗余。但是因为我使用的是密封类，所以很难想出一个好的方法来扩展它。组合它们的另一个挑战是，现在每个 Lambda 和应用程序都需要在类型级别跟踪其参数的语言。

这个例子并没有那么糟糕，因为它非常小，但是想象一下对于严格的 HTML/弱 HTML 也有同样的问题。

4

2 回答 2

3

这个问题的经典答案是有一个通用的 AST 和一个额外的验证通道。您将不得不使用语法结构良好但无法通过验证（类型检查）的 AST。

如果您想在类型级别进行区分，则类型检查通过可能会产生新的 AST。您可能可以为此使用路径相关类型。

作为旁注，您的示例似乎有一个循环：创建 aLambda您需要 a Variable，但要创建 aVariable您需要 external Lambda。

于 2014-05-14T12:59:44.397 回答
1

在决定如何进行泛化时，有时考虑一个需要对泛化结构进行操作的示例函数会很有帮助。因此，请进行一些您希望在绑定树和自由树上执行的操作。采取 eta 减少：

def tryEtaReduce(x: Expression): Option[Expression] =
  x match {
    case Lambda(v1, Application(f, v2: Variable)) if v1 == v2 => Some(f)
    case _ => None
  }

对于上面的函数，像下面这样的概括将起作用，尽管它有一个明显的丑陋：

trait AST {
  sealed trait Expression

  type Scope

  case class Variable(scope: Scope, name: String) extends Expression
  case class Lambda(v: Variable, inner: Expression) extends Expression
  case class Application(function: Expression, input: Expression) extends Expression
}

object BoundAST extends AST {
  type Scope = Lambda
}

object FreeAST extends AST {
  type Scope = Unit
}

trait ASTOps {
  val ast: AST
  import ast._

  def tryEtaReduce(x: Expression): Option[Expression] =
    x match {
      case Lambda(v1, Application(f, v2: Variable)) if v1 == v2 =>
        Some(f)
      case _ =>
        None
    }
}
于 2014-05-14T17:49:54.073 回答