`fixed-point` 中的内部 `try` 交互

Question

我正在阅读 SICP 的fix-point：

#+begin_src emacs-lisp :session sicp :lexical t
(defvar tolerance 0.00001)
(defun fixed-point(f first-guess)
  (defun close-enoughp(v1 v2) 
    (< (abs (- v1 v2)) tolerance))
  (defun try(guess) ;;
    (let ((next (funcall f guess)))
      (if (close-enoughp guess next)
          next
          (try next))))
  (try first-guess))
(fixed-point #'cos 1.0)
#+end_src

#+RESULTS:
: 0.7390822985224024

从上面的案例中了解到while的一个本质是抽象概念"try"

#+begin_src ipython :session sicp :results output pySrc/sicp_fixedpoint2.py
import math

def fixed_point(f, guess):
    while True:
        nex = f(guess)
        if abs(guess-nex) < 0.0001:
            return nex
        else:
            guess = nex #local assignment is nature of lambda
print(fixed_point(math.cos, 1))
#+end_src

#+RESULTS:
: 0.7390547907469174

所以我可以用有效的函数抽象思维在 python 中编写迭代。

当反思try，超过"try is a while in iteration"，它教会了我什么？

可以不用try重新构造，但是直接returnreturn fixed_point(f, nex)

#+begin_src ipython :session sicp :results output :tangle pySrc/sicp_fixedpoint.py
import math
tolerance = 0.00001

def fixed_point(f, guess):
    def good_enoughp(a, b):
        return abs(a-b) < tolerance

    nex = f(guess)
    if good_enoughp(guess, nex):
        return nex
    else:
        return fixed_point(f, nex)    

print(fixed_point(math.cos, 1))
#+end_src

#+RESULTS:
: 0.7390822985224024

那么为什么SICP在这里引入try，我想效率可能不是作者的重点考虑。

用 elisp 测试

#+begin_src emacs-lisp :session sicp :lexical t
(defvar tolerance 0.00001)
(defun fixed-point(f guess)
  (defun close-enoughp(v1 v2) ;
    (< (abs (- v1 v2)) tolerance))

  (let ((next (funcall f guess)))
    (if (close-enoughp guess next)
        next
      (fixed-point f next)))
  )
;;(trace-function #'fixed-point)
(fixed-point #'cos 1.0)
#+end_src

#+RESULTS:
: 0.7390822985224024

它按预期工作。

似乎 return fixed-point f next 比使用 try 的内部迭代要干净一些。

这里SICP的考虑是什么，想教什么？

Answer 1

恰恰相反：try 更简洁高效，因为它不需要重新定义 good-enough-p。

（另外，您不应该在 Python 中使用递归）。

带try的版本比调用顶层函数fixed-point的版本要好，因为fixed-point包含函数good-enough-p和try。一个头脑简单的编译器会编译它，以便在每次调用时它实际上在每次调用时一次又一次地重新定义这些定义。使用 try 就没有这样的担忧，因为它已经在 fixed-point 的内部环境中，其中 good-enough-p 已经被定义，所以 try 可以运行。

(correction/clarification: 上面的代码将你的代码视为 Scheme，使用内部 defines 而不是像你一样使用 defuns 的 Common Lisp显示。毕竟 SICP 是 Scheme。在 Common Lisp / ELisp 中甚至没有问题 - 内部 defuns 将始终执行，在每次调用封闭函数时，只是（重新）定义相同的函数一遍又一遍地在顶层。）

顺便说一下，我喜欢你的 Python 循环翻译，它是 Scheme 的尾递归循环的逐字翻译，一对一。

你的 while 翻译正是 Scheme 编译器在你的问题中给出第一个尾递归 Scheme 代码时应该做的。两者完全相同，一直到，就我个人而言，我非常喜欢它的直接性和清晰性。意思是，我不需要跟踪哪个值分配给了哪个变量以及最后返回了哪个变量——相反，只是返回一个值，就像在 Scheme 中一样。

Answer 2

在Python中写这样的东西的自然方式是这样的，我认为：

tolerance = 0.00001

def fixed_point(f, first_guess):
    guess = first_guess
    next_guess = f(guess)
    def close_enough(a, b):
        return (abs(a - b) < tolerance)
    while not close_enough(guess, next_guess):
        guess = next_guess
        next_guess = f(guess)
    return next_guess

这个：

使用 while 循环而不是 Python 中自然的递归方式；
不使用一些可怕的 while True ... 和令人困惑的转义。

（事实上，由于 Python 中的函数调用通常很慢，打开对 close_enough 的调用代码并完全删除本地函数可能更自然。）

但这是命令式代码：它充满了赋值（前两个 'assignments' 实际上是变量的绑定，因为 Python 在语法上不区分两者，但后面的赋值确实是赋值).我们想以一种没有赋值的方式来表达这一点。我们还想用不使用任何循环结构或根据函数调用表达这些循环结构的东西来替换它。

我们可以通过两种方式做到这一点：

我们可以把顶层函数当作我们递归调用的东西；
我们可以定义一些我们递归的局部函数。

我们做哪一个真的是一个选择，在这种情况下可能没什么区别。然而，第二种方法通常有显着的优势：一般来说，顶层函数（我们可能向人们公开的某些接口中的函数）可能有各种额外的参数，其中一些可能有默认值等上，我们真的不想继续通过后面的调用；顶层函数也可能根本没有合适的参数签名，因为迭代步骤可能会迭代一些从顶层函数的参数派生的值。

因此，尽管不一定总是这样，但通常最好用局部函数来表示迭代。

这是 Python 中的一个递归版本，它借此机会使顶级函数的签名更加丰富。请注意，这种方法在 Python 中将是糟糕的风格，因为 Python 不会对尾调用做任何特殊的事情。代码里也乱七八糟的是return因为Python不是表达式语言（别信人家说'Python is like Lisp'：不是）：

default_tolerance = 0.00001

def fixed_point(f, first_guess, tolerance=default_tolerance):
    guess = first_guess
    next_guess = f(guess)
    def close_enough(a, b):
        return (abs(a - b) < tolerance)
    def step(guess, next_guess):
        if close_enough(guess, next_guess):
            return next_guess
        else:
            return step(next_guess, f(next_guess))
    return step(first_guess, f(first_guess))

好吧，在 Scheme 中这更自然：这里是用 Scheme 编写的相同函数（实际上，在 Racket 中）：

(define default-tolerance 0.00001)

(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess next)
    (if (close-enough? guess next)
        next
        (try next (f next))))
  (try initial-guess (f initial-guess)))

唯一令人讨厌的是我们必须在定义 try 之后开始迭代。好吧，我们甚至可以用宏来避免这种情况：

(define-syntax-rule (iterate name ((var val) ...) form ...)
  (begin
    (define (name var ...)
      form ...)
    (name val ...)))

现在我们可以将函数写成：

(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (iterate try ((guess initial-guess) (next (f initial-guess)))
    (if (close-enough? guess next)
        next
        (try next (f next)))))

好吧，实际上我们不需要编写这个 iterate 宏：它在 Scheme 中非常有用，它已经作为 let 的特殊版本存在，称为 'named let'：

(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (let try ((guess initial-guess) (next (f initial-guess)))
    (if (close-enough? guess next)
        next
        (try next (f next)))))

对于这些版本中的任何一个：

> (fixed-point cos 0)
0.7390822985224023
> (fixed-point cos 0 #:tolerance 0.1)
0.7013687736227565

最后一个元评论：我不明白为什么你似乎在尝试使用 Emacs Lisp 来学习 Scheme。这两种语言完全不同：如果你想学习 Scheme，请使用 Scheme：可能有数百个 Scheme 系统，几乎所有系统都是免费的。

Answer 3

方案允许重新定义顶级符号，例如fixed-point；甚至函数 f 都可以重新定义它！编译器（和解释器）需要考虑到这一点，并在每次调用 fixed-point 时检查重新定义。另一方面，try 在 fixed-point 的定义之外是不可见的，所以 f 不能重新定义它。所以，编译器（或解释器）可以把这个尾递归函数变成一个循环。

`fixed-point` 中的内部 `try` 交互

The inner `try` interation in `fixed-point`

scheme

elisp

sicp

python-3.x

fixed-point-iteration