From mboxrd@z Thu Jan 1 00:00:00 1970 From: ludo@gnu.org (Ludovic =?utf-8?Q?Court=C3=A8s?=) Subject: Re: Generalizing DAG rewriting Date: Fri, 10 Feb 2017 10:55:22 +0100 Message-ID: <87tw82gyk5.fsf@gnu.org> References: <87r3394y6l.fsf@gmail.com> <874m04ekp4.fsf@elephly.net> <87mvdv3czp.fsf_-_@gnu.org> <9e6855cb-d160-e6ba-e9f9-3c40a01a3162@hypermove.net> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Return-path: Received: from eggs.gnu.org ([2001:4830:134:3::10]:34496) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cc7vO-0004r2-0P for help-guix@gnu.org; Fri, 10 Feb 2017 04:55:31 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cc7vK-0007N4-R5 for help-guix@gnu.org; Fri, 10 Feb 2017 04:55:30 -0500 In-Reply-To: <9e6855cb-d160-e6ba-e9f9-3c40a01a3162@hypermove.net> (amirouche@hypermove.net's message of "Fri, 10 Feb 2017 00:47:27 +0100") List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-guix-bounces+gcggh-help-guix=m.gmane.org@gnu.org Sender: "Help-Guix" To: Amirouche Cc: help-guix@gnu.org Hi Amirouche, Amirouche skribis: > Le 09/02/2017 =C3=A0 10:55, Ludovic Court=C3=A8s a =C3=A9crit : [...] >> I agree that this is asking for generalization. >> >> Another instance of DAG rewriting is the =E2=80=98package-with-=E2=80=99= 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=E2=80=99s we=E2=80=99re dealing with DAGs, not just trees, so the noti= on of =E2=80=98up=E2=80=99 and =E2=80=98down=E2=80=99 doesn=E2=80=99t directly apply. But apart from = that, we=E2=80=99re 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=E2=80=99s interesting, but I=E2=80=99m 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 =E2=80=98package-input-rewriting=E2=80=99 is around 20 lines of code. That said, there=E2=80=99s a need for generalized graph tools, and also too= ls in (guix graph) that would allow us to get various graph metrics efficiently (things like computing the =E2=80=9Crank=E2=80=9D of a node). = So if you=E2=80=99re into graphs you might be interested in fiddling with (guix graph) and see what cool things could be done. Thanks, Ludo=E2=80=99.