Re: Generalizing DAG rewriting

[ludo@gnu.org (Ludovic Courtès)]

Hi Amirouche,

Amirouche <amirouche@hypermove.net> skribis:

> Le 09/02/2017 à 10:55, Ludovic Courtès a écrit :

[...]

>> I agree that this is asking for generalization.
>>
>> Another instance of DAG rewriting is the ‘package-with-’ helpers in
>> (guix build-system gnu).
>>
>> We should have a general form of transformation procedure that handles
>> DAG traversal and memoization like all these procedures do.
>
> FWIW, I am very much interested in what you will come up with.
>
> How is different what you want to achieve from SXML Tree Fold [0]?

Here’s we’re dealing with DAGs, not just trees, so the notion of ‘up’
and ‘down’ doesn’t directly apply.  But apart from that, we’re
essentially writing a combinator to traverse the DAG, which is similar.

> Wikipedia's graph rewriting [2] page cites a few softwares that deals with
> the issue along with some theory.
>
> [2] https://en.wikipedia.org/wiki/Graph_rewriting
>
> The place where I will need DAG rewriting is the replacement ReLeX (from
> opencog which AFAIK does graph rewriting somehow) and semantic/intent
> framing.

[...]

> WDYT of my rambling?

Heheh.  :-)  I think it’s interesting, but I’m not sure the actual
pieces of software you mention could be used here.  At this point we
have fairly simple use cases, and a rewriting procedure like
‘package-input-rewriting’ is around 20 lines of code.

That said, there’s a need for generalized graph tools, and also tools in
(guix graph) that would allow us to get various graph metrics
efficiently (things like computing the “rank” of a node).  So if you’re
into graphs you might be interested in fiddling with (guix graph) and
see what cool things could be done.

Thanks,
Ludo’.