With the publication of SRFI 225 we have a proposal for a mechanism by which different implementations of similar abstract data types can be accessed under the same programming interface, something which the core Scheme language has never previously supported.

I think it may be worth taking this moment to consider whether, before we charge in and implement this 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, similar to how parameter objects became the generic counterparts to the current-input and -output-ports. For example, it might be useful to have a generic interface for converting any sequence type into a SRFI 158 generator; or a better abstraction than SRFI 225 in general might be a generic ‘ref’ procedure which can be taught to grab things out of any collection type, whether a mapping or sequence (like subscripting in Python, etc.).

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>:

• custom conversion to strings for the Python equivalents of the Scheme ‘write’ and ‘display’ procedures and formatting — we discussed making ‘write’ customizable in the SRFI 207 mailing list; a generic interface might be one approach
• getting the size of a collection
• getting, setting, and deleting individual items and ranges from collections (both sequences and mappings)
• getting an iterator from a collection
• overloading of arithmetic operators

Plus the following which are not relevant in Scheme:

• changing default class creation and instantiation behaviour; not needed in Scheme because you can define your own fake constructor which calls the real record-type constructor procedure underneath, and hide the real one by not exporting it
• overloading of comparison operators and hashing; not needed in Scheme because of comparators
• overloading of whether an object is considered true or false in ‘if’ statements; not needed in Scheme because #f is the only false object (unlike Python where 0, the empty list and string, etc are considered false)
• overloading of accessing properties of an object through dot notation; the Scheme equivalent might be identifier-syntax, since we have no dot operator
• overloading to make objects other than functions appear callable as functions — applicable record types and instances can almost be implemented portably, except for type predicates, which get tricky
• defining context manager behaviour — not needed in Scheme because of macros

Of the ones that are relevant, SRFI 225 provides the second and third, but only for key-value mappings, not for sequences. The fourth could be a very small library providing one procedure to register an iterable type and another to create the generator for any such registered type. Arithmetic operator overloading seems to me to be of very marginal value in the context of Scheme. (Perhaps it would be useful for a DSSSL compatibility library, if anyone still cared about DSSSL.)

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, since SRFI 225 does not (in the current draft) make any guarantee about what order the types will be checked in (although doing this in a thread-friendly way brings its own challenges); even cleverer implementations which can poke around in the Scheme system’s basement could guarantee consistent O(1) performance at least for some types by knowing which predicates respond #t to which underlying types, and storing some internal type object in a hash table instead of calling the predicates one-by-one. The latter is particularly magic and we can’t depend on implementations, even notionally performance-oriented ones, doing it, imo. The former approach depends on the fact that SRFI 225 dictionary 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.

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.

Best wishes,

Daphne