当 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

您可以将 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))))

Answer 2

对我来说，这看起来不错。这是一个典型的局部词法函数。

it seems that every time of the recursion a helper function is independently defined

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

解释代码（通过对 s 表达式使用解释器）在每次迭代中执行 FLET 语句时可能会有一些开销，但对于编译代码来说这无关紧要，因为编译通常只进行一次提前.

为了让代码更加模块化，有一些方法：

就像你的例子一样，定义一个局部函数。我什至会保留参数，即使它们在词法范围内时可以省略。可选择声明内联局部函数。保留参数使代码重构更简单，并通过使参数显式化来记录函数的参数。
将其定义为全局函数，并在稍后的调用中将所有参数提供给它。这些函数通常被命名为辅助函数，例如 %trace-eps-onestep（使用 % 作为不应直接调用的全局函数的前缀）或类似函数。有时这是首选，因为它可以更轻松地独立跟踪辅助函数。但是一些实现也可以单独跟踪局部函数。

全局 FLET：避免

让 FLET 绕过 DEFUN 并不是很好，因为它使 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 3

执行此类操作的一种相当明显的方法是在您想要的任何本地定义的函数中定义尾递归循环：

(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只有一个定义了。请注意，我还借此机会从所有调用中删除了第二个参数，因为它始终是同一个对象，并且我已将参数重命名为使我希望更有意义。

我喜欢这种内部带有一堆局部函数的大全局定义技巧，因为这意味着通过阅读代码可以完全清楚它们只是辅助函数供全局函数使用。

在这种特殊情况下，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))

我没有测试过这些函数中的任何一个（它们都可以编译，但是缺少定义）。

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

What happens when flet is inside a recursive function?

recursion

common-lisp