PikachuHy's Scheme

Appearance

pscm_cc 中 Proper List 和 Dotted Pair 的实现说明 ​

状态：已实现

Dotted Pair 支持功能已在 pscm_cc 中完整实现，通过 is_dotted 标记区分 proper list 和 dotted pair。

问题描述 ​

目前 pscm_cc 无法区分 (1 2) 和 (1 . 2)，这两个表达式在内部表示上完全相同，导致：

  1. 解析时无法正确记录 dotted pair 信息
  2. 打印时需要使用启发式方法猜测，不够准确
  3. 求值时可能产生错误的行为

当前架构 ​

数据结构 ​

cpp
struct SCM_List {
  SCM *data;        // car
  SCM_List *next;   // cdr (指向下一个节点，或 nullptr)
};

问题根源 ​

  • (1 2) 被表示为：{data=1, next={data=2, next=nullptr}}
  • (1 . 2) 也被表示为：{data=1, next={data=2, next=nullptr}}
  • 两者在内存中的表示完全相同，无法区分

当前解析逻辑（parse.cc:392-410） ​

cpp
// Check for dotted pair
if (*p->pos == '.') {
  // ... 解析 cdr
  tail->next = is_pair(cdr) ? cast<SCM_List>(cdr) : make_list(cdr);
  // 问题：这里仍然使用 SCM_List 结构，无法标记这是 dotted pair
}

当前打印逻辑（print.cc） ​

使用启发式方法猜测是否为 dotted pair：

  • 检查元素数量
  • 检查最后一个元素的类型
  • 检查上下文（是否嵌套）
  • 这些启发式方法不够可靠

Guile 1.8 的解决方案 ​

核心思想 ​

Guile 使用 pair 作为基本数据结构，而不是链表：

c
// Guile 中 pair 的结构（简化）
struct pair {
  SCM car;
  SCM cdr;  // 可以是任何 SCM 值，包括 nil、pair、原子值等
};

表示方式 ​

  1. Proper List (1 2)：

    • 表示为：(1 . (2 . ()))
    • 即两个 pair 的链，最后一个 pair 的 cdr 是 SCM_EOL（nil）

  2. Dotted Pair (1 . 2)：

    • 表示为：(1 . 2)
    • 即一个 pair，cdr 是原子值 2（不是 nil）

解析逻辑（read.c:362-376） ​

c
// 当遇到 '.' 符号时
if (scm_is_eq(scm_sym_dot, (tmp = scm_read_expression(port)))) {
  // 读取 cdr 表达式
  ans = scm_read_expression(port);
  // 直接返回，不构建 pair 链
  return ans;
}

// 在列表构建过程中遇到 '.'
if (scm_is_eq(scm_sym_dot, (tmp = scm_read_expression(port)))) {
  // 读取 cdr 并直接设置
  SCM_SETCDR(tl, tmp = scm_read_expression(port));
  // 检查是否以 ')' 结尾
  if (terminating_char != c)
    scm_i_input_error(...);
  goto exit;
}

区分方法 ​

通过检查最后一个 pair 的 cdr 是否为 nil 来区分：

  • 如果 cdr 是 nil → proper list
  • 如果 cdr 不是 nil 且不是 pair → dotted pair
  • 如果 cdr 是 pair → improper list（如 (1 . (2 . 3))）

架构调整方案 ​

方案1：在 SCM_List 中添加标记（推荐） ​

优点：

  • 最小侵入性，不需要改变现有代码结构
  • 保持链表结构的优势（操作简便）
  • 向后兼容

实现：

cpp
struct SCM_List {
  SCM *data;
  SCM_List *next;  // 类型仍然是 SCM_List*，即使 is_dotted=true
  bool is_dotted;  // 新增：标记最后一个节点是否为 dotted pair 的 cdr
};

重要说明：

next 指针的类型仍然是 SCM_List*，即使 is_dotted = true。这是因为：

  1. 存储 cdr 值需要结构：在 dotted pair (1 . 2) 中，我们需要一个节点来存储 cdr 值 2
  2. 统一的数据结构：使用 SCM_List 节点来存储 cdr 值，保持类型一致性
  3. 语义区分：is_dotted 标记用于区分语义：
    • is_dotted = false：next 指向 proper list 的下一个元素
    • is_dotted = true：next 指向的节点存储的是 dotted pair 的 cdr（原子值），而不是 list 的一部分

示例：

对于 (1 . 2)：

节点1: {data=1, next=指向节点2, is_dotted=false}
节点2: {data=2, next=nullptr, is_dotted=true}  // 注意：节点2的is_dotted=true

对于 (1 2)：

