PikachuHy's Scheme

Appearance

pscm_cc For-Each 实现分析 ​

概述 ​

本文档分析 pscm_cc 中 for-each 的实现方式，对比 Guile 1.8 的实现，并讨论其优劣以及改进方向。

pscm_cc 的实现 ​

核心函数 ​

eval_for_each - for-each 特殊形式处理 ​

c
SCM *eval_for_each(SCM_Environment *env, SCM_List *l) {
  // 1. 求值过程参数
  auto f = eval_with_env(env, l->next->data);
  int arg_count;
  
  // 2. 根据过程类型确定参数数量
  if (is_proc(f)) {
    auto proc = cast<SCM_Procedure>(f);
    arg_count = count_list_length(proc->args);
  } else if (is_func(f)) {
    auto func = cast<SCM_Function>(f);
    int list_count = count_list_length(l->next->next);
    arg_count = (func->n_args < 0) ? list_count : func->n_args;
  } else {
    eval_error("for-each: first argument must be a procedure or function");
    return nullptr;
  }
  
  // 3. 求值所有列表参数并存储（栈分配，最多 10 个）
  const int MAX_FOR_EACH_ARGS = 10;
  SCM_List *arg_lists[MAX_FOR_EACH_ARGS];
  for (int i = 0; i < arg_count; i++) {
    auto evaluated_list = eval_with_env(env, l->data);
    if (!is_pair(evaluated_list) && !is_nil(evaluated_list)) {
      eval_error("for-each: argument %d must be a list", i + 1);
    }
    arg_lists[i] = is_nil(evaluated_list) ? nullptr : cast<SCM_List>(evaluated_list);
    l = l->next;
  }
  
  // 4. 遍历所有列表
  while (true) {
    // 检查列表是否耗尽
    bool all_exhausted = true;
    bool any_exhausted = false;
    for (int i = 0; i < arg_count; i++) {
      if (is_list_exhausted(arg_lists[i])) {
        any_exhausted = true;
      } else {
        all_exhausted = false;
      }
    }
    
    if (all_exhausted) break;
    if (any_exhausted) {
      eval_error("for-each: lists must have the same length");
      return nullptr;
    }
    
    // 5. 构建调用表达式（使用 quote 包装参数）
    SCM_List args_dummy = make_list_dummy();
    args_dummy.data = f;
    for (int i = 0; i < arg_count; i++) {
      auto quoted_arg = scm_list2(scm_sym_quote(), arg_lists[i]->data);
      auto arg_node = make_list(quoted_arg);
      args_tail->next = arg_node;
      args_tail = arg_node;
      arg_lists[i] = arg_lists[i]->next;
    }
    
    // 6. 求值调用表达式
    SCM call_expr;
    call_expr.type = SCM::LIST;
    call_expr.value = &args_dummy;
    call_expr.source_loc = nullptr;  // 跳过调用栈追踪
    eval_with_env(env, &call_expr);
  }
  
  return scm_none();
}

实现特点：

  • 支持多个列表参数
  • 使用 quote 包装参数以防止重复求值
  • 栈分配数组（最多 10 个参数）
  • 检查列表长度是否匹配
  • 通过 eval_with_env 调用过程

优势 ​

  1. 实现简单：逻辑清晰，易于理解
  2. 错误处理：检查列表长度匹配和类型
  3. 内存安全：使用栈分配，避免 continuation 问题
  4. 灵活性：支持 procedure 和 function 两种类型
  5. 调试支持：有调试输出

劣势 ​

  1. 性能开销大：
    • 每次迭代都创建 quote 包装
    • 需要通过 eval_with_env 调用，开销大
    • 构建临时调用表达式
  2. 内存效率低：
    • 创建大量临时对象（quote 包装、调用表达式）
    • 每次迭代都重建参数列表
  3. 参数限制：
    • 最多支持 10 个参数列表（硬编码限制）
  4. 缺少优化：
    • 没有针对单列表、双列表的特殊优化
    • 没有使用 trampoline 优化
  5. 不必要的复杂性：
    • 使用 quote 包装是不必要的
    • 可以通过 apply_procedure 直接调用

