Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> writes:
> I may be more persuadable if you can show how to prevent that code using
> your interface doesn't become highly inefficient.

Sure.

We already have equal? to compare deep structures. It can inherently
also compare atomic structures (inefficiently, compared to eq?,
string=?, and =, for example).

In order to write efficient Scheme code it's important to know when to
use equal? and when to use type-specific comparison.

Similarly, it's important to know when to use a generic =? and when to
use string=?

Here is an implementation of generics that expands to idiomatic cond
pred? clauses.

https://idiomdrottning.org/call-table-generics

Notably, the most recently registered generics are tried first,
and it expands to:

(cond
 ((and (string? a) (string? b)) (string=? a b))
 (...))

This is on par with equals?

(define-generic (frob (string? a) (string? b)) (string=? a b))

(time
 (dotimes (i 10000000)
	  (frob "The quick brown fox jumps over the lazy dog"
		"The quick brown fox jumps over the lazy dog")))

⇒ 2.782s CPU time, 0.039s GC time (major), 936214/156033 mutations
(total/tracked), 76/67033 GCs (major/minor), maximum live heap: 533.14
KiB

(time
 (dotimes (i 10000000)
	   (equal? "The quick brown fox jumps over the lazy dog"
		   "The quick brown fox jumps over the lazy dog")))

⇒ 1.738s CPU time, 0.023s GC time (major), 540142/90021 mutations
(total/tracked), 42/40159 GCs (major/minor), maximum live heap: 533.09
KiB

In a really tight loop, you'd want to use the type specific comparator.

But, since the use case is for when you need, want, or feel like using
generics, I don't have to compare to string=? or even to equals?

My case here is that a generic =? with a stowed-away, extensible type
record is faster than the "uncurried" version of =? in the SRFI
interface.

(time
 (dotimes (i 10000000)
	  (foo (query-for-the-type-record)
           "The quick brown fox jumps over the lazy dog"
	   "The quick brown fox jumps over the lazy dog")))

couldn't possibly be faster than mine, where the type record has already
been unrolled (into cond clauses) during the binding of frob.

So, let's keep the three different scenarios separate:

• A. truly generic generics over an extensible type record object
• B. generics over a supplied subset that only need to dispatch between
     a handful of types, such as monster sprites vs player sprites
• C. type-specific monomorphic comparators such as string=?

You can not use the speed of scenario C to argue against scenario A.
Let's be clear about that.

That leaves us with this:

One,

(=? (query-for-type-record) x y) is inherently more expensive than an
(=? x y) with the type record hardcoded as long as those type records
are the same. I.e. we are wholly within scenario A.

That expense can only be justified if the speed-gains of scenario B — a
shorter, better-ordered, domain-specific type-record (e.g. fewer cond
clauses) — outweigh the call overhead cost of having to pass it as an
argument each and every time. (Unless facilities such as
define-syntactic-monad are used.)

That has not been shown to be true for every compiler.

My implementation has the default, plain-vanilla, in-almost-every-scheme
types checked last and domain-specific, recently-extended types checked
first. Making speed gains from B's tighter type record very small (yes,
it's non-zero, but again the B approach introduces overhead of its
own.).

Two,

It's possible that a compiler be more type-aware than RnRS facilities
allow and that a compiler can create implementation-specific generic
dispatching that are even faster than what we on the "user" / "library"
side can implement. Call-table-generics expand to cond+and+pred clauses.
A compiler with some amount of type-awareness could use another, internal,
dispatching structure to be even more efficient.

Within limits, of course, since Scheme has dynamic types.

Three,

To be clear about what the argument is here:

It's which out of scenario A vs scenario B should have the shorter
sweeter names and which out of scenario A vs scenario B should be
saddled with the long and cumbersome names. That's it.
Neither of us want to do away with string=? and string<?

Either of us would be capable of import renaming or argument-fixing.
Re-currying what the SRFI-128 spec has uncurried. (Speaking of
inefficiency! SRFI-128's code turns ((foo* r) x y) into (foo r x y) and
then we users of the library are expected turn it back into (bar x y)?)

So the argument is which duo makes the most sense:

• (=? default x y)
• (=?/default x y)

vs

• (=? x y)
• (=?/with-comparator comparator x y)

That's what we are disagreeing about.

Scenario B users not only wants to add their own types into the mix.
They want to remove the default types. They want to write code that is
"generic" not on all comparable types but instead only on their newly
added types.

Scenario A users don't always want to add new types in there, and when
they do, they also want to their generic code to work on the default
vanilla stuff.

> The only point I am arguing about is that =? with an implicit default
> comparator is not very helpful but would promote inefficient and too
> generic code.

Too generic.

I want to write generic code. I don't think I would ever use the =? as
they stand in the SRFI.

If I want to compare between only specific types, I'm not sure I need
the SRFI to do that.

Helper procedures that turn an < into =, >, ≥, ≤ are simple to make
(albeit expensively, compared to direct implementations of those if
available).

Let's say I have two custom types, bar and quux. I can make a
bar-or-quux< and I can then use

(map (make= bar-or-quux<) xs ys)

This use case wouldn't even need the SRFI.

The time for generic default implicit stuff is exploratory programming.
(map =? xs ys) is great in a function you don't know for sure you'll
keep or that it'll be a bottleneck. If it ends up being a well-loved
function that you refer to often, well, that's when you can sharpen it
up. And implement a proper, type-specific, bar-or-quux= function.

> This is similar to sort (whether it takes a plain comparison predicate or a
> comparator), which is generic as well.
>
> (=? c x y) is a good interface, which is to be used exactly in such generic
> algorithms.

It's not good because of the argument heterogenity and incompability
with sort.

((=? c) x y) would solve that since you could then do (sort xs (=? c))

> It's true that coding (=? string-comparator string1 string2) doesn't make
> much sense and that one should rather write (string=? string1
> string2).

Yes, exactly.

When I wrote before that you can't use the benefits of scenario C to
argue against scenario A… What we can do is to use the benefits of
scenario C to argue against scenario B!

Since in scenario A you are writing generic code for all kinds of
comparable types, while in scenario B as in scenario C you are writing
code for known types.

The pointlessness of

(=? string-comparator string1 string2)

is one of the best arguments for my case.