在Common Lisp中映射数组时,两个缺点指向相同的内存



我有以下功能:

(defun transform-matrix (matrix)
(let ((res (map 'vector
(lambda (x)
(map 'vector
(lambda (ix)
(if ix
'(t 0) ; --> Problem happens here
0))
x))
matrix)))
res))

这个函数将接受一个2d矩阵,其中每个元素可以是t或nil。然后它将转换t->'(t0)和nil->0.

结果数组有一个问题是每个(t0)cons现在都指向相同的内存位置。例如,如果我将结果数组保存在res变量中,并执行以下操作:

(eq (aref (aref res 0) 0)
(aref (aref res 1) 1))

*假设res[0][0]和res[1][1]是'(t,0)节点。

这将导致T。但像这样做的结果是零:

(eq '(t 0) '(t 0))

我能问一下,让创建的cons指向同一内存位置的变换矩阵会发生什么吗。

我在SBCL 2.0.0 Windows 64位上测试了这些代码。

谢谢。

查看此处问题的一种方法是将函数更改为:

(defun transform-matrix (matrix)
(let ((non-nil-value '(t 0))
(nil-value 0))
(map 'vector
(lambda (x)
(map 'vector
(lambda (ix)
(if ix non-nil-value nil-value))
x))
matrix)))

应该清楚的是,这个代码在功能上是相同的:两个函数都有一个'(t 0):这个只是给它起了一个名字。

但现在让我们来挖掘这个函数并考虑一下:

(defun ts ()
(let ((non-nil-value '(t 0)))
(eq non-nil-value non-nil-value)))

当然,我希望调用这个函数的结果是t

这就是为什么你得到的嵌套向量中的每个元素(不是0)都是一样的:因为你只构造过一个对象。

如果您希望返回值中的所有对象都是不同的对象(即不相同),则需要每次构造一个新对象,例如:

(defun transform-matrix (matrix)
(let ((non-nil-template '(t 0)))
(map 'vector
(lambda (x)
(map 'vector
(lambda (ix)
(if ix (copy-list non-nil-template) 0))
x))
matrix)))

这将确保结果对象的每个非零元素

  • 是不同的
  • 可以安全地变异

这两种情况以前都不成立。

对于(eq '(t 0) '(t 0))的情况,您可能认为它必须返回nil。这是(我认为肯定的)解释代码的情况。但对于编译后的代码来说,答案并不那么明确。至少对于文件编译器来说,很明显这可能会返回t。规范第3.2.4.4节规定,

如果用文件编译器处理的单个文件的源代码中出现的两个文本对象相同,则编译代码中的相应对象也必须相同。除了符号和包之外,文件编译器正在处理的代码中的任何两个文本对象都可以合并,当且仅当它们相似时;如果它们都是符号或都是包,则只有当且仅当它们相同时,它们才能合并。

(eq '(t 0) '(t 0))中,有两个文本列表,它们是相似的,因此可以由文件编译器合并。

一般来说,如果你想要一个可变对象,或者一个你需要确定与任何其他对象不相同的对象,你应该明确地构造它:变异文字对象从来都不安全(甚至是合法的),并且可以合并对象的规则足够复杂,构造对象通常更安全,这样你就知道发生了什么。


顺便说一句,你使用嵌套向量而不是二维矩阵是有原因的吗?

仅添加到TFB:

Lisp不会在函数调用中复制其参数。它将引用传递给它:

(let ((a '(1 2)))          ; A is a reference to (1 2)
(foo a)                  ; calls FOO and the same (1 2) will be 
; accessible via a new reference inside FOO
(setf (aref array 0) a)
(setf (aref array 1) a)  ; this will make the array at 0 and 1
;  reference the same list
)

如果我在REPL中使用quote版本'(t0)两次,我仍然可以得到两个不同的缺点。

这是因为在REPL中,您需要输入'(t 0)两次,并确保Reader(REPL中的R)构建新的列表,它通常会这样做:

CL-USER > (eq (read) (read))
(0 1) (0 1)
NIL

现在是REPL阅读器:

CL-USER 6 > '(1 2)
(1 2)                     ; result
CL-USER 7 > '(1 2)
(1 2)
CL-USER 8 > (eq * **)     ; comparing previous results
NIL

每次调用READ都会保存一个新的列表。

旁注:实际上还有更高级的REPL阅读器,可以引用已经存在的列表,比如在McCLIM监听器的REPL中。

首先,请注意,transform-matrix函数只包含'(t 0)语法的一个实例,而您在REPL中测试的表达式包含两个实例:(eq '(t 0) '(t 0))

因为该表达式有两个实例,所以这些实例可能是不同的对象。事实上,Lisp实现必须竭尽全力将它们变成一个对象,这是允许的。

(t 0)语法是该程序的一段源代码。程序可以将quote运算符('字符是其简写)应用于其语法片段,以将该语法用作文字。给定的文字是一个对象;对相同CCD_ 15的多个评价产生相同的对象。

当Lisp被天真地解释时,解释器递归地遍历原始的基于列表的源代码。quote运算符的实现只是将要遍历的代码段作为值返回。

编译Lisp时,基于列表的源代码会转换为其他代码,例如CPU直接执行的本地机器语言。在转换后的图像中,源代码不见了。然而,编译器必须识别quote的特殊形式并以某种方式对其进行翻译。要做到这一点,它必须采用quote所包含的源代码结构,并将该对象嵌入编译后的图像中,以便它在某种程度上可用于编译后的代码:即源代码中引用的部分不会消失,而是传播到翻译中。例如,编译后的图像可以附带一个专用于存储文字的静态矢量。每当编译器处理像'(t 0)这样的引号表达式时,它都会分配该向量中的下一个可用槽,比如位置47或其他位置,并将对象(t 0)粘贴到该槽中。然后,'(t 0)代码的编译版本将访问文字数据向量中的插槽47,每次执行时都会这样做,每次都检索相同的对象,就像程序的解释版本每次都检索自己的源代码一样。

编译文字时,编译器还可以搜索矢量并对其进行重复消除。它可能会扫描文字,发现索引13已经有(t 0),而不是分配下一个可用索引,如47。然后它生成访问索引13的代码。因此,(eq '(t 0) '(t 0))的编译版本很可能产生true。

现在,按照您提出问题的方式,没有证据表明共享(t 0)的单个实例的所有插槽都存在实际问题。

如果您通过突变将0值更改为其他值,则需要这些对象有所不同。然而,即使是这个问题也可以在不事先实际改变对象的情况下解决。也就是说,我们可以保持所有(t 0)条目对象指向同一个对象,如果我们想将其中一些更改为(t 3),我们可以在那时分配一个全新的对象,而不是(set (cadr entry) 3)。此外,也许我们可以使所有(t 3)条目都指向一个(t 3),就像我们对(t 0)所做的那样。

即使存在问题,也不可能说将'(t 0)更改为(list t 0)是解决问题的最佳方法。

最新更新