Thanks Daphne for this great thread.

On 2021-07-23 13:34, Daphne Preston-Kendal wrote:
> I think it may be worth taking this moment to consider whether, before
> we charge in and implement this

Yes.

> as a special thing just for key-value
> maps, there might be other patterns worth considering as useful to
> introduce this kind of interface polymorphism for, and whether we
> should consider adopting a generic way of doing this,

True

> The example of Python might be instructive when considering which of
> these interfaces we might want in any case. Python provides roughly
> the following through its ‘special method names’
> <https://docs.python.org/3/reference/datamodel.html>:

[...]

> One problem with interfaces defined in the SRFI 225 style is that they
> impose an O(n) startup overhead for type dispatching on every single
> individual call to a procedure which uses them, where n is the number
> of types which have been registered. So if I call dict-ref in a loop
> on the same concrete dictionary object, I theoretically have to wait
> for it to check through all the registered types anew each time. This
> problem is particularly acute if the SRFI 225 style of registration
> were to be adopted for things like numeric operator overloading where
> there is no way to get around the overhead by using the type-specific
> procedures directly when possible. Clever implementations could reduce
> this to O(n) on the first invocation and O(1) on the second invocation
> on data structures of the same type by caching which concrete types
> have been used most recently,

That is not the only optimization that is doable. Without subtyping and
predicate jointness / overlap, it is also possible for JIT compiler to
move to the top of the comparison chain (cond or switch) the predicate
that match most often.

It may even inline the concrete procedure in some cases.

When subtyping is considered, it builds a tree of if, where the
optimization can be applied by a sufficiently worked-on compiler. Those
optimizations call for predicate combinators and reasoning between
differents predicates.

> since SRFI 225 does not (in the current
> draft) make any guarantee about what order the types will be checked
> in

I think that is a good thing, but in the case where predicates overlap
(and without predicate combinators), it might lead to a
non-predicatable, non-deterministic, non-portable behaviors.

> type registrations make no account for subtyping: an implementation
> should, at least in some cases, always have to be sure to check
> subtype predicates before parent type predicates, so simply moving
> predicates to the front of the list would not work; some delicacy is
> involved.

To be completly safe, I think it requires to be able to reason about the
predicates, hence the predicate combinators (that includes predicates
about predicates) e.g. refuse to add a new dict type predicate that
overlap without subsuming another (or deal with it in so other way).

>
> One approach would be for generic interface procedures to be
> higher-order functions, only *returning* the correct implementation
> procedure for a particular operation on a particular datum, instead of
> being an all-in-one for both finding and calling the underlying
> implementation. So (dict-ref my-dict) would return hash-table-ref when
> my-dict is a hash table or alist-ref when it’s an alist, allowing
> constructs like (let loop ((ref (dict-ref my-dict)) … (ref my-dict
> some-key) …) where the correct procedure for one particular data
> structure is explicitly cached instead of being worked out anew each
> time through the loop. But for simple use this does result in the
> verbose ((dict-ref my-dict) my-dict some-key). My-dict could be cached
> (curried, one could say) within the returned procedure (so one would
> instead write (ref some-key) or ((dict-ref my-dict) some-key)), but
> this would mean consing a new procedure for each such simple access,
> unless a mythical ‘sufficiently smart compiler’ could eliminate it.

To go further down that road, they could be a procedure `dict-interface`
that returns all the procedures for first and only dict-like argument.

TIL: consing a new procedure.

> Best wishes,
>
>
> Daphne

Replying about other threads about CLOS: I have still no empirical
(practical) proof CLOS or CLOS-like with inheritance are a win. They are
widespread in mainstream languages that use in industrial solving
real-world problem (tm). Those are clues, in my humble opinion, that
CLOS et al. are an anti-pattern because they lead to code that is
difficult to reason, and because CLOS itself it is difficult to wholly
and fully understand (the latter does not need a elaborate proof).

Re type inheritance for exceptions: we do not necessarily need CLOS,
because exceptions make good use of inheritance, that can be handle with
predicate combinators (which happens to be useful for others).

Re fast generics, they are sort a leap of faith as far as I am
concerned, because it is new to me. But they have the practical and
elegant property that they build upon existing Scheme knowledge
(predicates) and look like or even are a pattern matching facility (and
that does not need to be proved, because it is a fact).