当flet在递归函数中时会发生什么？

Question

我一直在尝试实现NFA，下面的代码是导出所有当前状态的epsilon闭包。我想用递归的方式来实现它，因为epsilon闭包的定义是递归的。在当前的实现中，使用flet在主函数中定义了一个助手函数，而且每次递归时，助手函数似乎都是独立定义的。我的理解正确吗？如果是这样的话，在不多次定义相同的东西的情况下，实现这段代码的最简洁的方法是什么？

(defun eps-closure (states transition-rule)
  (flet ((trace-eps-onestep (states transition-rule)
           (remove-duplicates
            (flatten
             (append
              states
              (mapcar
               (lambda (state) (transition-state state :eps transition-rule))
               states))))))
    (let ((next (trace-eps-onestep states transition-rule)))
      (if (set-difference next states)
          (eps-closure next transition-rule)
          next))))

Answer 1

在我看来没问题。这是一个典型的局部词法函数。

似乎每次递归时助手函数都是独立定义的。

这在编译后的代码中并不重要，函数也不会被重新定义。没有创建函数对象，也没有对符号进行赋值。编译器甚至可能决定将其内联。

解释代码(通过对s-表达式使用解释器)可能会在每次迭代中执行FLET语句，但是对于编译过的代码，这并不重要，因为编译通常是提前一次完成的。

为了使代码与函数更加模块化，有几种方法：

• 就像在您的示例中一样，定义了一个本地函数。我甚至会保留这些参数，即使它们在词法范围内可以被省略。也可以声明为内联本地函数。保持参数使代码重构更简单，并通过使参数显式化来记录函数的参数。

• 将其定义为全局函数，并在稍后的调用中向其提供所有参数。这些函数通常被命名为助手函数，如%trace-eps-onestep (使用%作为不应该直接调用的全局函数的前缀)或类似的函数。有时，这是首选的，因为它使独立跟踪助手函数更容易。但是有些实现也可以跟踪本地函数individually.

。

全局FLET:避免

在DEFUN周围使用FLET并不好，因为它使DEFUN形成非顶层，并阻止文件编译器在文件编译期间可移植地识别它为全局函数定义。

使用SBCL编译器的示例

* (defun add42 (n)
    (flet ((do-it (n)
             (+ n 42)))
      (let ((x (do-it n)))
        (if (> x 100)
            :i-dont-do-it
            x))))

* (disassemble #'add42)
; disassembly for ADD42
; Size: 68 bytes. Origin: #x22661D81                          ; ADD42
; 81:       498B4510         MOV RAX, [R13+16]                ; thread.binding-stack-pointer
; 85:       488945F8         MOV [RBP-8], RAX
; 89:       488B55F0         MOV RDX, [RBP-16]
; 8D:       BF54000000       MOV EDI, 84
; 92:       FF1425C000B021   CALL QWORD PTR [#x21B000C0]      ; GENERIC-+
; 99:       488BC2           MOV RAX, RDX
; 9C:       488945E8         MOV [RBP-24], RAX
; A0:       BFC8000000       MOV EDI, 200
; A5:       FF1425E800B021   CALL QWORD PTR [#x21B000E8]      ; GENERIC->
; AC:       488B45E8         MOV RAX, [RBP-24]
; B0:       488BD0           MOV RDX, RAX
; B3:       41BB0FC04E20     MOV R11D, #x204EC00F             ; :I-DONT-DO-IT
; B9:       490F4FD3         CMOVNLE RDX, R11
; BD:       488BE5           MOV RSP, RBP
; C0:       F8               CLC
; C1:       5D               POP RBP
; C2:       C3               RET
; C3:       CC10             INT3 16                          ; Invalid argument count trap
NIL

正如您从生成的x86-64机器代码中可以看到的那样，不需要重新定义。

Answer 2

这样做的一个相当明显的方法是在您想要的任何本地定义的函数中定义尾递归循环：

(defun eps-closure (initial-states transition-rule)
  (flet ((trace-eps-onestep (states)
           (remove-duplicates
            (flatten
             (append
              states
              (mapcar
               (lambda (state) (transition-state state :eps transition-rule))
               states))))))
    (labels ((eps-closure-loop (states)
               (let ((next (trace-eps-onestep states)))
                 (if (set-difference next states)
                     (eps-closure-loop states)
                   next))))
      (eps-closure-loop initial-states))))

现在完全清楚的是，trace-eps-onestep只有一个定义。请注意，我还利用这个机会从所有调用中删除了第二个参数，因为它始终是同一个对象，因此我重新命名了参数，我希望这样做更有意义。

我喜欢这种it技巧，因为它意味着从代码中可以完全清楚地看到它们是辅助函数，只供全局函数使用。

在这种情况下，trace-eps-onestep完全是从一个地方调用的，实际上根本就没有存在的理由。一个好的编译器可能会彻底地优化它，但是我认为以下代码在任何情况下都更清晰：

(defun eps-closure (initial-states transition-rule)
  (labels ((eps-closure-loop (states)
             (let ((next (remove-duplicates
                          (flatten
                           (append
                            states
                            (mapcar
                             (lambda (state)
                               (transition-state state :eps transition-rule))
                             states))))))
               (if (set-difference next states)
                   (eps-closure-loop next)
                 next))))
    (eps-closure-loop initial-states)))

最后，这种尾递归局部函数在CL中并不是很自然的(尽管我经常这样编程！)：下面这样的内容可以说更清楚，我认为：

(defun eps-closure (initial-states transition-rule)
  (loop for states = initial-states then next
        for next = (remove-duplicates
                    (flatten
                     (append
                      states
                      (mapcar
                       (lambda (state)
                         (transition-state state :eps transition-rule))
                       states))))
        if (null (set-difference next states))
        return next))

我没有测试任何这些函数(它们都是编译的，但是缺少定义)。

Answer 3

您可以将FLET放在DEFUN周围，因此它不会在全局范围内。

(flet ((trace-eps-onestep (states transition-rule)
          (remove-duplicates
           (flatten
            (append
             states
             (mapcar
              (lambda (state) (transition-state state :eps transition-rule))
              states))))))
  (defun eps-closure (states transition-rule)
    (let ((next (trace-eps-onestep states transition-rule)))
      (if (set-difference next states)
          (eps-closure next transition-rule)
        next))))

或者您可以在本地定义它，就像在原始代码中一样。不需要将参数传递给它，因为本地函数可以访问所有局部变量。在这种情况下，对每个递归重新定义它是合理的，因为变量是不同的。

(defun eps-closure (states transition-rule)
  (flet ((trace-eps-onestep ()
           (remove-duplicates
            (flatten
             (append
              states
              (mapcar
               (lambda (state) (transition-state state :eps transition-rule))
               states))))))
    (let ((next (trace-eps-onestep)))
      (if (set-difference next states)
          (eps-closure next transition-rule)
          next))))