节点1: {data=1, next=指向节点2, is_dotted=false}
节点2: {data=2, next=nullptr, is_dotted=false}

修改点：

  1. parse.cc：解析 dotted pair 时，在最后一个节点上设置 is_dotted = true
  2. print.cc：检查最后一个节点的 is_dotted 标记决定打印格式
  3. list.cc：scm_cons 等函数需要正确处理标记
  4. make_list 等辅助函数需要初始化 is_dotted = false

注意事项：

  • is_dotted 应该只在最后一个节点上有意义（即 next == nullptr 或 next->next == nullptr 的节点）
  • 需要确保所有创建 SCM_List 的地方都正确初始化 is_dotted = false
  • 在访问 next 时，类型仍然是 SCM_List*，但语义上需要根据 is_dotted 来理解

方案2：添加新的 SCM 类型 PAIR ​

优点：

  • 类型系统层面区分，更清晰
  • 符合 Scheme 的语义（pair 是基本类型）

实现：

cpp
struct SCM {
  enum Type { NONE, NIL, LIST, PAIR, PROC, ... } type;  // 新增 PAIR
  void *value;
  // ...
};

// 或者复用 SCM_List，但通过 type 区分

修改点：

  1. 所有类型检查函数需要更新
  2. car/cdr 等函数需要处理两种类型
  3. 打印、求值等逻辑需要区分处理

方案3：使用特殊标记值（不推荐） ​

在 next 字段中使用特殊值（如 (SCM_List*)1）来标记 dotted pair，但这种方法：

  • 破坏类型安全
  • 难以维护
  • 容易出错

关于 next 指针类型的说明 ​

重要：即使 is_dotted = true，next 指针的类型仍然是 SCM_List*。

为什么 next 仍然是 SCM_List*？ ​

  1. 存储需求：在 dotted pair (1 . 2) 中，我们需要一个结构来存储 cdr 值 2
  2. 类型一致性：使用 SCM_List 节点来存储 cdr 值，保持类型系统的一致性
  3. 实现简化：不需要引入新的类型或联合体

语义区分 ​

虽然类型相同，但语义不同：

  • Proper List (1 2)：

    节点1: {data=1, next=指向节点2, is_dotted=false}
节点2: {data=2, next=nullptr, is_dotted=false}
    • 节点2 是 list 的一部分（最后一个元素）

  • Dotted Pair (1 . 2)：

    节点1: {data=1, next=指向节点2, is_dotted=false}
节点2: {data=2, next=nullptr, is_dotted=true}  // 注意这里
    • 节点2 不是 list 的一部分，而是 dotted pair 的 cdr（原子值）

访问模式 ​

在代码中访问时：

cpp
SCM_List *node = ...;
if (node->is_dotted) {
  // node->data 是 dotted pair 的 cdr（原子值）
  // node->next 应该是 nullptr
} else {
  // node->data 是 list 的元素
  // node->next 指向下一个元素（或 nullptr）
}

推荐实现：方案1 ​

具体修改步骤 ​

  1. 修改数据结构（pscm.h）：

    cpp
    struct SCM_List {
  SCM *data;
  SCM_List *next;
  bool is_dotted;  // true 表示这是 dotted pair 的最后一个节点
};

  2. 更新辅助函数（pscm.h）：

    cpp
    inline SCM_List *make_list() {
  auto l = new SCM_List();
  l->data = nullptr;
  l->next = nullptr;
  l->is_dotted = false;  // 默认不是 dotted
  return l;
}

  3. 修改解析器（parse.cc）：

    cpp
    // 在 parse_list 中，当遇到 '.' 时
if (*p->pos == '.') {
  // ... 解析 cdr
  tail->next = is_pair(cdr) ? cast<SCM_List>(cdr) : make_list(cdr);
  // 重要：在最后一个节点（存储 cdr 的节点）上设置 is_dotted = true
  tail->next->is_dotted = true;  // 标记为 dotted pair 的 cdr
  // ...
}

    注意：next 的类型仍然是 SCM_List*，只是这个节点存储的是 dotted pair 的 cdr，而不是 list 的下一个元素。

  4. 修改打印函数（print.cc）：

    cpp
    // 检查是否为 dotted pair
// 找到最后一个节点，检查其 is_dotted 标记
SCM_List *last = l;
SCM_List *prev = nullptr;
while (last->next) {
  prev = last;
  last = last->next;
}

