[Little Schemer Ch3 pp.34＆37]：为什么（rember a（cdr lat））作为第37个示例的cons的第2个参数被解释为未知的p.37示例

Question

我使用DrRacket调试模式逐步在p.34和p.37上运行这两个示例。以下是两个示例中第一次处理(cdr lat)时的堆栈窗口结果。

p.34，没有cons的失败例子

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) '())
      (else (cond
              ((eq? a (car lat)) (cdr lat))
              (else (rember a (cdr lat)))
              )))))

(rember 'c '(a b c d))

调试器中的堆栈区域：

（cdr ...） （rember ...）

p.37与cons在最后一行：

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) '())
      (else (cond
              ((eq? a (car lat)) (cdr lat))
              (else (cons (car lat)
                          (rember a (cdr lat)))))))))

(rember 'c '(a b c d))

调试器中的堆栈区域：

（cdr ...） （记得......） （记得......）

带有p.37代码的堆栈区域表示在处理rember之前，(cdr lat)的第二次调用已被归类为unknown。

两个例子的唯一区别是p.37添加了“cons”。 Cons需要2个参数，一个s表达式和一个列表。

没有(cdr lat)，rember本身不会返回列表。在本书的前40页中包含(cdr lat)的所有示例都具有相同的(function (cdr variable)格式。

我不明白为什么p.37示例rember本身被识别为未知并且有理由等待减少，而包含的(cdr lat)可以被处理。

或者为什么rember在cons的第二个论点的位置被解释为那样。

谢谢！

Answer 1

TL; DR：你看到（和误解）的是函数调用的堆栈，以及尾递归的效果。

---

要回答有关调试器的具体问题：您的解释是错误的。你看到的是函数调用的运行时堆栈，它让你到达现在执行时间线中的特定点。

它不是“未知”，也不是“以后减少”的东西。你已经通过它，到了你当前的执行点。它是什么，等待嵌套调用的结果，继续使用结果。

如果你再点击Step几次（使用p.37代码），你将会到达更深的点，你会看到更多的(rember)s出现在Stack区域。您当前的执行点出现在堆栈的最顶层;最早 - 最底层。

请注意，“变量”区域显示该特定调用帧的变量值。

如果移动鼠标光标并将鼠标悬停在较低的(rember)上并单击它，您将看到其变量的值：

Racket的调试器有点习惯了。

另请注意左上角的“最后评估值”字段以非常小的字母显示（在上图中）。这是一个非常重要和有用的信息，同时调试。它可以使用在屏幕上更加明显。

你没有看到(rember)s堆栈与第一个代码一起增长的原因（p.34），

是它是tail recursive。对于rember的深嵌套调用的结果没有什么可做的，除了将它返回到更远的位置;所以没有必要为此保存任何状态。这意味着rember的调用框架会被重用，替换，这就是为什么你只能在Stack的底部看到其中一个。

但是使用p.37的代码，返回的值要做更多的事情 - 前面的列表元素必须是consed到结果上。这意味着必须保留列表元素，在某处记住。在某个地方是rember的调用框架，其中该列表元素作为(car lat)被访问，对于lat的值，在执行时间轴中的那一点。

类似地，对于具有(else (function (cdr ...模式的所有其他函数，这意味着它们也是尾递归的。但如果你看到像(else (cons ... (function (cdr ...这样的东西，那么它们就不是。 cons挡路了。

---

为了更好地了解发生了什么，我们用等式模式匹配伪代码重写它：

(rember34 a lat) =
    { (null? lat)        ->  '() 
    ; (eq? a (car lat))  ->  (cdr lat)
    ; else               ->  (rember a (cdr lat))
    }

这进一步简化为三个条款，

rember34 a []          =  []
rember34 a [a, ...as]  =  as
rember34 a [b, ...as]  =  rember a as

这种伪代码在视觉上是否可以理解，而没有明确解释？我希望它是。另一个定义是

rember37 a []          =  [] 
rember37 a [a, ...as]  =  as
rember37 a [b, ...as]  =  [b, ...rember a as]

现在只需查看这些定义，我们就可以看到差异，以及每个人所做的事情。

第一个，rember34，沿着列表（这是它的第二个参数），(3rd clause)，直到它在其中找到a（它的第一个参数），如果它执行(2nd clause)，它返回列表的其余部分。如果没有a找到(3rd clause)，我们已到达列表(1st clause)的末尾，以便继续沿着的列表现在是空的（[]），空列表[]返回(1st clause)。

说得通。例如，

rember34 3 [1,2,3,4,5]              %   Tail-Recursive Call:
 = rember34 3 [2,3,4,5]             %    Just Returning The Result...
 = rember34 3 [3,4,5]               %     Call Frame Is Reused.
 = [4,5]

rember34 3 [1,2] 
 = rember34 3 [2]
 = rember34 3 []
 = []

第二个，rember37，做了同样的但有一个关键的区别：它将每个非匹配元素保留在它找到并删除之前（如前所述）。这意味着如果找不到这样的元素，将重新创建相同的列表。例如，

rember37 3 [1,2,3,4,5] 
 = [1, ...rember37 3 [2,3,4,5]]              % the->
       => [2, ...rember37 3 [3,4,5]]         %     stack->
              <= [4,5]                       %           grows
       <= [2,4,5]                            %      <-and
 = [1,2,4,5]                                 %  <-contracts

rember37 3 [1,2] 
 = [1, ...rember37 3 [2]]                    % must remember 1,
       => [2, ...rember37 3 []]              %     and 2, to be used
              <= []                          %          after the recursive call
       <= [2]                                %      has returned its result
 = [1,2]                                     %  to its caller

希望这能澄清事情。

---

旁注：在尾递归modulo cons优化下，它是

rember37 3 [1,2,3,4,5] 
 = [1, ...rember37 3 [2,3,4,5]]
 = [1, ...[2, ...rember37 3 [3,4,5]]]
 = [1,2, ...rember37 3 [3,4,5]]
 = [1,2, ...[4,5]]
 = [1,2,4,5]

rember37 3 [1,2] 
 = [1, ...rember37 3 [2]]
 = [1, ...[2, ...rember37 3 []]]
 = [1,2, ...rember37 3 []]
 = [1,2, ...[]]
 = [1,2]

这很像是懒惰的评价！

Answer 2

我强烈建议你在这里使用步进器，而不是调试器。我想你会看到一套更加一致的减少规则。具体来说，我认为你不会看到任何“被认为是未知的东西”。

要使用步进器：打开一个新缓冲区，确保语言级别设置为带有列表缩写的开始学生，并将定义和调用粘贴到定义窗口中。点击“步骤”。我想你会很快看到两个评估之间的差异。

如果没有意义，请询问后续问题！