lisp - gensym 在 Lisp 中做了什么？

Question

上下文化：我一直在做一个大学项目，我必须为正则表达式编写一个解析器并构建相应的 epsilon-NFA。我必须在 Prolog 和 Lisp 中这样做。我不知道这样的问题是否允许，如果不允许，我道歉。

我听到我的一些同学谈论他们如何使用功能 gensym ，我问他们它做了什么，甚至在网上查了一下，但我真的不明白这个功能做什么，为什么或者什么时候最好使用它。

特别是，我对它在 Lisp 中的作用更感兴趣。谢谢你们。

Answer 1

GENSYM创建独特的符号。每次调用都会创建一个新符号。该符号通常有一个名称，其中包含一个数字，该数字是向上计数的。该名称也是唯一的（符号本身已经是唯一的）带有一个数字，以便人类读者可以识别源代码中不同的非实习符号。

CL-USER 39 > (gensym)
#:G1083

CL-USER 40 > (gensym)
#:G1084

CL-USER 41 > (gensym)
#:G1085

CL-USER 42 > (gensym)
#:G1086

gensym通常在 Lisp 宏中用于代码生成，当宏需要创建新的标识符时，它不会与现有的标识符发生冲突。

示例：我们要将 Lisp 表单的结果加倍，并确保 Lisp 表单本身只计算一次。我们通过将值保存在局部变量中来做到这一点。局部变量的标识符将由 计算gensym。

CL-USER 43 > (defmacro double-it (it)
               (let ((new-identifier (gensym)))
                 `(let ((,new-identifier ,it))
                    (+ ,new-identifier ,new-identifier))))
DOUBLE-IT

CL-USER 44 > (macroexpand-1 '(double-it (cos 1.4)))
(LET ((#:G1091 (COS 1.4)))
  (+ #:G1091 #:G1091))
T

CL-USER 45 > (double-it (cos 1.4))
0.33993432

Answer 2

对现有答案的一点澄清（因为操作员还不知道典型的常见 lisp 宏工作流程）：

double-it考虑由先生提出的宏。约斯维格。为什么我们要费心创造这一大堆let？什么时候可以很简单：

(defmacro double-it (it)
  `(+ ,it ,it))

好的，它似乎正在工作：

CL-USER> (double-it 1)
;;=> 2

但是看看这个，我们想要增加x和加倍它

CL-USER> (let ((x 1))
           (double-it (incf x)))
;;=> 5 
;; WHAT? it should be 4!

原因可以从宏扩展中看出：

(let ((x 1))
  (+ (setq x (+ 1 x)) (setq x (+ 1 x))))

您会看到，由于宏不评估表单，只是将其拼接到生成的代码中，因此会导致incf执行两次。

简单的解决方案是将它绑定到某个地方，然后将结果加倍：

(defmacro double-it (it)
  `(let ((x ,it))
     (+ x x)))

CL-USER> (let ((x 1))
           (double-it (incf x)))
;;=> 4
;; NICE!

现在似乎没问题。它真的像这样扩展：

(let ((x 1))
  (let ((x (setq x (+ 1 x))))
    (+ x x)))

好的，那gensym事情呢？

假设您想打印一些消息，然后将您的值加倍：

(defmacro double-it (it)
  `(let* ((v "DOUBLING IT")
          (val ,it))
     (princ v)
     (+ val val)))

CL-USER> (let ((x 1))
           (double-it (incf x)))
;;=> DOUBLING IT
;;=> 4
;; still ok!

但是如果你不小心命名了 valuev而不是x：

CL-USER> (let ((v 1))
           (double-it (incf v)))

;;Value of V in (+ 1 V) is "DOUBLING IT", not a NUMBER.
;; [Condition of type SIMPLE-TYPE-ERROR]

它抛出了这个奇怪的错误！看看扩展：

(let ((v 1))
  (let* ((v "DOUBLING IT") (val (setq v (+ 1 v))))
    (princ v)
    (+ val val)))

它v用字符串从外部范围遮蔽，当您尝试添加 1 时，它显然不能。太糟糕了。

另一个例子，假设你想调用函数两次，并以列表的形式返回 2 个结果：

(defmacro two-funcalls (f v)
  `(let ((x ,f))
     (list (funcall x ,v) (funcall x ,v))))

CL-USER> (let ((y 10))
           (two-funcalls (lambda (z) z) y))
;;=> (10 10)
;; OK

CL-USER> (let ((x 10))
           (two-funcalls (lambda (z) z) x))

;; (#<FUNCTION (LAMBDA (Z)) {52D2D4AB}> #<FUNCTION (LAMBDA (Z)) {52D2D4AB}>)
;; NOT OK!

这类错误非常令人讨厌，因为你不能轻易说出发生了什么。解决办法是什么？显然不要命名v宏内部的值。您需要生成一些没有人会在他们的代码中复制的复杂名称，例如my-super-unique-value-identifier-2019-12-27. 这可能会拯救你，但你仍然不能确定。这就是 gensym 存在的原因：

(defmacro two-funcalls (f v)
  (let ((fname (gensym)))
    `(let ((,fname ,f))
       (list (funcall ,fname ,v) (funcall ,fname ,v)))))