Guile 1.8 的实现 ​

核心函数 ​

scm_for_each - for-each 函数实现 ​

c
SCM scm_for_each (SCM proc, SCM arg1, SCM args)
{
  long i, len;
  len = scm_ilength (arg1);  // 计算第一个列表的长度
  SCM_VALIDATE_REST_ARGUMENT (args);
  
  // 1. 单列表优化：使用 trampoline_1
  if (scm_is_null (args))
    {
      scm_t_trampoline_1 call = scm_trampoline_1 (proc);
      SCM_GASSERT2 (call, ...);
      while (SCM_NIMP (arg1))
        {
          call (proc, SCM_CAR (arg1));  // 直接调用，无分发开销
          arg1 = SCM_CDR (arg1);
        }
      return SCM_UNSPECIFIED;
    }
  
  // 2. 双列表优化：使用 trampoline_2
  if (scm_is_null (SCM_CDR (args)))
    {
      SCM arg2 = SCM_CAR (args);
      int len2 = scm_ilength (arg2);
      scm_t_trampoline_2 call = scm_trampoline_2 (proc);
      SCM_GASSERTn (call, ...);
      SCM_GASSERTn (len2 >= 0, ...);
      if (len2 != len)
        SCM_OUT_OF_RANGE (3, arg2);  // 检查长度匹配
      while (SCM_NIMP (arg1))
        {
          call (proc, SCM_CAR (arg1), SCM_CAR (arg2));  // 直接调用
          arg1 = SCM_CDR (arg1);
          arg2 = SCM_CDR (arg2);
        }
      return SCM_UNSPECIFIED;
    }
  
  // 3. 多列表情况：使用向量优化
  arg1 = scm_cons (arg1, args);
  args = scm_vector (arg1);  // 转换为向量
  check_map_args (args, len, ...);  // 检查所有列表长度
  while (1)
    {
      arg1 = SCM_EOL;
      // 从向量中收集每个列表的一个元素
      for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--)
        {
          SCM elt = SCM_SIMPLE_VECTOR_REF (args, i);
          if (SCM_IMP (elt))
            return SCM_UNSPECIFIED;  // 某个列表已耗尽
          arg1 = scm_cons (SCM_CAR (elt), arg1);
          SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt));  // 更新向量
        }
      scm_apply (proc, arg1, SCM_EOL);  // 应用过程
    }
}

关键特性：

  1. 性能优化：

    • 单列表优化：使用 trampoline_1 直接调用
    • 双列表优化：使用 trampoline_2 直接调用
    • 多列表优化：使用向量存储列表指针

  2. 直接调用：

    • 不使用 quote 包装
    • 不使用 eval_with_env
    • 直接调用过程，性能高

  3. 长度检查：

    • 在双列表情况下检查长度是否匹配
    • 在多列表情况下使用 check_map_args 检查

  4. 向量优化：

    • 将列表转换为向量，提高访问效率
    • 直接在向量中更新列表指针

Guile 1.8 的优势 ​

  1. 性能优化：
    • 单列表、双列表特殊优化
    • 使用 trampoline 避免分发开销
    • 使用向量提高多列表访问效率
  2. 内存效率：
    • 直接传递元素值，不需要 quote 包装
    • 使用向量减少内存分配
  3. 类型安全：
    • 检查列表长度匹配
    • 验证参数类型
  4. 无参数限制：
    • 支持任意数量的列表参数

Guile 1.8 的劣势 ​

  1. 实现复杂：
    • 需要 trampoline 机制
    • 需要向量转换
  2. 依赖其他组件：
    • 依赖 trampoline 系统
    • 依赖向量实现

对比总结 ​

