max-lisp-eval-depth 找到 sqrt-iter

Question

我正在研究重写演示案例的 SICP 练习 1.6

#+begin_src emacs-lisp :session sicp :results output
(defun sqrt(x)
  (sqrt-iter 1.0 x)) 

(defun sqrt-iter(guess x)
  (if (good-enough-p guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(defun good-enough-p(guess x)
  (< (abs (- (square guess) x)) 0.001))

(defun improve(guess x)
  (average guess (/ x guess)))

(defun average(x y)
  (/ (+ x y) 2))
#+end_src

有效并得到输出

#+begin_src emacs-lisp :session sicp :lexical t :results output
(print (sqrt 11))
(print (sqrt (+ 100 37)))
(print (sqrt (+ (sqrt 2) (sqrt 3))))
#+end_src

#+RESULTS:
: 
: 3.3166248052315686
: 
: 11.704699917758145
: 
: 1.7739279023207892

于是来到习题1.6，改写为cond

#+begin_src emacs-lisp :session sicp :lexical t
(defun sqrt-iter-cond(guess x)
  (cond ((good-enough-p guess x) guess)
        (t (sqrt-iter-cond (improve guess x) x))
   )
  )
(sqrt-iter-cond 1 10)
#+end_src

它报告错误：

  ob-async-org-babel-execute-src-block: Lisp nesting exceeds ‘max-lisp-eval-depth’

看完各种解释，我陷入了更多的困惑，甚至产生了隐隐的恐惧，不敢使用cond后记。因为它看起来显然逻辑正确。

能给点提示吗？

Answer 1

cond版本没有问题，从一个空缓冲区开始试试这个，它会工作：

(defun sqrt (x)
  (sqrt-iter-cond 1.0 x))

(defun sqrt-iter-cond (guess x)
  (cond ((good-enough-p guess x) guess)
        (t (sqrt-iter-cond (improve guess x) x))))

(defun good-enough-p (guess x)
  (< (abs (- (square guess) x)) 0.001))

(defun improve (guess x)
  (average guess (/ x guess)))

(defun average(x y)
  (/ (+ x y) 2))

(print (sqrt 11))
=> 3.3166247903554

但是这个练习不是关于用 cond 重写过程，它应该告诉你你不能用过程来写你自己的 if 版本，你需要一个特殊的具有特殊评估规则的形式 - 因为程序的评估规则将同时评估结果部分和替代部分，这是行不通的！看看这个简单的例子就明白我的意思了：

(if t 'ok (/ 1 0))

以上将 return 'ok，即使那里有被零除：那部分从未被执行。但是，如果我们尝试使用我们自己的 if 作为正常过程来实现它，它将失败并出现被零除错误：

(defun my-if (condition consequent alternative)
  (cond (condition consequent)
        (t alternative)))

(my-if t 'ok (/ 1 0))

现在回到您的代码并尝试它，当然它也会失败，但这次会出现无限递归错误（这就是 "Lisp nesting exceeds ‘max-lisp-eval-depth’" 消息的意思）：

(defun sqrt-iter (guess x)
  (my-if (good-enough-p guess x)
         guess
         (sqrt-iter (improve guess x)
                    x)))

Answer 2

sqrt-iter 之所以这样命名是因为它是尾递归的。它旨在由将其编译为迭代的 Scheme 实现进行处理。 Emacs Lisp 不是尾递归的，因此代码执行实际的递归。它生成了如此多的函数激活，以至于达到了深度限制。

我们可以做的是将其重写为显式迭代：

(defun sqrt-iter(guess x)
  (while (not (good-enough-p guess x))
    (setq guess (improve guess x)))
  guess))

另一个想法是尝试使用此 Elisp tail call module.

提供的 defun-tco 宏

max-lisp-eval-depth 找到 sqrt-iter

max-lisp-eval-depth to find sqrt-iter

lisp

elisp

sicp