// 如果最后一个节点的 is_dotted = true，说明这是 dotted pair
bool is_dotted = (last->is_dotted);
if (is_dotted) {
  // 打印为 (a b c . d) 格式
  // last->data 是 cdr 值
} else {
  // 打印为 (a b c) 格式
}

    注意：last->next 的类型仍然是 SCM_List*（这里是 nullptr），但 last->is_dotted 标记告诉我们这个节点存储的是 dotted pair 的 cdr。

  5. 更新其他相关函数：

    • scm_cons：正确处理 dotted pair
    • scm_append：保持 dotted pair 的标记
    • car/cdr：不需要修改（结构不变）

关于 Scheme 语法规则 ​

重要：(1 . 2 3) 这种语法是不合法的。

在 Scheme 中，dotted pair 的语法规则是：

  • (car . cdr) - 正确：. 后面只能有一个表达式
  • (1 . 2) - 正确
  • (1 2 . 3) - 正确（improper list，等价于 (1 . (2 . 3))）
  • (1 . (2 3)) - 正确（cdr 是一个 list）

不合法的语法：

  • (1 . 2 3) - 错误：. 后面不能有多个元素
  • (1 . ) - 错误：. 后面必须有元素

当前解析器的处理（parse.cc:392-415）：

cpp
if (*p->pos == '.') {
  // 解析 cdr（只有一个表达式）
  cdr = parse_expr(p);
  tail->next = make_list(cdr);
  break;  // 遇到 '.' 后立即退出循环
}

// 检查是否以 ')' 结尾
if (*p->pos != ')') {
  parse_error(p, "expected ')' to close list");  // 如果还有元素，会报错
}

所以如果输入 (1 . 2 3)，解析器会：

  1. 解析 1
  2. 遇到 .，解析 2 作为 cdr
  3. break 退出循环
  4. 发现 *p->pos 是 3（不是 )），报错："expected ')' to close list"

测试用例 ​

scheme
;; 应该打印为 (1 2)
(display '(1 2))

;; 应该打印为 (1 . 2)
(display '(1 . 2))

;; 应该打印为 (1 2 3)
(display '(1 2 3))

;; 应该打印为 (1 2 3 . 4)
(display '(1 2 3 . 4))

;; 测试 cons
(display (cons 1 2))  ; 应该打印 (1 . 2)
(display (cons 1 '(2)))  ; 应该打印 (1 2)

;; 不合法的语法（应该报错）
;; (1 . 2 3)  ; 语法错误：'.' 后面不能有多个元素

实际实现 ​

实现状态 ​

✅ 已完全实现，采用方案1（在 SCM_List 中添加 is_dotted 标记）

实现细节 ​

  1. 数据结构（pscm.h）：

    cpp
    struct SCM_List {
  SCM *data;
  SCM_List *next;
  bool is_dotted;  // true 表示这是 dotted pair 的最后一个节点（存储 cdr 的节点）
};
    • ✅ 已添加 is_dotted 字段

  2. 辅助函数（pscm.h）：

    • ✅ make_list() 函数已更新，默认设置 is_dotted = false

  3. 解析器（parse.cc）：

    • ✅ 解析 dotted pair 时，在最后一个节点上设置 is_dotted = true
    • ✅ 正确处理 (1 . 2) 和 (1 2) 的区分

  4. 打印函数（print.cc）：

    • ✅ 已实现 _is_dotted_pair() 辅助函数
    • ✅ 根据 is_dotted 标记决定打印格式
    • ✅ 正确打印 (1 2) 和 (1 . 2)

  5. 列表操作（list.cc）：

    • ✅ scm_cons 正确处理 dotted pair
    • ✅ scm_append 保持 dotted pair 的标记

实现代码示例 ​

实际实现与推荐方案完全一致：

cpp
// parse.cc 中的实现
if (*p->pos == '.') {
  // ... 解析 cdr
  tail->next = is_pair(cdr) ? cast<SCM_List>(cdr) : make_list(cdr);
  tail->next->is_dotted = true;  // 标记为 dotted pair 的 cdr
  // ...
}

// print.cc 中的实现
static bool _is_dotted_pair(SCM_List *l) {
  if (!l || !l->next) {
    return false;
  }
  SCM_List *last = l;
  while (last->next) {
    last = last->next;
  }
  return last->is_dotted;  // 检查最后一个节点的标记
}

总结 ​

Guile 1.8 通过使用 pair 作为基本数据结构，自然地区分了 proper list 和 dotted pair。pscm_cc 由于使用链表结构，在架构层面添加了 is_dotted 标记来区分。

实际实现采用方案1：在 SCM_List 结构中添加 is_dotted 布尔标记，这是最小侵入性的方案，能够准确区分 proper list 和 dotted pair，同时保持代码的简洁性。

✅ 实现完成：所有相关功能已完整实现并正常工作。

This website is released under the MIT License.

Copyright © 2022 PikachuHy