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.

This is achieved using a DDL which can be regarded primarily as a
language for writing a schema which describes what values can legally
be recorded in the database and this is achieved without any
dependence or even reference to physical representations. In that
sense the types are purely abstract and this approach maximises
physical independence. It should be understood that implementations
sometimes impose additional limitations on what values can be
physically represented, but these are regarded as deficiencies of the
implementation, even if they seem inevitable. The DDL is illustrated
with examples below.

Types are fully abstract in the sense that they are simply declared
and not defined in terms of possible representations. For example:

type Bool;
type Natural;
type Integer;
type Rational;
type Real;
type Point;
type Circle;
type Ellipse;

Note that there is no difficulty declaring a type like Real even
though it is uncountably infinite. At this stage the ways of logically
or physically representing values of these types is unspecified and
therefore open ended.

Let us write T1 isa T2 to declare the fact that T1 is a subtype of
T2. This means every value of type T1 is also a value of type T2. It
follows that any operator with an argument of type T2 can also be
passed a value of type T1. For example, the schema may declare:

Natural isa Integer;
Integer isa Rational;
Rational isa Real;
Circle isa Ellipse;

As for types, consider that all operators are treated in a fully
abstract way as well. i.e. the signatures are declared but no
implementations of the operators are defined. This is because as far
as a DDL is concerned we are concerned with (logical) data
representation and not with defining a computation to be performed on
a computer. For example:

Natural <--- 0;

Real <--- add(Real, Real);
Real <--- subtract(Real, Real);
Real <--- mult(Real, Real);
Real <--- divide(Real x, Real y) on not(y = 0);
Real <--- pi;
Real <--- sin(Real);
Real <--- cos(Real);

Circle <--- circle(Point centre, Real radius) on radius >= 0;
Point <--- centre(Circle);
Real <--- radius(Circle);

Operators can have arity 0, allowing for literals like false, true, 0,
pi or e. To the extent that all operators are declared but not
defined, operators of arity 0 can be regarded as representing
otherwise unspecified abstract values.

Operators can declare constraints (i.e. a domain on which the operator
is defined). For example, divide(Real x, Real y) is only defined on
nonzero y.

Covariant return types
----------------------

Consider these operator declarations:

Natural <--- add(Natural, Natural);
Natural <--- mult(Natural, Natural);

Real <--- add(Real, Real);
Real <--- mult(Real, Real);

It would appear that operator overloading is supported (e.g. 'add' is
declared on both Natural and Real). The purpose here is not to
redefine behaviour but rather only to express covariant return types.
This appears useful if implicit downcasts are not permitted.

Operator expressions
--------------------

The schema in effect defines a grammar for nested expressions of
operator invocations. Each legal expression is a literal meaning it
denotes a value. For example from the following two operators

Natural <--- 0;
Natural <--- s(Natural);

we can represent any natural number starting from 0 and using the
successor operator s as many times as required:

1 is logically represented by s(0)
2 is logically represented by s(s(0))
3 is logically represented by s(s(s(0)))
etc

We regard these expressions as /logical representations/ of values, to
distinguish them from physical representations on some physical
medium. For example the value with a logical representation
s(s(s(0))) may be physically represented in computer memory as a
single byte with the binary value 00000011, or in countless other
ways.

The following two operators provide two different ways to select
geometrical point values (and can be compared to POSSREPS, although
here we make it very clear that we are strictly talking about
alternative logical representations):

Point <--- cartesian(Real x, Real y);
Point <--- polar(Real modulus, Real arg) on modulus >= 0;

The fact that regardless of physical representation we can always
retrieve the "components" of these two representations is reflected in
the following operators:

Real <--- x(Point);
Real <--- y(Point);
Real <--- modulus(Point);
Real <--- arg(Point);

Note that we don't designate some operators as "selectors" and some
not.

One can imagine a representation of rationals using a pair of
integers:

Rational <--- rational(Integer n, Integer d) on not(d=0);

In this case unless we specify a canonical representation for the pair
of integers there are no corresponding operators to retrieve numerator
or denominator from a given rational.

As another example,

circle( cartesian(0,0), s(0) )

denotes the unit circle.

Notice that these expressions only represent values and there is no
implied calculation to be performed. We don't assume the operators
map to executable functions in the implementation, e.g. which allow an
expression like 2*3+1 to designate a calculation to be performed on
binary representations of numbers. All such concepts are irrelevant
at the logical level of discourse.

