Thoughts about OO types systems. What is it? it it enough how does it relate to current implemented models, e.g. prototypes Is it implementable, useful. Want some terminology: object, class, subclass, type, subtype, inheritance want to talk about zones of objects of a type: a pointer can point to a member of a zone. Look into islands too. Try to characterise linked lists and doubly linked lists. The basic premise of OO is that "computing is done with objects", or is that "programing is done with classes"??. An "object" appears as a record of operations together with some opaque state. The operations appear similar to functions in that they accept arguments/parameters, and produce a result. In a typed setting there will be a signature indicating the allowed types of arguments and the required type of result. The operations are not functions because they have the state of the object as well as the arguments as inputs, and because they may change the state of the object. The state of an object is only accessable though the operations that it contains. The implementation of those operations normally see the state of the object as a record of state variables which are themselves objects. The implementation may define further operations on those state variables, which are visible only within the object or its descendants (see below). These are not really "object operations" but are simple procedures. The two are easily confused, but should not be. If two objects contain the same set of operations with the same signatures, then either can be use in place of the other (at least as far as type correctness is concerned). More generally, if a piece of code requires an object to supply a certain set of operations, then any object which supplies those operations, whether or not they supply others, can be used. This is called "polymorphism" as objects of many different shapes can be used in the one place. This leads to a partial ordering on types of objects where a type A is <= a type B is any object of type A can be used wherever an object of type B is required. Applying this recursively gives a useful subtype relation. If A<=B and A.x : a->b and B.x:c->d then a>=c and b<=d It seems tidy to assume that every object responds to every message. This implies that the top of the type latice which we shall call "OBJECT" should give signature BOT->OBJECT to every message, where BOT is the bottom of the type lattice, a subtype of every type. If we exclude the existance of any BOT object, then such operations would not be callable, which is what we would like. Only once the signature has been changed by subtyping to elevate the argument type will operations be callable. To make operations a bit more meaningful, we will associate a specification with each operation. i.e. a precondition and a postcondition. These will normally need "access" to the state of the object, which is best described abstractly with variants and an invariant. Now, if A<=B and A.x :: [a/b] and B.x::[c/d] then c->a and b->d. So the specification for all operations on OBJECT should be [True/False] == MAGIC. Similarly operations on BOT have signature OBJECT->BOT and specification [False/True] == ABORT Clearly a BOT object is useless so excluding them is not a problem. Parameterised types: ------------------- It turns out to be useful to be able to talk about incompletely specified, or parameterised types. This is similar to parameterised expressions that we call functions. So we defined parameterised types: P == lambda x<=T . F(x) We treat this like a virtual type, i.e. no object have this type, they only conform to this type. A conforms to (is a subtype of) this P if there exists some t <= T such that A <= P t Of course, P t may be another parameterised type. Parameterised types are not the same as types, they are only second class types. A variable/name-binding must have a closed type, not a parameterised type. A name-binding can have a closed type by applying a parameterised type to a type variable within another parameterised type. A word about inheritance: ======================== The only required relationship between a subtype and its supertype is that the signatures of all operations be in the same sub/super relationship, and that the invarient of the subtype imply the invariantof the supertype. In particular, the state does not need to be represented in a similar way at all. However, it is often of practical value to use the implementation of a super type when implementing the subtype. In this case the subtype will contain at least the state variables of the supertype and probably much of the procedure code of the supertype. Precisely, any local name binding (local variable or procedure) that is assumed by any borrowed code must be provide with compatible signature in the subtypes implementation. We will call a procedure that only calls operations on the current object, never observes state directly, a pure procedure. A pure procedure used as an operation on a supertype can be used as an operation on any subtype, indepentantly of state storage. If a subtype only uses pure procedures from its supertype(s) then we will call this pure inheritance. If a subtype uses non-pure procedures and/or directly accesses state, we will call this dirty(?) inheritance. It violates encapsulation. Both of these types of inheritance follows subtyping. The literature suggests to thoughts about inheritance which do not follow subtyping. They involve co-variance and deviance.":-)" Co-variance happens when we want the arguements to a operation are re-typed down the type latice during inheritance. A typical example is with binary operators. e.g. addition The super-class can be added to itself, the subclass can be added to itself, but not to the superclass. I don't have any really good example through which to address this, (I don't this point/colour-point makes sense) but I feel that parameterised types can provide the desired fnctionality. Deviance is when heavy handed changes are made to operation signatures, such as removing an operation or changing the signatures in other non-conformant ways. Given that the type of self gets modified in such a heavy handed way, it is hard to see that the new self will make any sense in the context of the originaly operations. If it does, it can only be (I guess) because there is a common implicit super type to which both the superclass and the subclass conform, and the operation of the superclass which are being borrowed are infact valid for this common super class. I really need some more examples to understand this better. Object creation =============== A question (prompted by abstract factory patten in 'design patterns') How are objects created and initialised. Initialisation is particularly important for immutable objects. If creation is the result of an operation, the owner of the operation could be: 1/ an object of same class as the one being created. This begs the question how was that object created. This is done in prototype systems by allowing the type of an object to be modified dynamically by adding operations. 2/ an object which represents the class. The object would have to be a pre-existing singleton. Then, what other operations might a class have: what is it's type. 3/ a "memory" object could create other objects, but how would the type of the returned object be guarenteed. Also, are we really concerned with where something is stored, and can't the storage type of an object change.