时间戳

首页 > 解决方案 > 当 flet 在递归函数中时会发生什么？

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

问题描述

我一直在尝试实现一个 NFA，底部的代码是导出所有当前状态的 epsilon 闭包。我想以递归方式实现它，因为 epsilon 闭包根据定义是递归的。在当前的实现中，在 main 函数中使用 定义了一个辅助函数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))))

标签： recursioncommon-lisp

解决方案

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

似乎每次递归都有一个辅助函数是独立定义的

这在已编译的代码中无关紧要，并且无论如何都不会重新定义该函数。没有创建函数对象，也没有分配给符号。编译器甚至可能决定内联它。

解释的代码（通过对 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 机器代码中可以看出，没有进行重新定义。

推荐阅读