Re: An alternative to possreps

From: David BL <>
Date: Tue, 31 May 2011 02:54:47 -0700 (PDT)
Message-ID: <>

On May 30, 6:03 pm, Erwin <> wrote:
> On 30 mei, 08:35, David BL <> wrote:
> > On May 29, 8:34 pm, Eric <> wrote:
> > > On 2011-05-27, David BL <> wrote:
> > > > The purpose of this post is to outline an alternative to POSSREPS for
> > > > distinguishing between a type and the physical representation of
> > > > values of that type on a system.
> > > I am beginning to think you are trying to solve a problem that doesn't
> > > really exist.
> > It's an alternative to possreps. I think it's neither more nor less
> > powerful.
> > However it's clearly much simpler. I think possreps raise more
> > questions than my proposal. Here are some off the top of my head
> > after reading Date's Introduction book:
> > 1. Do union types (and particularly dummy types) contradict Date's
> > statement that every type has at least one possible representation?
> > How does it fit in with the claim that the set of values of a given
> > type must be well defined?
> I think it's important to realize that there is a distinction between
> RM prescriptions, and IM prescriptions.
> There is "Manifesto _without_ type inheritance", and a "Manifesto
> _with_ type inheritance", so to speak.
> RM prescriptions constitute the "Manifesto _without_ type
> inheritance", and some of them need a great deal of refinement in the
> "Manifesto _with_ type inheritance". The requirement that "the set of
> values of a given type must be well-defined" is one such, methinks.
> Also keep in mind that the inheritance part is not a "required" thing
> to support for implementations. So all the RM prescriptions are
> relevant as they are, for an implementation that does not support type
> inheritance, but for one that does, some of them are superseded by the
> "refined" versions defined by the IM prescriptions.

That makes sense, thanks.

> > 2. What are dummy types for? Can dummy types have subtype
> > relationships declared amongst them? If so what happens with
> > CONSTRAINT declarations? Aren't these always required when expressing
> > subtype as specialisation by constraint?
> If I recall well, dummy types are precisely all the union types that
> do not have a possrep of their own.
> If you accept UNION types, then no, CONSTRAINTS are not always needed.
> A constraint is needed if a type is given, and you want to define a
> subtype of that type in a predicative way. The type constraint being
> precisely, your predicate on the given type.
> A constraint is not needed if two types are given (say, type POINT and
> type TEMPERATURE), and you want to create the UNION type ('SILLY') of
> the two. POINT and TEMPERATURE do become a subtype of SILLY, but
> neither of them 'becomes defined in a predicative way in terms of
> SILLY'. Both of them remain defined "as they are".

Is there anything in TTM that prohibits one from making every type a dummy type? Would that make it essentially the same approach which I've described?

> > 3. Must POSSREPSs have a canonical representation? What happens if I
> > don't want the selector RATIONAL(numerator,denominator) to have a
> > constraint on the two given integers apart from a nonzero
> > denominator? What happens if I can much more easily define
> > equivalence than a constraint that forces a canonical representation?
> > Is equality implicitly defined at the logical level? If so what
> > exactly are the assumptions that allow for the definition of logical
> > equality to be implied? Alternatively is it up to the implementation
> > to define the equality operator (just like the implementation of any
> > other operator)?
> No comment. The discussion has been had on the TTM discussion list.
> At quite some length. Nobody changed positions as a result of it.
> > 4. Can preconditions be declared on operators? If so would it be true
> > to say it seems to overlap in purpose with CONSTRAINT declarations?
> Preconditions such as "the argument value for any LN(FLOAT) invocation
> must be >=0" ?

Yes. Eiffel uses that term. I think "domain" would be a more conventional term, but the database community has often used 'domain' for 'type'. I would treat ln(0) as undefined.

> D&D's position here can be summarized, I think, as "this issue must be
> addressed by defining the proper type".
> (And note that this approach does not require type inheritance ! Even
> without type inheritance, it is not impossible to define a (distinct)
> type STRICTLYPOSITIVEFLOAT. If you can _prove_ to them that this
> approach is unacceptably impractical, please please do !)

I agree it seems impractical, and selectors are treated differently to other operators (only selectors have constraints).

Also, what happens with non-separable constraints on operators with multiple arguments? E.g. foo(x,y) is defined on x+y > 0. Is one forced to make it into a unary operator on a type which can express that constraint on its POSSREP? The effect is to define a selector which can handle the constraint.

> > 5. Can additional POSSREPS be added to a type without modifying the
> > original declaration of that type? Can a new supertype be added to
> > the type system without needing to modify the definitions of all its
> > subtypes?
> No and No.
> As for the first "No" : I don't see an impractical difference between
> "just adding an extra possrep", and "re-issuing the entire type
> declaration which now includes the extra possrep".
> As for the second "No" here, this has been discussed on TTM and nobody
> changed positions.

A type system could be so large that these restrictions create difficulties. For example a client of some third party library wants to declare one of their types to be a supertype to one of the types defined in the library.

> > 7. For the types, operators and subtype relationships that comprise a
> > type system, the way in which it is expressed using POSSREPS, dummy
> > types, free standing operators and so forth doesn't appear to be
> > uniquely defined. Is there a recommended methodology? What makes one
> > POSSREP more desirable than another? What is the purpose of defining
> > multiple POSSREPS? Is it just a way to provide more operators?
> > What's wrong with adding free standing operators instead? In practise
> > would POSSREPs be expected to provide hints for implementations or is
> > that not really an intention?
> Hmmmmmmmmm.
> The way I see it, types are a "given thing". They are defined by the
> type implementer (which is the system itself, or the provider of an
> "external package", or the user itself, or ...), and the TYPE
> statement is a way to describe its properties. There is no logical
> difference between THE_ operators that are provided as an inherent
> part of a type definition, or similar operators that are implemented
> "independently". But note that in addition to creating THE_
> operators, possrep components also create pseudo-variables (and
> independent operators don't do this) :
> VAR POINT P := ... ;
> THE_X(P) := new x coordinate value;
> THE_THETA(P) := new theta value;
> As for the "implementation hints" question, I think not, except if the
> TYPE statement is used by a user as the means for expressing his
> requirements toward a type implementer, which is not an inconceivable
> scenario.

I'm not sure what to think about pseudo variables. How useful are they? There are many issues to consider when updating a database because it interacts with so many things (e.g. update semantics, constraint checking, locking, concurrency, data replication). The semantics of update operations is particularly relevant to Operational Transformation which I'm interested in. I would say pseudo variables aren't generally compatible with OT.

> > 8. Is it possible to add super-types to the built-in types?
> All types are first-class citizens. No distinctions between built-in
> and user-defined types.

I would say it may be impractical if the answers to Q5 are no. The built-in types are probably analogous to a third party library which users have no control over.

For example, if the system provides a built-in type INTEGER but not RATIONAL, then when someone implements the latter in terms of a pair of INTEGER they also want to declare RATIONAL to be a supertype of INTEGER, so that integers can be passed into all their operators that take RATIONAL. This is awkward if they have to edit the system provided definition of INTEGER.

From an implementation perspective I cannot see a good reason to outlaw adding supertypes to pre-existing types. E.g. it is easy to emulate in C++

class Rational

    // Allows implicit conversion from int to Rational,
    // which is like declaring Rational to be a
    // supertype of int.

    Rational(int x) : n(x), d(1) {}



    int n,d;
}; Received on Tue May 31 2011 - 11:54:47 CEST

Original text of this message