macros - SBCL 中奇怪的宏展开错误

Question

我想使用适用于 Windows x86_64 的 SBCL 1.3.3 在 Lisp 中编写斐波那契数计算函数 fib。使用惰性计算来避免重复。到目前为止的工作代码是:

(defvar *fibs* (make-hash-table))

(defun get-value (idx)
  (if (functionp (gethash idx *fibs*))
    (setf (gethash idx *fibs*)
      (funcall (gethash idx *fibs*)))
    (gethash idx *fibs*)))

(defun fib (n)
  (loop for i from 0 below n
    if (< i 2) do (setf (gethash i *fibs*) 1)
    else do (setf (gethash i *fibs*)
      (eval `(lambda () (+ (get-value ,(- i 2))
                           (get-value ,(- i 1)))))))
  (get-value (- n 1)))

现在，我不想在fib中调用eval，所以我在这里引入宏:

(defvar *fibs* (make-hash-table))

(defun get-value (idx)
  (if (functionp (gethash idx *fibs*))
    (setf (gethash idx *fibs*)
      (funcall (gethash idx *fibs*)))
    (gethash idx *fibs*)))

(defmacro code-for (idx)
  `(lambda () (+ (get-value ,(- idx 2))
                 (get-value ,(- idx 1)))))

(defun fib (n)
  (loop for i from 0 below n
    if (< i 2) do (setf (gethash i *fibs*) 1)
    else do (setf (gethash i *fibs*) (code-for i)))
  (get-value (- n 1)))

但是它说:

; in: DEFUN FIB
;     (CODE-FOR I)
; 
; caught ERROR:
;   during macroexpansion of (CODE-FOR I). Use *BREAK-ON-SIGNALS* to intercept.
;   
;    Argument X is not a NUMBER: I
; 
; compilation unit finished
;   caught 1 ERROR condition

很奇怪:我在代码中没有参数X，而I总是作为整数使用。

经过研究，我发现在一个宏loop中有code-for的宏展开，code-for收到了i 作为符号 (?) 而不是数字，这就是提示。尽管如此，我仍然不知道为什么代码是错误的，或者如何改进它。

编辑 12.04.2018。

正如 tfb 所指出的，解决问题的最佳方法取决于问题是什么。整个问题是向学生解释什么是惰性评估，如何在 Lisp 中完成它以及为什么它可能是必要的。斐波那契数列不是本例的主要目标。

coredump 显示了问题的根本原因(宏扩展)及其解决方案(对 i 的额外绑定(bind))。不幸的是，由于过多的额外解释，这使得所有代码都不适合展示。所以我最终通过递归更改 loop :

(defvar *fibs* (make-hash-table))

(defun get-value (idx)
  (if (functionp (gethash idx *fibs*))
    (setf (gethash idx *fibs*)
      (funcall (gethash idx *fibs*)))
    (gethash idx *fibs*)))

(defun fib (n &optional (i (- n 1)))
  (if (< i 2) (setf (gethash i *fibs*) 1)
    (setf (gethash i *fibs*)
      (lambda () (+ (get-value (- i 2))
                    (get-value (- i 1))))))
  (if (zerop i) (get-value (- n 1))
    (fib n (- i 1))))

Answer 1

[注意 coredump 的回答解释了你的宏有什么问题:我关注的是函数的问题以及解决问题的更好方法。]

我不确定你为什么认为你需要 EVAL 或宏:你可以用 LAMBDA 做一个函数。这是您的代码的一个版本:

(defvar *fibs* (make-hash-table))

(defun get-value (idx &optional (default nil))
  ;; return the value and whether it was there.  If it's a function,
  ;; call it and stash the result
  (multiple-value-bind (got presentp)
      (gethash idx *fibs* default)
    (values
     (typecase got
       (function (setf (gethash idx *fibs*)
                       (funcall got)))
       (t got))
     presentp)))

(defun fib (n)
  (loop for i from 0 below n
        if (< i 2) do (setf (gethash i *fibs*) 1)
        else do (setf (gethash i *fibs*)
                      (let ((i i))
                        ;; rebind I as we don't want to depend on whatever
                        ;; LOOP does, which probably is mutate a single
                        ;; binding of I
                        (lambda () (+ (get-value (- i 2))
                                      (get-value (- i 1)))))))
  ;; just return the first value as we know the second will be T, and
  ;; it's not interesting
  (values (get-value (- n 1))))

但这是一个相当糟糕的方法。相反，您可以只使用如下所示的显式内存函数:

(defun fibonacci (n)
  ;; an explicitly-memoized version of the Fibonacci function
  (let ((memo (make-hash-table :test #'eql)))
    (labels ((fib (m)
               (cond
                ((< m 1)
                 (error "defined on naturals (excluding 0)"))
                ((< m 3)
                 1)
                (t
                 (multiple-value-bind (v p) (gethash m memo)
                   (if p
                       v
                     (setf (gethash m memo) (+ (fib (- m 1))
                                                (fib (- m 2))))))))))
      (fib n))))

更好的是，定义一个宏让你记住任何函数:有一些包可以让你这样做，虽然我不确定它们是什么(一个是我的，但我不确定是否有不是更好的，或者实际上是现在找到我的合适的地方!)