Re: Object-relational impedence

From: S Perryman <>
Date: Wed, 12 Mar 2008 08:54:42 +0000
Message-ID: <fr85ot$uio$>

Marshall wrote:

> On Mar 6, 9:27 am, S Perryman <> wrote:

>>You regard "X-oriented" as something for which the facilities to support
>>X are provided at a fundamental level (like arithmetic ops, CAR/CDR in
>>Lisp etc) and not built (by whoever) from the fundamental constructs of
>>a prog lang.

>>Fair enough.

> Right. If we consider *potential* built constructs, and we are
> speaking of general purpose programming languages, then
> right away all languages collapse into a single category.

> We might make some allowances for languages whose standard
> library contains specific constructs, however. We might reasonably
> classify some functional languages that make extensive use of
> map, filter, and fold as being at least modestly list-oriented,
> despite the fact that their list constructs are really recursively
> defined union types. But it's probably better to consider the
> recursively defined type together with the higher-order function
> constructs as being the axiomatic signature of such languages.

I wouldn't consider it so, but it does no harm in debate to do so.

> Another important reason to consider the fundamental constructs
> of a PL is so that we can treat the PL as an axiomatic system.
> To me, the most interesting thing one can do with code is
> *reason* about it. This is why type systems are interesting
> (and "dynamically typed" languages not so much.) It's also
> part of why the relational model is so interesting. And it's
> why OOPLs don't hold my interest so much any more;
> their axioms are complicated and often weak.

Which "axioms" in particular cause you pain ??

M>Virtually no languages have primitive support for anything like a
M>collection. SQL and SETL and a few others; that's it. There are
M>some languages that were designed from the start with *list*
M>processing in mind: lisp (and I should probably also mention the
M>APL family here.) There are some *very* interesting things
M>in there, but not things I would say could be strictly described
M>as set-oriented.

>>I take a slightly different view in that I obviously have the need
>>for various collection types, and support for a Relational "calculus"
>>to use on those collections. I also need support for collections of >>ADTs in particular.

> The collections question is quite interesting: Lists, maps, bags,
> sets, tables, trees. It is apparent after only a modest amount
> of study that maps, sets, and tables are thoroughly and beautifully
> handled with relations.

Collections should be deliberately vague. Insert and remove. Empty. Contains an item, how many occurrences of an item etc.

A set is a specific form of collection (contains 0 or 1 instance of any given element, insertion of a contained element has no effect etc) .

And so on.

> It took me a lot longer but I've reached
> the conclusion that lists fall in to the same category.

Sequences are conceptually a partial mapping of (Index,Element) tuples. Certain mappings being undefined (hence partial) .

> Trees no longer seem like a single category to me: there
> are what I call "statically structured" trees, for example
> Customers/ Invoices/InvoiceLineItems, and "dynamically
> structured" trees, such as a parse tree.

A tree is a specific form of graph.
Graphs are conceptually two sets with an invariant relationship
between the sets. Trees merely define additional invariants on those sets.

> Statically structured
> trees are are a particular strong point for SQL and also a
> strong point for the RM. Dynamically structured trees *can be*
> handled with the RM but I don't think it does as good a job
> as is done in, say, FP languages with union types and
> structural recursion. I conjecture that it may be possible
> to develop best practices and/or tiny extensions to the
> RM such that it does as good a job, but currently I'm
> leaning in the direction of thinking this will not be possible.
> I'm not completely thrilled with structural recursion, but
> I have yet to see anything better.

Is your issue with performance for things like breadth/depth traversal etc ??

>>If possible I would like the prog lang user to be able to construct
>>specific collections such as sets etc, and for the prog lang env to be
>>within reasonable performance of something that is designed for the
>>support of some one specific aspect (as Lisp is for lists etc) .

>>I think that FP is the paradigm that could possibly do this.

> An important aspect of the performance requirement is physical
> independence, something that is largely ignored in PL theory,
> sadly.

The separation of specification (interface) from implementation is something key to ADT theory. And for those prog langs (CLU, Modula-2 etc) that support one impl of each ADT per program unit, you have the independence.

However, the coming of OO (unintentionally) threw a spanner in the works. It became possible to have multiple *different* impls of one ADT used *concurrently* in the same program unit.

A rough analogy (that AFAIK is not supported in commercial systems) would be an SQL database that for some given table operates a B-tree for certain records in the table, hashing for others etc. And expects the performance for ops on the entire table to be the same whatever predicates are applied to the table.

> If we look at the mathematical universe, we usually encounter
> an extensional viewpoint. And if something is expressed
> intensionally, or algorithmically, mathematicians are free to
> immediately think of its extension, because they do not have
> to limit themselves to what is computable.

> On the other hand, if we look at the computable universe, we
> see more often the intensional viewpoint. And we are not
> free to immediately shift into extensional mode, because
> of the possibly-infinite, almost-certainly-prohibitive cost of
> doing so.

> The RM gives the best handle on the computably extensional
> viewpoint I have encountered. FP gives the best handle
> on the intensional viewpoint.

I would say that FP has a strong extensional viewpoint too, solely because it too is based on mathematical concepts (functions) .

Steven Perryman Received on Wed Mar 12 2008 - 09:54:42 CET

Original text of this message