Hi Maxime,

Thanks for sharing your code!

I don't see many delimited continuations at work, though.  The
continuation-related primitive in your code is basically
abort-to-prompt, which is here of equal power as C's longjmp or other
languages throw/catch (and reflects the most typical use of Scheme's
classical call/cc).  But maybe I miss something in your code.

This is, of course, no criticism of your code; quite the contrary.  If
it doesn't need the power of delimited continuations, it is even
simpler, and simplicity is good!

Cheers,

Marc

Am Do., 13. Apr. 2023 um 17:13 Uhr schrieb Maxime Devos
<xxxxxx@telenet.be>:
>
> Hi,
>
> It's probably not important for finishing SRFI-234, but for the
> interested: I have a stateless implementation of topological sorting
> based on (delimited) continuations:
>
> https://notabug.org/maximed/cargoless-rust-experiments/src/master/topological-sort.scm
>
> I tried implementing it the simple way first, with explicit stacks,
> but I couldn't figure it out, so I thought: ‘If the simple approach is
> hard, perhaps a complicated approach will be easy!’ and somehow this
> troll logic worked out.
>
> The idea behind this implementation, IIRC, is that:
>
>    * if the graph were a tree, you could find a topological ordering
>      by doing a depth-first traversal (*) of the graph starting at the
>      root and printing all the nodes.
>
>    * if it's a tree, that can be implemented with basic recursion.
>
>    * but it's a (directed, acyclic) graph, not a tree, so we must
>      skip some recursions
>
>    * recursion is ‘stuff‘ with the call stack and continuation does
>      shenanigans with the call stack.
>
> (*) For trees depth-first/breadth-first/... doesn't matter, but IIRC it
> does matter for DAGs.
>
> (The continuation stuff can probably be avoided by passing around the
> current value 'visting' and 'visited', but that's what I tried before
> and couldn't figure out ...)
>
> I find it interesting that while I don't understand standard algorithms
> on topological sorting, if I just look a the basic idea behind the
> algorithms (e.g.: ‘based on depth-first sorting’) and allow myself to
> use supposedly complicated stuff like continuations, then I can easily
> figure out an alternate implementation by myself.
>
> Greetings,
> Maxime.