我正在读取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
的一个本质是抽象概念"尝试">
#+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
所以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
它按预期工作。
看起来返回fixed-point f next
比带有try的内部迭代要干净一些。
SICP在这里有什么考虑,打算教什么?
恰恰相反: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 Lisp。毕竟,SICP就是Scheme。在Common Lisp/ELisp中,甚至没有任何问题——内部defun
s总是在每次调用封闭函数时执行,只是在顶层一遍又一遍地(重新)定义相同的函数再次。)
顺便说一句,我喜欢您的Python循环翻译,它是Scheme尾部递归循环的逐字翻译,一对一。
考虑到问题中的第一个尾部递归Scheme代码,while
翻译正是Scheme编译器应该做的。这两者完全相同,直到"可怕的while True ...
有一次逃脱",就我个人而言,我非常喜欢它的即时性和清晰度。也就是说,我不需要跟踪哪个值被分配给哪个变量,哪个变量最终被返回——相反,一个值只是被返回,就像Scheme中一样。
在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 ...
和一个令人困惑的escape
(事实上,由于Python中的函数调用通常非常慢,因此打开对close_enough
的调用代码并完全删除本地函数可能会更自然。)
但这是命令式代码:它充满了赋值(前两个"赋值"实际上是变量的绑定,因为Python在语法上没有区分这两个,但后面的赋值实际上是赋值)。我们想用一种没有赋值的方式来表达这一点。我们还想用不使用任何循环结构或用函数调用来表达这些循环结构的东西来代替它。
我们可以通过两种方式做到这一点:
- 我们可以将顶级函数视为我们递归调用的东西
- 我们可以定义一些递归的局部函数
我们确实可以选择其中的哪一个,在这种情况下,这可能没有什么区别。然而,第二种方法通常有显著的优势:一般来说,顶级函数(我们可能向人们公开的某个接口中的函数)可能有各种额外的参数,其中一些可能有默认值等等,我们真的不想在以后的调用中不断传递这些参数;顶层函数也可能根本不具有适当的参数签名,因为迭代步骤可能在从顶层函数的参数导出的某组值上迭代。
因此,通常最好用局部函数来表达迭代,尽管它可能并不总是这样
这里有一个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中编写的相同函数(事实上,在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
的一个特殊版本存在,称为"命名为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系统,几乎所有系统都是免费的。
Scheme允许重新定义顶级符号,如fixed-point
;甚至函数f
也可以重新定义它!编译器(和解释器)需要考虑到这一点,并在每次调用fixed-point
时检查是否有重新定义。另一方面,try
在fixed-point
的定义之外是不可见的,因此f
不能重新定义它。因此,编译器(或解释器)可以将这个尾部递归函数变成一个循环。