当 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（%用作不应直接调用的全局函数的前缀）或类似的。有时这是首选，因为它使独立跟踪辅助函数更容易。但是一些实现也可以单独跟踪本地函数。

全局 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 机器代码中看到的那样，没有进行重新定义。