如何在lisp中制作引用结构插槽的符号？

Question

我是自学lisp，并认为一个不错的非平凡的程序将是写一套标准的树插入和操作例程。我想这可以用缺点来解决，但我想用一个结构来尝试。

我整理了一个有效的版本：

(defstruct treenode data left right)

(defun tree-insert ( value tree )
"Insert data into tree"
(if tree
  (if (< value (treenode-data tree))
       (setf (treenode-left tree) (tree-insert value (treenode-left tree)))
       (setf (treenode-right tree) (tree-insert value (treenode-right tree))))
  (setf tree (make-treenode :data value)))
tree)

每一步都要重建这棵树，这看起来计算效率很低。低效率，我的意思是，我必须使用setf每次我做另一个级别的递归。因此，我想尝试一个通过引用而不是通过值传递树的方案，这样我就可以在插入到树中的子例程中进行分配。

我把以下几点拼凑在一起，这是行不通的(但请相信我有意见)：

(defstruct treenode data left right)

(defun tree-insert ( value tree )
"Insert data value into tree, using pass by reference.

value  A datum to insert, in this version has to be a number.
tree   The tree passed as a symbol."  

(setq tval (symbol-value tree))
(if (eq tval nil)
  (set tree (make-treenode :data value))          ; Empty tree. Place data here.
  (if (< value (treenode-data tval))              ; Non-empty node.  Decide which subtree for insert.
      (tree-insert value (treenode-left tval))    ; Left side
      (tree-insert value (treenode-right tval)))) ; Right side.  This is a stable sort.   
nil)

? (setf tr nil)
NIL
? (tree-insert 10 'tr)
NIL
? tr
#S(TREENODE :DATA 10 :LEFT NIL :RIGHT NIL)
? 

初始插入很好。传递一个符号(设置树.)正确地插入左、右端口零的结构。

当然，接下来的问题是，在递归调用树-insert时，我没有传递符号。

那是挂断。我还没有找到一种方法来将一个结构槽作为一个符号，然后我可以传递给树插入。

几天来，我一直在寻找这个关于defstruct宏的有趣评论："defstruct不仅为每个插槽定义了一个访问函数，而且还安排了setf正确地处理这些访问函数，定义了一个名为name-p的谓词，定义了一个名为make-name的构造函数，并定义了一个名为copy的复印机函数。在处理defstruct表单时，所有自动创建函数的名称都被嵌入在当前的任何包中(参见包)。此外，所有这些函数都可以在实现中酌情声明，以提高效率；如果不希望某些函数在内联中声明，请按照defstruct表单使用notinline声明覆盖任何自动内联声明。“

那么，我能做什么来做setf所做的魔法呢？我知道我可以用setf给插槽做作业，但由于词法范围规则，我还没有让setf在函数中工作。也许像添加自动函数来允许符号生成，比如(treenode-数据-符号tr)？

当然，lisp程序员在我的第一个PDP-8/L之前就开始处理二叉树了，那么lisp的方法是什么呢？

这是一个经过编辑的问题。用户Rainer给出了一个非常迅速和简洁的答复。我从他给出的例子中学到了很多。我感兴趣的是直接修改树的问题，而不是使用函数的返回值。

从我在这里看到的评论，以及Rainer Joswig的一个答案，我是否应该得出这样的结论:指针操作的计算成本很低，最好的lisp方法是使用返回树的函数，而不是依赖修改参数的方法？

Answer 1

感谢Rainer和Will，我现在更好地理解了Common。关于没有一流指针的问题是很重要的。我不再需要继续寻找它了，尽管我确实看到了一个包，它在我的搜索中实现了推荐。

我的方法中的关键问题是，我将一个空树定义为零。由于传递nil不允许对参数进行任何操作，所以nil是不可变的，因此该算法必然会失败。

将空树重新定义为'(nil)允许程序工作。

;; Make list of 5 random numbers.
(setf r5 (loop for i from 1 to 5 collect (random 100)))

;; Initialize tr to empty tree.
;; Empty tree is '(nil). Tree with data is '(data left right),
;; where left and right are either empty tree or tree with data.
(setf tr '(nil))

(defun tree-insert ( value tree )
  "Insert data into tree. tree is modified with an insertion."
  (if (equal tree '(nil))
      (progn                ; Empty (sub)tree.  Insert value.
        (setf (car tree) value)
        (setf (cdr tree) (list (list nil)(list nil))))
      (progn                ; Non-empty subtree.
        (if (< value (car tree))
              (tree-insert value (second tree))    ; Insert on left.
              (tree-insert value (third tree)))))  ; Insert on right.
  nil)

;; Load tree with the list of random numbers defined above.
(mapc (lambda (val) (tree-insert val tr)) r5)

(defun tree-walk (tree)
"Retrieve keys in sorted order."
  (if (car tree) 
      (progn
        (tree-walk (second tree))     ; Left subtree.
        (format t " ~d" (car tree))
        (tree-walk (third tree)))))   ; Right subtree.

;; Walk the tree.
(tree-walk tr)

正在使用的例子：

? (setf r5 (loop for i from 1 to 5 collect (random 100)))
(22 50 76 20 49)
? (setf tr '(nil))
(NIL)
? (mapc (lambda (val) (tree-insert val tr)) r5)
;Compiler warnings :
;   In an anonymous lambda form at position 37: Undeclared free variable TR
(22 50 76 20 49)
? tr
(22 (20 (NIL) (NIL)) (50 (49 (NIL) (NIL)) (76 (NIL) (NIL))))
? (tree-walk tr)
 20 22 49 50 76
NIL
? 

所以，有几件事可以让这件事发挥作用。可变对象必须传递给过程。在这种情况下，我重新设计了一个列表，要么'(nil)表示空，要么‘(数据左向右)，其中左和右都是'(nil)或’(数据左向右)。包含零的列表可以被操纵。但是，我必须使用car和cdr来访问结构，以便保存传递给过程的Lisp指针。

我必须做的另一件事是在函子定义中不使用列表常量。我相信知识渊博的人会对此有所了解，并对随后出现的不透明错误提出一点意见，直到问题被理解为止，但如果我在树中使用了‘((Nil)(Nil)而不是(list (list nil)(list nil)) --插入它是行不通的。看起来，Lisp将列表简写符号编译为指向内存中的一个对象的指针，该指针用于函数的所有后续调用。

噢，树插入中有一个剩余的progn函数调用。这是从我用progn包装所有内容时开始的，它允许我在调试期间添加print语句。

在这些函数上运行计时非常有趣。太快了！我将运行一些时间比较，以比较功能重新分配方法与搜索和插入算法。

再次感谢专家的评论。自上一次发表文章以来，我已经了解了一些有关map、循环/收集的知识，以及在函数定义中不使用let时，函数中的变量会泄漏到全局空间中。同时也用大量的输出包装函数。在使用大数据结构后，节省屏幕空间。通过这个练习，我学到了很多东西。

Answer 2

为您的灵感提供简单版本：

(defstruct node a b v)

(defun insert-tree (tree value)
  (cond ((null tree)
         (setf tree (make-node :v value)))
        ((> (node-v tree)
            value)
         (setf (node-a tree)
               (insert-tree (node-a tree) value)))
        (t
         (setf (node-b tree)
               (insert-tree (node-b tree) value))))
  tree)

使用它：

CL-USER 171 > (let ((tree nil))
                (loop for i in '(4 7 3 5 9 10 11 8)
                      do (setf tree (insert-tree tree i)))
                (pprint tree)
                (values))

#S(NODE :A #S(NODE :A NIL :B NIL :V 3)
        :B #S(NODE :A #S(NODE :A NIL :B NIL :V 5)
                   :B #S(NODE :A #S(NODE :A NIL :B NIL :V 8)
                              :B #S(NODE :A NIL
                                         :B #S(NODE :A NIL
                                                    :B NIL
                                                    :V 11)
                                         :V 10)
                              :V 9)
                   :V 7)
        :V 4)