特性pscm_ccGuile 1.8
单列表优化❌✅ (trampoline_1)
双列表优化❌✅ (trampoline_2)
多列表处理✅✅ (向量优化)
性能较低较高
内存效率较低（quote 包装）较高（直接传递）
调用方式eval_with_env直接调用/trampoline
长度检查✅✅
参数限制10 个（硬编码）无限制
实现复杂度中等较高

关键差异 ​

1. 调用方式 ​

pscm_cc：

c
// 使用 quote 包装，通过 eval_with_env 调用
auto quoted_arg = scm_list2(scm_sym_quote(), arg_lists[i]->data);
SCM call_expr;
call_expr.type = SCM::LIST;
call_expr.value = &args_dummy;
eval_with_env(env, &call_expr);  // 通过求值器调用

Guile 1.8：

c
// 直接调用，使用 trampoline
scm_t_trampoline_1 call = scm_trampoline_1 (proc);
call (proc, SCM_CAR (arg1));  // 直接调用，无分发开销

// 或多列表情况
scm_apply (proc, arg1, SCM_EOL);  // 直接应用，不通过求值器

2. 参数传递 ​

pscm_cc：

c
// 使用 quote 包装参数
auto quoted_arg = scm_list2(scm_sym_quote(), arg_lists[i]->data);

Guile 1.8：

c
// 直接传递元素值
call (proc, SCM_CAR (arg1));  // 单列表
call (proc, SCM_CAR (arg1), SCM_CAR (arg2));  // 双列表
scm_apply (proc, arg1, SCM_EOL);  // 多列表

3. 性能优化 ​

pscm_cc：

  • 没有特殊优化
  • 所有情况都使用相同的代码路径

Guile 1.8：

  • 单列表：trampoline_1
  • 双列表：trampoline_2
  • 多列表：向量优化

pscm_cc 的改进方向 ​

1. 短期改进（高优先级） ​

1.1 移除 quote 包装，直接调用 ​

问题：使用 quote 包装和 eval_with_env 调用开销大。

改进：直接使用 apply_procedure 或 eval_with_func。

c
// 修改前
auto quoted_arg = scm_list2(scm_sym_quote(), arg_lists[i]->data);
SCM call_expr;
call_expr.type = SCM::LIST;
call_expr.value = &args_dummy;
eval_with_env(env, &call_expr);

// 修改后
// 构建参数列表（直接使用元素值）
SCM_List args_dummy = make_list_dummy();
SCM_List *args_tail = &args_dummy;
for (int i = 0; i < arg_count; i++) {
  args_tail->next = make_list(arg_lists[i]->data);  // 直接传递，不需要 quote
  args_tail = args_tail->next;
  arg_lists[i] = arg_lists[i]->next;
}

// 直接调用
if (is_proc(f)) {
  SCM_Procedure *proc = cast<SCM_Procedure>(f);
  apply_procedure(env, proc, args_dummy.next);  // 直接调用
} else if (is_func(f)) {
  SCM_Function *func = cast<SCM_Function>(f);
  SCM_List *evaled_args = eval_list_with_env(env, args_dummy.next);
  SCM_List func_call;
  func_call.data = f;
  func_call.next = evaled_args;
  eval_with_func(func, &func_call);  // 直接调用
}

1.2 优化单列表情况 ​

问题：单列表是最常见的情况，但没有优化。

改进：为单列表添加特殊处理。

c
SCM *eval_for_each(SCM_Environment *env, SCM_List *l) {
  // ... 前面的代码 ...
  
  // 单列表优化
  if (arg_count == 1) {
    SCM_List *list1 = arg_lists[0];
    
    while (list1) {
      // 直接调用，不需要构建参数列表
      if (is_proc(f)) {
        SCM_Procedure *proc = cast<SCM_Procedure>(f);
        SCM_List *arg_list = make_list(list1->data);
        apply_procedure(env, proc, arg_list);
      } else if (is_func(f)) {
        SCM_Function *func = cast<SCM_Function>(f);
        SCM_List func_call;
        func_call.data = f;
        func_call.next = make_list(list1->data);
        eval_with_func(func, &func_call);
      }
      list1 = list1->next;
    }
    
    return scm_none();
  }
  
  // 多列表情况（现有代码，但移除 quote 包装）
  // ...
}

