Re: An alternative to possreps

From: David BL <davidbl_at_iinet.net.au>
Date: Thu, 9 Jun 2011 02:49:42 -0700 (PDT)
Message-ID: <2fe3c67f-600b-41af-8891-3de142e7982c_at_y27g2000prb.googlegroups.com>


On Jun 8, 6:01 pm, Erwin <e.sm..._at_myonline.be> wrote:
> On 7 jun, 10:05, David BL <davi..._at_iinet.net.au> wrote:
>
>
>
> > Yes, but that is not a problem. Let Ellipse be a "dummy type". If
> > you're interested in a subtype Circle of Ellipse then you can simply
> > declare Circle as another dummy type. I'm assuming you can declare
> > subtype relationships between dummy types. In my approach you use
> > these declarations:
>
> > type Ellipse;
> > type Circle;
> > Circle isa Ellipse;
>
> > I consider types like Circle and Ellipse to be defined by their
> > operators. In that sense there is no problem treating all types as
> > "dummy types".
>
> In TTM, and more precisely in the inheritance model, the term "dummy
> type" is quite precisely defined. A type is a dummy type if and only
> if it is defined as being a UNION type that has no possrep of its
> own. The term is relevant only within the context of the inheritance
> model. And even then, it could be questioned just how relevant,
> because it still remains the case that "all types are first-class
> citizens".

Fair enough. The term "dummy type" is mentioned briefly in Date's Introduction book in reference to a type named PLANE_FIGURE but there's no detailed discussion of what a dummy type is. On the surface it appeared analogous to my approach, and I proceeded to guess at its meaning in TTM.

> You seem to be confused in the area of "manifesto-with-inheritance" (M
> +I) vs. "manifesto-without-inheritance" (M-I). In M-I, there is no
> speaking of dummy types because there is no I. Yet, there must still
> be a way to let the user define types.

It would be more accurate to say I'm ignorant of these matters. I don't own a copy of the TTM book.

> Now, your argument seems to be that between the following two, (b) is
> better for some reason :
>
> (a) stating the definition of a type in terms of what its constituent
> components are, and deriving from that which "constructors" (/
> selectors) will exist, including which preconditions (/constraints/
> predicates) apply to the values of the arguments passed onto such
> "constructors",
> (b) not stating the type per se, but instead stating what
> "constructors" exist (including preconditions etc.), and deriving from
> that that the type exists.
>
> I see no difference. Except that (b) gives me the feeling that if I
> were a user using those types/operators, it might be harder for me to
> discover which types/operators are available to me. Just a feeling.

I think there are some interesting differences to consider. Consider the following wikipedia article on algebraic data types:

    http://en.wikipedia.org/wiki/Algebraic_data_type

This has an example of a recursive type named 'Tree' written in Haskell as follows:

data Tree = Empty

          | Leaf Int
          | Node Tree Tree

Assuming Tutorial D doesn't balk at recursive types, it would appear this could be written equivalently as follows:

    TYPE TREE

        POSSREP EMPTY {}
        POSSREP LEAF {INTEGER}
        POSSREP NODE {LEFT TREE, RIGHT TREE};

However, my understanding is that each POSSREP has to be "complete" in its ability to represent all values of the type, so this is wrong. Instead it would need to be written like this:

    TYPE TREE IS EMPTY UNION LEAF UNION NODE;     TYPE EMPTY IS TREE POSSREP {};
    TYPE LEAF IS TREE POSSREP {INTEGER};     TYPE NODE IS TREE POSSREP {LEFT TREE, RIGHT TREE}; I find this proliferation of types rather extravagant. I'm not suggesting it is inconsistent - indeed thinking of EMPTY as a subtype of TREE is agreeable to me, but I would rather think of empty, leaf and node as operators that return Tree values, as in the approach I described in a previous post:

    type Tree;

    Tree <--- empty;
    Tree <--- leaf(Integer);
    Tree <--- node(Tree left, Tree right);

In Prolog (which supports algebraic data types very nicely) empty, leaf and node would be functors of arity 0,1 and 2 respectively. It seems unwieldy to treat functors as types.

I note that in my approach I need unification to express useful algorithms, whereas Tutorial D instead must use type testing, which is cumbersome but probably a better fit for procedural code.

> Furthermore, if types are to be defined in terms of their
> "constructors", then you cannot carry over that MO to what TTM calls
> "dummy types", because those types simply _do not have_ a
> "constructor" (one of their own, I mean). So just like TTM, you need
> to introduce a second way for defining types, which is, exactly as in
> TTM, by declaring the UNION that makes up the type.

Subtype declarations encompass union declarations. E.g.

    type PlaneFigure;

    type Circle;
    Circle isa PlaneFigure;

    type Polygon;
    Polygon isa PlaneFigure;

Any existing type is open to new ways of representing values of that type in two ways:

  • by declaring operators that return values of that type
  • by declaring new subtypes

I don't require completeness of representations for any type. In fact many types (e.g. Real, Point, Circle, Polygon, PlaneFigure) are uncountably infinite. Obviously it cannot be assumed operators are surjective in general.

