Common Lisp 中的递归、推值和斐波那契数列
Recursion in Common Lisp, pushing values, and the Fibonacci Sequence
这是不是家庭作业。在以下代码中：
(defparameter nums '())
(defun fib (number)
(if (< number 2)
number
(push (+ (fib (- number 1)) (fib (- number 2))) nums))
return nums)
(format t "~a " (fib 100))
由于我对 Common Lisp 缺乏经验，所以我不知道为什么函数没有 return 值。我正在尝试打印斐波那契数列的第一个 'n' 个值，例如 100。
谢谢。
你的函数无条件地 returns nums（但前提是存在名为 return 的变量）。要知道为什么，我们可以这样格式化：
(defun fib (number)
(if (< number 2)
number
(push (+ (fib (- number 1)) (fib (- number 2))) nums))
return
nums)
如果 number 小于 2，那么它会无用地计算表达式 number，并丢弃结果。否则，它将 (+ ....) 表达式的结果推入 nums 列表。然后它无用地评估 return，丢弃结果。如果名为 return 的变量不存在，那就是错误情况。否则，它计算 nums，即 return 值。
在 Common Lisp 中，有一个 return 运算符用于终止和 return 退出匿名命名块（名称为符号 nil 的块）。如果您使用 defun 定义命名函数，则存在一个非匿名的不可见块：它与该函数具有相同的名称。在那种情况下，可以使用return-from：
(defun function ()
(return-from function 42) ;; function terminates, returns 42
(print 'notreached)) ;; this never executes
某些标准控制流和循环构造建立了一个隐藏的匿名块，因此可以使用 return：
(dolist (x '(1 2 3))
(return 42)) ;; loop terminates, yields 42 as its result
如果我们使用 (return ...) 但是没有封闭的匿名块，那就是一个错误。
表达式 (return ...) 不同于 return，后者计算由符号 return 命名的变量，并检索其内容。
不清楚如何修复您的 fib 功能，因为要求未知。将值推入全局列表的副作用通常不属于像这样的数学函数，它应该是纯的 (side-effect-free).
计算斐波那契数的一个明显方法是：
(defun fib (n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(defun fibs (n)
(loop for i from 1 below n
collect (fib i)))
稍微想一想就会告诉您为什么没有像这样的方法可以帮助您计算前 100 个斐波那契数：计算 (fib n) 所花费的时间等于或略多于计算 (fib n) 所花费的时间计算 (fib (- n 1)) 加上计算 (fib (- n 2)) 所花费的时间：这是指数级的（参见 this stack overflow answer）。
一个很好的解决方案是 memoization：(fib n) 的计算重复了很多次子计算，如果我们能记住我们最后计算的答案是时候我们可以避免再次这样做了。
（这个答案的早期版本在这里有一个过于复杂的宏：类似的东西通常可能有用，但在这里不需要。）
这里是你可以记忆的方法 fib:
(defun fib (n)
(check-type n (integer 0) "natural number")
(let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
(labels ((fibber (m)
(when (> m (car (first so-far)))
(push (cons m (+ (fibber (- m 1))
(fibber (- m 2))))
so-far))
(cdr (assoc m so-far))))
(fibber n))))
这会保留一个 table – 一个列表 – 到目前为止计算的结果，并使用它来避免重新计算。
使用这个记忆版本的函数：
> (time (fib 1000))
Timing the evaluation of (fib 1000)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 101944 bytes
0 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
上面的定义在每次调用 fib 时使用一个新的缓存：这很好，因为本地函数 fibber 确实重用了缓存。但是你可以通过将缓存完全放在函数之外来做得更好：
(defmacro define-function (name expression)
;; Install EXPRESSION as the function value of NAME, returning NAME
;; This is just to avoid having to say `(setf ...)`: it should
;; probably do something at compile-time too so the compiler knows
;; the function will be defined.
`(progn
(setf (fdefinition ',name) ,expression)
',name))
(define-function fib
(let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
(lambda (n)
(block fib
(check-type n (integer 0) "natural number")
(labels ((fibber (m)
(when (> m (car (first so-far)))
(push (cons m (+ (fibber (- m 1))
(fibber (- m 2))))
so-far))
(cdr (assoc m so-far))))
(fibber n))))))
此版本的 fib 将在调用之间共享其缓存，这意味着它速度更快，分配的内存更少，但可能更少 thread-safe:
> (time (fib 1000))
[...]
Allocation = 96072 bytes
[...]
> (time (fib 1000))
[...]
Allocation = 0 bytes
[...]
有趣的是，记忆化是由 Donald Michie 发明（或至少命名）的，他致力于打破 Tunny（因此与 Colossus 一起工作），我也略微了解他：计算的历史仍然很短！
请注意，记忆化是您最终可能与编译器进行战斗的时代之一。特别是对于这样的函数：
(defun f (...)
...
;; no function bindings or notinline declarations of F here
...
(f ...)
...)
然后允许编译器（但不是必需的）假定对 f 的明显递归调用是对其正在编译的函数的递归调用，从而避免大量开销全功能调用。特别是不需要检索符号 f 的当前函数值：它可以直接调用函数本身。
这意味着尝试编写一个 函数 ，memoize 可用于 mamoize 现有的递归函数，因为 (setf (fdefinition 'f) (memoize #'f)) 可能不工作：函数 f 仍然直接调用其自身的未记忆版本，并且不会注意到 f 的函数值已更改。
事实上，即使递归在许多情况下是间接的，这也是正确的：允许编译器假设对函数 g 的调用（在同一文件中有定义）是对文件中定义的版本，再次避免完整调用的开销。
处理这个问题的方法是添加 suitable notinline 声明：如果一个调用被 notinline 声明覆盖（编译器必须知道）那么它必须作为一个完整的电话。来自 spec:
A compiler is not free to ignore this declaration; calls to the specified functions must be implemented as out-of-line subroutine calls.
这意味着，为了记忆函数，您必须为递归调用添加 suitable notinline 声明，这意味着记忆要么需要通过宏来完成，或者必须依靠用户向要记忆的函数添加 suitable 声明。
这只是一个问题，因为允许 CL 编译器变得聪明：几乎总是 好 事情！
你的全局变量 num 实际上是个不错的主意。
它即将拥有关于已经计算出哪些斐波那契数的中央记忆。并且不再计算那些已经计算过的数字。
这就是记忆的理念。
但首先，我使用全局变量的方式很糟糕。
带有全局变量的错误版本 *fibonacci*
(defparameter *fibonacci* '(1 1))
(defun fib (number)
(let ((len (length *fibonacci*)))
(if (> len number)
(elt *fibonacci* (- len number 1)) ;; already in *fibonacci*
(labels ((add-fibs (n-times)
(push (+ (car *fibonacci*)
(cadr *fibonacci*))
*fibonacci*)
(cond ((zerop n-times) (car *fibonacci*))
(t (add-fibs (1- n-times))))))
(add-fibs (- number len))))))
;;> (fib 10)
;; 89
;;> *fibonacci*
;; (89 55 34 21 13 8 5 3 2 1 1)
好功能版（备忘）
在记忆中，你隐藏了全局*fibonacci*变量
进入词法函数的环境（函数的记忆版本）。
(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal)))
#'(lambda (&rest args)
(multiple-value-bind (val win) (gethash args cache)
(if win
val
(setf (gethash args cache)
(apply fn args)))))))
(defun fib (num)
(cond ((zerop num) 1)
((= 1 num) 1)
(t (+ (fib (- num 1))
(fib (- num 2))))))
之前的全局变量*fibonacci*，这里其实是memoize函数的局部变量cache——来自全局环境的encapsulated/hidden，
accessible/look-up-able 只能通过函数 fibm.
在 fib 上应用记忆（错误版本！）
(defparameter fibm (memoize #'fib))
由于 common lisp 是 Lisp 2（函数名和变量名之间的命名空间分开），但我们必须在这里将记忆函数分配给变量，
我们必须使用 (funcall <variable-name-bearing-function> <args for memoized function>).
(funcall fibm 10) ;; 89
或者我们再定义一个
(defun fibm (num)
(funcall fibm num))
并且可以做到
(fibm 10)
- 然而，这 saves/memoizes 只有 out 调用，例如这里只有
10 的斐波那契值。尽管如此，斐波那契数
对于 9, 8, ..., 1 也被计算。
要保存它们，请看下一节！
在 fib 上应用记忆（@Sylwester 的更好版本 - 谢谢！）
(setf (symbol-function 'fib) (memoize #'fib))
现在原来的fib函数是memoized函数，
所以所有 fib-calls 都将被记忆。
另外调用memoized版本不需要funcall，
但只要做
(fib 10)
所以你可能知道，如果你知道前两个数字，你就可以计算下一个。 3, 5 之后是什么？如果你猜到 8 你就明白了。现在，如果您从 0, 1 开始，然后滚动 1, 1、1, 2 等，您将收集第一个变量，直到获得您想要的数字数量：
(defun fibs (elements)
"makes a list of elements fibonacci numbers starting with the first"
(loop :for a := 0 :then b
:for b := 1 :then c
:for c := (+ a b)
:for n :below elements
:collect a))
(fibs 10)
; ==> (0 1 1 2 3 5 8 13 21 34)
Common Lisp 中的每个形式 "returns" 一个值。你可以说它评估为。例如。
(if (< a b)
5
10)
计算结果为 5 或 10。因此，您可以这样做并期望它的计算结果为 15 或 20:
(+ 10
(if (< a b)
5
10))
您基本上希望您的函数具有 一个 表达式来计算结果。例如。
(defun fib (n)
(if (zerop n)
n
(+ (fib (1- n)) (fib (- n 2)))))
这会计算出 if 表达式的结果... loop 和 :collect returns 列表。你也有 (return expression) 和 (return-from name expression) 但它们通常是不必要的。
这是不是家庭作业。在以下代码中：
(defparameter nums '())
(defun fib (number)
(if (< number 2)
number
(push (+ (fib (- number 1)) (fib (- number 2))) nums))
return nums)
(format t "~a " (fib 100))
由于我对 Common Lisp 缺乏经验，所以我不知道为什么函数没有 return 值。我正在尝试打印斐波那契数列的第一个 'n' 个值，例如 100。
谢谢。
你的函数无条件地 returns nums（但前提是存在名为 return 的变量）。要知道为什么，我们可以这样格式化：
(defun fib (number)
(if (< number 2)
number
(push (+ (fib (- number 1)) (fib (- number 2))) nums))
return
nums)
如果 number 小于 2，那么它会无用地计算表达式 number，并丢弃结果。否则，它将 (+ ....) 表达式的结果推入 nums 列表。然后它无用地评估 return，丢弃结果。如果名为 return 的变量不存在，那就是错误情况。否则，它计算 nums，即 return 值。
在 Common Lisp 中，有一个 return 运算符用于终止和 return 退出匿名命名块（名称为符号 nil 的块）。如果您使用 defun 定义命名函数，则存在一个非匿名的不可见块：它与该函数具有相同的名称。在那种情况下，可以使用return-from：
(defun function ()
(return-from function 42) ;; function terminates, returns 42
(print 'notreached)) ;; this never executes
某些标准控制流和循环构造建立了一个隐藏的匿名块，因此可以使用 return：
(dolist (x '(1 2 3))
(return 42)) ;; loop terminates, yields 42 as its result
如果我们使用 (return ...) 但是没有封闭的匿名块，那就是一个错误。
表达式 (return ...) 不同于 return，后者计算由符号 return 命名的变量，并检索其内容。
不清楚如何修复您的 fib 功能，因为要求未知。将值推入全局列表的副作用通常不属于像这样的数学函数，它应该是纯的 (side-effect-free).
计算斐波那契数的一个明显方法是：
(defun fib (n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(defun fibs (n)
(loop for i from 1 below n
collect (fib i)))
稍微想一想就会告诉您为什么没有像这样的方法可以帮助您计算前 100 个斐波那契数：计算 (fib n) 所花费的时间等于或略多于计算 (fib n) 所花费的时间计算 (fib (- n 1)) 加上计算 (fib (- n 2)) 所花费的时间：这是指数级的（参见 this stack overflow answer）。
一个很好的解决方案是 memoization：(fib n) 的计算重复了很多次子计算，如果我们能记住我们最后计算的答案是时候我们可以避免再次这样做了。
（这个答案的早期版本在这里有一个过于复杂的宏：类似的东西通常可能有用，但在这里不需要。）
这里是你可以记忆的方法 fib:
(defun fib (n)
(check-type n (integer 0) "natural number")
(let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
(labels ((fibber (m)
(when (> m (car (first so-far)))
(push (cons m (+ (fibber (- m 1))
(fibber (- m 2))))
so-far))
(cdr (assoc m so-far))))
(fibber n))))
这会保留一个 table – 一个列表 – 到目前为止计算的结果，并使用它来避免重新计算。
使用这个记忆版本的函数：
> (time (fib 1000))
Timing the evaluation of (fib 1000)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 101944 bytes
0 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
上面的定义在每次调用 fib 时使用一个新的缓存：这很好，因为本地函数 fibber 确实重用了缓存。但是你可以通过将缓存完全放在函数之外来做得更好：
(defmacro define-function (name expression)
;; Install EXPRESSION as the function value of NAME, returning NAME
;; This is just to avoid having to say `(setf ...)`: it should
;; probably do something at compile-time too so the compiler knows
;; the function will be defined.
`(progn
(setf (fdefinition ',name) ,expression)
',name))
(define-function fib
(let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
(lambda (n)
(block fib
(check-type n (integer 0) "natural number")
(labels ((fibber (m)
(when (> m (car (first so-far)))
(push (cons m (+ (fibber (- m 1))
(fibber (- m 2))))
so-far))
(cdr (assoc m so-far))))
(fibber n))))))
此版本的 fib 将在调用之间共享其缓存，这意味着它速度更快，分配的内存更少，但可能更少 thread-safe:
> (time (fib 1000))
[...]
Allocation = 96072 bytes
[...]
> (time (fib 1000))
[...]
Allocation = 0 bytes
[...]
有趣的是，记忆化是由 Donald Michie 发明（或至少命名）的，他致力于打破 Tunny（因此与 Colossus 一起工作），我也略微了解他：计算的历史仍然很短！
请注意，记忆化是您最终可能与编译器进行战斗的时代之一。特别是对于这样的函数：
(defun f (...)
...
;; no function bindings or notinline declarations of F here
...
(f ...)
...)
然后允许编译器（但不是必需的）假定对 f 的明显递归调用是对其正在编译的函数的递归调用，从而避免大量开销全功能调用。特别是不需要检索符号 f 的当前函数值：它可以直接调用函数本身。
这意味着尝试编写一个 函数 ，memoize 可用于 mamoize 现有的递归函数，因为 (setf (fdefinition 'f) (memoize #'f)) 可能不工作：函数 f 仍然直接调用其自身的未记忆版本，并且不会注意到 f 的函数值已更改。
事实上，即使递归在许多情况下是间接的，这也是正确的：允许编译器假设对函数 g 的调用（在同一文件中有定义）是对文件中定义的版本，再次避免完整调用的开销。
处理这个问题的方法是添加 suitable notinline 声明：如果一个调用被 notinline 声明覆盖（编译器必须知道）那么它必须作为一个完整的电话。来自 spec:
A compiler is not free to ignore this declaration; calls to the specified functions must be implemented as out-of-line subroutine calls.
这意味着，为了记忆函数，您必须为递归调用添加 suitable notinline 声明，这意味着记忆要么需要通过宏来完成，或者必须依靠用户向要记忆的函数添加 suitable 声明。
这只是一个问题，因为允许 CL 编译器变得聪明：几乎总是 好 事情！
你的全局变量 num 实际上是个不错的主意。
它即将拥有关于已经计算出哪些斐波那契数的中央记忆。并且不再计算那些已经计算过的数字。
这就是记忆的理念。
但首先，我使用全局变量的方式很糟糕。
带有全局变量的错误版本 *fibonacci*
(defparameter *fibonacci* '(1 1))
(defun fib (number)
(let ((len (length *fibonacci*)))
(if (> len number)
(elt *fibonacci* (- len number 1)) ;; already in *fibonacci*
(labels ((add-fibs (n-times)
(push (+ (car *fibonacci*)
(cadr *fibonacci*))
*fibonacci*)
(cond ((zerop n-times) (car *fibonacci*))
(t (add-fibs (1- n-times))))))
(add-fibs (- number len))))))
;;> (fib 10)
;; 89
;;> *fibonacci*
;; (89 55 34 21 13 8 5 3 2 1 1)
好功能版（备忘）
在记忆中，你隐藏了全局*fibonacci*变量
进入词法函数的环境（函数的记忆版本）。
(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal)))
#'(lambda (&rest args)
(multiple-value-bind (val win) (gethash args cache)
(if win
val
(setf (gethash args cache)
(apply fn args)))))))
(defun fib (num)
(cond ((zerop num) 1)
((= 1 num) 1)
(t (+ (fib (- num 1))
(fib (- num 2))))))
之前的全局变量*fibonacci*，这里其实是memoize函数的局部变量cache——来自全局环境的encapsulated/hidden，
accessible/look-up-able 只能通过函数 fibm.
在 fib 上应用记忆（错误版本！）
(defparameter fibm (memoize #'fib))
由于 common lisp 是 Lisp 2（函数名和变量名之间的命名空间分开），但我们必须在这里将记忆函数分配给变量，
我们必须使用 (funcall <variable-name-bearing-function> <args for memoized function>).
(funcall fibm 10) ;; 89
或者我们再定义一个
(defun fibm (num)
(funcall fibm num))
并且可以做到
(fibm 10)
- 然而，这 saves/memoizes 只有 out 调用，例如这里只有 10 的斐波那契值。尽管如此，斐波那契数 对于 9, 8, ..., 1 也被计算。 要保存它们，请看下一节！
在 fib 上应用记忆（@Sylwester 的更好版本 - 谢谢！）
(setf (symbol-function 'fib) (memoize #'fib))
现在原来的fib函数是memoized函数，
所以所有 fib-calls 都将被记忆。
另外调用memoized版本不需要funcall，
但只要做
(fib 10)
所以你可能知道，如果你知道前两个数字，你就可以计算下一个。 3, 5 之后是什么？如果你猜到 8 你就明白了。现在，如果您从 0, 1 开始，然后滚动 1, 1、1, 2 等，您将收集第一个变量，直到获得您想要的数字数量：
(defun fibs (elements)
"makes a list of elements fibonacci numbers starting with the first"
(loop :for a := 0 :then b
:for b := 1 :then c
:for c := (+ a b)
:for n :below elements
:collect a))
(fibs 10)
; ==> (0 1 1 2 3 5 8 13 21 34)
Common Lisp 中的每个形式 "returns" 一个值。你可以说它评估为。例如。
(if (< a b)
5
10)
计算结果为 5 或 10。因此，您可以这样做并期望它的计算结果为 15 或 20:
(+ 10
(if (< a b)
5
10))
您基本上希望您的函数具有 一个 表达式来计算结果。例如。
(defun fib (n)
(if (zerop n)
n
(+ (fib (1- n)) (fib (- n 2)))))
这会计算出 if 表达式的结果... loop 和 :collect returns 列表。你也有 (return expression) 和 (return-from name expression) 但它们通常是不必要的。