1.3 移除参数限制 ​

问题：硬编码限制最多 10 个参数。

改进：使用动态分配或更大的栈数组。

c
// 方案 1：使用 std::vector（推荐）
std::vector<SCM_List*> arg_lists;
arg_lists.reserve(arg_count);
for (int i = 0; i < arg_count; i++) {
  // ...
  arg_lists.push_back(list_ptr);
}

// 方案 2：增加栈数组大小
const int MAX_FOR_EACH_ARGS = 100;  // 增加到 100
// 或使用动态分配
SCM_List **arg_lists = new SCM_List*[arg_count];
// ... 使用后记得 delete[]

1.4 优化列表耗尽检查 ​

问题：每次迭代都检查所有列表，效率可以更高。

改进：简化检查逻辑。

c
// 修改前
bool all_exhausted = true;
bool any_exhausted = false;
for (int i = 0; i < arg_count; i++) {
  if (is_list_exhausted(arg_lists[i])) {
    any_exhausted = true;
  } else {
    all_exhausted = false;
  }
}

// 修改后
// 更简洁的检查
bool all_exhausted = true;
for (int i = 0; i < arg_count; i++) {
  if (!is_list_exhausted(arg_lists[i])) {
    all_exhausted = false;
    break;  // 提前退出
  }
}
if (all_exhausted) break;

// 然后检查是否有列表耗尽（长度不匹配）
for (int i = 0; i < arg_count; i++) {
  if (is_list_exhausted(arg_lists[i])) {
    eval_error("for-each: lists must have the same length");
    return nullptr;
  }
}

2. 中期改进（中优先级） ​

2.1 实现双列表优化 ​

问题：双列表是第二常见的情况，但没有优化。

改进：为双列表添加特殊处理。

c
// 双列表优化
if (arg_count == 2) {
  SCM_List *list1 = arg_lists[0];
  SCM_List *list2 = arg_lists[1];
  
  // 检查长度（可选，提前检查）
  int len1 = list_length(list1);
  int len2 = list_length(list2);
  if (len1 != len2) {
    eval_error("for-each: lists must have the same length");
    return nullptr;
  }
  
  while (list1 && list2) {
    // 构建双元素参数列表
    SCM_List *arg_list = make_list(list1->data);
    arg_list->next = make_list(list2->data);
    
    // 调用过程
    if (is_proc(f)) {
      SCM_Procedure *proc = cast<SCM_Procedure>(f);
      apply_procedure(env, proc, arg_list);
    } else {
      // function 处理
    }
    
    list1 = list1->next;
    list2 = list2->next;
  }
  
  return scm_none();
}

2.2 优化参数列表构建 ​

问题：每次迭代都构建参数列表，效率低。

改进：重用参数列表节点。

c
// 预分配参数列表节点
SCM_List **arg_nodes = new SCM_List*[arg_count];
for (int i = 0; i < arg_count; i++) {
  arg_nodes[i] = make_list(nullptr);  // 占位符
  if (i > 0) {
    arg_nodes[i-1]->next = arg_nodes[i];
  }
}

// 在循环中只更新数据
while (true) {
  // 检查列表是否耗尽
  // ...
  
  // 更新参数节点数据（不重新分配）
  for (int i = 0; i < arg_count; i++) {
    arg_nodes[i]->data = arg_lists[i]->data;
    arg_lists[i] = arg_lists[i]->next;
  }
  
  // 调用过程
  if (is_proc(f)) {
    SCM_Procedure *proc = cast<SCM_Procedure>(f);
    apply_procedure(env, proc, arg_nodes[0]);
  }
  // ...
}

delete[] arg_nodes;

2.3 添加提前长度检查 ​

问题：在循环中才发现长度不匹配，浪费计算。

改进：在开始循环前检查所有列表长度。

