Cat - C# 中的静态类型编程语言解释器

• 下载源代码和可执行文件 - 108 Kb

引言

本文介绍了一个静态类型函数式堆栈式编程语言Cat (http://www.cat-language.com/) 的解释器。Cat 可以最简洁地被描述为带有类型系统的函数式Forth的近亲。Cat 的灵感来源于多种语言，其中最著名的是Joy（另一个函数式Forth的近亲，但没有类型系统）。相关语言列表可在本文的末尾找到。

本文附带的Cat解释器版本为0.9.6。最新版本的解释器和源代码可在 http://www.cat-language.com/download.html 公共访问。

本文和源代码应该对那些对实现解析器、编译器或解释器感兴趣的人有所帮助。本文不是教程，因此不推荐初学者阅读，而是一个文档较好、功能齐全的解释器示例，它实现了类型推断和类型检查，您可以将其作为独立解释器或脚本插件进行修改和定制。

许可证

Cat的可执行文件和源代码均属于公共领域。这意味着您可以无限制地使用和修改它们，无需要求或署名。您可以以任何许可协议发布此代码的任何修改版本，或用于任何目的。您可以随意在任何商业产品中使用源代码，并在您的老板面前展现出色的表现。但请注意，我们不对代码提供任何明示或暗示的保证。这意味着您使用代码的风险自行承担，就像获取任何免费内容一样。

背景

Cat的设计初衷是成为一种具有强类型系统且可移植的中间语言的简单脚本语言。我发现现有的中间语言难以阅读和编写，并且通常缺乏类型系统。我还发现许多脚本语言倾向于拥有繁琐的语法，并且缺乏静态类型系统。我认为Cat的优势在于其简洁性、表达力、可扩展性和可移植性。

Cat语言的语法和语义受到堆栈式编程语言（如Forth、Postscript、Joy）、中间语言（如CIL/MSIL、Java字节码）以及静态类型函数式语言（如Haskell、OCaml）的启发。

对于脚本语言而言，Cat有些与众不同，因为它具有静态类型和类型推断功能。这并非一个独特想法，已有多种语言实现了这一点（例如Haskell、OCaml、Scala、F#），但您在CodeProject上很快就会找到它们的C#版本源代码。

Cat可能让您感兴趣的几个原因：

• 它属于公共领域，因此对商业应用友好。
• 语言定义非常小巧，易于实现和移植。
• 源代码是用C#编写的。
• 可以非常容易地实现Cat的动态版本。

静态类型

具有类型推断的静态类型语言的行为与动态语言非常相似，因为不需要类型注解。因此，Cat程序可以非常紧凑。例如，考虑以下将值加一的Cat程序：

define inc { 1 + }  

在弱类型语言中，您可能可以将字符串传递给这样的函数，并在执行期间导致错误。

当然，这假设控制流确实会执行。动态类型的一个挑战是类型错误可能会潜伏，直到软件公开发布后才暴露。

类型推断的特别之处在于，该函数需要整数的事实是在编译时推断出来的，并且可以使用非整数的调用可以被检测到。类型推断减轻了为函数编写类型注解的开销，但又不牺牲编译器识别类型错误的安全。安全又便捷。

Cat基础

Cat编程环境由一组函数定义（用户定义和原始函数）和两个评估堆栈组成。大多数操作会操作“主”堆栈，少数操作会使用“辅助”堆栈。当我只提到“堆栈”时，我指的是主堆栈。

Cat函数从堆栈中弹出其参数，并将结果推入堆栈。字面数字（例如 `42`、`0`、`1999` 等）和字面字符串（例如 `"all your base are belong to us"`）也作为函数，将单个值推入堆栈。

二元算术运算符（例如 +、*、<= 等）从堆栈顶部获取其操作数，并将结果推回到堆栈。在Cat中，顶部的值被视为右操作数，其下方的值被视为左操作数。因此，Cat的语法看起来像逆波兰表示法（RPN）。以下是Cat运行示例：

>> 33 3 *
main stack: 99
>> 1 2 + 5 *
main stack: 99 15
>> >
main stack: true
>> pop
main stack: _empty_

语言中的所有短语（由换行符终止的术语序列）要么是新函数的定义，要么是解释器要执行的指令。

Cat函数定义如下：

>> define what_is_the_answer { 6 7 * }
main stack: _empty_
>> what_is_the_answer
main stack: 42  

有关Cat语言的更多信息，请参阅Cat的详细教程：http://code.google.com/p/cat-language/wiki/Tutorial。关于该语言更深入、更技术性的描述可以在 http://www.cat-language.com/manual.html 找到。

Cat语法的正式定义可以在 http://www.cat-language.com/manual.html#syntax 找到。简而言之，Cat解释器直接接受文本词、符号组、数字、字符串或引用的形式的命令。

我想指出，Cat的一个有趣特性是能够定义新符号。因此，如果我喜欢Atari Basic中的老式“?”运算符，我可以这样写：

>> define ? { write_line }

源文件

这里没什么特别的，只列出了项目中的文件及其简要描述。

CatBase.cs	定义了一个包含有用实用函数的类型的基类
CatStack.cs	定义了一个自定义堆栈类，用于实现主评估堆栈和辅助评估堆栈
CatType.cs	定义了Cat的基类和简单的原始类型
Config.cs	包含一组全局标志，用于控制解释器的行为
ConstraintSolver.cs	由类型推断引擎使用，通过解决约束规则来计算类型
Executor.cs	管理主堆栈和辅助堆栈，并包含原始函数的实现
Functions.cs	提供了表示Cat函数的类的定义
FxnType.cs	定义了表示函数类型的对象
Interpreter.cs	包含解释器的获取和执行循环
Main.cs	提供了应用程序的入口点，并调用初始化过程
Parser.cs	定义了抽象语法树（AST）节点类型，并从字符串创建类型和程序的AST表示
Primitives.cs	注册预定义的原始函数和库定义
Scope.cs	定义了Scope类，用于处理和存储定义
TypeInferer.cs	从函数定义中推断出函数的类型
TypeStack.cs	用于存储类型序列，如函数类型的消耗和产生
TypeVars.cs	定义了类型变量和类型变量声明
UnitTest.cs	包含大量标准库和类型推断引擎的测试

解释器

以下是解释器工作原理的广泛概述：

• 解释器从用户那里获取命令。
• 指令被发送到全局作用域对象（通过 `Scope.Global()` 访问）进行处理。
• 作用域对象会检查指令是否实际上是定义。判断依据是它是否以单词“define”开头，后跟空格。
• 如果解释器接收的指令是一个定义，那么：
  • 创建一个定义对象
  • 推断类型
  • 如果定义中存在类型注解，则将其与推断出的类型进行比较。

  或

  如果指令确实是直接为编译器设计的指令，那么它们会被解析并按顺序执行。

解析器

解析器的作用是将源代码从文本格式转换为更易于管理的格式，通常是抽象语法树（AST）。传统上，解析是词法分析阶段之后的第二步，该阶段将文本流分解为标记。词法分析（lexxing）阶段实际上不是必需的，并且在Cat语言中被完全跳过。

Cat解析器生成的AST使用 `AstNode` 类表示。

Cat解析器是所谓的简单递归下降解析器的直接实现。Cat解析器会为语言的每个不同元素创建一个新的树节点，这些元素在语法产生式中有所表达。存在多种不同类型的语言元素需要创建节点，这些类型通过 `NodeType` 枚举区分。

public enum NodeType
{
    Definition,
    StackState,
    SimpleType,
    FxnType,
    Root,
    Quotation,
    Word,
    Number,
    String,
    ParanGroup,
    BraceGroup,
    LineComment,
    Reference,
    VarDecl,
    Undefined
};

语言解析器使用各种线索，并在必要时查看单个字符以决定正在解析的语言元素。这避免了Cat解析器在失败时需要回溯。在更复杂的语言中，解析器通常需要能够放弃一个解析规则，删除当前节点，然后尝试下一个。

Cat语言的一个值得指出的重大区别是，符号序列被标记为 `NodeType.Word`，并用于定义新函数。

类型推断器

[注意：本节只是对类型推断算法的粗略简化，并且非常技术化。您可以轻松跳过本节，仍然能够理解和使用该项目]

Cat的类型推断算法非常复杂，当前的实现有些脆弱。这部分原因是这是一个全新的实验性类型系统，并且正在积极开发中。以下算法描述只是步骤的近似。我试图传达的是逻辑，而不是细致的现实。

类型推断算法以具有类型签名的函数初始化：

(_main_:any*)(_aux_:any*) -> (_main_)(_aux_)

这被称为返回类型。构成函数定义的每个操作的操作被抽象地模拟在包含类型的堆栈上。也就是说，只模拟类型消耗和产生，而不模拟实际操作本身。

类型检查和类型推断算法通常通过在类型级别模拟函数的操作来工作。例如，要模拟整数加法函数，您会从类型堆栈中弹出两个整数，并将一个整数推入类型堆栈。

在类型推断算法的情况下，类型堆栈使用一个多类型变量进行初始化。当从类型堆栈中弹出类型并找到多类型变量时，它会传达一个约束：类型变量必须与该值匹配。通过演绎过程，该约束用于更精确地描述类型变量。

在Cat类型推断算法中，模拟的类型堆栈取自一个名为 `ret` 的 `FunctionType` 对象。通过应用以下算法，从定义的第一条指令开始，可以正确推断出返回类型：

• 指令的类型被转换为规范形式。也就是说，为消耗和产生添加了一个默认的主变量和辅助变量。
• 对于当前指令的每个主消耗类型：
  • 如果匹配，则从 `ret` 的产生中弹出一个类型。
  • 如果类型不匹配，则其中一个必须是类型变量，或者已发生类型错误。
  • 如果一个或两个类型是变量，则生成一个约束规则。该规则对变量定义了约束，说明它必须匹配的类型。
• 然后对辅助消耗类型重复之前的算法。
• 现在我们有了描述各种类型变量的许多约束。需要解决这些约束。
• 约束解析算法确保每个类型变量要么保持为变量引用，要么与单个具体变量关联，或者如果它是多类型变量，则与一组具体变量关联。
• 在约束解析过程的结果之后，`ret` 中的所有已解析变量以及当前函数的类型都被映射到新类型。
• 当前指令的类型（现在已解析）的主产生和辅助产生被添加到返回类型的产生中。
• 如果有下一条指令，则重复此过程；否则，退出。

现在所有指令都已模拟，并且所有约束都已解决，`FxnType` `ret` 现在包含了推断出的类型。

执行器

执行器管理主堆栈和辅助堆栈，并提供原始函数的实现。原始函数是 `static void` 函数，没有参数。它们通过PrimitiveDelegation委托类型进行引用。

执行器提供一个公共函数来执行原始字符串，但实际处理字符串的工作则委托给 `Scope` 对象。这个设计决定可能显得有些奇怪，但它为Cat未来版本可能支持命名空间奠定了基础。命名空间需要单独的作用域对象，并且这些对象可能可以嵌套。

函数

`AtomicOps` 类使用 `RegAtomicOp` 方法将所有函数注册到全局作用域对象 `Scope.Global()`。 `RegAtomicOp` 方法需要一个 `PrimitiveDelegate`、一个函数名称的 `string`、函数的类型的 `string`，以及描述的 `string`。描述用于 `help` 和 `desc_of` 原始函数。

或者，您可以使用现有函数定义标准库函数。为此，您可以使用 `AtomicOps.RegLibFxn` 方法。`RegLibFxn` 方法在结构上类似于 `RegAtomicOps`，但需要以 `string` 形式定义函数，并且类型可以推断。如果您提供了类型，它将与从指令推断出的类型进行比较，作为确保类型安全的最后一道防线。

单元测试

单元测试可能更准确地称为集成测试，因为它们只测试高级功能，如类型推断机制和原始函数。测试是通过观察其在多种情况下的预期行为，并与您自己的期望进行比较来学习语言的绝佳方式。测试可以通过 `Config` 类中的各种标志来打开和关闭，并修改其行为。

已知问题

在当前实现下，某些类型系统的测试会失败。这些测试位于 `RunKnownIssuesTests` 函数中，默认情况下不执行。控制此项的标志位于 `Config` 类中。

当前Cat版本的一些已知问题是：

• 类型错误对用户不够友好。
• 类型系统无法表达递归定义的类型。
• 传递给解释器的指令不是静态类型检查的。

无类型Cat (Kitten)

Cat不必用作静态类型语言。可以忽略类型注解，并关闭类型推断功能。要做到这一点，只需在 _Config.cs_ 中将标志 `Config.gbStaticTyping` 设置为 false，然后您就得到了一个Kitten解释器。Kitten是Cat的无类型变体的名称。

每个Cat程序都将是一个有效的Kitten程序，但Kitten解释器会更加宽松。例如，您可以在Kitten中编写以下代码，而在Cat中会失败：

define f { [42] ["all your base"] if }  

Cat的类型要求（Kitten中不强制执行）是传递给 `if` 函数的两个函数必须具有相同的签名。在示例中，一个将整数推入堆栈，另一个将字符串推入堆栈。

值得注意的是，Kitten比Cat更接近Joy语言。

相关工作

以下是一些启发Cat语言或与其非常相关的语言：

堆栈式语言

• Joy编程语言
• Forth编程语言
• Delta Forth
• Factor编程语言
• Strong Forth
• Postscript [PDF]

中间语言

• Parrot Byte Code
• LLVM编译器基础结构
• Java Byte Code
• Typed Assembly Language (TAL)
• C-- (C minus minus)
• Small C
• Common Intermediate Language (CIL，又称MSIL)

函数式语言

• Scheme
• OCaml
• Haskell
• F#

脚本语言

• Lua
• EcmaScript

结论

我非常乐意听到由此工作产生的衍生项目，或者您感兴趣实现的Cat语言应用程序的想法。我希望这些代码对您有帮助，并希望您发现该语言有趣且实用。