关于remove!的讨论

By guenchi at 2018-07-20 • 0人收藏 • 137人看过

前几天,群里有人报出一个bug


Chez Scheme Version 9.5
Copyright 1984-2017 Cisco Systems, Inc.

> (define x '(1 2 3 4 5))
> x
(1 2 3 4 5)
> (remove! 1 x)
(2 3 4 5)
> x
(1 2 3 4 5)
> (remove! 2 x)
(1 3 4 5)
> x
(1 3 4 5)
>


嗯 看似低级,低级到你不相信chez会出这样的bug


以下是Andy Keep的回复:(翻译中)


让我们看看这里发生了什么:

remove! is a function, and in a pass by value language, the body of the remove! function is not passed x it passed the value of x.所以,即使他想他也不能修改x的值。

所以,什么是x的值? 是列表 0, 1, 2, 3, 那么,链表在scheme里是什么呢? It is a sequence of cons cells or pairs, where the first element of the pair contains a value (0, 1, etc.) and the second element points to the next pair in the list or '() (aka null), at least if it is a proper list.

这个链表在这里可以图像化如下:

   +---+---+  +---+---+  +---+---+  +---+-----+
x: | 0 |  -+->| 1 |  -+->| 2 |  -+->| 3 | '() |
   +---+-+-+  +---+---+  +---+---+  +---+-----+

所以传递给x的值仅仅是一个指向链表的指针。  remove!可以修改链表内的对。 比如 当我们 remove! 1, 含有0的序对,  即指向含有1的序对,被修改为指向含有2的序对。结果如下:

   +---+---+             +---+---+  +---+-----+
x: | 0 |  -+------------>| 2 |  -+->| 3 | '() |
   +---+-+-+             +---+---+  +---+-----+
                           ^
              +---+---+    |
              | 1 |  -+----+
              +---+---+

注意包含1的序对仍然存在,并且仍然指向包含2的序对,只有包含0的序对被修改了。 所以如果你有一个指向含有1的序对的值你就会看到它仍然在链表中:

% scheme
Chez Scheme Version 9.5.1
Copyright 1984-2017 Cisco Systems, Inc.

> (define x (list 0 1 2 3))
> (define y (cdr x))
> x
(0 1 2 3)
> y
(1 2 3)
> (remove! 1 x)
(0 2 3)
> x
(0 2 3)
> y
(1 2 3)
>

Again, this is because remove! is only mutating the pairs in the list, not the value which was passed to it, which was really just a pointer to the first pair. When we remove! 0, there is nothing in the list to modify, since the it is only the first pair that is impacted, and nothing in the list points to that pair.

             +---+---+  +---+---+  +---+-----+
r:           | 1 |  -+->| 2 |  -+->| 3 | '() |
              +---+-+-+  +---+---+  +---+-----+
                ^
   +---+---+    |
x: | 0 |  -+----+
   +---+---+

Where r: here is the pair returned by remove! as a result.

So, how is this different from remove? Well, remove is not allowed to modify the pairs of the list that was passed to it, so if we started back with our original list:

   +---+---+  +---+---+  +---+---+  +---+-----+
x: | 0 |  -+->| 1 |  -+->| 2 |  -+->| 3 | '() |
   +---+-+-+  +---+---+  +---+---+  +---+-----+

remove 1 would need to rebuild the pairs of the list leading up to this, giving us the following result:

   +---+---+  +---+---+  +---+---+  +---+-----+
x: | 0 |  -+->| 1 |  -+->| 2 |  -+->| 3 | '() |
   +---+-+-+  +---+---+  +---+---+  +---+-----+
                           ^
                 +---+---+ |
              r: | 0 |  -+-+
                 +---+---+

So, we needed to allocate a new pair containing 0 that points to 2 so that the original list still exists unaltered. This is what differentiates remove!, which never needs to allocate new pairs, but may modify the existing pairs from remove which never modifies existing pairs, but may need to allocate new pairs.

Another way to think about this, is that "passing x" to remove! is really just passing an expression whose value happens to be the list 0, 1, 2, 3? For instance:

> (remove! 1 (iota 4))
(0 2 3)

What would remove! "modify" in its argument?


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...