c
// 在求值所有列表后，循环开始前
int *list_lengths = new int[arg_count];
int min_length = INT_MAX;
for (int i = 0; i < arg_count; i++) {
  list_lengths[i] = list_length(arg_lists[i]);
  if (list_lengths[i] < min_length) {
    min_length = list_lengths[i];
  }
}

// 检查所有列表长度是否相同
for (int i = 1; i < arg_count; i++) {
  if (list_lengths[i] != list_lengths[0]) {
    eval_error("for-each: lists must have the same length");
    delete[] list_lengths;
    return nullptr;
  }
}

// 现在可以安全地循环 min_length 次
for (int j = 0; j < min_length; j++) {
  // 构建参数列表并调用
  // ...
}

delete[] list_lengths;

3. 长期改进（低优先级） ​

3.1 实现 Trampoline 机制 ​

问题：缺少 trampoline 优化。

改进：实现类似 Guile 的 trampoline 机制（参考 map 实现文档中的说明）。

c
// 定义 trampoline 类型
typedef void (*pscm_t_trampoline_1)(SCM_Procedure *proc, SCM *arg1);
typedef void (*pscm_t_trampoline_2)(SCM_Procedure *proc, SCM *arg1, SCM *arg2);

// 在 for-each 中使用
if (arg_count == 1 && is_proc(f)) {
  pscm_t_trampoline_1 call = pscm_get_trampoline_1(f);
  if (call) {
    // 使用 trampoline
    while (list1) {
      call(proc, list1->data);
      list1 = list1->next;
    }
  }
}

3.2 使用向量优化多列表 ​

问题：多列表情况下效率可以更高。

改进：使用向量存储列表指针（类似 Guile）。

c
// 将列表转换为向量
std::vector<SCM_List*> list_vec;
for (int i = 0; i < arg_count; i++) {
  list_vec.push_back(arg_lists[i]);
}

// 在循环中使用向量
while (true) {
  // 检查是否有列表耗尽
  bool all_non_empty = true;
  for (int i = 0; i < arg_count; i++) {
    if (!list_vec[i]) {
      all_non_empty = false;
      break;
    }
  }
  if (!all_non_empty) break;
  
  // 构建参数列表
  SCM_List args_dummy = make_list_dummy();
  SCM_List *args_tail = &args_dummy;
  for (int i = 0; i < arg_count; i++) {
    args_tail->next = make_list(list_vec[i]->data);
    args_tail = args_tail->next;
    list_vec[i] = list_vec[i]->next;  // 更新向量
  }
  
  // 调用过程
  // ...
}

3.3 支持尾调用优化 ​

问题：for-each 中的过程调用可能不是尾调用优化的。

改进：确保过程调用是尾调用（如果可能）。

c
// 注意：for-each 本身不返回值，所以过程调用不需要是尾调用
// 但如果过程内部有尾调用，应该保证它们被优化

3.4 并行化支持 ​

问题：可以并行处理多个元素（如果过程没有副作用）。

改进：实现并行 for-each（如果支持多线程）。

c
// 并行 for-each（伪代码）
// 注意：只有当过程没有副作用时才安全
void parallel_for_each(SCM_Procedure *proc, SCM_List **lists, int num_lists) {
  // 将列表分成多个块
  // 并行处理每个块
  // 注意同步
}

实现示例 ​

改进后的 for-each 实现（简化版） ​

