On 20 Oct 2024, at 08:45, Artyom Bologov <xxxxxx@aartaka.me> wrote:

> Hi y'all,
>
> One of the early drafts of this SRFI has case-checked, a
> predicate-dispatching macro akin to Common Lisp typecase or Chicken's
> compiler-typecase.

While planning the optimization layer for my pattern matcher recently, I realized that the addition of record types without also a type-case form has arguably created a perverse incentive, *in theory,* to *not* use real record types when type-dispatching performance matters and to use old-style tagged vectors instead (i.e. vectors where element 0 is a symbol telling you what type the pseudo-record has).

The reason is that ‘case’ exists in Scheme and can (again, in theory – see below) provide constant time dispatch over a statically-known set of symbols, so you can use (case (vector-ref 0) …) for fast dispatch. But you can’t do this if you use real records.

As a real example, see figure 7 in Maranget’s optimal decision trees paper: <http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf>
The dispatch on c.1 has 11 branches checked by type. In Scheme, if you used ‘real’ record types, the only way to compile that decision tree node is to do:
(cond ((push? c1) (code-for-case-two))
      ((pushenv? c1) (code-for-case-eight))
      ((apply? c1) (check-a))
      #;etc)
and so on, checking the types one by one, even though they are almost record types (so the implementation has an internal tag which it could use for a constant time dispatch) and certainly disjoint from one another (something an implementation doing whole-program optimization can always know, at the very least). By contrast, if c were not a real record but a vector pseudo-record, you could use ‘case’ for a more direct compilation which can theoretically run much faster. Ideally it could compile to:
(type-case c1
  ((push?) (code-for-case-two))
  ((pushenv?) (code-for-case-eight))
  ((apply?) (check-a))
  #;etc)

However, go and look at your favourite Scheme implementation’s output from macro-expanding ‘case’ and you will find that, in practice, nobody bothers to make that run in constant time either, as far as I can tell. They all just expand to ‘cond’, checking one ‘case’ clause at a time. So perhaps this is too much fuss over nothing and nobody would implement the constant-time check anyway.

> Thus the question: does type dispatching belong to SRFI-253?

Maybe. I think probably a separate SRFI would be better. (I will say here, the SRFI sample implementation would only be meaningful if it actually did constant-time dispatch.)

> Or should
> it better be left to OOP and generics to dispatch over function argument
> types/classes/properties?

No. Those are high-level features which will (touch wood) never infect the Scheme reports, but are user-defined or implementation-specific libraries for those who want/need them. Type-case is a low-level primitive which can be useful in *implementing* OOP/generics/whatever.

Daphne