Re: Generalizing DAG rewriting

[Amirouche <amirouche@hypermove.net>]

Le 09/02/2017 à 10:55, Ludovic Courtès a écrit :
> Hi!
>
> Ricardo Wurmus <rekado@elephly.net> skribis:
>
>> Myles English <mylesenglish@gmail.com> writes:
>>
>>> Hello Fede, Eric,
>>>
>>> on [2017-02-07] at 15:15 Federico Beffa writes:
> [...]
>
>>>> it seems that the only Python specific part of
>>>> 'package-with-explicit-python' is the keyword '#:python'. What do you
>>>> think of generalizing it by making it a function keyword argument and
>>>> move the procedure to its own module (maybe (guix build-system
>>>> utils)?).
>>> ...I came the same conclusion as Fede: it could be generalised.  It is
>>> probably close to working for me (with respect to ghc) so I will keep
>>> going for now.  I am not competent enough to generalise it but if
>>> someone else does I can help test it.
>> I’m doing the same for some Perl packages.  I defined a procedure
>> “package-for-perl-5.14” which takes a package and rewrites it.
>>
>> It looks like this:
>>
>> (define (package-for-perl-5.14 pkg)
>>    (let* ((rewriter (package-input-rewriting `((,perl . ,perl-5.14))
>>                                              perl-5.14-package-name))
>>           (new (rewriter pkg)))
>>      (package
>>       (inherit new)
>>       (arguments `(#:perl ,perl-5.14
>>                    ,@(package-arguments new))))))
>>
>> The problem here is that it doesn’t rewrite the “#:perl” argument
>> recursively, so the dependencies of a Perl package will still refer to
>> the latest version of Perl as that’s what’s used in the build system.
>>
>> We would need a solution that would take care of this problem for all
>> build systems.
> 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]?

[0] 
https://www.gnu.org/software/guile/manual/html_node/SXML-Tree-Fold.html#SXML-Tree-Fold

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.

I think opencog deals with graph rewriting in general (not only DAG) and
they must support heterogeneous vertex types whereas guix deals exclusively
with DAG and packages as vertices. Also AFAIK, they do not traverse the
(hyper) graph but patttern match subgraphs with placeholders called
Varéntax *similar*
to the following:

(define has-perl-dependency/pattern '(Package
(Package/version $version))  ;; exemple use of a variable in the pattern
(Package/inputs (ListLink "perl" $inputs ...)
                                                              ...))

PS: I don't think opencog support `...`

Basically they have a DSL to declare graph templates to execute pattern
match against them, just like we do in scheme with lists using ice-9 match.

Maybe one can do the following against a given PKG:

- If PKG has perl as dependency replace it with perl-5
- Compute new input of PKG: recurse and replace inputs with the returned 
value
- Return new-pkg (which can be the same as PKG if none of its ancestors 
have perl input).

I think that you look for an API where the transformation is not always 
about the inputs, isn't it?

WDYT of my rambling?



[3] here be dragons: http://wiki.opencog.org/w/VariableNode & 
http://wiki.opencog.org/w/SatisfactionLink_and_BindLink