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节点所属的范围，这样才能使它变得有用.因此，我想以某种方式包装这个东西，以便每次添加声明时都要构建一个节点到作用域的哈希映射。

我考虑过许多模式，但我找不到一种方法来做到这一点：

• 功能
• 无可变状态
• 不错(也就是说，不让我觉得写东西是多余的)

有人能想出点好东西吗？

Answer 1

您可能想看看前往斯卡拉。它是一个纯函数库，用于构造具有作用域绑定的语言。与从符号到作用域的映射不同，在这种情况下，您必须为您的符号提供一个新的名称来源，绑定允许您使用“本地无名”术语，并完成输入、退出和遍历以及替换为您的作用域的所有工作。

库的核心是数据类型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编程语言的源代码可以很好地参考如何在实践中使用这个库。