Now that the PPL is no longer limited to ordinary convex polyhedra and many new abstractions are finding their way to the library, I believe that the distinction between syntax and semantics is fundamental. According to this view, the PPL would support a set of "syntactic objects" (variables, linear expressions, constraints, congruences, generators, grid-generators, ... and finite systems of such things) and a set of "semantic objects" (polyhedra, grids, bounded-difference shapes, octagons, bounding boxes, ..., powersets of the above, ..., linear programming problems, ...).
I think this distinction must be kept as clear as possible. We are already doing it, to some extent, but the fact that some syntactic objects are directly used in the implementation of semantic objects has caused some of our syntactic objects to expose some inner details of their role in the implementation of semantic objects. To clarify, this program
#include <ppl.hh>
using namespace Parma_Polyhedra_Library; using namespace Parma_Polyhedra_Library::IO_Operators; using namespace std;
int main() { Variable x(0); Variable y(1); Variable z(2); Linear_Expression e = x+y+z; cout << e << " has space dimension " << e.space_dimension() << endl; e -= z; cout << e << " has space dimension " << e.space_dimension() << endl; return 0; }
prints
A + B + C has space dimension 3 A + B has space dimension 3
whereas it should print
A + B + C has space dimension 3 A + B has space dimension 2
The same sin is committed by Constraint, Generator and so forth. I believe we should stick to one, unambiguous definition of "space dimension" and be consistent with it throughout the library. We know what "space dimension" is for a semantic object: it is also clearly stated in the documentation. We need to find a similar definition that works for syntactic objects (such as the minimum space dimension for which the object makes sense) or conclude that the notion of "space dimension" should be reserved to semantic objects only and find another name for this other concept. Feedback is welcome on all these points. Ciao,
Roberto
Roberto Bagnara wrote:
[...]
The same sin is committed by Constraint, Generator and so forth. I believe we should stick to one, unambiguous definition of "space dimension" and be consistent with it throughout the library.
If a Constraint/Generator has to become a syntactic object, then several things have to be changed, besides the space dimension issue. Currently, a Constraint is an affine half-space or an affine hyperplane, i.e., a semantic object. This allows for the automatic normalization of the variables' coefficients and of the inhomogeneous term, as well as for semantic comparisons. Therefore, if I understand what you mean, we should maybe have both a semantic and a syntactic constraint (with appropriate naming schemes).
For instance, considering polyhedra, the semantic constraints should correspond to, say, Hyperplane, Closed_Halfspace and Open_Halfspace. Their syntactic counterpart is given by linear constraints (or affine constraints, if we want to be terminologically strict) having rational coefficients.
Similarly, the semantic generators will be (automatically normalized) lines, rays, points and closure points, all having integer coefficients and (for points and closure points) a divisor. Their syntactic counterparts are given by (possibly un-normalized) vectors having rational coefficients.
We know what "space dimension" is for a semantic object: it is also clearly stated in the documentation. We need to find a similar definition that works for syntactic objects (such as the minimum space dimension for which the object makes sense) or conclude that the notion of "space dimension" should be reserved to semantic objects only and find another name for this other concept. Feedback is welcome on all these points. Ciao,
Roberto
When considering systems of semantic objects, all the object in a system will have the same space dimension. They can be reordered and modified as long as the semantics of the system stays the same. We can add/remove redundant objects in the multiset.
In contrast, a system of syntactic objects is a list of syntactic objects: should reordering and/or semantics-preserving modifications be allowed on it? What is the "space dimension" of this object? The maximum of the "space dimensions" of the objects it contains?
To keep it short, I think that this change of perspective has to be carefully considered, one facet at a time, striving for maximum consistency and clarity. It will take some time to foresee all of the possible consequences of any design change in this respect ...
Ciao, Enea.
Enea Zaffanella wrote:
When considering systems of semantic objects, all the object in a system will have the same space dimension. They can be reordered and modified as long as the semantics of the system stays the same. We can add/remove redundant objects in the multiset.
Systems of semantic objects seem redundant to me: a finite system of semantic objects is a semantic object, and I see little value in calling it with two names. In other words, a system of hyperplanes and halfspaces is a polyhedron: Constraint_System outght to be another thing. Notice that I am not insisting on a religious view of "syntax" (as usual, we do not distinguish between syntactically different constraints defining the same affine half-space so that, for example, x >= 2 and 2x >= 4 are the same constraint).
In contrast, a system of syntactic objects is a list of syntactic objects: should reordering and/or semantics-preserving modifications be allowed on it?
We can negotiate. But this does not seem a big problem to me. Reordering: why not? Normalization: why not? Let us take an "abstract syntax view" and forget about all the syntactic sugar.
What is the "space dimension" of this object? The maximum of the "space dimensions" of the objects it contains?
Yes.
To keep it short, I think that this change of perspective has to be carefully considered, one facet at a time, striving for maximum consistency and clarity. It will take some time to foresee all of the possible consequences of any design change in this respect ...
Yes, but it cannot take ages: work on the foreign interfaces has to start soon. In order to do this, we must come up with an abstract view of our objects (syntactic and semantic ones) that has a chance of surviving the additions we have already made (grids, bd-shapes, powersets) and that we are about to make.
However, before attacking Constraint_System, let us start from the easy example in my message: is
A + B has space dimension 3
somehow defensible?
I don't know if my thoughts here are relevant - this discussion seems a little strange to me! So I may be missing the point.
I thought that all objects seen by the user had a semantic interpretation and whatever information that we returned was semantic - in the context of the object itself. We do not want to give the syntactic representation in the PPl as the meaning of the object.
I feel that we should not try and decide if this object semantic or syntactic but what the semantics of the object are.
polyhedra, grids, BDS are clear to me - they denote points in some n-dimensional space.
What about a constraint system? Is this a set of hyperplanes - or should it have the same semantics as the polyhedron it describes? Probably the latter - but I am not really sure of the issues.
and so on
then linear expressions could have the semantics of the expression as an algebraic construct so that A + A is the same as 2*A - but then we should not say they have a space dimension; or, maybe the semantics could be the vector of the coordinates - then we can talk about the smallest space in which the vector could have a meaning - but then why say A + C has space dimension 2 while A + B has space dimension 2? Also the inhomogeneous term would not fit into this picture.
Ciao, Pat
On Wed, 1 Feb 2006, Roberto Bagnara wrote:
Enea Zaffanella wrote:
When considering systems of semantic objects, all the object in a system will have the same space dimension. They can be reordered and modified as long as the semantics of the system stays the same. We can add/remove redundant objects in the multiset.
Systems of semantic objects seem redundant to me: a finite system of semantic objects is a semantic object, and I see little value in calling it with two names. In other words, a system of hyperplanes and halfspaces is a polyhedron: Constraint_System outght to be another thing. Notice that I am not insisting on a religious view of "syntax" (as usual, we do not distinguish between syntactically different constraints defining the same affine half-space so that, for example, x >= 2 and 2x >= 4 are the same constraint).
In contrast, a system of syntactic objects is a list of syntactic objects: should reordering and/or semantics-preserving modifications be allowed on it?
We can negotiate. But this does not seem a big problem to me. Reordering: why not? Normalization: why not? Let us take an "abstract syntax view" and forget about all the syntactic sugar.
What is the "space dimension" of this object? The maximum of the "space dimensions" of the objects it contains?
Yes.
To keep it short, I think that this change of perspective has to be carefully considered, one facet at a time, striving for maximum consistency and clarity. It will take some time to foresee all of the possible consequences of any design change in this respect ...
Yes, but it cannot take ages: work on the foreign interfaces has to start soon. In order to do this, we must come up with an abstract view of our objects (syntactic and semantic ones) that has a chance of surviving the additions we have already made (grids, bd-shapes, powersets) and that we are about to make.
However, before attacking Constraint_System, let us start from the easy example in my message: is
A + B has space dimension 3
somehow defensible?
participants (3)
-
Enea Zaffanella -
P M Hill -
Roberto Bagnara