Am Fr., 25. Juni 2021 um 09:31 Uhr schrieb Shiro Kawai <xxxxxx@gmail.com>:

On Thu, Jun 24, 2021 at 9:19 PM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:

I think the extra allocation can be neglected. For very small containers, lists and alists can't be beaten. For larger containers where it makes sense to use mappings, sets, etc., the extra allocation is irrelevant. Moreover, it is not necessarily an extra indirection. For a tree-like data structure, one can simply use the tree's root.

Agreed that extra allocation can be neglected.

On a tree structure - If we don't use indirection, we need at least to copy the root node, right?
Say, we have a set based on tree, and we have something as {1 . {2 . 3}}. We pass it to a functional delete procedure to remove '1'. The functional delete procedure can't return the subtree {2 . 3} directly, for it may be passed to mutators, so either it needs to copy the root node (of the subtree).

Yes, we can't return {2 . 3} because {1 . {2 . 3}} could have been the output of functionally updating a tree {2 . 3}. And modifying the latter mustn't change anything derived from it.

Anyway, it is covered by "non-eqv?" requirements. It may be odd for those who come from the functional world, but the more I think about it, the more it seems to make sense.

I think the important thing here is that the API is safe in a sense that everything you expect to work actually works, that there is no spooky action at a distance, and that actually more works than one may think (for those "coming from the functional world").

@Wolfgang Corcoran-Mathe As SRFI 224 is still not finalized (and had linear update procedures), maybe we can persuade Wolfgang to implement this proposal so that we can experiment with it before SRFI 224 is finalized.

In general, the implementation should include some kind of hook to link with the host's garbage collector so that the shared counters are actually decreased. This is so that the imperative versions don't have to copy if a previously shared object has been garbage collected. On the other hand, this is not strictly necessary. If a counter is not used, it is enough to have an atomic "shared" flag on each inner node. This is initially cleared, set as soon as a functional update procedure is applied, and reset when an imperative update procedure actually copies.

One gets a cheap implementation when the shared flag is inherited by subnodes, meaning if a node has the shared flag set, all subnodes are implicitly shared. 