From: pcg@aber.ac.uk (Piercarlo Grandi)
Newsgroups: comp.object
Subject: Re: O.M() versus M(O) notation
Date: 14 Aug 92 17:07:01 GMT
	<__5mtrq.objsys@netcom.com>
Reply-To: pcg@aber.ac.uk (Piercarlo Grandi)
Organization: Prifysgol Cymru, Aberystwyth

On 13 Aug 92 01:58:32 GMT, objsys@netcom.com (Bob Hathaway) said:

pcg> There is, I am afraid, the usual fuzziness as to what the word
pcg> "type" is intended to mean: a denotation, an implementation, a
pcg> declaration?

objsys> Type is well defined.

Really? I see the word 'type' used with very different referents by
different people at different times. At some of these times I get a
strong suspicion that they themselves are not clear as to what they are
talking about.

objsys> In ASU's Compilers, type is defined as "the type of a construct
objsys> matches that expected by its context" and includes checking that
objsys> an operator (and perhaps method) is applied to a compatible
objsys> operand(receiver).

This is the kind of definition expected in a compiler writer's book. It
is highly related to the notational (it refers to "construct"s,
"operator"s and "operand"s, which are syntactic entities) aspects of a
program. Here you seem to define 'type' as 'type as declared/defined in
a program text'.

objsys> No mention is made of implementation since type systems only
objsys> deal with types.

Hardly surprising! If 'type systems' were dealing with blondes, than
that would be news!

objsys> Kim and Lochovsky in OO Concepts, Databases and Applications