> > That might be true in D&D, but I see no reason for that in principle.
> > Operators are sufficient for allowing (logical) representations of
> > values (using nested expressions of operator invocations). E.g. the
> > operator
>
> > Circle <--- circle(Point centre, Real radius) on radius >= 0;
>
> > allows for circle values to be (logically) represented without any
> > POSSREP.
>
> Does it ? I see here that a circle has a Point component called
> 'centre', that it has a Real component called 'radius', and that the
> value of the 'radius' component is subject to a certain constraint.
> How is that different from what a possrep achieves ? I say the
> possrep is still there, even if there is no keyword 'POSSREP' in the
> syntax. (Note that if your complaints are about the _syntax_, then by
> definition you are only criticising the Tutorial D language, not the
> manifesto itself.)

At the moment I can only say that my issues are with the presentation of the topic given in Date's Introduction book, so I cannot say whether they are specific to Tutorial D or encompass the Manifesto as well.

Would D&D require information to be given on which operators are surjective, in order for only those operator declarations to serve as "possible representations"?

> (To pursue that latter remark a bit further : D&D also insist that
> 'relational assignment' must be supported in order to comply with the
> manifesto. In my project SIRA_PRISE, I "don't do that", so to speak.
> I don't allow the user to use the ' := ' token in between a relational
> variable on the LHS and a relational expression on the RHS. Yet, D&D
> still agree that I do comply with the manifesto, because I do offer
> Insert+delete+multiple assignment, which is perfectly equivalent to
> "assignment as such".)

How is your project going? I've had a look at your web site a few times, but not read it in any detail. Have you implemented a DBMS that supports ACID transactions? Did you develop your own storage mechanism (e.g. based on ARIES)?

> > You appear to be contradicting yourself in saying both:
>
> > (a) "this issue must be addressed by defining the proper type"; and
>
> > (b) the arguments to LS(FLOAT) must satisfy a certain predicate.
>
> (a) was an _assumption_ of mine of what D&D's answer would probably be
> if your questions/objections/remarks were put to them directly. It is
> a valid solution to the problem, but I agree it might not be the most
> practical one in every circumstance. BTW, it is not forbidden to join
> the TTM discussion list and throw your questions/proposals in there.
>
> Regardless : the "business rule" that the argument to an LN()
> invocation must be strictly positive, still applies no matter what.
>
> Do you think the difference is more than merely psychological whether
> that rule is stated as a "precondition" in an operator definition, as
> a "possrep constraint" in a type definition for POSITIVEREAL, or (to a
> lesser extent) just documented as a few lines of open-source code that
> raise the IllegalArgumentException if and when needed ?

I'm not sure. I guess my problem at the moment is that POSSREPS in Tutorial D make this issue a bit harder to think about. I see that constraints can be declared both inside POSSREPS and outside, and they overlap in purpose with defining restrictions on the domains of operators, restrictions on the possible values of a type, and defining the equality operator. For various reasons I find my approach easier to think about, just because ultimately types are only "knowable" through the operators, and in my approach that is all that one declares. The entry barrier for DBMS implementations is very low by allowing all operators to be defined by the implementation (and not necessarily generated automatically by the DBMS based on the schema).

> > These problems don't exist in the approach I outlined. E.g. assuming
> > Integer is already defined, one can define Rational like this:
>
> > type Rational;
> > Integer isa Rational;
> > Rational <--- rational(Integer n, Integer n) on d != 0;
> > Rational <--- divide(Rational q, Rational d) on d != 0;
> > etc
>
> Which rationals are integers and which aren't ?

It is implied by the equality operator (just as in Tutorial D, I might add).

It is possible for a language to define the equality operator at the logical level of discourse, and I think it would be very interesting to study how that could work. Alternatively it is defined by the implementation just like any other operator.

In chapter 5 of his Introduction book Date gives an example of implementing the equality operator on the POINT type, but states that equality can be defined by the implementation.

> In TTM, the system can know because the system is given the type
> constraint that answers precisely that question, as a part of the type
> declaration (mind you, always supposing it were possible to begin with
> to have the integers as a subtype of the rationals).

The constraint expressed on CIRCLE such as

    CONSTRAINT THE_A(ELLIPSE) = THE_B(ELLIPSE) tells you which subset of the supertype corresponds to the subtype. However it doesn't tell you which representations of the supertype equal which representations of the subtype. Therefore I find it a cumbersome approach, because the mapping between the representations has to be specified as well.

An alternative which seems superior to me is to specify how a given subtype representation such as circle(R,C) is mapped to a supertype representation like ellipse(R,R,C). This defines both the constraint and the mapping between representations, and suggests unification. I suspect it makes life easier for the implementation.

> How does the system know this in your approach ? Is there a separate
> operator to be declared and implemented called 'isInteger(Rational
> x)' ?

I think it's appropriate for operators of the form is<T1>(T2) to be declared implicitly by subtype declarations. Received on Thu Jun 09 2011 - 11:49:42 CEST

Original text of this message