Am Do., 18. Nov. 2021 um 22:29 Uhr schrieb John Cowan <xxxxxx@ccil.org>:

On Thu, Nov 18, 2021 at 3:41 PM Marc Nieper-Wißkirchen <xxxxxx@gmail.com> wrote:

The idea is to implement a mapping as a lightweight structure that has two fields. The first field "shared-counter" is initialized with 1 and the other field is a handle to the actual data structure. If a functional update procedure is used, the old and the new mapping each have their shared counter increased. When a mutation procedure is applied to a mapping with a shared counter higher than 1, the actual data structure is copied first and the shared counter of the mutated result is reset to 1. (This can be done more fine-grained for shared substructures, of course.)

Why is a counter required? A simple shared/unshared boolean should suffice.

I made a mistake in explaining (was a long day!). The shared counter should be on the actual tree of data and not on the handle. This way, when a copy is made prior mutation, the shared counter of the original tree can be decremented. This can also be employed in Scheme systems supporting finalizers when handles are garbage collected.

For that matter, why not just a simple box around the tree/HAMT? Read-only operations look at the data structure currently in the box. A functional update allocates a fresh box containing the updated data structure and returns the new box. A mutation likewise does the functional update, puts the updated data structure into the original box, and returns an unspecified value. That takes advantage of any sharing the functional update may provide, and is universally applicable to any type that doesn't do functional update by copying.

This would be my poor man's implementation should I ever amend SRFI 146.  In general, however, in place mutation will be faster than functional update, so an implementation that wants to offer fast mutations will want to use the shared counter approach from above. For HAMTs, I did the latter in Gnulib's hamt module (in C, not in Scheme).

This use of boxes is briefly discussed in the third paragraph of the SRFI 111 rationale. In order to do type discrimination, you would want to use a unique record type rather than generic SRFI 111 boxes.