A particularly badly written and hopelessly fuzzy book. I urge everybody
to read it, just for the experience! (Loan it from your library! Don't
buy it! Don't reward such works!). After reading this book you will
start to think that my postings are as well written and thought out as
Gettysburg's address, by comparison.

objsys> clearly
        ^^^^^^^
An adjective that seems out of context here, somehow.

objsys> distinguish between the superficial difference between type and
objsys> class and define type purely as specifications.

Of what? Of the underlying algebra? Of the syntax used for the type
description?

objsys> So "In the presence of dynamic binding it is (in general)
objsys> impossible to determine statically the class of a variable, but
objsys> with the appropriate type rules we can still perform
objsys> type-checking."

Another lot of meaningless, self referential verbiage. One could rewrite
it as

	"In the presence of type checking with deterministic type rules
	it is in general appropriate to perform..."

or any other permutation of this fine collection of buzz words, and the
meaning would not change.

objsys> They go on to give examples but this sort of definition (as also
objsys> quoted from Booch in my last posting) is *so* common I think it
objsys> already has been adopted as a standard.

Ah, such fumbling with buzzwords is all too common, it is virtually a
standard. Insight is not a standard instead; last year there were these
two guys, a well known Professor, and a well known Consultant, that had
never realized that objects (except in actor based languages) are indeed
(implemented as) closures, something that is not just 'obvious', but
also is clearly and incontrovertibly described in a first year
programming textbook from MIT... Bah.

objsys> Class (or whatever) defines implementation and type defines an
objsys> abstract specification.

Ah, here we get (from you! not from any of the famous authors above) a
more clear distinction: here you seem to be saying that the referent
for the word 'type' is the formal description of a mathematical entity,
of an algebraic structure, and that 'class' is the (corresponding?)
implementation. This is quite different from the definition given in the
AWU book on compilers, that you seem to agree with above.

This is open to many observation:

* why have 'type' have as referent the formal specification of a
  mathematical entity and not the mathematical entity itself? You
  seem to be saying that 'type' Unsigned is not the algebra of modulo
  2^N naturals, but a formal specification of that algebra. There can be
  many different formal specifications for that algebra. Which one is
  meant by 'type' Unsigned?

* Why use 'type' do refer to the underlying mathematical entity, or its
  formal specification? In virtually all existing languages the keyword
  'type' refers to the syntax defining an algorithmic description of the
  underlying mathematical entity. This is bound to be confusing, as in
  "are you talking about 'type complex = record re,im: real end;' or
  about the 'type' Complex (which is quite a different thing
  semantically!".

* If 'class' refers to the implementation of a 'type', does it refer to
  the interface or to the code behind that interface or to the
  assertions that decorate ? They are all 'implementation'! And if it
  refers to all of them at the same time, how can I distinguish between
  those orthogonal aspects? 

objsys> Perhaps this is a clue to the solution of the age old proverb:
objsys>		Why not concrete data types?
objsys> Types can be viewed as abstract data types, and classes (or
objsys> whatever representational construct) can be viewed as concrete
objsys> ones!

More meaningless/fuzzy verbiage...

pcg> In cases where they they are needed, writing a specification and
pcg> getting it right is a hard job.

objsys> How so?  I don't see that its any harder than writing the class
objsys> specification.

Ah surely; an argument could be made that actually they are the one and
same thing, otherwise the 'class' is not a faithful algorithmic
representation of the corresponding 'type'

objsys> Just define what's required.

pcg> It's that "just" that drives one crazy. Writing proper specifications
pcg> is often *harder* than writing the corresponding code, and longer.

objsys> Perhaps we're confusing terminology;

Ah, that's one of the few sure things in this discussion.

objsys> it appears to me that writing class specifications and type
objsys> specifications are not much different.

Ah indeed, and both are fiendishly difficult things. Just try to write a
*full* formal specification for a B-Tree 'type'.

objsys> Perhaps you're discussing the greater difficulty posed by
objsys> creating both kinds of specifications verses that of creating
objsys> the class/rep implementation?

Probably yes, indeed.

pcg> The trouble that many people have is that they don't define their
pcg> terms precisely. The confusion between type as denotation and
pcg> representation and syntax is rampant. Probably you are right to
pcg> suspect that Booch is not very clear about it himself, not just
pcg> "mortals".

objsys> I think Booch's definition is correct but IMHO he blew it by
objsys> combining the two in his presentation, hence the real confusion.
objsys> Hopefully we may have cleared up this confusion, at least in
objsys> this newsgroup.

Well, that's quite optimistic.

objsys> Type (specification) defines an abstract interface

Ah no, here you are changing your mind again! Or maybe I misread you
above: you seemed to say that 'type' is the formal specification
describing a mathematical entity, now you ssaying it is the
specification of an abstract *interface*? I am confused: does 'type'
refer to interfaces (something that belong in programs) or semantics
(something that belong in mathematics)?

objsys> and Class (or whatever representational/implementation
objsys> device as appropriate) defines the concrete structure of an
objsys> object.

So 'class' is only the structure of an object, not the implementation of
operations on it?

pcg> Again, while I agree with the meaning, some linguistic difference:
pcg> I find slightly disturbing to talk of object type and class. Maybe
pcg> one should say 'type denotation' or semantics instead of 'object
pcg> type', and 'type declaration' instead of 'class' (class syntax is
pcg> just one of the possible syntaxes used to declare a type).

objsys> No, type and type systems are independent of implementation.  I
objsys> think this distinction is very important from both a compiler
objsys> and applications point of view.

But the compiler never sees any of 'type' and 'type system'! The
compiler only sees interfaces and implementations! Or, at best,
assertions that decorate them and are derived from specifications.

pcg> There is absolutely no reason to believe that structural reuse
pcg> opportunities need to happen in a hierarchical fashion like with
pcg> inheritance.

objsys> Sure there is.  We do it all the time; its called
objsys> classification.

Yes, but all hierarchical taxonomies are inappropriate, in the sense
that they always cause bad classifications. Just consider the Unix
filesystem; one is forced to choose between thse two organizations:

	c_compiler/bin c_compiler/bin ada_compiler/man ada_compiler_man
	bin/c_compiler bin/ada_compiler man/c_compiler man/ada_compiler

when neither is really appropriate; the man page for the ada compiler is
both a man page and part of the ada compiler package, and neither aspect
prevails. Similarly in many data design instances. Hierarchical database
models have fallen from favour because they forced people to do data
designs that were strict taxonomies, that are inappropriate almost
always, except for 'parts explosion' situations.

objsys> Once wants the ability (my favourite peeve) to independently
objsys> reuse interfaces, specifications, and implementations, and a
objsys> general purpose algebra for all of thse things.

objsys> Some systems with inheritance may not provide this but I don't
objsys> see any inherent restrictions.

Well, except that you insist otherwise that type systems should be
hierarchical. Isn't that a fairly large inherent restriction?

objsys> Another good question: lets define type as an abstract
objsys> specification,

Here we are back to 'type' as 'abstract specification', not 'interface
specification'. Still, I am puzzled by your insistence that 'type'
should refer to the specification itself, and not the mathematical
entity described by the specification.

objsys> class as an implementation construct, and abstract class as an
objsys> incomplete implementation construct.

What do you mean by 'complete' and 'incomplete' here?  You may be
referring to the fact that unfortunately in most (improperly designed)
OO languages one cannot describe indepdently interfaces and
implementations, so 'classes' force you to define both together, and
'abstract classes' are 'incomplete' in the sense that they stand in for
a proper and separate interface definition facility. If so, I think it
stinks...

objsys> To what extent are these constructs interchangeable?  Can or
objsys> should types be used as abstract classes?

Here I might be lost completely. Certainly the specification of a
mathematical structure is in a different domain from a language idiom
like an abstract class, and the two are not interchangeable at all. Have
you gone back to the definition of 'type' as 'interface specification'?
If so, I can only emphatically agree that 'no' is the answer to your
rhetorical question:

objsys> If so, should abstract classes exist at all?

objsys> Should classes without their implementations be usable as types
objsys> (grab their public interface only) to allow for multiple
objsys> implementations?

I agree with some of sentiment here...

objsys> What do you think???

... but surely it would be better if interfaces, specificationa nd
implementations could be defined _separately_, and there existed
notation to combine them with each other into a 'class'.  So a 'class'
would be built out of quite separately defined interfaces,
implementations and specifications, and only if all three elements were
present (possibly empty, but this should be documented) it would be
instantiatable.

pcg> * given a deque interface, derive stack and queue interfaces by
pcg>   _subtracting_ the appropriate elements;

objsys> there's only theoretical arguments against it.

Mathematicians do this all the time. We can do it as well. Especially in
finite domains typical of computing.

objsys> You could also include the deque as a member of stack and queue
objsys> and simply don't redefine the subtracted interface.  This should
objsys> be the preferred solution.

Why ever preferred? Probably it would be a very inappropriate, and
redundant, description of a stack. A stack is not *implemented* using a
deque, it is an entity on the same abstraction level as a deque, only
not as general. Both a deque and a stack may *share* (reuse) certain
elements of their interfaces, implementations, assertions, simply
because the underlying algebras are largely overlapping. This should be
directly reflected in the program text.

pcg> * given two deque implementations, one with lists and the other
pcg>   with resizable arrays, attach one to a stack interface, and one to
pcg>   a queue interface;

objsys> Given an abstract dequeue class with two implementation classes,
objsys> List_Dequeue and Array_Deque, why not derive Stack from
objsys> List_Dequeue and Queue from Array_Dequeue.

But I want to derive the stack and queue *interfaces* from the *deque*
interface (or viceversa of course!), and then _independently_ attach
(parts of) any of the deque *implementation*s to either. Speaking of
'derivation' is absolutely misleading and appropriate; 'derivation' is
just a particular (and hierarchical) way to do reause. Here I want to be
able to directly reuse separately defined components and mix and match
them to build 'classes'.

I think the alternatives you are giving are just hacks; yes, some things
can be done even with popular inheritance based languages, but forcing
things. Compare 'abstract classes' with pure 'interface specifications'.
In the former case you are tempted to use the word 'incomplete class',
in the latter you know that an interface specification is part of class
definition, but is a fundamentally different entity.

pcg> * given a specification of a variable size deque, derive from it a
pcg>   fixed size deque specification by adding the specification of a size
pcg>   constraint;

objsys> Just adding a constraint?  Sounds like behavioural inheritance a
objsys> la DRAGOON.

Yes, again, little bits of what I am saying appear here in there, in
more or less contrived forms. Modula-3 and to some extent ADA and other
have got some form of interface specification, and DRAGOON and Eiffel
and a few others may have got some form of assertion reuse. But we are
talking of contrivances, not of clear, clean, direct descriptive
devices. Programming is already hard enough in the substance, to afford
distraction caused by inappropriate terminology of notation.

objsys> This may be lacking in most OO notations but I don't see it as a
objsys> fundemental flaw in inheritance.

Well, if by 'inheritance' you mean 'a fully general (including all
the "obvious" set operations like union, intersection, ...) way to
independently reuse separately defined interfaces, implementations,
assertions' then we are entirely agreed. My point precisely.

Unfortunately you have expressed, if I interpreted what you said
correctly, the notion that 'type systems' should be hierarchical,
because classification systems should be hierarchical.  This is quite a
more restrictive statament. Most of the verbi^H^H^H^H^Hliterature on
this subject tends to agree with you (there are even several articles on
formalization of inheritance, which only have little more merit than
those on formalization of exception handling).

All in all, I think that just problems with buzzw^H^H^H^H^Hterminology
loom so large in any such discussion that it is hard to make any
progress. Still trying, though.

Just for entertainment, I have collected here some of your statements on
what the word 'type' stands for.

objsys> Class (or whatever) defines implementation and type defines an
objsys> abstract specification.

objsys> Type (specification) defines an abstract interface [ ... ]

objsys> Can or should types be used as abstract classes?

objsys> [ ... ] lets define type as an abstract specification, class as
objsys> an implementation construct, and abstract class as an incomplete
objsys> implementation construct.

objsys> In ASU's Compilers, type is defined as "the type of a construct
objsys> matches that expected by its context" and includes checking that
objsys> an operator (and perhaps method) is applied to a compatible
objsys> operand(receiver).

objsys> [ ... ] type and type systems are independent of implementation.



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