[comp.lang.smalltalk] Smalltalk types

abbott@aerospace.aero.org (Russell J. Abbott) (08/30/89)

Sorry my previous message had the wrong subject line.  It really was
about types.

-- 
-- Russ abbott@itro3.aero.org

rad@aragorn.cm.deakin.oz.au (Robert Alan Dew) (09/01/89)

In article <56930@aerospace.AERO.ORG> abbott@itro3.aero.org writes:

>if an object has a response defined for a message sent to it, then it
>is of the "right type."  

Basically all objects produce a response to any message.  I guess you
want to exclude the doesNotUnderstand: response.

>In trying to understand what that means, I came up with the
>following.  I'm sure this must have been worked out properly somewhere.
>Does anyone know where?

Two suggestions:
 - forget about 'type'.
 - understand the following and there relationships
	class
	class instance
	message
	instance variable
	instance method
	class variable
	class method

	inheritance of
	  instance variables
	  instance methods
	  class variables
	  class methods
	
	self
	super

Anyway, if you want to think about types then class is the analogy.

>where a message is a message name, a list of the types of the
>parameters, and the type of the result, i.e.,
>
>Msg ::= Name(param1: Type1; param2: Type2; ..., paramn: Typen): Type

A message has:
 - a selector.  Which is a Symbol and does consist of the 'message names'.
			eg. #at:put:
 - arguments.  An Array containing the parameters.

A message does not return an object, therefore no result type is required.
For a better understanding separate messages from methods.
The method returns an object, the method is not restricted to returning
only one class of object.

Anyway, part of a system I am building includes a class where:
 - a variety of messages can be sent to instances of that class.
 - an instance of the class does not understand any of the messages, except
   for the doesNotUnderstand: and a few initialization messages.
 - the class instance was intended not to understand messages.  The
   response when an instance did not understand would be due to the
   method for doesNotUnderstand:. which was redefined in the class.

Robert Dew                                rad@aragorn.cm.deakin.oz
Department of Computing and Mathematics
Deakin University
Geelong 
Victoria
Australia 3217

alan@ux.cs.man.ac.uk (Alan Wills) (09/02/89)

Russ Abbott asks about Smalltalk and types, and wonders if his notion of
type in Smalltalk is cicularly-defined.  
Robert Dew suggests he forget about types in Smalltalk, and just
concentrate on thinking about classes.

Types *are* a useful concept for programming in any language, whether it
has its own notation for them or not; and types aren't (necessarily) the
same as classes.  To see why, first start with the idea that we want to
reason about programs --- to check that they do the right things, for
example.  Now there are a lot of ways of doing this reasoning, but it's
always a good start to separate out the easy bits from the hard ones.  The
notion of 'types' is a way of separating out some of the more
straightforward parts of the work.  Usually it's that part which can be done in
reasonable time by a compiler; but it can also be just a system used by the
programmer as a useful concept in reasoning --- even about Fortran, Lisp,
assembler code, or Smalltalk.

Traditionally (though not necessarily --- one could invent alternatives),
there are three levels at which you (or the machine) checks a program:
correct syntax (easy), type consistency (computable by the compiler), and
correct behaviour (depends on whether you know what the correct behaviour
is, and generally needs human brainwork to help decide).

Types are about the validity of a given value in a given context.  Cardelli
suggests that any set of values (with one or two restrictions for avoiding
Russel's paradox) can be regarded as a type, an `ideal type'.  Some
languages give us the means to describe some subset of all the possible
ideal types, and these are what constitute `types' in that language.  In
languages where there is not much provision for describing types, we are
free to invent our own (and it doesn't need to be based on any deeper
definition of what a type is, which is why Russ Abbott's definition is
fine). The main criterion for judging a definition of type is `does it give
us a good way of separating those values which will support the desired
behaviour of the program from those which won't, when they appear in a
given context such as an assignment or message-argument?' [Sorry, that was
a bit long winded!]

In many languages, the type system assigns a type to every context in which
a value could appear (assignment RHS, message-argument, record field, etc)
and also assigns a type to every value.  The system is such that you can
tell at compile time whether the types of the values in a particular
context will always match the context's type.  In more sophisticated
systems, each context has a set of acceptable types; or each value may belong
to more than one type.