扩展到：

(let ((y 10))
  (let ((#:g654 (lambda (z) z)))
    (list (funcall #:g654 y) (funcall #:g654 y))))

您只需为生成的代码生成 var 名称，它保证是唯一的（这意味着没有两个gensym调用会为运行时会话生成相同的名称），

(loop repeat 3 collect (gensym))
;;=> (#:G645 #:G646 #:G647)

它仍然可能以某种方式与用户 var 发生冲突，但是每个人都知道命名并且不调用 var #:GXXXX，因此您可以认为这是不可能的。您可以进一步保护它，添加前缀

(loop repeat 3 collect (gensym "MY_GUID"))
;;=> (#:MY_GUID651 #:MY_GUID652 #:MY_GUID653)

Answer 3

GENSYM 将在每次调用时生成一个新符号。可以保证，该符号在生成之前不存在，并且永远不会再次生成。如果您愿意，可以指定符号前缀：

CL-USER> (gensym)
#:G736
CL-USER> (gensym "SOMETHING")
#:SOMETHING737

GENSYM 最常见的用途是为项目生成名称以避免宏扩展中的名称冲突。

另一个常见的目的是生成用于构建图形的符号，如果您唯一的需求是将属性列表附加到它们，而节点的名称并不重要。

我认为，生成 NFA 的任务可以很好地利用第二个目的。

Answer 4

这是对其他一些答案的注释，我认为这很好。虽然gensym是制作新符号的传统方法，但实际上还有另一种方法效果很好，而且我发现通常更好make-symbol：：

make-symbol创建并返回一个新的、非内部的符号，其名称是给定的名称。new-symbol 既不是 bound 也不是 fbound 并且有一个 null 属性列表。

所以，它的好处是它用你要求的名称make-symbol制作了一个符号，确切地说，没有任何奇怪的数字后缀。这在编写宏时很有帮助，因为它使宏扩展更具可读性。考虑这个简单的列表集合宏：

(defmacro collecting (&body forms)
  (let ((resultsn (make-symbol "RESULTS"))
        (rtailn (make-symbol "RTAIL")))
    `(let ((,resultsn '())
           (,rtailn nil))
       (flet ((collect (it)
                (let ((new (list it)))
                  (if (null ,rtailn)
                      (setf ,resultsn new
                            ,rtailn new)
                    (setf (cdr ,rtailn) new
                          ,rtailn new)))
                it))
         ,@forms
         ,resultsn))))

这需要两个body 不能引用的绑定，用于结果，以及结果的最后一个缺点。它还以一种故意“不卫生”的方式引入了一个功能： inside collecting，collect意思是“收集一些东西”。

所以现在

> (collecting (collect 1) (collect 2) 3)
(1 2)

如我们所愿，我们可以查看宏扩展以了解引入的绑定具有某种意义的名称：

> (macroexpand '(collecting (collect 1)))
(let ((#:results 'nil) (#:rtail nil))
  (flet ((collect (it)
           (let ((new (list it)))
             (if (null #:rtail)
                 (setf #:results new #:rtail new)
               (setf (cdr #:rtail) new #:rtail new)))
           it))
    (collect 1)
    #:results))
t

我们可以说服 Lisp 打印机告诉我们，实际上所有这些非驻留符号都是相同的：

> (let ((*print-circle* t))
    (pprint (macroexpand '(collecting (collect 1)))))

(let ((#2=#:results 'nil) (#1=#:rtail nil))
  (flet ((collect (it)
           (let ((new (list it)))
             (if (null #1#)
                 (setf #2# new #1# new)
               (setf (cdr #1#) new #1# new)))
           it))
    (collect 1)
    #2#))

因此，对于编写宏，我通常发现make-symbol比gensym. 对于编写我只需要一个符号作为对象的东西，例如在某种结构中命名一个节点，那么gensym可能更有用。最后请注意，gensym可以通过以下方式实现make-symbol：

(defun my-gensym (&optional (thing "G"))
  ;; I think this is GENSYM
  (check-type thing (or string (integer 0)))
  (let ((prefix (typecase thing
                  (string thing)
                  (t "G")))
        (count (typecase thing
                 ((integer 0) thing)
                 (t (prog1 *gensym-counter*
                      (incf *gensym-counter*))))))
        (make-symbol (format nil "~A~D" prefix count))))

（这可能是错误的。）