c
SCM *eval_for_each(SCM_Environment *env, SCM_List *l) {
  assert(l->next);
  
  // 1. 求值过程
  SCM *f = eval_with_env(env, l->next->data);
  if (!is_proc(f) && !is_func(f)) {
    eval_error("for-each: first argument must be a procedure or function");
    return nullptr;
  }
  
  // 2. 确定参数数量
  int arg_count;
  if (is_proc(f)) {
    SCM_Procedure *proc = cast<SCM_Procedure>(f);
    arg_count = count_list_length(proc->args);
  } else {
    SCM_Function *func = cast<SCM_Function>(f);
    int list_count = count_list_length(l->next->next);
    arg_count = (func->n_args < 0) ? list_count : func->n_args;
  }
  
  l = l->next->next;
  
  // 3. 求值所有列表参数
  std::vector<SCM_List*> arg_lists;
  arg_lists.reserve(arg_count);
  for (int i = 0; i < arg_count; i++) {
    if (!l) {
      eval_error("for-each: args count not match, require %d, but got %d", arg_count, i);
      return nullptr;
    }
    SCM *evaluated_list = eval_with_env(env, l->data);
    if (!is_pair(evaluated_list) && !is_nil(evaluated_list)) {
      eval_error("for-each: argument %d must be a list", i + 1);
      return nullptr;
    }
    arg_lists.push_back(is_nil(evaluated_list) ? nullptr : cast<SCM_List>(evaluated_list));
    l = l->next;
  }
  
  // 4. 单列表优化
  if (arg_count == 1) {
    SCM_List *list1 = arg_lists[0];
    while (list1) {
      if (is_proc(f)) {
        SCM_Procedure *proc = cast<SCM_Procedure>(f);
        SCM_List *arg_list = make_list(list1->data);
        apply_procedure(env, proc, arg_list);
      } else {
        SCM_Function *func = cast<SCM_Function>(f);
        SCM_List func_call;
        func_call.data = f;
        func_call.next = make_list(list1->data);
        eval_with_func(func, &func_call);
      }
      list1 = list1->next;
    }
    return scm_none();
  }
  
  // 5. 多列表情况（移除 quote 包装）
  while (true) {
    // 检查所有列表是否耗尽
    bool all_exhausted = true;
    for (int i = 0; i < arg_count; i++) {
      if (!is_list_exhausted(arg_lists[i])) {
        all_exhausted = false;
        break;
      }
    }
    if (all_exhausted) break;
    
    // 检查是否有列表耗尽（长度不匹配）
    for (int i = 0; i < arg_count; i++) {
      if (is_list_exhausted(arg_lists[i])) {
        eval_error("for-each: lists must have the same length");
        return nullptr;
      }
    }
    
    // 构建参数列表（直接使用元素值，不需要 quote）
    SCM_List args_dummy = make_list_dummy();
    SCM_List *args_tail = &args_dummy;
    for (int i = 0; i < arg_count; i++) {
      args_tail->next = make_list(arg_lists[i]->data);  // 直接传递
      args_tail = args_tail->next;
      arg_lists[i] = arg_lists[i]->next;
    }
    
    // 调用过程
    if (is_proc(f)) {
      SCM_Procedure *proc = cast<SCM_Procedure>(f);
      apply_procedure(env, proc, args_dummy.next);
    } else {
      SCM_Function *func = cast<SCM_Function>(f);
      SCM_List *evaled_args = eval_list_with_env(env, args_dummy.next);
      SCM_List func_call;
      func_call.data = f;
      func_call.next = evaled_args;
      eval_with_func(func, &func_call);
    }
  }
  
  return scm_none();
}

结论 ​

pscm_cc 的 for-each 实现是一个功能完整但性能较低的实现。它正确地实现了 for-each 的基本功能，但存在一些性能问题，主要是使用 quote 包装和通过 eval_with_env 调用。

与 Guile 1.8 相比，主要差异在于：

  1. 性能优化：Guile 有针对单列表、双列表的特殊优化
  2. 调用方式：Guile 直接调用/trampoline，pscm_cc 通过 eval_with_env
  3. 参数传递：Guile 直接传递值，pscm_cc 使用 quote 包装
  4. 参数限制：Guile 无限制，pscm_cc 限制 10 个

建议优先实现：

  1. 移除 quote 包装，直接调用（提高性能）
  2. 单列表优化（处理最常见情况）
  3. 移除参数限制（提高灵活性）

这些改进将显著提高 for-each 的性能，同时保持代码的简洁性。更复杂的优化（如 trampoline、向量优化）可以根据实际需求逐步实现。

This website is released under the MIT License.

Copyright © 2022 PikachuHy