This is all separate from the idea of a class in Smalltalk.  If your
personal definition of a type in Smalltalk is based on what class an object
is an instance of, then classes and types needn't be distinguished.  But
there's plenty of evidence that that isn't necessarily the most useful
definition.  Russ Abbott's one is a lot more useful: a type is the set of
objects that respond to a particular set of messages.  For example: say you
invent a new sorting agent; it will accept a list of anything, and hand you
back a sorted version; so long as the `anythings' understand `<'.  When you
document this goodie for distribution, you need to express that
restriction: and people who use your goodie need to check that wherever
they use it, all the list-members conform to this property.  The idea that
the set of all objects that understand `<' forms a type is clearly a useful
one here.

It would be nice if the inheritance system gave some guarantees about
subtyping: but in most OO languages, this isn't so.  Meyer recommends
writing your classes in such a way that inheritors have at least the same
essential properties as their ancestors, but his language Eiffel has no
way of enforcing this.  Inheritance is perhaps better regarded as a useful
way of factoring descriptions, rather than a formally tractable relation.

Here are some relevant refs:
* "On types, data abstraction, and polymorphism"  Luca Cardelli and Peter
  Wegner ACM Comp Surveys 17(4) 1985
  Great stuff.  What a type is, how their model fits most type systems;
  what inheritance is about.
* "Type theories and oo programming" Scott Danforth & Chris Tomlinson
  ACM Comp Surveys 20(1) March 88 pp29-72
  Tries to model some oo language features in the light of current ideas on
  types, and manages it partially, shedding lots of light on the subject in
  the process.
* "Type-checking Smalltalk" Ralph Johnson OOPSLA 88 [ACM -- SIGPLAN?] & 86
  Johnson's main aim here was to add types to the Smalltalk notation, so that
  the compiler could do some speed-ups, by taking some of the load off the
  run-time binding mechanism (which chooses methods for messages).
* "Dimensions of object-oriented design" Wegner & Brown OOPSLA 87 p168
  A taxonomy of features of OO languages.  Helps to separate out the
  notions of class and type.

Alan Wills
University of Manchester, M13 9PL UK
+44 61-273 6135
-- 
Alan Wills
+44-61-273 7121 x5699

cook@hplabsz.HPL.HP.COM (William Cook) (09/02/89)

>> = abbott@aerospace.aero.org (Russell J. Abbott)

>> I've been playing around with Smalltalk for a few weeks now and still
>> feel like a novice.  As you know, Smalltalk does not have declared
>> types.  "Type checking" is basically done dynamically: if an object has
>> a response defined for a message sent to it, then it is of the "right
>> type."  In trying to understand what that means, I came up with the
>> following.  I'm sure this must have been worked out properly somewhere.
>> Does anyone know where?

You may feel like a novice, but I think you have gone immediately to
the heart of the problem!  My group has been working on this problem
for some time.  We have formalized a notion of "type" for
object-oriented programming that is essentially the same as your
sketch.  Our paper, "Interfaces for strongly-typed object-oriented
programming" will be at OOPSLA this year.  We also have a prototype
implementation of a flexible kernel language for strongly-typed
object-oriented programming.

We have gone a little farther than you have in dealing with the fact
that object implementations often use parametric polymorphism and
object types are often recursive (the resulting problems are quite
subtle!).  Parametric polymorphism allows the definition of an
implementation List[T] that works for any element type T.  Recursive
types occur when a collection returns another collection as a result
of a map message, a list returns another list when it is reversed, an
number takes another number as an argument for most operations, etc...

Our type system is an extension of Cardelli's, as described in

    L. Cardelli.
    A semantics of multiple inheritance.
    In Semantics of Data Types, LNCS 173, pages 51-68.
      Springer-Verlag, 1984.

    L. Cardelli and P. Wegner.
    On understanding types, data abstraction, and polymorphism.
    Computing Surveys, 17(4):471-522, 1985.

The title of this first paper is misleading.  Cardelli is trying to
use subtyping to explain inheritance.  Although subtyping (aka subtype
polymorphism) is one of the fundamental notions in object-oriented
programming, it does not explain inheritance.  (Inheritance was the
subject of my dissertation;  see "A denotational semantics of
inheritance and its correctness" (with Jens Palsberg) also to appear
at OOPSLA.)  Inheritance is a mechanism for incremental programming in
the presence of recursive definitions;  it is not a relationship
between types.

The Emerald group also have a similar notion of type and a subtype
rule that is like Cardelli's.  See

    Andrew Black et al.
    "Distribution and Abstract Types in Emerald".
    IEEE Transactions on Software Engineering, SE-13, 1, 1987.

>> (In _Smalltalk-80:  The Language_, by Goldberg and Robson, the word
>> "type" does not appear in the index.)

The closest term in Smalltalk is "Protocol".

I hope this helps.  I think you are on the right track (ok, one could
say that I think so because I am on the same track...  time will
tell).  I would not have written but the first response to your
message was so typical of the misconceptions about typing and
object-oriented programming that I had to rebut:

> = rad@aragorn.cm.deakin.oz.au (Robert Alan Dew)

>Two suggestions:
> - forget about 'type'.
> - understand the following and there relationships
        [good list of oop terminology]

I think it is important not to become too caught up in object-oriented
terminology.  One of OOP's big problems is its inability to
communicate with the rest of the world.  OOP is novel, but it is not
such a completely radical departure from previous techniques that it
cannot be described using familiar terminology.  One should be able to
*reduce* object-oriented terminology to familiar constructs for
explanation.

>Anyway, if you want to think about types then class is the analogy.

NO!  NO!  NO!  Classes are *implementations*.  They often have type
information mixed in with them (it is nice to know what type your
implementation satisfies) but they are *not types*.  Types are
abstract loose specifications that describe *what* messages an object
handles, not *how* it handles them.  Any object of a given type is
free to handle its messages however it pleases;  this is one of the
wonders of OOP.

>>where a message is a message name, a list of the types of the
>>parameters, and the type of the result, i.e.,
>>
>>Msg ::= Name(param1: Type1; param2: Type2; ..., paramn: Typen): Type
>
>A message has:
> - a selector.  Which is a Symbol and does consist of the 'message names'.
>			 eg. #at:put:
> - arguments.  An Array containing the parameters.
>
>A message does not return an object, therefore no result type is required.

This response to the definition of Msg seems to be more about the
*syntax* of a message send than about message types.  The definition
of Msg given above is an abstract specification of the type of a
message.  It has nothing to do with syntax.  Given a collection of
such Msg definitions would can precisely define the interface or
protocol of an object.

>For a better understanding separate messages from methods.

I agree.
   Types are made up of descriptions of messages (like Msg).
   Classes are made up of descriptions of methods.

>The method returns an object, the method is not restricted to returning
>only one class of object.

The fact that a given message defines the *type* of object returned
does not mean that it defines the *class* of that object.  Any class
of object that supports the messages specified in the return-type can
be returned.

William Cook
HP Labs

sa1z+@andrew.cmu.edu (Sudheer Apte) (09/03/89)

Hi,

In article <7776@charlie.OZ>:
>Anyway, if you want to think about types then class is the analogy.

I disagree. I think protocol is the analogy. In fact, a typical non-OO
language has only a few pre-defined protocols, and these are only vaguely
defined as "types."  Some languages allow you to create new types.  What
Smalltalk allows you to do is to create new "types" (protocols) *without*
regard to implementing them (writing the methods). This, IMHO, is what
makes Smalltalk code reusable-- the second programmer gets a
set of types with a high degree of specialized functionality.

Thanks,
	Sudheer.
-----------------
.

rad@aragorn.cm.deakin.oz.au (Robert Alan Dew) (09/04/89)

In response to Alan Wills and William Cook where:

cook@hplabsz.HPL.HP.COM (William Cook) wrote
>NO!  NO!  NO!  Classes are *implementations*.  They often have type
>information mixed in with them (it is nice to know what type your
>implementation satisfies) but they are *not types*.

alan@ux.cs.man.ac.uk (Alan Wills) wrote
>Types *are* a useful concept for programming in any language, whether it
>has its own notation for them or not; and types aren't (necessarily) the
>same as classes.

I did not say types are classes.

I said, "Anyway, if you want to think about types then class is the analogy."

It seems that I was to abstract in my analogy.  When I wrote that 'types
are analogous to classes' I was thinking of something like:

	Class, Type := A description of a set of similar objects.


Robert Dew            rad@aragorn.cm.deakin.oz

rad@aragorn.cm.deakin.oz.au (Robert Alan Dew) (09/04/89)

In article <56929@aerospace.AERO.ORG> abbott@itro3.aero.org (Russell J. Abbott) writes:
>(In _Smalltalk-80: The Language_, by Goldberg and Robson, the word
>"type" does not appear in the index.)

On page 13 of the above named book a brief mention of types occurs, it
is pretty trivial though.

Robert Dew        rad@aragorn.cm.deakin.oz

rad@aragorn.cm.deakin.oz.au (Robert Alan Dew) (09/04/89)

>From: cook@hplabsz.HPL.HP.COM (William Cook)
>I think it is important not to become too caught up in object-oriented
>terminology.  One of OOP's big problems is its inability to
>communicate with the rest of the world.

I think OO terms should be used.  Where would we all be if new terms
(in any field) were not used?

>Types are abstract loose specifications that describe *what* messages an object
>handles, not *how* it handles them.

This is why class is attractive to me, a class specifies an object in
more detail than a type.

********************
>From: alan@ux.cs.man.ac.uk (Alan Wills)

>The main criterion for judging a definition of type is `does it give
>us a good way of separating those values which will support the desired
>behaviour of the program from those which won't, when they appear in a
>given context such as an assignment or message-argument?'

