多次执行 cl-sort 得到的结果不一致

先上代码。

;;; sort-test.el --- test sort -*- lexical-binding: t; -*-

(require 'cl-seq)

(defun sorter (a b)
  (< a b)
  )

(defun make-test-list ()
  (let (li)
    (setq li '(100 50 20 35 80 90 99))
    li
    )
  )
;; (make-test-list)

(defun test-sort ()
  (let ((li (make-test-list)))
    (message "li before %S" li)
    (setq li (cl-sort li #'sorter))

    (message "li after %S" li)
    )
  )

;; (test-sort)


遇到的问题是:第一次执行test-sort,message里输出

li before (100 50 20 35 80 90 99)
li after (20 35 50 80 90 99 100)
"li after (20 35 50 80 90 99 100)"

然后再次执行test-sort,message里会输出:

li before (100)
li after (100)
"li after (100)"

我用27.2和native comp的master都试过,一样的行为。

我只能发现跟cl-sort有关,这算是个bug还是说cl-sort有啥特别的地方?

试试这个

(defun make-test-list ()
  (let (li)
    (setq li (list 100 50 20 35 80 90 99))
    li
    )
  )

在这个例子里,改成你说的这样,确实没有问题了。

我是在我的一个package里发现了问题,然后提取出来的例子。但是我的代码并没有使用,我再研究一下看看。

多谢。

这可能是 lisp 底层的实现导致的, '后的list 是作为常量的,有副作用的函数和这种常量一起作用,有时候会出现意外的结果。

1 个赞

sort/cl-sort是destructive function,我原来对这个destructive的理解有问题,以为它在重用待排序seq的存储的情形下还会保持原来的seq结构(如果seq是list,排序后也还是list)。

我改了一下帖子标题。

这个问题讨论多次了:

竟然还有这种坑, 有用的知识又增加了 :crazy_face:

看了看实现似乎确实不太一样.

quote 返回的是指向自己 args 的指针, 这些 args 应该是在解析函数定义的时候就创建了, 所以后面每次调用函数返回的都是同一个 Lisp_Object:

list 则是每次把 args 拷贝一遍, 返回拷贝之后的 Lisp_Object:

Common Lisp 也有类似的限制, 看来大家都是从远古的某些 lisp 继承下来的设计.

The consequences are undefined if literal objects (including quoted objects ) are destructively modified.

http://clhs.lisp.se/Body/s_quote.htm

'(1 2 3 4)的列表(1 2 3 4)是read时构造的, 接下来程序执行中就只有一个实例,所以用sort进行破坏式修改就会影响其他引用了该list的程序.

写成(list 1 2 3 4)就是一个函数调用,运行时每次都会创建新的list,这样行为才是正常的

可以理解成C语言里用static修饰的变量

1 个赞

lisp 中的 list 其实是 cons 的简化形式:

(cons 1 (cons 2 (cons 3 nil)))
;; => (1 2 3)

对应到 C 语言中就是单向链表:

  * <- ptr
 / \
1   *
   / \
  2   *
     / \
    3  nil

排序之后当然无法再通过原来的节点把链表串起来:

  *
 / \
3   *
   / \
  2   * <- ptr
     / \
    1  nil

除非重新把指针指向链表头:

(let ((xs (list 1 2 3)))
  (sort xs '>)
  xs)
;; => (1)

(let ((xs (list 1 2 3)))
  (setf xs (sort xs '>))
  xs)
;; => (3 2 1)