From: pcg@aber.ac.uk (Piercarlo Grandi)
Newsgroups: comp.object
Subject: Re: O.M() versus M(O) notation
Date: 18 Aug 92 16:17:44 GMT
	<__5mtrq.objsys@netcom.com> <PCG.92Aug14170701@aberdb.aber.ac.uk>
	<1992Aug15.124149.28538@m.cs.uiuc.edu>
	<PCG.92Aug16184526@aberdb.aber.ac.uk>
	<DOUG.92Aug16200024@monet.ad
Reply-To: pcg@aber.ac.uk (Piercarlo Grandi)
Organization: Prifysgol Cymru, Aberystwyth

On 17 Aug 92 04:00:24 GMT, doug@monet.ads.com (Doug Morgan) said:

doug> Of the popular OO books I have looked through, I only
doug> remember Meyer's OOSC as even hinting at the subject with any sort
doug> of internal consistency and abstraction.

Ah, yes. One may or may not agree with Meyer but at least he has
somewhat clear ideas. I even somewhat liked the similar (and competing)
book by Cox, even if the slant is very much different.

pcg> type denotation:	the algebraic structure; [ ... ]

pcg> I would personally use 'type' alone for the 'type denotation', [
pcg> ... ]

doug> Your personal usage of "type" is better than "type denotation."
doug> If an adjective is ever needed it should probably be more like
doug> "denoted type" or "type denoted by such and such notation."

Agreed, agreed. I was tempted this way, it's quite clearer, but then I
preferred 'type denotation' because it can be shortened to 'denotation',
which is less overloaded than 'type', and also rhymes well with
'implementation' and 'specification' (I was also tempted to use
'notation' for 'interface' or 'protocol' or 'signature', but 'notation'
is already too overloaded).

doug> (A running system as mutating specification?)

A good description: in the sense that each state of a system is
characterized by a predicate, and a specification is the 'union', or
generator, of all such predicates.

doug> I would extend this to say that at any one time an instance of a
doug> class should also denote some type.  That is, with the proper
doug> context instances and specification should both denote the same
doug> abstract types.

I would be hugely surprised if this were not so! :-) Actually this is a
good description of what goes on anyhow.

With one warning though: most languages and their implementations
actually short circuit this by tagging, directly or indirectly, values
(aka class instances) with a 'typing' code, that stands in lieu of the
type denotation, which is hard to represent anyhow in the material world
:-).

This is a bit like the rule in some languages (like Ada) that 'type a =
real' and 'type b = real' are two different and incompatible 'types',
even if so far* their denotation is the same, because 'a' and 'b' are
different tags.

	*However usually one then defines different sets of additional
	operations on 'a' and 'b', so their denotations diverge.

Other languages (like Algol 68) synthetize tags and assign one to all
different 'types' that have the same canonical representation. This
alternative is usually called 'name' vs.  'structure' based 'type'
equivalence (and is a very hard choice; with Pascal it has changed every
few years...).

I used to call this very common technique 'typing', short for 'typecode
tagging' (but I agree with the objection I have been made that this is
not the best erminology, but I am still trying to think of a better
one), and the choice it forces between name and structural equivalence
is a big nuisance, as if had to choose between 'eq' and 'equal' in Lisp
systems, and blurs the distinction between a 'type' and its
representation (which may well be another 'type', but the two are not
then equivalent in any sense).

pcg> [ ... separation of interface/implementation/specification is good
pcg> but not done in today's OO languages ... ]

doug> I think the goal is wonderful.  A few questions:

doug> O Do you have or know of any proposals for a system implementing
doug> this principle?

I am thinking of a proposal, but currently my main research interests
are elsewhere, so the thing has been down my TODO list for years now.
On the other hand I know of several partial, but useful, realization of
this not quite new idea:

* There used to be this library sw to catalogue of implementation
components, called Calico, developed for the MDL OOL, done by people at
the Programming Technologies Group of the MIT LCS. Calico was, and still
is, probably the neatest and most effective example of a module
repository, and one designed to support one of the neatest OO languages
to date, MDL. It can also be argued that one of the main reason for the
design of Multics shared libraries and dynamic linking was
implementation reuse on a massive scale. Also, there is some work on
programmer's assistants that is about recurring program idioms, etc.

* At the University of Wales (ask rjg@aber.ac.uk) there is this thing
called CDL (Component Description) which is a language to describe
interfaces and that offers notation for a full algebra on interfaces. It
is similar to IDL (Interface Description), a bit nicer; the issue of
interface description languages is fairly common in IPSE research, as it
is quite important for building module repositories. Some languages
offer some restricted form of interface reuse, for example Modula 3.

* Several people working on VDL and Z have had this idea of creating
'modular' specification, that is to have specifications that can be
assembled more or less arbitrarily by mix/match of other specifications.
Eiffel attaches snippets of specification to interfaces/implementations
and subjects them to derivation. There used to be in the seventies some
modular languages, like Alphard, which attempted to merge in some way
specification into code (interface and implementation).

doug> O How would this new system handle the fact (?)  that
doug> specifications are most often handled off-line on paper or in
doug> someone's head?

By giving everybody a laptop with GNU Emacs, LaTeX and the relative VDL
or Z editing/formatting modes :-).