Including 'behaviour' indicates to me that you want to separate into classes
not types.  The current type definition excludes any behaviour of the object.

>Russ Abbott's one is a lot more useful: a type is the set of
>objects that respond to a particular set of messages.

This is not what Russ Abbott said.

>For example: say you
>invent a new sorting agent; it will accept a list of anything, and hand you
>back a sorted version; so long as the `anythings' understand `<'.  

Why are you associating a comparison procedure with the message '<'.
The message '<' does not imply what is written in the method.
eg. redirection in Unix is not a comparison.

>The idea that
>the set of all objects that understand `<' forms a type is clearly a useful
>one here.

If 'anything' understands '<' and each 'anything' also understands a
unique message then the 'anythings' are all of different types.
It is more important to be more specific, we need to know
whether the 'anythings' understand '<' not if they are of the same type.
But, understanding the message '<' is not strong enough.  It is the
method associated to the message which is important.

********************
The following three definitions of type have appeared in the
discussion so far.

>By  abbott@aerospace.aero.org (Russell J. Abbott)
>In Smalltalk, a type is a set of "messages" that objects of that type
>can receive.

>By  alan@ux.cs.man.ac.uk (Alan Wills)
>Russ Abbott's one is a lot more useful: a type is the set of
>objects that respond to a particular set of messages.

>By  cook@hplabsz.HPL.HP.COM (William Cook)
>Types are abstract loose specifications that describe *what* messages an object
>handles, not *how* it handles them.

I think the first two are trying to say:
Objects that respond to a particular set of messages are of the same type.
This definition indicates that an object can belong to many types.
eg. a set of objects respond to m1, => type A.
    a subset of the first set union another disjoint set respond to
    m2, => type B.
    therefore objects in the subset are of type A and type B.

How about this one?

Let O be the set of all objects.
Let M be the set of all messages.
Let S denote a subset of M.
Let T:O -> S be a mapping from an object to a set of all messages the object
understands.

Two objects o1 and o2 are of the same type iff
		T(o1) = T(o2).

Robert Dew   rad@aragorn.cm.deakin.oz

rkr@cs.washington.edu (R. K. Raj) (09/05/89)

Here is my $.02 to the types discussion. William Cook (rightly, imho) points
out that "it is important not to become too caught up in object-oriented
terminology".  On the other hand, Robert Alan Dew thinks that "OO terms
should be used."  I believe that we should use object-oriented terminology
but should relate the terms we use to those in traditional programming, as
well as terms used in other object-oriented programming languages. One of
the biggest problems in understanding object-oriented programming is that
there isn't ONE STANDARD terminology: people tend to use the words they
learned in their first object-oriented language/system, and there sure are
lots of such first object-oriented languages!

Many problems are thus caused by the use of the same `English' word to mean
different programming concepts. That's where the problem with `class' and
`type' comes in: some people tend use these terms synonymously, others use
`class' as a description of complete object implementation and `type' as a
description of the object interface. There are other minor and major
variations on the usage of these terms, as well as those of other terms. I
believe that one should try to understand and appreciate the underlying
concepts of an object-oriented programming language rather than get
religious about the words that are being used to describe the concepts!!!