现在，如果希望执行较少的setf操作，则可以检查返回的子树是否与我们传递的相同。只有在我们创建一个新节点时才会出现这种情况。

(defun insert-tree (tree value)
  (cond ((null tree)
         (setf tree (make-node :v value)))
        ((> (node-v tree)
            value)
         (let ((new-tree (insert-tree (node-a tree) value)))
           (unless (eql new-tree (node-a tree))
             (setf (node-a tree) new-tree))))
        (t
         (setf (node-b tree)
               (insert-tree (node-b tree) value))))
  tree)

或者使用本地宏隐藏代码的一部分：

(defun insert-tree (tree value)
  (macrolet ((insert (place call &aux (new-value-sym (gensym "new-value")))
               `(let ((,new-value-sym ,call))
                  (unless (eql ,place ,new-value-sym)
                    (setf ,place ,new-value-sym)))))
    (cond ((null tree)
           (setf tree (make-node :v value)))
          ((> (node-v tree)
              value)
           (insert (node-a tree) (insert-tree (node-a tree) value)))
          (t
           (insert (node-b tree) (insert-tree (node-b tree) value))))
    tree))

Answer 3

试图从另一个角度添加一个答案。

在标准的Common结构中，有许多限制使得它们的使用效率很低。在这些限制中：

• 未定义通过槽名访问结构槽的权限。有些实现是这样做的，另一些则不这样做。
• 重新定义结构定义会产生未定义的后果。这意味着在某些情况下，最好重新启动Lisp .

背后的想法是:对结构的所有操作都应该能够内联，并且一个正在执行的程序不需要任何关于结构槽(它们的名称、内存位置、.)的进一步信息。运行时将不进行动态查找。

那么，在一般情况下，Common还有进一步的限制:它没有第一类指针。没有提供指针的机制，只能直接指向结构的槽。在一些较老的Lisp方言中，这可能是通过使用这些语言中的本地词-指针的概念来实现的。通用Lisp不支持这一点。

这实际上意味着:要更新结构的插槽，需要访问结构和setter操作。

如何更新结构的插槽？

我可以想到两种简单的方法：

• 传递结构、新值和指示符，然后更新->，然后在指示器上分派，并调用右更新程序

示例

(defun update (s indicator value)
  (case indicator
    (:a (setf (node-a s) value))
    (:b (setf (node-b s) value))))

(update tree :a (make-node :v 100))

• 传递一个闭包，该闭包执行更新

示例：

(let ((tree ...))
  (flet ((do-something (updater)
           (funcall updater (make-node :v 100))))
    (do-something (lambda (value) (setf (node-a tree) value) ...)))