Hi Marc,

Marc Nieper-Wißkirchen <xxxxxx@gmail.com> writes:
> Am Mo., 4. März 2024 um 01:17 Uhr schrieb Arthur A. Gleckler <xxxxxx@speechcode.com>:
>  * Change to returning #f for cycles (allowing (values #f message circular)) and providing topological-sort/exception for the previous
>  behavior
>
> Remove topological-sort/exception, as this can easily be provided by the user (or some general procedure converting #f into an exception). If
> every standard/SRFI procedure that conceptionally returns a Maybe came also with a version that raises an exception instead of the Nothing
> value, we would see a combinatorial explosion of the number of procedures.

The reason for the exception is to provide additional information on the
failure without mandating that the non-exception-throwing procedure
always provide multiple values.

The reason why a topological sort failed has been essential to know in
every usage I had of topological sort, for example because they are
cyclic dependencies in a module system. This information is far cheaper
to obtain during calculation than if it has to be gathered after seeing
the returned #false.

>  * returns (values nodes #f #f) on success, else (values #f msg cycle).
>
> That a procedure like topological-sort may return different numbers of values is very uncommon and makes it inconvenient to call and use.
> Just return the sorted list of nodes or #f if the graph is circular or raise an exception if the preconditions were violated.

The implementation returns multiple values, but this is not mandated in
the SRFI, so this is an implementation detail.

>> <p>Returns the list of topologically sorted nodes or <code>#f</code>
>> if the graph cannot be sorted topologically.</p>
>>
>> <p>If <em>graph</em> is circular, <code>topological-sort</code> may
>> return <code>values</code> where the second value is an error message
>> and the third value provides information about at least one cycle. If
>> a second and third value are provided outside error conditions, they
>> must both be <code>#f</code>.</p>

This allows implementations which always return multiple values as well
as implementations which never return multiple values.

Though it is a part I’d be comfortable with removing. Then the procedure
returning multiple values would be purely internal and the only way to
access information about the failure would be through the exception.

> If new SRFIs define new exception values, they should explain how these fit into the condition hierarchy of R6RS.

Is that compatible with R7RS conditions?

Besides that: do you have a suggestion? What I see as fitting are either
&domain or &incompatible, but I’m no expert on r6rs conditions.

>  * Use equal? as default for = — and document for the edgelist procs
>
> For large graphs, edge lists are not the best data structure. Vectors will be faster (more cache-friendly) and will use only half the memory on a
> typical Scheme implementation.

The edgelist procs convert between edgelists and the internal structure.

To enable more efficient implementations, it may be a more
straightforward option to remove the definition of the graph structure
(define that as implementation detail) and instead only require the
conversion procedures from and to edgelists.

This would also make it easier to realize compatible extensions to this
SRFI with abstract accessors to edges (i.e. retrieving them from a
database) without requiring current implementations to support that.

To the meta-discussions:

> (A SRFI that is only efficient for small sizes is not worth standardizing, I think.)

I disagree with that. The set operations in SRFI-1 are only efficient
for small sizes, but they are very useful — and thus were worth
standardizing.

> I should also say that I am not convinced that it is a good idea to publish APIs and implementations like this one as SRFIs (unless you really
> think that the API is ripe for future RnRS standardisation). I think it is better to develop, improve and maintain them as portable libraries. Only
> if a good portable implementation is not possible, a SRFI fixing this should be submitted.

While I like portable libraries, I disagree in principle that publishing
SRFIs that may not become part of a RnRS isn’t a good idea.

SRFIs provide building blocks that can be included in and fleshed out by
different implementations, and they have been very useful for me many
times.

Best wishes,
Arne
--
Unpolitisch sein
heißt politisch sein,
ohne es zu merken.
draketo.de