If I wasn't clear, my main point is the "newly allocated" part of the functional interface.  It severely limits efficient implementation.  My suggestion is to come up with a wording that allows different strategies.

That said, explicit conversion was the first one I thought of.  But strict type separation doesn't seem to play well without static parameterized types.

- It doesn't only stay in SRFI APIs, but carried over to any utilities built on top of it.  An intermediate library written on top of srfi needs to provide both functional type interface and linear type interface in parallel, bloating everything.

- A remedy is to provide a generic interface that accepts both functional and linear type argument, by just applying *-copy on it, but that's not ideal---it can't actually distinguish the case that caller truly passing a linear type argument---that is, the caller knows it won't be reused again, thus copying is redundant.  We cannot distinguish it easily at runtime, unless we introduce convoluted reference counting or ownership mechanism.

Using mutability is a second-optimal solution, and we can have 'ensure-mutable' procedure that copies the input if it's immutable and passes through if it's mutable, as well as the ordinary copy procedure.   Then, an intermediate library that potentially takes functional or linear type arguments can avoid unnecessary copying.  If the caller of such a library wants to pass a mutable shared object, he can just explicitly copy it.

But then, if every intermediate library puts the ensure-mutable procedure, we can just embed it into the original linear-updating API, which became the strategy I outlined in the original email.

I see strict segregation has clear semantics in terms of types, but my emphasis is how to allow wider implementation strategies.  We already allow linear types to be subsumed by functional types so that 'foo!" is just an alias of "foo".

On Mon, May 31, 2021 at 2:45 AM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:

Functional updaters and linear updates operate on semantically different types. Functional updaters work on normal types, linear updaters on affine versions of these. In Scheme, we do not have a way to express this statically, but nevertheless, semantically these different categories of types are in the background.

From a higher point of view, applying a linear updater on a result returned by a functional updater is a typing error.

When you propose that linear updaters should dispatch on a flag, you are effectively making them ad-hoc polymorphic because they would then be defined on two very different types. In general, we try to limit ad-hoc polymorphism in Scheme, so I don't think that your proposal is a good idea.

The Scheme way would be to have adapters converting from the normal types to affine types and back. The converters are, of course, implemented by a copy procedure. My point is that calling such a procedure should remain explicit.

PS A functional updater should never allocate a new structure unless necessary. The semantics of SRFI 113, SRFI 146, ... regarding the question of what "newly allocated" means, are not very good and should eventually be corrected.

Am Mo., 31. Mai 2021 um 13:06 Uhr schrieb Shiro Kawai <xxxxxx@gmail.com>:

(I cc'ed srfi-224 since I came to this idea when I'm implementing it, but it has wider scope and it's relevant in srfi-discuss.)

Recent trend of data structure SRFIs is to provide two flavors of updating procedures:

- Functional updaters never mutate the input structure, and *always* return a newly allocated structure.
- Linear updaters are *allowed* to reuse the storage of input structure to produce the output, given that the caller guarantees the input structure will never be used.

Functional interface has a good nature--it won't create hidden dependencies thus the code is easy to reason about. It also plays nicely with concurrent execution, for you don't need to worry that your operations step on other threads' toes.

Linear updating interface gives the user to express opportunities of optimization. The implementation can take advantage of it to reduce allocations.

So, it appears to be a nice combination---except that, I think, the way they are currently specified is actually pulling each one's leg and reducing their merits.

----

Performance-sensitive users often frown on functional data structures, for they seem to copy everything every time. "It won't be that bad," functionally-minded users replies, "for it is often the case that the input structure and the updated structure can share most of their internals; the updated structure just allocates enough to store the updated parts. In the extreme case, the updater can just return the input as is, when it finds out the structure isn't altered at all (e.g. adjoining an item to a set that already has the item). The beauty of functional programming is that nobody cares whether it is shared or not---only the content matters."

It is true if everything is written functionally. However, to use the linear-updating interface, the caller needs to know that the structure to pass in isn't shared. If the functional interface may return a (partially) shared structure, it's hard to guarantee the "no-share" condition. Thus, SRFI states the functional interface always copies the input, even if there's no change at all. It can't take advantage of partial sharing as well, if the linear-updating version mutates internal structure.

This takes out the opportunity of optimization in the functional interface. The implementation needs to choose either (1) makes a slow functional version, in order to provide an efficient linear-updating version, or (2) makes a linear-updating version not mutate the input at all, and put functional optimizations.

I think we can do better. One idea is this:

- The data structure has a mutability flag internally.
- The functional interface always returns immutable data. It may return the input as is, or return a structure that partially shares the input, if the input structure is flagged immutable. If the input is flagged mutable, it always returns a fleshly copied immutable structure.
- The linear-updating interface may mutate the input structure if it is flagged mutable, and copies if the input structure is flagged immutable.

If the SRFI does not provide an explicitly-mutating interface, it is actually almost indistinguishable from the existing SRFI spec, except when you compare input and output structures with eq?.

Given that explicitly-mutating interfaces (such as vector-set!) aren't popular in the SRFIs, I think it's good to *allow* the implementation to take the latter choice.  (The implementation of course can choose the current way, if it desires.  It's just another option.)