“定点”中的内部“尝试”插入

Question

我正在阅读“国际化学品安全公约”的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的一个本质是抽象的概念“尝试”。

#+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的情况下对其进行重构，但直接返回return 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

那么，为什么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

它如预期的那样工作。

返回fixed-point f next似乎比尝试的内部迭代要干净一些。

SICP在这里的考虑是什么，打算教什么？

Answer 1

恰恰相反:它使用try更干净、更高效，因为它不需要重新定义good-enough-p。

(而且，您不应该在Python中使用递归)。

try版本优于调用顶级函数fixed-point的版本，因为fixed-point包含函数good-enough-p和try的内部定义。一个简单的编译器会编译它，这样在每次调用时，它实际上都会一次又一次地对每个调用进行这些定义。对于try，没有那么多的顾虑，因为它已经在fixed-point的内部环境中定义了good-enough-p，所以try可以直接运行。

(更正/澄清:上面将您的代码视为Scheme，内部define__s而不是defun__s的Common，如您所示。毕竟，SICP是一项计划。在Common / ELisp中，甚至没有一个问题--在每次调用封闭函数时，总是执行内部defun__s，只是(重新)在顶层一次又一次地定义相同的函数。

顺便说一句，我喜欢您的Python循环翻译，它是一个逐字翻译方案的尾递归循环，一对一。

给定问题中的第一个尾递归方案代码，您的while转换正是Scheme编译器应该做的事情。两者是完全相同的，直到"horrible while True ... with an escape"，就我个人而言，我非常喜欢它的即时性和清晰性。也就是说，我不需要跟踪哪个值被分配给哪个变量，哪个变量在最后被返回--相反，一个值只是返回，就像它在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

这是：

在Python;

• doesn't中，
• 使用while循环而不是递归，使用一些可怕的带有转义的while True ...，这是令人困惑的。

(事实上，由于Python中的函数调用通常非常慢，所以打开对close_enough的调用并完全删除本地函数可能更自然。)

但这是命令式代码:它充满了赋值(前两个“赋值”实际上是变量的绑定，因为Python没有在语法上区分这两个变量，但后面的赋值实际上是赋值)。我们想用一种没有任务的方式来表达这一点。我们还希望用不使用任何循环结构或用函数调用来表示那些循环结构的东西来替换它。

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

我们可以把顶层函数看作是recursively;

• we可以定义一些局部函数的东西，通过它我们可以恢复.

。

我们所做的选择实际上是一种选择，在这种情况下，它可能没有什么区别。然而，第二种方法通常有明显的优势:一般来说，顶层函数(我们可能向人们公开的某个接口中的函数)可能有各种额外的参数，其中一些参数可能有默认值等等，我们真的不想继续传递对它的稍后调用；顶级函数也可能根本没有适当的参数签名，因为迭代步骤可能会迭代从参数到顶层函数的一些值集。

因此，通常最好用局部函数来表示迭代，尽管它可能并不总是这样。

这里是Python中的递归版本，它也使顶级函数的签名更加丰富。请注意，这种方法在Python中将是非常糟糕的风格，因为Python不会对尾调用执行任何特殊的操作。代码中还到处都是return的，因为Python不是一种表达式语言(不要相信那些说'Python就像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编写的函数(实际上，在球拍中)：

(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宏:它在方案中非常有用，它已经作为名为“命名let”的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来学习Scheme。这两种语言一点也不一样:如果你想学习“计划”，那就使用“计划”吧:可能有几百个系统，几乎所有的系统都是免费的。

Answer 3

方案允许重新定义顶级符号，如fixed-point；甚至f函数也可以重新定义它！编译器(和解释器)需要考虑到这一点，并检查是否重新定义了fixed-point的每个调用。另一方面，try在fixed-point定义之外是不可见的，因此f不能重新定义它。因此，编译器(或解释器)可以将这个尾递归函数转换为一个循环。