Google Summer of Code

Massimo Dentico m.dentico at
Fri Jun 10 10:25:38 PDT 2005

"Robin Green" <greenrd at> wrote:

> > So, you implement a common protocol (interface) for *all* your collection
> > types and you end up with... what? If it is sufficient general then this
> > protocol is no more powerful than the Relational Algebra or the Tuple/Domain
> > Calculi (this is not exactly true, RA is not Turing-equivalent on purpose).
> That is a crucial difference. Therefore it _is_ more powerful.

You don't know what you are speaking about: RA is not Turing-equivalent
to avoid not terminating operations (infinite loops), because end-users
and application programmers can formulate arbitrary queries and too much
power in this case is dangerous. It is an engineering/HCI trade-off.
Remove this retrictions and you and up with so-called "deductive databases".

> No, the values semantics does not determine whether a Set is a Bag.
> Only the operation semantics ultimately determines that.
> Kiselyov defines a Bag in this article as "an unordered collection of
> possibly duplicate items".
> But this is insufficiently precise. This definition does not include
> any *operations*. Without that, you don't know whether the operation
> called "add" will add everything, add only things that match certain
> criteria (like "not already in the collection"), or do something crazy
> like delete everything.
> To talk meaningfully about whether one OO type is a subtype of another
> OO type, we must unambiguously specify the operational interface of both
> - that is, all those operations which will be present as public methods,
> constructors, destructors or attributes (properties) in those classes.
> Anything less is handwaving.

A straw man here. Of course, the example does not specify pre/post conditions
and invariants (your "contracts") to remain simple.

If you properly specify pre/post conditions and invariants the difference
lay in values/pointers semantics. You cannot escape this. See below.

> [long rant cutted]

A Set is a special case of a Bag and so is a Circle wrt an Ellipse,
period. OO is supposed to mimic the application domain faithfully..
so why is it not able to render this subset relation properly?

If you give up with pointer semantics (or no object identity, no aliasing;
there are subtle differences, see the paper about Kaleidoscope below)
there are no problems with subtyping and supertyping (subsets and supersets).


Part 1:
Part 2:
Part 3:
Part 4:
Part 5:
Part 6:

Also, read this paper about Kaleidoscope, "Constraints and Object Identity":

especially "6.1 Object Identity Not Semantically Significant"
in "6 Some Plausible Alternative Designs".

> [cutted]

> > Do you let
> > your end users to do this and write procedural code to print a simple,
> > not pre-programmed, report?
> No, you provide code to help them. They should not have to write loops
> and things themselves.

Yes, of course: you assign the work to a busy programmer when power
users can do it with the right tools (RDBMS and reporting tools).

> > Do you present your objects to the user and
> > say "look, this is the interface".
> The objects' interfaces can be as low-level or as high-level as you like.
> You can have a method called selectCustomerWithName(String). No problem.
> You can even have a SQL-style query language. You can even have a wrapper
> that presents the prevaylent system as a virtual SQL database to the world.

Yes, of course: any sufficiently complicated C++ or Java program with
Prevalence will contains an ad hoc informally-specified bug-ridden slow
implementation of half of a DBMS... just to paraphrase Philip Greenspun's
Tenth Rule of Programming.

> [.. and other nonsense like this cutted]

I must invoke Date’s Incoherence Principle here: it is not possible
to treat coherently that which is incoherent... and a corollary:
life is too short.

> > Do you understand that you are constructing, with your "librify it",
> > "what is the problem", a DBMS, bit by bit?
> Yes. An OODBMS, which I prefer to an RDBMS.

Done in the past. Failed.

> I predict that OO languages will go one better than RDBMSs.

Hierarchical and network DBMSs where obsoleted by SQL DBMSs,
in the 1980s, even if SQL is not faithfull to the relational
data model. OODBMSs where a fad between the late 1980s and
the early 1990s. We are in 2005 and SQL DBMSs are predominant,
in spite of their deficiencies beacuse are better of their
competitors anyway (but SQL standards can be instrumental to
erode this advantage).

> Eventually, they will not merely "error out" on constraints violations
> like RDBMSs can, but they will actually model-check a program to prove
> that it is incapable of violating any integrity constraints. (That's my
> main research interest.) Beat that!

I don't need to beat anything. You cannot statically check something
that does not exist yet: an arbitrarly constraint can check values of
one time-varying table (relvar) aginst the values of another time-varying
table or you need to check constraints when a user arbitrarly manipulate

Of course, the more you can statically check the better. But you cannot
statically check everything in a dynamic system, at least not with the
same precision as a dynamic check (not enough information, you end up
with an estimate). Well, this dynamic vs static checking is a false
dichotomy: it is better not to fix the time when you check.

Very *ironically* researchers in program analysis and model checking
are realizing that a Relational Algebra interface to their tools (BDDs
to be specific) simplifies things greatly, see point 4. under the
section "Now, the evidence" here:

This is enough and I WILL STOP HERE, sorry.


Massimo Dentico

More information about the TUNES mailing list