# hw_lambda

**Repository Path**: harede/hw_lambda

## Basic Information

- **Project Name**: hw_lambda
- **Description**: lambda表达式作业
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-10-10
- **Last Updated**: 2026-10-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Lambda 表达式解析与求值

本次上机包含两项任务：用 C++17 实现一个 Lambda 表达式处理程序，以及在 Playground 中编写表达式定义。实验提供表达式节点、辅助函数、运行入口和测试工具，学生完成五个接口与 `.lam` 文件中的待填部分。

## 1. 表达式的文本语法

核心语言由变量、函数抽象和函数应用组成：

```text
expr := atom { atom }
atom := VAR | '(' expr ')' | '\' VAR '.' expr
VAR  := [a-z]+
```

`{ atom }` 表示零个或多个后续项。变量名使用一个或多个小写英文字母；空白用于分隔 token，括号确定分组。

- `xy` 是一个变量；`x y` 和 `x(y)` 都表示应用。
- `f x y` 按左结合组成 `((f x) y)`。
- `\x.x y` 表示 `\x.(x y)`，函数体延伸到当前括号层级的末尾。
- `(\x.x) y` 表示将函数 `\x.x` 应用到参数 `y`。

核心表达式使用反斜杠表示抽象，不接受 λ 字符、大写别名、数字字面量、注释或 `let`。空输入、非法字符、缺少点号、括号不配对等输入应抛出 `ParseError{pos}`；`pos` 为从 0 开始的输入字节位置，输入结束处可用字符串长度表示。

## 2. 作用域、等价与归约

### 变量绑定与 α 等价

变量由包围它的、最近的同名形参绑定。没有对应形参的出现称为自由出现；判断时需要明确表达式范围。

```text
\x.\x.x     最里面的 x 由内层形参绑定。
\x.\y.x y   x 由外层形参绑定，y 由内层形参绑定。
\x.x y      在整个表达式中，x 被绑定，y 自由出现。
```

改变形参及其绑定的出现，同时保持原有绑定关系，称为 α 转换。比较 α 等价时允许形参名不同，但自由变量名必须一致：

```text
\x.x       ≡ \y.y
\x.\y.x    ≡ \a.\b.a
\x.\y.x    ≠ \x.\y.y
\x.x y     ≠ \z.z w
```

### β 归约与捕获避免代入

一次函数应用的展开规则为：

```text
(\x.M) N → M[x := N]
```

M、N 是规则中的表达式占位符。代入只替换函数体 M 中 x 的自由出现；内层绑定同名变量时停止向该作用域内替换。例如：

```text
(\x.x) y → y
(\x.\x.x) y → \x.x
```

代入应保持参数中自由变量的身份。例如 `(\x.\y.x y) y` 需要先改内层形参，再代入：

```text
(\x.\y.x y) y ≡ (\x.\z.x z) y → \z.y z
```

直接得到 `\y.y y` 会把参数中的自由 y 绑定到内层形参，称为变量捕获。新名字可以采用 z、yq 等未使用的小写名字；比较结果时允许 α 等价。

### 求值顺序与步数

按最左最外顺序选择可归约应用：先检查当前节点，再检查应用的函数侧与参数侧；抽象还需要检查函数体。求值终止于整棵树都没有可归约应用的范式。

令 K、I、Ω 为下面的讲解简写：

```text
K = \x.\y.x
I = \x.x
Ω = (\x.x x)(\x.x x)

K I Ω → (\y.I) Ω → I
```

Ω 自身归约后仍是同一结构，会持续消耗步数。默认 `fuel = 200000`；一次 β 归约消耗一步，扫描、复制和 α 换名不计步数。已经是范式时可直接返回；仍需归约但预算耗尽时抛出 `FuelOut`。

## 3. C++ 接口与实现任务

在 `starter/src/lambda.cpp` 中完成以下函数，接口声明和详细契约见 `starter/include/lambda.h`：

| 函数 | 职责与结果 |
|---|---|
| `parse(s)` | 完整解析输入，返回新的 `Term` 树，语法有误时抛 `ParseError` |
| `print(t)` | 输出合法文本，使重新解析后的树与输入 α 等价 |
| `equalModuloRename(a,b)` | 返回两棵树是否 α 等价，结果类型为 `bool` |
| `substitute(M,x,N)` | 返回捕获避免代入 M[x := N] 后的新树 |
| `normalize(t,fuel)` | 返回最左最外归约到范式的新树，超限抛 `FuelOut` |

`Term` 用 `kind` 区分 Var、Abs、App。Var 保存名字；Abs 保存形参名和 `left` 函数体；App 的 `left` 是函数，`right` 是参数。提供的 `mkVar`、`mkAbs`、`mkApp`、`cloneTerm`、`freeTerm`、`occursFree`、`freshName` 可直接调用。

所有输入树都是借用的，不修改、不释放。`parse`、`substitute`、`normalize` 返回独立的新树，调用者负责释放；函数内部的临时树由函数自身清理。父节点接管子树后，由整棵树统一释放。同一子树指针不能交给多个父节点；复制表达式应使用深拷贝。

最终评测使用提供的接口调用实现。运行限制：单核 CPU 1000 ms，内存 64 MB，挂钟兜底限制 3000 ms。测试包含深层嵌套、变量遮蔽、捕获避免、持续归约和内存安全场景。

## 4. 本地命令与公开样例

在 `starter/` 目录执行 `make build`，运行 `./bin/app` 后逐行输入命令：P 用于解析与打印，E 比较两个表达式，N 求值。`==` 是 E 命令的分隔符，不属于核心表达式。

### 样例一：解析、打印与等价比较

输入：

```text
P \x.x y
E \x.x == \y.y
E \x.\y.x == \x.\y.y
```

一种合法输出：

```text
\x.(x y)
1
0
```

结构与比较过程：

```text
文本 \x.x y → Abs(x, App(Var(x), Var(y))) → 保持结构的文本
两个表达式 → 分别解析 → 比较结构、绑定关系和自由变量名
```

P 输出允许不同的合法括号形式。

### 样例二：代入、作用域与步数

输入：

```text
N (\x.x) y
N (\x.\x.x) y
N (\x.\y.x y) y
N (\x.x x)(\x.x x)
```

一种合法输出：

```text
y
\x.x
\z.(y z)
OUT_OF_FUEL
```

```text
解析输入 → 查找最左最外调用 → 捕获避免代入 → 得到新树
                           ↑                  |
                           └── 还有调用时继续 ─┘
没有调用：输出范式；仍有调用但步数耗尽：输出 OUT_OF_FUEL
```

改名后的结果允许 α 等价。未完成的骨架输出 `NOT_IMPLEMENTED`。输入行只写命令与表达式，行尾不添加注释。其他测试方式与提交步骤见 `starter/README.md`。

## 5. Playground 定义文件

在 `starter/puzzles/*.lam` 中填写 `?`。定义格式为 `def NAME = 表达式`，例如 `def IDD = \x.x`；`#` 开头的行是注释。名称使用 `[A-Z][A-Z0-9_]*`，引用已可用的别名；新定义按书写顺序展开，不直接引用自身或尚未定义的名字。

每关的参考求值器提供所需前置定义，例如数字、选择函数或递归所需的 Y。请按文件注释确认可用接口。提供的定义需保持语义，待填部分写成完整表达式。展开节点上限为 10000，归约步数上限为 200000。

Playground 独立于学生 C++ 求值器评测，可以并行尝试。参考求值器展开定义后应用测试参数，比较结果范式的 α 等价。00–06 为基本练习，07 FIB 为加分练习；具体评分以课程要求为准。