More seriously: by being humble, making use only of specification
snippets, a la Eiffel. The experience with Alphard and the like, which
promoted heavvy merging of specification into code, has not been
entirely positive, as one has then the double burden of maintaining both
spec and code, and in synch. This might be useful in itself, but often
it is mostly redundant (as the gap between a function and its intension
often is not that great, an observation that 'logic' or 'functional'
programming people have applied often improperly, and that 'constraint'
programming technology is mostly about).

doug> How would it deal with specifications it can't really "understand"
doug> well enough to transform to appropriate machine code. [ ... ]

Well, practically speaking, you punt. Ah right, you say, that's
cheating. Indeed:

doug> And even if you do them right, today's compilers and systems
doug> wouldn't be able use them.

But at least it helps having the facility there, even if it is neither
completely implemented (the state of the art on theorem provers and
program synthesis is not exactly brilliant) nor all powerful. Just a
little bit of statement decoration with assertions helps a lot, just as
it does help in many cases to decorate with 'typing' assertions (aka
'declarations') entity definitions.

doug> O An example?  How about seeing how the new system would address a
doug> question that pops up on this group every month or two.  The
doug> question is always how to organize the inheritance of a mutable
doug> square class instance with three slots and a mutable rectangle
doug> class instance with four slots.

doug> Now, how would this new system help clarify the notions of
doug> abstract types (rectangle and square),

In no way at all! That's a problem for algebrists to solve. What is the
optimal conceptual orthogonal base for an algebra that encompasses both?
It's not a problem for the language designer. The task of the latter is
to provide clean, general notation to _describe_ such things.

doug> class instances denoting specific types, and different constraints
doug> on the mutation of instances?

Ah, ah. Here I think that really the problem is not 'reuse', which is
(hopefullyl) maximized by the holy trimurti I mention so often, but is
one of that 'typing' vs. 'type' problem I have mentioned above.

The question here really is that existing systems by and large do
something really horrible, they assign over time the same typecode tag
to values beloning to different type denotations. Suppose that I wrote a
simple application to tell me the area code of a place, and this read a
file containing a table whose entries were:

	struct areacode { unsigned code; char place[256]; };

and then I want to extend this application to internal phone calls; I
could easily change the source to:

	struct areacode { unsigned country, code; char place[512]; };

but now the 'areacode' tag has a different type denotation! And the
application will fail when reading the old file, of course. The problem
exists, and is especially hard, in OO languages with some sort of
workspace or persistency, e.g. Smalltalk. It is a huge problem
everywhere, for example in data design and database implementation, and
is called 'data reorganization'.

What independently reusable interface/implementation/specification can
do is to make the cost of reorganization lower, by maximing reuse. For
example with databases reorganizations are usually hidden thanks to
'view' definitions. Now these are really interface and implementation
reuse, with fairly general algebras being possible.

Database people would find it incomprehensible to have views restricted
to hierarchical derivation. *Both* joins and projections, (and
dynamically computed fields), are really required in many views.

doug> O Could the system simultaneously and cleanly treat class
doug> instances themselves (if there are such things as classes and
doug> instances) as an interesting abstract type?

Well, here we are again strictly speaking outside reuse, and back to the
little applied distinction between what I call 'typing' and 'type'.
Class instances are, strictly speaking, just representations of the
'typing' information about a value. They are really internal data
structures of the implementation (this point of view is taken for
example in Self).

Since 'typing' is important for practical reasons (just as 'eq' is, and
for the same reason for which computers don't have content addressable
memories), maybe exposing 'typing' information helps, maybe in the same
way that having the catalog part of the database helps (and is required
by Codd for example for relational databases). In that case surely the
ability to describe in my favourite way the representation of the meta
information contained in 'class objects' does help.

doug> I think this second denotation (mentioned above) is needed to
doug> solve many efficiency, meta-class, and OODB-type problems.

Not easy problems. The database people, who have been having a go at
data dictionaries/catalogs for ages, still find it hard. Having a nice,
flexible metamodel, and the ability to represent it with a model in the
database itself, and they know how hard it is to do on the fly
reorganization of both database and catalog structure with no semantics
hazards.

However at least it helps to have a crisper terminology, cleaner
insights, and more general and orthogonal notation that maximizes reuse.
--
Piercarlo Grandi                   | JNET: pcg@uk.ac.aber
Dept of CS, University of Wales    | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.uk
Newsgroups: comp.object