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

On Thu, Jun 24, 2021 at 7:47 PM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:
That functional update procedures return objects that are not "eqv?" to any existing objects will be added.

Ah, I thought this wasn't necessarily the case (e.g. adjoining an item to a set that already has the item), but if we allow the returned object to be passed to mutating procedures, this guarantee is indeed necessary.

It also makes reasoning and semantics easier. We don't have to talk about shared substructures in the spec (which is an implementation thing). It will be enough to talk about "eqv?" things.

Shall we mandate that a linear-updating procedure always mutates the input? I tend to say no, to allow other strategies, including making linear-updating procedures be aliases of functional ones.

If we dropped this mandate, we would again have the unfortunate situation that we would need error-prone linear update procedures.

Is the concern that asking the user to ensure "at-most-used-once" protocol is error prone and hard to check?

This, and that users may use the linear update procedures as follows:

(begin

  (mapping-set! m k v)

m))

because it works with their particular implementation. But such code wouldn't be portable. (This actually happened with the SRFI 113 test suite.)

Better to make the above correct code if we can get it cheaply (which we can).

OK, to think of it some more, mandating mutation does seem reasonable if we accept the premise:
- An object returned from a functional interface can be passed to a mutating procedure.

Then, a functional object needs at least one indirection (handle -> actual structure, where functional updates always allocates a fresh handle), if it wants to avoid copying everything every time.

Then, mandating mutation is no problem even if the underlying structure is immutable, since the mutator can create a new (updated) structure and change the pointer of the header.

Yeah, that's consistent and simple to reason about.

I was worried about the overhead of extra indirection, which wouldn't be necessary either if every interface is functional or if every interface is side-effecting. But yes, if we want to provide good parts of both worlds, the indirection seems inevitable.

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.