SML实现《现代编译器ML版》1.1b习题lookup函数的空树返回问题

关于lookup函数边界处理的说明 #

• 题目要求的'a tree * key -> 'a函数类型完全合法，不存在题目表述错误，你遇到的边界场景可以通过SML的异常机制合法实现，不需要修改原定的返回类型。
• 你对SML异常的规则存在误解：抛出异常的表达式属于不产生正常返回值的计算分支，它的类型是无约束多态的，类型检查器会自动将其类型适配到函数要求的任意'a类型，根本不需要你提供对应类型的默认值，也不存在“抛出异常必须捕获”的强制要求——如果抛出的异常没有上层捕获，程序会直接中断计算并打印错误信息，这是SML的标准运行行为。
• 之前代码报错的核心原因是你在lookup(LEAF,key) =后面留空了分支表达式，没有完成分支定义，并不是抛出异常的写法不被允许。符合题目要求的完整实现如下：

(* 定义键查找失败的自定义异常 *)
exception KeyNotFound;

fun lookup(LEAF, key) = raise KeyNotFound
  | lookup(TREE(l, k, v, r), key) =
    if k = key
    then v
    else if key < k
    then lookup(l, key)
    else lookup(r, key)

• 这种实现完全匹配题目要求的类型签名：因为raise KeyNotFound永远不会正常返回值，类型系统不会要求这个分支提供一个真实存在的'a类型实例，整个函数的泛型类型检查可以顺利通过。原书后续章节涉及的所有键值查找函数，遇到查找失败场景时的标准处理方式都是抛出NotFound类的异常，和这个实现逻辑完全一致。
• 你提到的Scala用Option包装返回值、Common Lisp用续体处理查找失败场景的思路，是函数式语言中另一种类型安全的设计选择，但这类思路需要修改函数的返回类型，和本题固定要求的'a返回类型不匹配。

关于Emacs sml-mode强制缩进的说明 #

• 这种自动缩进行为是sml-mode的设计特性，不是程序bug：
  • sml-mode默认遵循SML语言的布局排版规范，核心设计逻辑是自动识别顶层表达式的分隔符，把同属一个表达式序列的语句自动对齐到匹配的缩进位置，避免排版混乱。
  • 触发强制缩进的直接原因是你在val t3 = insert("b",3,t2)后面单独写了一个顶格的分号，sml-mode会把这个分号识别为顶层表达式序列的分隔符，所以后续的lookup调用会被自动识别为序列内的语句，执行缩进对齐。实际上SML里顶层的表达式不需要单独用独立的分号分隔，删掉这个多余的分号，后续的缩进行为就会恢复正常。
  • 如果后续还是觉得自动缩进不符合使用习惯，可以手动修改缩进量，也可以通过配置调整默认缩进宽度，不会实际影响SML代码的运行逻辑。

内容的提问来源于stack exchange，提问作者Jim Newton