A schema is necessarily incomplete on uncountable sets like the reals.
i.e. there must exist reals for which no logical representation
exists. Nevertheless the schema may allow for expression of some
useful countable subset that occur in particular applications (e.g.
ruler and compass geometry) but are not simply the rationals or even
the algebraic numbers. The schema ends up precisely defining the set
of values that can be expressed. Even though the schema only ends up
allowing for a subset of the reals to be expressed, it may not be
appropriate to invent some name for it.

The logical representations form equivalence classes according to the
value that they represent. For example, the following expressions all
represent the integer 1:

s(0)
add(s(0),0)
subtract(s(s(0)),s(0))
radius( circle( cartesian(0,0), s(0) ) )

Since all expressions are literals, it can be assumed for example that
any boolean valued expression is either equivalent to 'false' or
'true' (but not both at the same time). Any natural number valued
expression is equivalent to exactly one expression of the form
s(s(...s(0)...)). In both these cases we have a concept of a
canonical form.

In principle the equivalence relation could be defined in some
language, entirely at an abstract level (i.e. just as for the schema,
without any dependency on physical representations). I find the idea
intriguing that once the equivalence relation has been defined we have
a basis for modelling computation on literals that generalises
arithmetic but is entirely divorced from physical representations.

Perhaps there are cases where the grammar and/or operators are so
complicated that determining whether two literal expressions are
equivalent is undecidable. This is a computational problem and
outside the scope of a DDL per se. It is a crucial consideration for
physical representations.

Physical representation
-----------------------

Ideally for each type T there are bijections between the following:

1) values
2) equivalence classes over logical representations; and
3) equivalence classes over physical representations.

Clearly this cannot be achieved on the reals. It seems best to regard
floats as representing ill-defined overlapping ranges of reals (which
means there is no mapping from reals to floats or vice versa).

It shouldn't be assumed that a schema forces the implementation to
directly represent nested expressions in a generic manner suitable for
arbitrary symbolic manipulation. For example the logical
representation of the unit circle given previously might be physically
realised using an instance in memory of a Circle struct in the C
programming language defined as follows

struct Circle
{
Cartesian centre;
float radius;
};

Union types
-----------

Since we have chosen to allow for uncountable types, we can for
example allow for the type Set<Point> which is associated with any set
of points on the 2D plane:

type Set<Point>;

and declare:

Circle isa Set<Point>;
Rectangle isa Set<Point>;

In a sense Set<Point> acts like a union type, which is "open" because
it can be a supertype for any number of types representing 2D shapes
added to the type system in the future. This type is useful for
expressing some operators that are uniformly available on all its
subtypes:

Set<Point> <--- intersection(Set<Point>, Set<Point>);
Set<Point> <--- union(Set<Point>, Set<Point>);
Set<Point> <--- difference(Set<Point>, Set<Point>);
Set<Point> <--- translate(Set<Point>, Real dx, Real dy);
Set<Point> <--- rotate(Set<Point>, Real theta);
Set<Point> <--- scale(Set<Point>, Real sx, Real sy);

E.g. we can then express literals like

rotate(
intersection(
circle(cartesian(0,0),1)),
translate(unitsquare,0.5,0.5)),
pi/4)

without declaring specific operators such as for the intersection of
circles and rectangles. This is an advantage of allowing uncountable
types.

We may also want to express closed union types. E.g.

type CircleOrRectangle;

Circle isa CircleOrRectangle;
Rectangle isa CircleOrRectangle;

The distinction being made here is that we don't expect new types to
declare themselves as subtypes of CircleOrRectangle.

The proposed DDL avoids syntactically distinguishing open and closed
union types because it separates declarations of types from
declarations of subtype relationships between types.

Elegant and orthogonal operators
--------------------------------

Uncountable types tend to allow more elegant and orthogonal operators
which are an advantage for data representation. For example, consider
the following two data types:

a) "idealised images" which are mappings on a domain which is the
entire R^2 plane, which is both unbounded and a continuum.

b) "digital images" which are mappings from a finite set of pixel
locations to a finite set of brightness or colour values, and allows
for a finite physical representation.

Consider rotation, scaling and translation operators on these two data
types. For idealised images these operators are simple and elegant. By
contrast on digital images they are extremely ugly. For example they
raise the question of how pixel interpolation should be performed
(e.g. nearest neighbour, linear interpolation etc). Pixel
interpolation also has to deal with special cases near the edges or
corners of the sampled image. Also these operations beg the question
of what bounding rectangle should be used to contain the result, and
what happens in areas in the result that aren't mapped to any part of
the original image. It is noteworthy that on digital images these
operators don't generally preserve information, and don't have nice
inverses. For example scaling an image by 0.5 then by 2 typically
results in pixel averaging.

