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 节点所属的范围，以便使这个东西有用...... 因此，我想以某种方式包装这个东西，以便每次添加声明时都构建节点到范围的 HashMap 。

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

• 功能性
• 没有可变状态
• 很好(即不会让我写出多余的东西)

有人能想出一些好东西吗？

Answer 1

您可能想看看Bound for Scala 。它是一个纯函数库，用于构建具有范围绑定(bind)的语言。 Bound 不是从符号到范围的映射，在这种情况下，您必须为符号提供新名称的来源，Bound 允许您使用“本地无名”术语，并完成为您进入、退出、遍历以及替换范围。

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

为了演示其工作原理，您的语言中单个变量的绑定(bind)可以用 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< 类型的绑定(bind)变量，或自由变量，在这种情况下它将是另一个 Exp[A]。

Ermine programming language的源代码对于如何在实践中使用该库是一个很好的引用。