Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!ucbvax!hplabs!hplabsz!cook
From: cook@hplabsz.HPL.HP.COM (William Cook)
Newsgroups: comp.lang.smalltalk
Subject: Re: Smalltalk Types
Summary: type not equal class, literature references
Message-ID: <3893@hplabsz.HPL.HP.COM>
Date: 1 Sep 89 20:46:43 GMT
References: <56930@aerospace.AERO.ORG> <7776@charlie.OZ>
Organization: Hewlett-Packard Laboratories
Lines: 129



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