1

我使用 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 ...）
（记住...）

p.37cons最后一行：

(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 ...)
(rember ...)
(rember ...)

带有 p.37 代码的 Stack 区域表明第二次调用 ofrember已被归类为在处理之前未知(cdr lat)。

2 个示例的唯一区别是第 37 页添加了“ cons”。Cons 接受 2 个参数，一个 s 表达式和一个列表。

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

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

或者为什么要以这种方式解释rember第二个论点。cons

谢谢！

4

2 回答 2

2

TL；DR：您看到（和误解）的是函数调用堆栈，以及尾递归的影响。

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

它不是“未知”，也不是“以后会减少”的东西。您已经通过它，到达您当前的执行点。它是什么，正在等待嵌套调用的结果，以继续使用results进行工作。

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

在此处输入图像描述

请注意，变量区域显示了该特定调用框架的变量值。

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

在此处输入图像描述

Racket 的调试器有点习惯了。

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

您看不到(rember)s 堆栈随着第一个代码（第 34 页）增长的原因，

在此处输入图像描述

是它是尾递归的。深度嵌套调用的结果没有什么可做的，rember除非将其返回更远；所以没有必要为此保存任何状态。这意味着 for 的调用框架被重用、替换，这就是为什么您只能在 Stackrember底部看到其中一个。

但是对于 p.37 的代码，需要对返回值做更多的事情——必须将前面的列表元素添加cons到结果中。这意味着必须保留列表元素，并在某处记住它。某处是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

希望这可以澄清事情。

旁注：在尾递归模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]

这很像它也会受到懒惰的评估！

于 2018-03-11T19:31:07.513 回答
2

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

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

如有任何不妥之处，请追问！

于 2018-03-11T06:16:50.437 回答