| << Prev | - Up - | Next >> |
Implementation of normalization.
solveConstraint.pl: View Download
What remains to be implemented now is the normalization of constraints (see Section 6.2.2). It is done in two steps: First, parent normalization is performed, and secondly redundant dominance edges are removed. The predicate normalize/2 (in solveConstraint.pl) calls the respective predicates. It accepts a constraint graph as input, and returns the normalized graph.
normalize(Usr,Normal) :-
liftDominanceConstraints(Usr,Lifted),
elimRedundancy(Lifted,Normal).Parent Normalization
The predicate liftDominanceConstraints/2 (from solveConstraint.pl) recursively goes through all dominance edges. If there is a dominance edge dom(X,Y) and the node Y is a child of the node Z via a solid edge, the dominance edge is lifted and becomes dom(X,Z). Here is the code:
liftDominanceConstraints(Usr,Lifted) :-
Usr = usr(Ns,LCs,DCs,BCs),
mySelect(dom(X,Y),DCs,RestDCs),
idom(Z,Y,Usr),!,
liftDominanceConstraints(usr(Ns,LCs,[dom(X,Z)|RestDCs],BCs),Lifted).
liftDominanceConstraints(Usr,Usr). The predicate mySelect/3 removes the dominance edge dom(X,Y) from DCs and the list RestDCs now contains the remaining dominance edges. Then, idom/3 (see cllsLib.pl) succeeds iff the node Z immediately dominates the node Y, i.e. there is a solid edge from Z to Y. If this is the case, the parent normalization is continued with a constraint that is like the input constraint. Except for the list of dominance edges which now contains all but the removed ("lifted") edge, plus the new edge dom(X,Z). In other words, dom(X,Y) has become dom(X,Z).
In Exercise 6.6, you can try to reimplement this predicate using a simple member check instead of select.
| << Prev | - Up - | Next >> |