On 2011-05-27, David BL <davidbl (AT) iinet (DOT) net.au> wrote:
I am beginning to think you are trying to solve a problem that doesn't
really exist.

<snip>
Well, so we can, but why do it in this context? You can't go back to
first principles in everything every time, not if you want to end up
with something usable.

<snip>
Aaaaargh! I think this is the point at which I ought to give up!

Eric

On May 29, 8:34 pm, Eric <e... (AT) deptj (DOT) eu> wrote:
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?

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?

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)?

4. Can preconditions be declared on operators? If so would it be true
to say it seems to overlap in purpose with CONSTRAINT declarations?

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?

6. Are covariant return types supported?

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?

8. Is it possible to add super-types to the built-in types?

9. Do TYPE and POSSREP definitions express more information than
simply declaring the existence of types, subtype relationships and
operators? If so what is contained in this additional information and
what is it for? How does one avoid repetition when specifying both
logical and physical representations for a given type, or is that not
an issue?


My proposal has the effect of treating specialisation by constraint as
simply part of the problem of defining equivalence classes on logical
representations. If the system leaves it up to the hidden
implementation to define the equality operator, the DDL is simpler.
For example, there is no need for the DDL to somehow express the fact
that for all radius R and centre C

circle(R,C) = ellipse(R,R,C)

Note that Date requires a definition of CIRCLE to have a constraint
declared like this:

CONSTRAINT THE_A(ELLIPSE) = THE_B(ELLIPSE)

My understanding is that many of the implementations inspired by TTM
have yet to implement subtyping by constraint. I think at the moment
it's reasonable to require implementations of user defined types to
define the equality operator rather than have it generated
automatically. This is probably a good approach in computational
geometry where data types can be rather complex (e.g. triangulated
surfaces) and manually written comparison operators are appropriate.


The purpose here was only to illustrate the idea that the declared
types, subtype declarations and operator signatures define a grammar
for logical expressions, where operator signatures are analogous to
production rules of formal language grammars. It was also a good
example to clarify the distinction between logical and physical
representations of values. Obviously in practise a system would
provide built-in types and allow for syntactic sugar for representing
literals like 100, 1.5e04, "hello world", {1,2,3}, [1,2,3] etc.

On 30 mei, 08:35, David BL <davi... (AT) iinet (DOT) net.au> wrote:
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.



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".



No comment. The discussion has been had on the TTM discussion list.
At quite some length. Nobody changed positions as a result of it.



Preconditions such as "the argument value for any LN(FLOAT) invocation
must be >=0" ?

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 !)



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.



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.



All types are first-class citizens. No distinctions between built-in
and user-defined types.

On May 30, 6:03 pm, Erwin <e.sm... (AT) myonline (DOT) be> wrote:
That makes sense, thanks.


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?


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.


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.


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.


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.


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
{
public:
// 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) {}

etc

private:
int n,d;
};

On 31 mei, 11:54, David BL <davi... (AT) iinet (DOT) net.au> wrote:
Not "in TTM". What prohibits this is "reality", I'd rather say.

If you're interested in a subset of T, then you can't define this
subset by means of UNIONs involving T.

And if you're interested in UNIONing things together because that
union somehow is of interest to you, then you still must be given some
things to union. Somewhere down the line, some non-dummy types must
be just given.

I didn't look at the details of your proposed approach because you
said yourself that it is neither more nor less powerful than TTM
possreps.



Not quite accurate. Selectors do not "have constraints". Possreps
do. As a consequence, of course whenever a selector invocation is
made, the arguments given must satisfy that constraint, or an
exception results. But I don't see how this is different from "non-
selector" operators such as LN(FLOAT) ! There too, the arguments
effectively passed must satisfy a certain predicate. I find it only a
psychological difference that in the case of selectors, the arguments'
predicate is declared as part of the construct that gave rise to the
existence of the selector operator, whereas in the case of "regular"
operators, that predicate is declared in the documentation, or in the
metadata, or in the worst case, it is merely implied by the operator's
implementing code.



No, one is not forced to do that.

OPERATOR FOO(X INT, Y INT) RETURNS ... ;
IF (X+Y)<=0 RAISE ILLEGALARGUMENTEXCEPTION("...");
/* note that dealing with exceptions, or how to raise them, is not
part of TTM */
....
END OPERATOR;



Completely agreed. But **Tutorial** D is for tutoring purposes
exclusively.

I've made this mistake dozens of times myself : so beware that you
DON'T take certain "properties" of the **Tutorial** D language, to be
prescribed properties of the Manifesto **per se**. Other D languages
can be totally different from **Tutorial** D, and still be a D (all
THAT takes is to conform to the RM (+IM) prescriptions+proscriptions
PER SE).

