调用局部声明函数

Question

下面是来自Lisp的Lisp的一段代码(第138页或此处：http://landoflisp.com/wumpus.lisp)：

(defun get-connected (node edge-list)
 (let ((visited nil))
    (labels ((traverse (node)
                (unless (member node visited)
                  (push node visited)
                  (mapc (lambda (edge)
                          (traverse (cdr edge)))
                        (direct-edges node edge-list)))))
      (traverse node))
   visited))

作为新手，我想知道第9行的(遍历节点)是否是在“包装器”函数中调用这个“本地”定义的函数的地方也就是说，当调用get-connected时，它会“构造”遍历(第3-8行)，然后在第9行调用/使用它。此外，访问的局部变量似乎被遍历E 215填充了push命令，然后留在E 116letE 217块的后门，我猜这是一个“返回值”？当然，这必须是某种形式的返回值，"live“，并可用于调用函数；否则，整个get-connected函数就没有意义了！

对我来说，Lisp/functional，这一切看起来都很奇怪。这是我听说过的那些封闭野兽之一吗？如果是这样/不是，我通过这样一个奇怪的构造函数得到了什么？我理解它所做的--它从一个图顶点开始，遍历尽可能多的边，尽可能记住顶点--但是(除了很好的递归)，这是典型的Lisp/函数策略吗？

顺便说一句，下面是一个边缘列表的例子

*test-edges* = ((2 . 8) (8 . 2) (4 . 5) (5 . 4) (6 . 2) (2 . 6) (3 . 10) (10 . 3) (7 . 5) 
(5 . 7) (7 . 10) (10 . 7) (4 . 5) (5 . 4) (9 . 3) (3 . 9) (3 . 5) (5 . 3)
(3 . 1) (1 . 3) (5 . 8) (8 . 5) (8 . 9) (9 . 8) (5 . 2) (2 . 5) (1 . 2)
(2 . 1))

节点只是其中之一，这里是介于1到10之间的整数。下面是一些输出：

CL-USER> (get-connected 1 *test-edges*)
(9 6 2 8 4 5 7 10 3 1)

Answer 1

让我们改进缩进：

(defun get-connected (node edge-list)
  (let ((visited nil))
    (labels ((traverse (node)
               (unless (member node visited)
                 (push node visited)
                 (mapc (lambda (edge)
                         (traverse (cdr edge)))
                       (direct-edges node edge-list)))))
      (traverse node))
    visited))

这个函数的构造并不奇怪。它基本上是一个函数，它设置一些变量，定义一个本地自递归函数，然后调用一个本地函数一次。

闭包怎么办？闭包是带有环境的函数对象。我们构造函数对象的唯一地方是在带有lambda的MAPC表单中。否则，不创建和传递/返回函数对象。传递给MAPC的函数对象，第一个参数是闭包。

我们也可以把它写成两个全局函数。局部函数方法的优点是：

• 本地函数名并不是全局已知的。因为我们只在当地使用它，所以没有真正的必要使它成为全球性的。
• 我们不需要将所有信息传递给本地函数。它可以访问周围的变量。
• 我们可以有一个共享的词法变量，用于收集结果。

我们可以把它写成两个全局函数。看起来可能是这样的：

现在，遍历是一个全局函数，我们需要扩展边框列表和访问节点列表的参数列表(到目前为止)。我们还需要构造一个返回值:已访问的节点。

(defun traverse (node edge-list visited)
  (if (member node visited)
      visited
    (progn
      (mapc (lambda (edge)
              (setf visited (traverse (cdr edge) edge-list (cons node visited))))
            (direct-edges node edge-list))
      (cons node (remove node visited)))))

然后，您在函数式编程中看到的一个典型模式也将MAPC替换为某种形式的递归。

这是我们的新的全局功能：

(defun get-connected-1 (node edge-list)
  (traverse node edge-list nil))

它传递变量并添加访问节点的空列表。

回到原来的功能：

(defun get-connected (node edge-list)
  (let ((visited nil))    ; a shared local variable
    (labels ((traverse (node)    ; a local self-recursive function
               (unless (member node visited)
                 (push node visited)   ; update the shared local variable
                 (mapc (lambda (edge)  ; loop over the direct edges
                         (traverse (cdr edge)))  ; traverse the connected
                       (direct-edges node edge-list)))))
      (traverse node))  ; call the local function from get-connected
    visited))           ; get-connected returns this as the return value

上面的局部遍历函数有什么不好呢？它会在某些较大的图上造成堆栈溢出。需要将其重写为尾递归变体。

我们还可以消除本地函数，自行管理已访问和尚未访问的节点列表：

(defun get-connected-2 (start-node edge-list)
  (let ((visited nil)
        (nodes-to-visit (list start-node)))
    (loop for node = (pop nodes-to-visit)
          while node do
          (unless (member node visited)
            (push node visited)
            (loop for (nil . to) in (direct-edges node edge-list)
                  do (pushnew to nodes-to-visit))))
    visited))