如何在 lisp 中制作引用结构槽的符号？
How does one make symbols that refer to structure slots in lisp?
我正在自学 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)
?
初始插入工作正常。传递一个符号 the (set tree ...) 正确地插入结构，左右指针为 nil。
当然，接下来的问题是在对树插入的递归调用中我没有传递符号。
那就是挂断。我还没有找到将结构槽作为符号引用的方法，然后我可以将其传递给树插入。
我已经四处寻找了几天，发现了关于 defstruct 宏的有趣评论："defstruct not only defines an access function for each slot, but also arranges for setf to work properly on such access functions, defines a predicate named name-p, defines a constructor function named make-name, and defines a copier function named copy-name. All names of automatically created functions are interned in whatever package is current at the time the defstruct form is processed (see package). Also, all such functions may be declared inline at the discretion of the implementation to improve efficiency; if you do not want some function declared inline, follow the defstruct form with a notinline declaration to override any automatic inline declaration."
那么，我该怎么做才能发挥 setf 的魔力呢？我知道我可以使用 setf 对槽进行赋值，但由于词法范围规则，我还没有让 setf 在函数中工作。也许喜欢添加自动功能以允许符号生成，例如 (treenode-data-symbol tr)?
当然，在我第一次 PDP-8/L 之前，lisp 程序员就已经在处理二叉树了。什么是 lispy 方法来做到这一点？
这是一个经过编辑的问题。用户 Rainer Joswig 给出了非常快速和简洁的回复。我从他举的例子中学到了很多东西。我对直接修改树而不是使用函数中的 return 值的问题很感兴趣。
根据我在这里看到的评论和 Rainer Joswig 的一个回答，我是否应该得出这样的结论：指针操作的计算成本很低，而且最好的 lisp 方法是使用一个函数 return是一棵树而不是依赖修改参数的方法？
激发灵感的简单版本：
(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))
尝试从另一个角度添加答案。
在标准的 Common Lisp 结构中有很多限制，使它们低级和高效使用。在这些限制中：
未定义通过插槽名称访问结构插槽。有些实现会这样做，有些则不会。
重新定义结构定义会产生未定义的后果。这意味着在某些情况下，最好重新启动 Lisp 来做到这一点...
其背后的想法：所有对结构的操作都应该能够被内联，并且正在执行的程序不需要任何关于结构槽的更多信息（它们的名称、它们的内存位置，...）。在运行时不会有动态查找。
然后 Common Lisp 通常有进一步的限制：它没有第一个 class 指针。没有提供仅直接指向结构槽的指针的机制。在一些较旧的 Lisp 方言中，这可能通过 locatives 的概念实现——这些语言中的指针。 Common 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) ...)))
非常感谢 Rainer 和 Will，我现在更了解 Common Lisp。没有第一个 class 指针的意义重大。我不必再继续寻找它了，尽管我确实在搜索中看到了一个实现 refs 的包。
我的方法中的关键问题是我将空树定义为 nil。由于传递 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) 表示空，或者'(data left right)，其中 left 和 right 要么是'(nil) 要么是'(data left right)。可以操纵包含 nil 的列表。但是，我不得不使用 car 和 cdr 来访问该结构，以保留传递给过程的 Lisp 指针。
我必须做的另一件事是不在函数定义中使用列表常量。我相信知识渊博的人会知道这一点，并且在理解问题之前会出现一些不透明的错误，但是如果我使用了 '((nil)(nil)) 而不是 (list (list nil)(list nil)) 在 tree-insert 中是行不通的。看起来 Lisp 将 list shorthand 符号编译为指向内存中一个对象的指针，该对象将用于该函数的所有后续调用。
哦，tree-insert中有一个遗留的progn函数调用。那是从我用 prog 包装所有东西让我在调试期间添加打印语句开始的。
运行 函数的时间安排很有趣。它很快！我将 运行 进行一些时序比较，以比较功能重新分配方法与搜索和插入算法。
再次感谢专家的意见。自上次贡献以来，我对 map loop/collect 有了一些了解，并且当函数定义中未使用 let 时，变量会从函数泄漏到全局 space 中。在使用大型数据结构后，使用 (progn ... nil) 包装具有大量输出的函数可以节省屏幕 space。通过这次练习，我学到了很多。
我正在自学 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)
?
初始插入工作正常。传递一个符号 the (set tree ...) 正确地插入结构，左右指针为 nil。
当然，接下来的问题是在对树插入的递归调用中我没有传递符号。
那就是挂断。我还没有找到将结构槽作为符号引用的方法，然后我可以将其传递给树插入。
我已经四处寻找了几天，发现了关于 defstruct 宏的有趣评论："defstruct not only defines an access function for each slot, but also arranges for setf to work properly on such access functions, defines a predicate named name-p, defines a constructor function named make-name, and defines a copier function named copy-name. All names of automatically created functions are interned in whatever package is current at the time the defstruct form is processed (see package). Also, all such functions may be declared inline at the discretion of the implementation to improve efficiency; if you do not want some function declared inline, follow the defstruct form with a notinline declaration to override any automatic inline declaration."
那么，我该怎么做才能发挥 setf 的魔力呢？我知道我可以使用 setf 对槽进行赋值，但由于词法范围规则，我还没有让 setf 在函数中工作。也许喜欢添加自动功能以允许符号生成，例如 (treenode-data-symbol tr)?
当然，在我第一次 PDP-8/L 之前，lisp 程序员就已经在处理二叉树了。什么是 lispy 方法来做到这一点？
这是一个经过编辑的问题。用户 Rainer Joswig 给出了非常快速和简洁的回复。我从他举的例子中学到了很多东西。我对直接修改树而不是使用函数中的 return 值的问题很感兴趣。
根据我在这里看到的评论和 Rainer Joswig 的一个回答，我是否应该得出这样的结论：指针操作的计算成本很低，而且最好的 lisp 方法是使用一个函数 return是一棵树而不是依赖修改参数的方法？
激发灵感的简单版本：
(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))
尝试从另一个角度添加答案。
在标准的 Common Lisp 结构中有很多限制，使它们低级和高效使用。在这些限制中：
未定义通过插槽名称访问结构插槽。有些实现会这样做，有些则不会。
重新定义结构定义会产生未定义的后果。这意味着在某些情况下，最好重新启动 Lisp 来做到这一点...
其背后的想法：所有对结构的操作都应该能够被内联，并且正在执行的程序不需要任何关于结构槽的更多信息（它们的名称、它们的内存位置，...）。在运行时不会有动态查找。
然后 Common Lisp 通常有进一步的限制：它没有第一个 class 指针。没有提供仅直接指向结构槽的指针的机制。在一些较旧的 Lisp 方言中，这可能通过 locatives 的概念实现——这些语言中的指针。 Common 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) ...)))
非常感谢 Rainer 和 Will，我现在更了解 Common Lisp。没有第一个 class 指针的意义重大。我不必再继续寻找它了，尽管我确实在搜索中看到了一个实现 refs 的包。
我的方法中的关键问题是我将空树定义为 nil。由于传递 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) 表示空，或者'(data left right)，其中 left 和 right 要么是'(nil) 要么是'(data left right)。可以操纵包含 nil 的列表。但是，我不得不使用 car 和 cdr 来访问该结构，以保留传递给过程的 Lisp 指针。
我必须做的另一件事是不在函数定义中使用列表常量。我相信知识渊博的人会知道这一点，并且在理解问题之前会出现一些不透明的错误，但是如果我使用了 '((nil)(nil)) 而不是 (list (list nil)(list nil)) 在 tree-insert 中是行不通的。看起来 Lisp 将 list shorthand 符号编译为指向内存中一个对象的指针，该对象将用于该函数的所有后续调用。
哦，tree-insert中有一个遗留的progn函数调用。那是从我用 prog 包装所有东西让我在调试期间添加打印语句开始的。
运行 函数的时间安排很有趣。它很快！我将 运行 进行一些时序比较，以比较功能重新分配方法与搜索和插入算法。
再次感谢专家的意见。自上次贡献以来，我对 map loop/collect 有了一些了解，并且当函数定义中未使用 let 时，变量会从函数泄漏到全局 space 中。在使用大型数据结构后，使用 (progn ... nil) 包装具有大量输出的函数可以节省屏幕 space。通过这次练习，我学到了很多。