From: johnson@m.cs.uiuc.edu (Ralph Johnson)
Subject: Re: O.M() versus M(O) notation
Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
Date: Sat, 15 Aug 1992 12:41:49 GMT

Piercarlo is right that there are many different definitions of the
word 'type', and that sometimes the same person will use several of
the definitions at once.  He also does a good job of enumerating the
different kinds of definitions.  I'd like to focus on one particular
distinction, between a mathematical object and a description of a
mathematical object.

pcg@aber.ac.uk (Piercarlo Grandi) writes:

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

Because all that we or our programs can manipulate is the formal
specification of a mathematical entity, and not the mathematical
entity itself.  The mathematical entity 'Integer' exists only in
our heads.  A formal specification of it can be observed by many
people, discussed, and manipulated.  The only way we can talk about
Integer is by giving a formal specification of it.  Thus, we tend to
call the formal specification 'Integer', too.  Although this might
be a mistake from a philosophic point of view, it seems to be a very
common one, and one that nearly all mathematicians make.  

For example, the lambda calculus crowd says that a type is a
set of values (a mathematical entity) and then they give a syntax for
specifying types and call such an expression a type!    It would be
better to call it a type description, I suppose, and maybe some of
them do.  It's been awhile since I've looked at those papers.

>* Why use 'type' to 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? 

Piercarlo is right that all of this is part of the implementation.  However,
usually only the code behind the interface is called 'implementation'.
Most languages don't support assertions that decorate the interface.
Thus, 'type' is usually taken to mean just the interface.  If a language
also supported assertions, as Eiffel does, then type would be interface
+ assertions.  (Note, however, that Eiffel defines type as interface +
assertions + implementation.)

'Type' is *also* used to mean some sort of mathematical object, though
not the nice and elegant ones that Piercarlo is looking for.  It means
the set of values (objects, in this case) that support the interface.
Thus, you can have a type of things that support +, -, /, and *, but
you can't specify the Integers modulo 2^N, because there is no way to
specify that adding 1 to itself 2^N times results in 0 (unless you had
assertions, of course).

In the OO community, claiming that classes and types should be
different usually is part of an argument that interfaces and implementation
should be seperated so that they can be reused seperately, and that
inheritance should be different from "can this object be used in place
of that object".  Bertrand Meyer is probably the chief opponent to this
view.  He says that one of the chief advantages of OOP is that it
*combines* interfaces with code, and that people who try to seperate
them are making a mistake.  Thus, it would be a mistake to think that
there is a concensus on this issue.

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

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

Bob is using 'type' as 'interface specification'.  I think he is fairly
consistent with this use, though he also uses it to refer to the set of
objects that meet the interface.

'Type' can mean
  a mathematical object -- all 'objects' that meet a specification
  an interface specification
  an expression that denotes an interface specification
  the data structure inside a compiler that represents an interface spec.

Moreover, I don't think it is fair to complain that someone that uses
several of these at once is being inconsistent, he is just blurring the
distinction between something and its referent that people always do.

I remember a short story (probably science fiction) in which there was
a line like: "My name is Jonathon Marks.  The name of my name is
Big Bill.  Call me Wally."  Also, his gun had a name, the name of
his gun had a name, and he called his gun something else.  This
seems to illustrate the problem well.  Does anybody remember the
author and title of this short story?

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

An abstract class is much more than just an interface specification.  It
also includes part of the implementation of the class, but it has some
'holes' in it that subclasses must fill in.  It is really a reusable
design for subclasses, not an interface specification.  Of course, in
languages without seperate interface specifications, people use abstract
classes to make a seperate entity in their program that is just interface.