(I probably even made this mistake once again where I said that
"declaring a UNION type requires re-declaration of the constituent
subtypes". This is so in Tutorial D. But I don't think there is an
explicit prescription to this effect in the manifesto per se. Mea
culpa.)

Hence, the freedoms an implementer has to _deviate_ from **Tutorial**
D, really go quite far.



In the most recent book, "Database Explorations", Date argues that
integer numbers are not rational numbers. You should not take the
existence of a certain kind of correspondance between the _algebraic
structures_ "Z,+,*" and "Q,+,*" (the former is a 'subgroup' of the
latter, it is said) to imply that "the members of Z must be a subset
of the members of Q".

At any rate, the whole idea is also problematic in that :

- if you set up the super/subtype relationship without using a UNION
type, then declaring RATIONAL requires the existence of INTEGER
(otherwise RATIONAL's possrep cannot be defined), and INTEGER requires
the existence of type RATIONAL (_and_ the existence of operators for
RATIONAL, otherwise the type constraint for INTEGER in terms of
RATIONAL cannot be defined, but that type constraint will have to
involve INTEGER factoring, which requires the existence of type
INTEGER, etc. etc.)
- if you set up the super/subtype relationship by declaring an extra
type NONINTEGERRATIONAL (with a constraint that numerator is not a
perfect multiple of denominator), and then declare RATIONAL to be a
UNION type of INTEGER and NONINTEGERRATIONAL, then you'd still be in
trouble once you start defining operators such as rational division,
which is not the same operator as integer division, while the IM
prescriptions requires, essentially, that operators such as, e.g.
"DIVIDE(RATIONAL,RATIONAL)" and "DIVIDE(INT,INT)", are effectively the
very same operator if INT is effectively a subtype of RATIONAL.



Are they "outlawed" ? Did I say that in those words ?

On Jun 6, 9:26 pm, Erwin <e.sm... (AT) myonline (DOT) be> 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".


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.


As a minimum I'm suggesting POSSREPS are unnecessary and don't add
anything useful. But I'm now thinking my approach is more powerful
(see below on algebraic types).


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.

I took (a) to mean that at the logical level of discourse, the
argument to the natural logarithm operator would be something like
POSITIVEREAL instead of REAL and therefore there is no need to express
additional constraints on the operator, or the concept of exceptions
(which should be obvious anyway because that is an implementation
concept).

I'm not sure what distinction you're making when saying POSSREPS have
constraints whereas selectors don't. Either way some selectors have
conditions on their arguments that are not simply implied by the types
of the arguments. This is different from the case of the natural
logarithm operator that takes a POSITIVEREAL.

I take that to mean that one can choose to ignore explicit
specification of the constraint at the logical level of discourse. I
agree it is possible to do that.


Ok, good point.


I see many advantages in assuming the integers are a subset of the
rationals. What are the disadvantages?


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

I don't specify the order in which declarations like "Integer isa
Rational" shall appear. Therefore a "new" type can declare itself to
be a supertype of an "existing" type. I also allow for covariant
return types on operators like divide as discussed in the original
post.

This leads me to think about recursive types. E.g. a binary tree
containing integers at the leaf nodes:

type Tree;
Tree <--- empty;
Tree <--- leafnode(Integer);
Tree <--- internalnode(Tree left, Tree right);

I don't think POSSREPS allow for expressing "algebraic data types" (as
they are sometimes called in functional programming). It appears my
approach is inherently more powerful than POSSREPS.


No on the contrary you suggested otherwise when saying "No
distinctions between built-in and user-defined types". My point is
that I think the ability to add supertypes to pre-existing types
should be one of the objectives of the language design. If D&D added
it as a prescription then it appears Tutorial D would fail that
prescription.

David BL wrote:

Either the operators define the equivalent of possreps or the type model
doesn't really describe ellipses and circles. So what are you trying
to achieve?

On Jun 7, 9:49 pm, Bob Badour <b... (AT) badour (DOT) net> wrote:
I'm suggesting the operators define the equivalent of possreps.
Possreps are redundant.

The equality operator has a role to play in this. The possrep
constraint which specifies which representations of ellipses are
circles is instead defined indirectly by the equality operator (which
defines which representations of ellipses are equal to some
representation of a circle).

David BL wrote:

How do operators express that center is held invariant when changing
only radius? And vice versa?

Or perhaps more clearly with complex number types: How do operators
express that phase is held constant when changing only magnitude? And
vice verse. Even though both realPart and imaginaryPart change?