1

我正在阅读fix-pointSICP：

#+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在这里介绍SICP，我猜效率可能不是作者的主要考虑因素。

用 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

它按预期工作。

似乎 returnfixed-point f next比带有 try 的内部迭代更干净一些。

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

4

3 回答 3

1

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

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

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

（更正/澄清：上面将您的代码视为Scheme，使用 internal defines 而不是带有defuns 的 Common Lisp，毕竟 SICP 是 Scheme。在 Common Lisp / ELisp 中甚至没有问题 -在每次调用封闭函数时，将始终执行internal defuns，只是一遍又一遍地（重新）在顶层定义相同的函数。）

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

鉴于您问题中的第一个尾递归方案代码，您的while翻译正是方案编译器应该做的事情。两者完全相同，下至“可怕while True ...的逃脱”，就我个人而言，我非常喜欢它的直接性和清晰性。意思是，我不需要跟踪哪个值被分配给哪个变量以及最终返回哪个变量——相反，一个值只是返回，就像它在 Scheme 中一样。

于 2019-12-26T14:09:33.897 回答
1

在 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 中自然的方式使用while循环而不是递归；
  • 不使用一些可怕while True ...的逃逸，这只是令人困惑。

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

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

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

  • 我们可以将顶层函数视为我们递归调用的东西；
  • 我们可以定义一些我们递归的局部函数。

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

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

这是 Python 中的递归版本，它借此机会也使顶级函数的签名更加丰富。请注意，这种方法在 Python 中将是一种糟糕的风格，因为 Python 没有对尾调用做任何特殊的事情。代码中也充满了returns，因为 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 编写的相同函数（实际上是在 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 系统，几乎所有这些系统都是免费的。

于 2019-12-26T15:31:18.880 回答
1

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

于 2019-12-26T15:49:26.020 回答