Having said all this, let me add on to the confusion. An ABSTRACT type is a
set of message specifications for an object while a CONCRETE type (aka class
in many languages) is a description of the implementation of the object.
Both these aspects are useful in their own way. It is usually a good idea to
keep in mind whether any discussion is about abstract or concrete aspects of
a type/class/whatchmacallit.

Just one more thing. Robert Dew (rad@aragorn.cm.deakin.oz) has suggested
the following definition of type equivalence:

>Let O be the set of all objects.
>Let M be the set of all messages.
>Let S denote a subset of M.
>Let T:O -> S be a mapping from an object to a set of all messages the object
>understands.
>
>Two objects o1 and o2 are of the same type iff
>		T(o1) = T(o2).

The concept of conformity is useful in object-oriented languages in
extending the notion of type equivalence. We should be interested in knowing
when one object can be used in place of another. For instance, using the
above notation, we can say that o1 can be used in place of o2 iff
        T(o1) is a superset of T(o2).  
In other words, o1 conforms in type to o2. Such a notion of type conformity
was first used in Emerald and Trellis/Owl, respectively described by Black
et al and Schaffert et al in papers in the 86 OOPSLA. Eiffel also has
something called conformance (see Meyer's book), but William Cook has
pointed out several problems in Eiffel (see Cook's paper in ECOOP 89).

  - R. K. Raj
    rkr@cs.washington.edu
    rkr@uw-june.UUCP

johnson@p.cs.uiuc.edu (09/05/89)

In my opinion, the following three definitions are equivalent.

>By  abbott@aerospace.aero.org (Russell J. Abbott)
>In Smalltalk, a type is a set of "messages" that objects of that type
>can receive.

>By  alan@ux.cs.man.ac.uk (Alan Wills)
>Russ Abbott's one is a lot more useful: a type is the set of
>objects that respond to a particular set of messages.

>By  cook@hplabsz.HPL.HP.COM (William Cook)
>Types are abstract loose specifications that describe *what* messages an
>object handles, not *how* it handles them.

The first definition describes a type syntatically, i.e. it describes
how you describe a type.  The last two describe a type sematically,
i.e. they describe the values in the type.  All three are quite vague,
as any one sentence definition must be.  

There has been a lot of work in the area of type systems for 
object-oriented languages.  A type system where types are sets of operations
(what I call signature types) is one way to go, and, in my opinion, is
better than a type system that equates types and classes, such as that of
C++, Eiffel, and Trellis/Owl.  If you are inventing your own language
then either of these two approaches will work.  However, neither will
work for Smalltalk.  My paper in OOPSLA'86 describes why.

>By rad@aragorn.cm.deakin.oz (Robert Dew)
>Let O be the set of all objects.
>Let M be the set of all messages.
>Let S denote a subset of M.
>Let T:O -> S be a mapping from an object to a set of all messages the object
>understands.

>Two objects o1 and o2 are of the same type iff
>		T(o1) = T(o2).

I think that Robert's point is that objects with the same type must understand
the identical set of messages.  There is no reason to make this restriction.  
There is nothing wrong with saying that an object can be in many types at once.
You can either say that an object is in many types or you can say that a 
function can take arguments that are in many types.  As far as I know (which 
isn't very far), these two approaches give the same result.  However, 
polymorphism is a fundamental characteristic of object-oriented languages in 
general and Smalltalk in particular, and you have to have some way of handling
it.

Ralph Johnson - University of Illinois at Urbana-Champaign

rad@aragorn.cm.deakin.oz.au (Robert Alan Dew) (09/06/89)

In article <9120@june.cs.washington.edu> rkr@june.cs.washington.edu.cs.washington.edu (R. K. Raj) writes:
  [  ...  ]
#Just one more thing. Robert Dew (rad@aragorn.cm.deakin.oz) has suggested
#the following definition of type equivalence:
#
#>Let O be the set of all objects.
#>Let M be the set of all messages.
#>Let S denote a subset of M.
#>Let T:O -> S be a mapping from an object to a set of all messages the object
#>understands.
#>
#>Two objects o1 and o2 are of the same type iff
#>		T(o1) = T(o2).
#
#The concept of conformity is useful in object-oriented languages in
#extending the notion of type equivalence. We should be interested in knowing
#when one object can be used in place of another.

I agree, but knowing whether the objects are of the same type is
only part of the solution.

#For instance, using the
#above notation, we can say that o1 can be used in place of o2 iff
#        T(o1) is a superset of T(o2).  

I disagree.  The definition for replacement must be stronger.
Care should be taken when o1 replaces o2, this is because o1 can have a
completely different behaviour when recieving the same message.

The message does not imply the same behaviour for objects of the same type.

Robert Dew            rad@aragorn.cm.deakin.oz

rad@aragorn.cm.deakin.oz.au (Robert Alan Dew) (09/06/89)

The discussion of types, classes, objects, etc. prompted me to find
all sets of classes, where a single set of classes would indicate that
all messages understood by an instance of any class in the set can be
understood by an instance of any other class in the set.

Let a type be associated with only such a set of classes.

Below is 24 sets of 59 classes.  I searched in Smalltalk-80 v2.3
which contained 243 classes, therefore 184 extra sets should be listed.
I decided not to list them since they only contained one class each.

Number of types is 24 + 184 = 208
1 class   per type 88.46%
2 classes per type  8.17%
3 classes per type  1.92%
4 classes per type  0.96%
5 classes per type  0.48%

{ False True Boolean }
{ Arc Circle }
{ Path Curve LinearFit }
{ Switch Button }
{ TextHolder StringHolder }
{ ContextInspector Inspector }
{ ExternalPort CShellPort }

{ IdentitySet Set }
{ Array ArrayedCollection }
{ WordArray DisplayBitmap }
{ LiteralDictionary Dictionary }

{ Change OtherChange }
{ ClassRelatedChange ClassChange }
{ ClassCommentChange ClassOtherChange } 

{ SelectionInListController ListController }
{ MouseMenuController ClockController }
{ Controller BinaryChoiceController NoController }
{ CodeController OnlyWhenSelectedCodeController AlwaysAcceptCodeController }
{ StringHolderController CRFillInTheBlankController ChangeController
	FillInTheBlankController }
{ IndicatorOnSwitchController SwitchController MenuButtonController
	LockedSwitchController }

{ SwitchView BooleanView }
{ BinaryChoiceView View }
{ InspectorView StandardSystemView }
{ ProjectView TextCollectorView FillInTheBlankView TerminalView
	StringHolderView }

Robert Dew                                rad@aragorn.cm.deakin.oz
Department of Computing and Mathematics
Deakin University
Geelong 
Victoria
Australia 3217

rkr@cs.washington.edu (R. K. Raj) (09/08/89)

In <7792@charlie.OZ> rad@aragorn.UUCP (Robert Alan Dew) writes:
 >#>
 >#>Two objects o1 and o2 are of the same type iff
 >#>		T(o1) = T(o2).
 >#
 >#The concept of conformity is useful in object-oriented languages in
 >#extending the notion of type equivalence. We should be interested in knowing
 >#when one object can be used in place of another.
 >#For instance, using the
 >#above notation, we can say that o1 can be used in place of o2 iff
 >#        T(o1) is a superset of T(o2).  
 >
 >I disagree.  The definition for replacement must be stronger.
 >Care should be taken when o1 replaces o2, this is because o1 can have a
 >completely different behaviour when recieving the same message.
 >
 >The message does not imply the same behaviour for objects of the same type.
 >
 >Robert Dew            rad@aragorn.cm.deakin.oz

Notice that I only said that o1 can be used in place of o2 and did not
guarantee that you'd get the same behavior.  What one would like is to say
that o1 can be used in place of o2 iff
        B(o1) is a superset of B(o2).  (B = Behavior)

Unfortunately, the problem is: how do you (or the compiler) figure out what
is equivalent behavior? It therefore makes sense to relax the behavior
requirement and accept the weaker requirement of mere conforming types.

This isn't much different from what is done in more traditional languages.
For example, when a procedure call such as SORT(A) is made in a Pascal
program, there is no simple way of determining that the actual procedure
body of SORT does what it is intuitively expected to do: all the programmer
and the compiler do is to ensure that procedure call and procedure header
interfaces match. While techniques based on program verification can be
used, they typically are not used. Why? That's another story.

  - R. K. Raj
    rkr@cs.washington.edu,     rkr@uw-june.UUCP

alan@ux.cs.man.ac.uk (Alan Wills) (09/08/89)

Robert Dew's list of sets of Smalltalk classes which understand the same set of
messages is worth contrasting with the notion of a type as being the set of
objects which understand a particular set of messages.  For example, in
Smalltalk, if we look at the set of all objects which understand the
messages "<", "=<", ">", ">=", "=" : we get all instances of Magnitude (and
its subclasses) and all instances of String (and its subclasses).  Even
more interesting is that, although the implementations of these functions
are different in the two inheritance subtrees, this correspondence isn't just a mere
overloading of names: the relations obey the same rules about how they're
interrelated. For example:
   if I know     and also          then I can infer
   x < y                             (y < x) not
   x =< y       (x = y) not           x < y
   x > y                              y < x
   x < y         y < z                x < z
etc

I guess this helps to illustrate that this notion of type --- equivalence
sets wrt parts of behaviours --- is useful when into the nitty-gritty of
reasoning about programs to check they're going to do the right things.

Alan Wills
Manchester University, UK
-- 
Alan Wills
+44-61-273 7121 x5699

wilson@carcoar.Stanford.EDU (Paul Wilson) (09/09/89)

[This is a slightly revised version of something I posted, but
which looks from here like it never got out to the net.  Sorry
for any redundancy.  -- PRW]

It seems to me that types are abstracted *roles* that objects can play.
The same set of messages may mean a different thing in one role
than in another, so sets of messages really don't capture this
intuition.

For example in my role as a computer scientist, if somebody asks
me "what do you do?" I respond in one way, but in my role as
a boardsailer, I respond in another.  So at a conference, I
may say "garbage collection and reconstructive memory," but
at the beach I say "I fall down a lot."

Similarly, when an object is of more than one type, you get
collisions between messages understood by one type and same-named
messages understood by another.  For example, suppose a window
object responds to a "size" message by returning a point object
giving its screen dimensions in pixels;  suppose also that
a queue object responds by returning an integer saying how
many things are in the queue.

What happens when an object is both a queue and a window (say,
because it's a queue that can represent its contents to the
user)?

It seems to me that the "right," intuitive way to do this,
in a strongly typed system, is to resolve this by the
role the object is playing.  If the window system has
a pointer to it *as a window*, it should respond as
a window.  And if a simulation object has a pointer to
it *as a queue*, it should respond as a queue.

Does anybody do types this way?  It seems to me the most
natural way to do things:  if an object is of multiple
types, it has multiple interfaces -- different "languages"
it can speak.  And different languages may have the same
words, but with different meanings.  That's okay, as
long as the object knows what language it's being
spoken to in.

This leads to a more refined notion of type safety -- not
only should an object "understand" all messages that could
be sent to it at runtime (in the sense of having a method
defined for that message), but it should understand it
_in_the_right_way_.  It should be speaking the "same language"
as the message sender.

In summary:

A type should be a role with an associated protocol.
That's different from a set of messages, since two
different protocols could use exactly the same message
selectors and mean entirely different things.  So it's more
abstract that syntactically matching messages to method names.

It's also different from a class, because it's *not* a statement
about implementation.  Different objects of (subtypes of) the
same type do "the same thing" in response to the same messages,
even if they do it "in different ways," as determined by their
implementations.

And a class is a particular implementation that implements one
or more types.  Note that all of these things have identities
rather than just properties;  even types should be testable
for identity as well as the strucural equivalence
implied by accepting a particular set of messages.

On this view, types end up being capabilities to which
access can be restricted via scoping or maybe (if they're
first class) by controlling who they're handed to.
One object might be allowed to see another object
as "an underling I can order around," while yet another is
only allowed to see it as "a peer I can't talk to that way."

Now it's not clear to me that making all these distinctions,
but it seems like the kind of explicitness static-typing fans
would like.

Any comments?  Whose wheels am I reinventing? :-)

      -- Paul


Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@bert.eecs.edu
Box 4348   Chicago,IL 60680 


Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@carcoar.stanford.edu
Box 4348   Chicago,IL 60680 

wilson@carcoar.Stanford.EDU (Paul Wilson) (09/13/89)

I got several responses to the effect that my types-as-roles model
is very intuitive, but pointing out what at first appears to
be a problem with multiple inheritance.  I don't think it's really
a problem, and in fact is a major strength if you believe in
strong typing. 

   [ to recap a little:  I said that types should be *roles* that objects
can play, which is a lot like sets of messages they respond to.  It's
stronger than that, though, because it's an explicit declaration
that the object understands the messages in a particular way.  For
example, what makes an object a number is not just that it understands
messages like ">", but that it promises to respond to them in a way
that makes sense as a number.  This avoids accidental coincidences of
naming, and in software engineering terms helps establish responsibility
for whether something can be used in a particular context. 
     I made the example of an object that is a window and is a queue as 
well, and can respond to the "size" message as either one;  if you
have a pointer to it as a window, it responds as a window, returning
a point giving its screen dimensions.  If you have a pointer to it
as a queue, it returns an integer telling how many elements are in
the queue. ]

    The problem comes up that you may have a window-queue object with
a message name collision like this, and you may have a pointer to it
as a window-queue, rather than as either a window or a queue.  What
happens then?

    I submit that you should have to explicitly disambiguate the context.
This is not as gross and restrictive as it sounds, and in fact it's not
restrictive at all.  Remember, roles are *external* interfaces, and
may cross-classify with inheritance for code reuse.  If you have a pointer
to something that can behave as a window or behave as a queue, it's
no violation of information hiding to tell it what you mean.

     If you take the conversational message-passing metaphor seriously,
this is exactly how things ought to be.  If I've established more than
one conversational context with somebody, ambiguities must be resolved.
If I'm at a CS conference but I'm talking to somebody I've recently
talked to about windsurfing, a question like "what do you do?" has
to be disambiguated:

    "what do you do? -- as a hacker, I mean --"  vs.
    "what do you do?  Wavesailing, slalom?"

     This is not an invasion of my privacy because both contexts have
already been established.  Presenting myself as a CS guy and a boardhead
does *not* imply, for example, that I'll answer questions about my
religion or political views or whether my family is thoroughly inbred
white trash:  disambiguating *roles* doesn't imply knowing anything about
the *class* of a reciever that it hasn't already told you.


     Oddly, I just came across something like this in a thoroughly
*dynamically* typed language -- Ungar & Smith's "Self" language, which
has no classes at all, just prototypes.  In Self, multiple inheritance
lookups are guided by the "sender path constraint," which sort of like
the kind of disambiguation I'm talking about.  It only works with
messages an object sends to itself, though, because other objects
can't tell anything about the type of the receiver.  Basically,
if an window-queue object sends itself a "size" message while executing
a message inherited from "window," it responds with its window version.
If it's executing a method inherited from "queue" when it sends itself
a "size" message, it likewise assumes it's considering itself a queue
at that point, and responds with the queue size.

     Actually, though, Self isn't making a distinction here between
interface and implementation -- it assumes that they correspond.
In a virtuous strongly-typed language (with all the Truth, Beauty,
and Righteousness that does or doesn't imply), the roles would
be explicit and checked.  Since the size method of a queue is probably
not an implementation of the same interface as the one for a window,
no conflict would occur.  If it *is* the programmer should know
about it and have to say what he/she means.


     In general, I see Ungar's point of view that strong typing is
a hassle and a pain in the ass.  But I'm not sure you couldn't get
rid of most of the hassle by the use of defaults and a little
automation.  For example, when you implement a subclass, it would
be, by default, a subtype of the type(s) of its parent(s).  And if
you write code that assigns a particular value to an untyped
variable, the type is inferred, etc.  In general, pretty safe
guesses would be made and the programmer's attention brought to
the ambiguities.  The latter might be deferred until runtime
errors, or a tightening-up phase after a prototyping phase.  You
might have an optionally-typed language with automated support for going
back in and strongly-typing things as needed.  (Either to satisfy
your anal-retentive supervisor :-) or if you feel that maybe your
program's doing the wrong thing because you have undetected role
mismatches.)

     It seems to me that programmers generally have a very good idea
of what roles are appropriate at what point in a piece of code, and
the trouble is not in any serious brainwork or overcommitment that
the programmer must do, but in some low-level explication that might
be largely automated, getting the best of both worlds.  (Note that
the programmer could always use the degenerate role "object" for
things that must truly be dynamically typed.  But for things in
which the intent of the code obviously restricts the plausible roles
anyway, like generic numeric code, specifying the role "number" is not
restrictive.  And if in some cases the programmer overcommits, then
there should be automated support for generalizing, like going back
and substituting a more general role and pointing out any mismatches
or ambiguities it causes.  This might actully be *more* flexible
than dynamic typing, because some of the "freedom" of dynamic
typing creates more work by making it harder to find hidden
assumptions and dependencies.  If you overcommited when you wrote
the code, you might as well have done it explicitly, so a tool
can help you fix it.)

BTW,  David Keppel has pointed out to me that Eiffel has a renaming
facility, but it's really not doing the kind of disambiguation that
I mean.  It's for disambiguating name collisions *across* contexts,
to establish a single non-role-dependent interface.  This seems wrong
and against the object-oriented grain to me.  If an object is a
queue and a window, it should be able to function both as a queue and
as a window, without breaking existing code.  The window management
software should not have to be changed, and neither should software
that uses queues.  It should not matter to either one what some
object does in other contexts, just as it is irrelevant that a
word in English means something else in French.  The introduction of
bilingual entities should not require changes to either language,
unless there's some fortuitous advantage to it.



Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@carcoar.stanford.edu
Box 4348   Chicago,IL 60680