Paret语言研究的类型推理算法.pdf

【Paret语言的类型推理算法】 在此次任务中，我们将关注于实现Paret语言的类型推断算法。这个算法是我们在讲座中学习的核心内容，它主要用于一个无类型的Paret语言，该语言没有像在Type Checker任务中那样为`lam`（lambda表达式）和空表达式指定类型注解。实际上，正是类型推断算法负责恢复这些注解。 9.2 Paret语言 Paret语言在这个任务中的形式与有类型的Paret语言非常接近，主要的区别在于去除了显式的类型信息。我们还重新引入了`and`和`or`表达式，并将`let`从基本表达式转换为语法糖。因此，你需要实现一个desugarer（脱糖器），将`and`、`or`和`let`表达式转换为等价的函数形式。 9.2.1 语法规则 无类型的Paret语言的语法规则如下： 1. 基本数据类型：`<num>`（数字）、`<string>`（字符串）、`true`（布尔值真）、`false`（布尔值假） 2. 操作符：`+`（加法）、`++`（连接）、`num=`（数字相等）、`str=`（字符串相等） 3. 控制结构：`if`（条件分支） 4. 变量引用：`<id>`（标识符） 5. 函数应用：`( <expr> <expr> )` 6. 元组操作：`first`（获取元组第一个元素）、`rest`（获取元组剩余元素）、`is-empty`（检查列表是否为空） 7. 构造函数：`link`（创建列表）、`empty`（创建空列表） 8. 函数定义：`lam (<id>) <expr>`（匿名函数） 9. 语法糖：`let (<id> <expr>) <expr>`（局部变量绑定）、`and <expr> <expr>`（逻辑与）、`or <expr> <expr>`（逻辑或） 9.3 分配 在实现类型推断算法时，你需要考虑以下几个关键点： 9.3.1 术语 理解术语的含义对于实现算法至关重要。`Term`在这里指的是Paret语言中的表达式，它们可以是基本类型、操作、函数应用或构造函数等。 9.4 需要实现的特性 9.4.1 Desugaring with Labels 这里的"Desugaring"是指将糖语法（如`and`和`or`）转换为其等价的基本语言结构。你需要为`and`和`or`表达式创建相应的转换规则。 9.4.2 Label Environment 标签环境（Label Environment）用于存储变量及其关联的类型信息。在类型推断过程中，它将帮助跟踪和确定表达式的类型。 9.4.3 类型推断算法 算法分为两个阶段： 9.4.3.1 生成约束（Phase 1: Constraint Generation） 在这一阶段，你将遍历源代码，根据语法规则生成表示类型关系的约束。 9.4.3.2 统一（Phase 2: Unification） 统一对阶段1生成的约束进行处理，找到满足所有约束的类型分配。这通常涉及到解决类型变量的代换问题。 9.4.4 异常处理 在处理不同类型或无法推断的表达式时，你可能需要处理异常情况。 9.5 测试 为了确保算法的正确性，你需要编写测试用例来覆盖各种情况，包括边缘案例和复杂表达式。 9.6 开始代码 9.6.1 Set Library 提供了一个预定义的集合库，可以用于在类型推断过程中存储和操作类型信息。 9.7 提交内容 你需要提交的包括实现的类型推断算法、测试用例以及相关的文档说明。 通过完成以上步骤，你将实现一个完整的类型推断系统，它能自动推断Paret语言表达式的类型，使得程序在执行前就能检测到潜在的类型错误。这是静态类型语言编译器和解释器的关键部分，它有助于提高代码的可靠性和可维护性。