Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!mcsun!ukc!mucs!alan
From: alan@ux.cs.man.ac.uk (Alan Wills)
Newsgroups: comp.lang.smalltalk
Subject: Re: Smalltalk Types
Message-ID: <6475@ux.cs.man.ac.uk>
Date: 1 Sep 89 19:39:37 GMT
References: <56930@aerospace.AERO.ORG> <7776@charlie.OZ>
Organization: Dept. of Computer Science, University of Manchester, UK.
Lines: 90
In-reply-to: rad@aragorn.cm.deakin.oz.au's message of 1 Sep 89 02:57:19 GMT

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