Scala函数模式计算状态

Question

我正试图为一种名为minijava的迷你语言编写一个小型编译器，以便深入了解编译器构造和函数编程。我目前的实现是在Scala中，这也是我刚刚开始学习的语言。

sealed class Record()
case object Usage extends Record
case class Declaration(
    definition: Term,
    typ: Type
) extends Record
class Scope(
val parent: Option[ Scope ],
val scopes: List[ Namespace ],
// represents the actual (local) symbol-table
val symbols: Map[ (Namespace, String), Record ] = new HashMap()
) extends Immutable {
def add( ns: Namespace, id: String, record: Record ): Scope =
    new Scope(parent, scopes, symbols + Tuple2((ns, id), record ))
def enter_scope(scopes: List[ Namespace ]) = new Scope( Some(this), scopes )
def leave_scope() = parent
}

现在，我可以使用这个类通过遍历AST并构建范围树来构建符号表。使用模式匹配可以很好地实现这一点，而scala中的函数编程通过这种方式是有意义的。

然而，我需要跟踪AST节点所属的范围，以便使它变得有用。。。所以我想以某种方式包装这个东西，以便在每次添加声明时构建一个节点到作用域的哈希映射。

我考虑了很多模式，但我找不到一种方法来做到这一点，那就是：

• 功能性的
• 没有可变状态
• nice（即不会让我写一些感觉多余的东西）

有人能想出什么好主意吗？

Answer 1

您可能想了解一下Bound for Scala。它是一个纯粹的函数库，用于构建具有作用域绑定的语言。Bound允许您使用"本地无名称"术语，并为您完成所有进入、退出、遍历和替换到范围的工作，而不是从符号到范围的映射（在这种情况下，您必须为符号提供新名称的来源）。

库的核心是数据类型Scope[B,F[_],A]，其中F是表达式语言，B是绑定变量的占位符，A是自由变量的占位符。这封装了（本质上）类型为F[Either[B, F[A]]]的值。

为了演示这是如何工作的，语言中单个变量的绑定可以用类似lambda术语的东西来表示：

trait Exp[A]
...
case class Variable[A](a: A) extends Exp[A]
case class Lambda[A](e: Scope[Unit, Exp, A]) extends Exp[A]

lambda的主体是Exp，当您达到Variable时，它将是类型为Unit的绑定变量，或者是自由变量，在这种情况下，它将成为另一个Exp[A]。

Ermine编程语言的源代码对于如何在实践中使用这个库是一个很好的参考。