如何使符号引用Lisp中的结构槽？

Question

我自学Lisp，并认为一个不错的简单程序是编写一组标准的树插入和操作例程。我认为可以使用CONS完成此操作，但想尝试使用一种结构。

我整理了一个可行的版本：

(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)
? 

初始插入工作正常。传递符号（（设置树...））正确插入带有左右porinters nil的结构。

当然，接下来的问题是在对树插入的递归调用中，我没有传递符号。

那就是挂断电话。我还没有找到一种将结构插槽作为符号引用的方法，然后可以将其传递给树插入。

我已经逛了几天，发现了有关defstruct宏的有趣评论：“ defstruct不仅为每个插槽定义了一个访问函数，而且还安排setf在此类访问函数上正常工作，定义了一个谓词为name-p，定义一个名为make-name的构造函数，并定义一个名为copy-name的复印机函数，将自动创建的函数的所有名称插入处理defstruct表单时的最新包中（请参见package）。 ，可以在实现时自行决定是否将所有此类函数声明为内联，以提高效率；如果您不希望将某些函数声明为内联，请遵循defstruct形式并使用notinline声明来覆盖任何自动内联声明。”

那么，我该怎么做setf的魔力呢？我知道我可以使用setf对插槽进行赋值，但是由于词法作用域规则，我没有让setf在函数中工作。也许喜欢添加自动功能以允许生成符号，例如（treenode-data-symbol tr）？

当然，自从我第一次使用PDP-8 / L之前，Lisp程序员就开始处理二进制树。什么是狡猾的方式来做到这一点？

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

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

Answer 1

简单的版本，您的灵感来源：

(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))