Morphisms between graphs

A morphism from G₁ to G₂ is a (total) mapping from the nodes of G₁ to the nodes of G₂.If m₁ is a morphism from G₁ to G₂ and m₂ is a morphism from G₂ to G₃, one by functional composition can define m₁+m₂, a morphism from G₁ to G₃.Likewise, one for any G can define the morphism id_G as the identity mapping.

Remark: If one had defined morphisms to be partial map-pings, garbage collection would be modeled.The theory is being somewhat complicated by such an approach – in sec-tion 4.10 we briefly sketch how to pursue this line.

When illustrating morphisms by means of figures, we will often garbage collect some of the nodes (so one can concen-trate on the essential parts of the morphism).It should be rather easy to “complete” such figures.

We will be interested in several kinds of morphisms, e.g. specializations and reductions, to be motivated briefly:

• A specialization from G₁ to G₂ models that G₁ is “more general”

than G₂.For instance, the graph (represented by the term) f(v) (v being a virtual node) is more general than the term g(f(3),3), as

✒✑

1) v has been instantiated to 3 in the latter graph 2) in the latter graph, some context (g) is included.Accordingly, as depicted in figure 4.1, there is a specialization s from G1 to g(f(3),3) where G1

is the “sum” of f(v) and the graph g(v₁,3). s maps e.g. v into 3 and v₁ into the bottommost application node.

• A reduction fromG₁ toG₂ models thatG₁ “is reduced to”G₂ during the process of evaluating G₁.For instance, one could imagine that f(x) →x + x is a clause in the source program.Then there will be a reductionr₁ from f(x)to x + x, as depicted in the left part of figure 4.2. Here r₁ maps the application node in the former graph into the topmost application node in the latter graph.On the other hand, if f(x) →x is a clause in the source program then the situation is as depicted in the right part of figure 4.2, where there is a reduction r₂ from f(x) to x.Here r₂ maps the application node in the former graph as well as the virtual node v into the virtual node in the latter graph.In both cases, the f-node has been implicitly garbage collected.

Some notation: we say that a morphism m from G₁ to G₂ respects a node n iff the following holds¹: m(n) is the same kind of node (ac-tive/passive/virtual) as n; if n is passive then L2(m(n)) = L1(n) (hence also Ar₂(m(n)) = Ar₁(n)); and if n is active or passive then for all

1[Rao84] uses the terminology that mis a morphism atniff the last two conditions hold, i.e.

if labels and successors are preserved.

✒✑ is an isomorphism iff m is bijective and respects all nodes. ✷ It seems fair to say that if there is an isomorphism from G to G, then “G and G cannot be distinguished”.We say that G and G are isomorphic.

Definition 4.1.7 Let m be a morphism from G to G.We say that m is a homomorphism iff m respects all active and passive nodes. ✷ Lemma 4.1.8 Suppose h1 is a homomorphism from G1 to G2 and h2 is a homomorphism from G2 to G1, such that h1+h2 = idG₁, h2+h1 = idG₂.

Then h₁ and h₂ are isomorphisms. ✷

Definition 4.1.9 A reduction r from G to G is a morphism such that 1. r respects all passive and virtual nodes, and all partial applications.

2. r is injective on virtual nodes, i.e. r(v₁) = r(v₂) implies v₁ = v₂.

✷ The motivation for 1 is that one, during graph reduction, only performs

“non-trivial rewriting” on nodes which are “redices”.The motivation for 2 is that one cannot allow two distinct “holes” to be unified - if e.g. the first hole is a placeholder for a passive node and the second hole is a placeholder for a partial application, then a conflict will arise.

Definition 4.1.10 A specialization s from G to G is a morphism such that

1. s respects all active and passive nodes.

2.If s(a₁) = s(a₂), with a₁ = a₂, then a₁ and a₂ are partial applica-tions.

3.For all a in G there exists an a such that s(a) = a; for all p in G there exists a p such that s(p) = p; for all v in G there exists a v such that s(v) = v (this is a stronger requirement than surjectivity).

✷ Condition 1 is quite natural; and condition 3 is motivated by our choice to model “G is more general than G” by the existence of a specialization from the sum of some G1 and G to G, rather than by the existence of a specialization fromGitself toG(cf. lemma 4.1.18). Concerning condition 2, the technical motivation is that if s(a₁) = s(a₂), a₁ = a₂ and a₁ not a partial application, then – as a reduction r does not necessarily preserve active nodes which are not partial applications – r(a₁) is “out of control”

and may differ “significantly” from r(a₂), thus making it impossible to define the pushout².Pragmatically, the motivation is that it will never pay off to “split” an active node – e.g. when looking at a graph f(gx)(gx) where the two occurrences of gx are shared, it will do no good to look at a more general graph where the two occurrences are not shared.

Observation 4.1.11 It is easily seen that ifais a (genuine) partial appli-cation and r a reduction, then r(a) is also a (genuine) partial application.

If s(a) is a partial application then so is a – but a is not necessarily a genuine partial application, even if s(a) is.

On the other hand, if a is a genuine partial application so is s(a) – but s(a) is not necessarily a partial application, if a is only a (non-genuine)

partial application. ✷

Fact 4.1.12 For all G, id_G is a morphism belonging to all kinds (i.e. a reduction, a homomorphism etc).An isomorphism belongs to all kinds of morphisms.All kinds of morphisms are stable under +. ✷ Proof: The claims concerning id_G are trivial; so is the fact that iso-morphisms, homomorphisms and reductions are closed under +.Now let us see that specializations are closed under +:

2Cf.the remarks [Rao84, p.11], to motivate why restrictions somewhat similar to condition 2 have been given.

1 and 3 are trivial.For 2, assume that s₂(s₁(a)) = s₂(s₁(a)) with a = a.Since s1 satisfies 1, s1(a) and s1(a) are active.If s1(a) = s1(a), we froms₁ satisfying 2 can conclude thata anda are partial applications.

If s₁(a) = s₁(a), we from s₂ satisfying 2 can conclude that s₁(a) as well as s₁(a) are partial applications, and hence (by observation 4.1.11) also

a and a are partial applications. ✷