pallas@eng.sun.com (Joseph Pallas) (03/26/91)
In <1991Mar22.210725.29448@neon.Stanford.EDU> hoelzle@neon.Stanford.EDU (Urs Hoelzle) writes: >But you aren't convinced and I've heard this argument often enough, >so let me give an example. Please show me how you would use the many >features of Ada to write this in Ada (or any other statically-typed >language): >[example of heterogeneous list of "unrelated" objects deleted] >To avoid misunderstandings, please note that the above example *is* >type-safe in an abstract sense: no 'message not understood' error can >occur because all elements of listC understand both 'foo' (which may >be sent by someProc) and 'display'. However, I claim that this piece >of code won't type-check in Ada, C++, Eiffel, ... Sooner or later, opponents of static typing bring out the heterogeneous collection. There's no question that it isn't possible with most traditional language type-systems to express the type of the list in Urs's example. Type systems that can express union types (such as, "an A or a B") or purely extensional types (such as, "anything that understands 'foo'") [is that the right name, type theory mavens?] are not common (but not unknown, either---I think Ralph Johnson's Typed Smalltalk can do this). The problem is, no one has ever come up with a convincing reason why I should want my type system to handle the heterogeneous collection. This is because no one has come up with a convincing reason why I should want to write programs that contain heterogeneous collections. Needing collections of otherwise-unrelated objects generally signals a flaw in the design, not a failing of the type system. joe
hoelzle@leland.Stanford.EDU (urs hoelzle) (03/26/91)
In article <pallas.669923769@red-dwarf>, pallas@eng.sun.com (Joseph Pallas) writes: |> |> Sooner or later, opponents of static typing bring out the |> heterogeneous collection. |> [stuff deleted] |> The problem is, no one has ever come up with a convincing reason why I |> should want my type system to handle the heterogeneous collection. |> This is because no one has come up with a convincing reason why I |> should want to write programs that contain heterogeneous collections. |> Needing collections of otherwise-unrelated objects generally signals a |> flaw in the design, not a failing of the type system. I think a few clarifications are in order because you're attacking on the wrong front, Joe: 1. I am not an "opponent of static typing". For some kinds of problems, they have advantages, and for others they have disadvantages. But I do disagree with people who say that typing does not impair reusability, or who say "I can do that in <your favorite typed language here>, too". 2. Here's why you want at least some form of heterogeneous collections: type T = "some type" type SubT = "subtype of T" procedure someProc(c: List[T]) I think that you'll agree with me that you'd like to use someProc with a Collection[SubT], especially if someProc just iterates through the list and sends 'foo' -- after all, every SubT "is a" T. But as soon as Lists are mutable (e.g. define insert(newElem: T)), the type system won't let you do it because List[SubT] is *not* a subtype of List[T]. You could try to fix this by splitting List into ReadOnlyList and a subtype ReadWriteList (which adds the insert operation), but this begins to stretch the correspondence between types and concepts (IMHO). And it certainly doesn't scale up very well, e.g. when you try to subclass List or when you have several methods like "insert" which you need to "turn off" in order to use someProc. In a way, the problem exists because today's type systems are based on what you *could* do to the list in someProc, not on what you actually do. 3. At least for rapid prototyping, your argument that "the type hierarchy isn't perfect if this situation occurs" is invalid: you *don't* want to rearrange lots of types just to try something out. Instead, you want to combine existing functionality in new ways which you didn't anticipate when you originally wrote the code. When (and if) you convert your prototype into a "product", *then* you go back and clean up the type hierarchies. Even in "production" programming, life isn't perfect and you might not be able to rearrange the type hierarchy because a) you're using some library or b) different uses have conflicting views, i.e. require conflicting type hierarchies. -Urs
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/26/91)
In article <1991Mar25.220525.11087@leland.Stanford.EDU> hoelzle@leland.Stanford.EDU (urs hoelzle) writes: > 2. Here's why you want at least some form of heterogeneous collections: > type T = "some type" > type SubT = "subtype of T" > procedure someProc(c: List[T]) > I think that you'll agree with me that you'd like to use someProc with > a Collection[SubT], especially if someProc just iterates through the > list and sends 'foo' -- after all, every SubT "is a" T. But as soon as > Lists are mutable (e.g. define insert(newElem: T)), the type system > won't let you do it because List[SubT] is *not* a subtype of List[T]. ``Subtype? What's a subtype?'' says the C programmer. To implement a generic list type in C, you use macros. Nowhere is there an explicit ``insert'' operation that demands its own prototypes. So if you do have an operation that works on multiple types, it will work correctly through a list. Maybe one ``object-oriented'' language or another works badly with lists, but that's not related to static versus dynamic typing. So: What use can anyone make of a heterogeneous list? ---Dan
boissier@irisa.fr (franck boissiere) (03/26/91)
> In article <pallas.669923769@red-dwarf>, pallas@eng.sun.com (Joseph Pallas) writes: > |> > |> Sooner or later, opponents of static typing bring out the > |> heterogeneous collection. > |> [stuff deleted] > |> The problem is, no one has ever come up with a convincing reason why I > |> should want my type system to handle the heterogeneous collection. > |> This is because no one has come up with a convincing reason why I > |> should want to write programs that contain heterogeneous collections. > |> Needing collections of otherwise-unrelated objects generally signals a > |> flaw in the design, not a failing of the type system. > There is at least one kind of system which must allow heterogeneous collections. It is often called Open System. Is these systems the person who writes the kernel do not know anything about what objects will be used by the persons who will extend the system. Another exemple is for debugging, where you might collect any kind of objects. -- Franck BOISSIERE boissier@irisa.irisa.fr C.C.E.T.T. B.P. 59 boissiere@ccett.fr 35512 CESSON SEVIGNE CEDEX FRANCE
mto@harvey.gte.com (Tamer Ozsu) (03/26/91)
In article <pallas.669923769@red-dwarf> pallas@eng.sun.com (Joseph Pallas) writes: >The problem is, no one has ever come up with a convincing reason why I >should want my type system to handle the heterogeneous collection. >This is because no one has come up with a convincing reason why I >should want to write programs that contain heterogeneous collections. >Needing collections of otherwise-unrelated objects generally signals a >flaw in the design, not a failing of the type system. > Well, let me see how I can take a position on both sides of this argument. I must admit that I missed the earlier segments, so if I am reiterating something that has been already addressed, my apologies. There are cases in object-oriented database systems where the results of a query is a heterogeneous collection. Object algebras take as input sets of objects and produce as output sets of objects (sometimes new objects that were not in the database to begin with -- e.g., explicit join -- but that is not important here). It is quite possible that the result set of objects is a heterogeneous collection. So, there is a need for the ability to handle heterogeneous sets of objects. On the other hand, I don't see why a type system and type checking mechanism cannot be developed to handle these collections. Some object algebras impose what is called union compatibility on the algebra operators [Shaw and Zdonik paper in the 6th Data Engineering Conference, 1990]. Union compatibility requires that members of the sets being operated on to be instances of types which are in a subtype relationship with one another. However, this may be too restricted. In last year's OOPSLA (1990), we presented a paper [pages 224-233] that discusses a more general type system for a simplified object algebra. The paper also discusses the issues of heterogeneous sets. This is by no means the definitive word on the subject, but it demonstrates that a type system, which is sometimes more restricted than one may like, can be developed. ==Tamer -- M. Tamer Ozsu Telephone: (617) 466-2098 GTE Laboratories Fax: (617) 290-0628 40 Sylvan Road Internet: mto@gte.com Waltham, MA 02254
pallas@eng.sun.com (Joseph Pallas) (03/27/91)
In <1991Mar25.220525.11087@leland.Stanford.EDU> hoelzle@leland.Stanford.EDU (urs hoelzle) writes: >I think a few clarifications are in order because you're attacking on >the wrong front, Joe: I didn't intend to attack, just to make a point. Heterogeneous collections just happens to be one of my buttons. Also, I shouldn't have portrayed you as an "opponent of static typing" when you were merely presenting one argument against static typing. >2. Here's why you want at least some form of heterogeneous collections: > > type T = "some type" > type SubT = "subtype of T" > procedure someProc(c: List[T]) > I think that you'll agree with me that you'd like to use someProc with > a Collection[SubT], especially if someProc just iterates through the > list and sends 'foo' -- after all, every SubT "is a" T. But as soon as > Lists are mutable (e.g. define insert(newElem: T)), the type system > won't let you do it because List[SubT] is *not* a subtype of List[T]. Aha! There's no heterogeneous collection here. There is, however, a problem with the notion of subtyping for parameter conformance. One solution to an overly restrictive static type checker is to weaken the static checking. Another solution, however, would be a smarter checker. > In a way, the problem exists because today's type systems are based > on what you *could* do to the list in someProc, not on what you actually > do. Indeed. If I could provide more information about someProc, such as the fact that it never attempts to modify its parameter (did I hear someone cough "const"?), then even a simple type checker would be happy to approve this operation. Urs is correct that subtyping is NOT the right way to express this relationship. Subtyping is too strict a conformance relation. >3. At least for rapid prototyping, your argument that "the type > hierarchy isn't perfect if this situation occurs" is invalid: you > *don't* want to rearrange lots of types just to try something > out. This is a fairly strong argument. A good programming environment could go a long way toward neutralizing it, however. I confess I'm not aware of any that really eliminates all the effort involved in making this kind of change. On the other hand, I rely on static type checking during my rapid prototyping. It helps me to keep my mental model synchronized with the code I'm actually manipulating. I also find that the more OOP I do, the less often that I make major changes during prototyping without going all the way back to rethink the design. Maybe I'm fossilizing. There are just opinions, of course, and your mileage may vary. joe
boehm@parc.xerox.com (Hans Boehm) (03/27/91)
hoelzle@leland.Stanford.EDU (urs hoelzle) writes: >2. Here's why you want at least some form of heterogeneous collections: > > type T = "some type" > type SubT = "subtype of T" > procedure someProc(c: List[T]) > I think that you'll agree with me that you'd like to use someProc with > a Collection[SubT], especially if someProc just iterates through the > list and sends 'foo' -- after all, every SubT "is a" T. But as soon as > Lists are mutable (e.g. define insert(newElem: T)), the type system > won't let you do it because List[SubT] is *not* a subtype of List[T]. As someone who hasn't yet completely converted to the object oriented religion, this has always struck me as using the wrong tool for the job. I really don't want a "list of T or subtype of T". I want a "list of objects that understand foo". Once I take that view, I have no problems, at least in the few statically typed languages that allow this (e.g. Russell, and probably FX from MIT, and probably Scratchpad II from IBM). I also don't need to construct my types in such a way that all types that understand foo are "derived" from a common supertype; I can use inheritance purely where it simplifies the implementation. And I get full static checking, though elements of the list will, of course, somehow carry the "foo" function with them. (In Russell, I would build a list of pairs <x: T, T: [algebra containing foo]>.) Hans-J. Boehm (boehm@xerox.com)
objtch@extro.ucc.su.oz.au (Peter Goodall) (03/27/91)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > ... >So: What use can anyone make of a heterogeneous list? >---Dan I have written a Smalltalk application which will unload fairly arbitary recursive objects to an append only Stream (pipe). We use this for spitting windows and their contents between workstations on a network. There is no way of knowing the contents of a window structure because they are very dynamic. When I write the structure out to a file I keep a heterogeneous Dictionary which has as keys each object encountered as the structure is traversed. The valu in the dictionary at an object is a unique number from a counter. So, if I find a new object, I increment the counter and store its value in the dictionary at the new object. Each time I encounter an object in the traversal I check the dictionary if it is already there I put its unique integer in the output stream. When I load a structure from a stream into the curent image I put each object as I re-create it into a heterogeneous list. It's index in this list is the unique number assigned in the output dictionary. When I encounter a reference number on input replace it with inputListAt: anInteger. While the structure of this text may not be too good. I believe this is an application where heterogeneous maniplulation of objects is essential. Peter Goodall
peter@ficc.ferranti.com (Peter da Silva) (03/27/91)
In article <26714:Mar2602:52:1891@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > So: What use can anyone make of a heterogeneous list? Message queue for a real-time operating system? -- Peter da Silva. `-_-' peter@ferranti.com +1 713 274 5180. 'U` "Have you hugged your wolf today?"
objtch@extro.ucc.su.oz.au (Peter Goodall) (03/27/91)
kramden.acf.nyu.edu (Dan Bernstein) writes: > ... >So: What use can anyone make of a heterogeneous list? >---Dan Allow me to turn my previous posting into something more coherent. (I hate writing in UNIX editors) :-). I spend quite a lot of time working on system functions in a client's Options Trading System. They have a need to pass Smalltalk/V windows between workstations on a network. These windows are essentially applications. They are all different in structure and functionality. For example a portfolio browser. This browser is not just some buttons and bitmaps, it contains the full details of the portfolio and all associated objects. I wrote, some code to write arbitrary, perhaps recursivley defined objects, serially to a file or pipe. Because this tool has to work with classes and structures which evolve over time there is no way I can predict which classes the tool will have to deal with at any particular time. To manage repeated and recursive references to an object on output, I recursively traverse the structure of the object to unload, and enter each object into a dictionary as it is encountered. The key to the dictionary is the object itself. A HETEROGENEOUS DICTIONARY. The dictionary entry at each object is an integer identifier which denotes that object as the n'th object encountered on traversal. If I've seen the object before on traversal then I write its integer identifier to the output. This handles recursion and repetition. When loading the complex object from the Stream into Smalltalk on another workstation Each object is stored on the end of an OrderedCollection (A HETEROGENEOUS LIST) , when an integer identifier is encountered in the input Stream, I replace it with the object in the OrderedCollection indexed by that integer. The Dictionary and the OrderedCollection must be Heterogeneous for such a tool to work. Peter Goodall (Sorry about the repost)
hoelzle@elaine13.Stanford.EDU (urs hoelzle) (03/27/91)
> To implement a generic list type in C, you use macros. Nowhere is there > an explicit ``insert'' operation that demands its own prototypes. So if > you do have an operation that works on multiple types, it will work > correctly through a list. > > Maybe one ``object-oriented'' language or another works badly with > lists, but that's not related to static versus dynamic typing. Really. I'm not sure I understand your solution, so could you please post it? Especially (if it is what I think it is), how does it generalize to larger problems? Just write more macros, I guess... Seriously: all programming languages are Turing-equivalent, so I'm sure you can do everything in C. But what about module interfaces (typed, of course), abstraction etc? How do you preserve them with macros? How do handle non-toy examples where the equivalent to "insert" is a complicated piece of code? Do you really want an "inlined" copy of that code at every call site? -Urs -- ------------------------------------------------------------------------------ Urs Hoelzle, CS PhD student hoelzle@cs.stanford.EDU Center for Integrated Systems, CIS 42, Stanford University, Stanford, CA 94305
yodaiken@chelm.cs.umass.edu (victor yodaiken) (03/27/91)
In article <6.9AL38@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <26714:Mar2602:52:1891@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >> So: What use can anyone make of a heterogeneous list? > >Message queue for a real-time operating system? >-- We're going to write a real-time operating system in a language with major run-time components? >Peter da Silva. `-_-' peter@ferranti.com >+1 713 274 5180. 'U` "Have you hugged your wolf today?"
hoelzle@leland.Stanford.EDU (urs hoelzle) (03/28/91)
> As someone who hasn't yet completely converted to the object oriented religion, > this has always struck me as using the wrong tool for the job. I really don't > want a "list of T or subtype of T". I want a "list of objects that understand > foo". Once I take that view, I have no problems, at least in the few > statically typed languages that allow this (e.g. Russell, and probably FX from > MIT, and probably Scratchpad II from IBM). I also don't need to construct > my types in such a way that all types that understand foo are "derived" from > a common supertype; I can use inheritance purely where it simplifies the > implementation. And I get full static checking, though elements of the list > will, of course, somehow carry the "foo" function with them. (In Russell, I > would build a list of pairs <x: T, T: [algebra containing foo]>.) This sounds good. However, I suspect that these languages don't (didn't?) have inheritance at all...? Plus, some people don't like functional languages. Could you post some pointers to the relevant literature? Thanks, -Urs ------------------------------------------------------------------------------ Urs Hoelzle hoelzle@cs.stanford.EDU Center for Integrated Systems, CIS 42, Stanford University, Stanford, CA 94305
bertrand@eiffel.UUCP (Bertrand Meyer) (03/28/91)
From <pallas.669923769@red-dwarf> by pallas@eng.sun.com (Joseph Pallas) quoted by boissier@irisa.fr (franck boissiere) in <1991Mar26.101051.29527@irisa.fr>: > > |> Sooner or later, opponents of static typing bring out the > > |> heterogeneous collection. To handle heterogeneous collections without endangering static typing, use genericity (Eiffel syntax): class COLLECTION [G] ... G, the formal generic parameter, describes the arbitrary type of collection elements. Clients obtain actual collections by providing some arbitrary type as actual generic parameter for G: my_fossil_collection: COLLECTION [FOSSIL] This is known as unconstrained genericity and works if no special property is required of collection elements; in other words, the only operations that class COLLECTION may apply to entities of type G are those operations which are defined for all types. If the elements of the collection must have specific properties, describe these properties by a class SPECIFIC and use constrained genericity as follows: class SPECIFIC_COLLECTION [G -> SPECIFIC] ... This means that any actual generic parameter must be a descendant of SPECIFIC. In other words, the declaration your_stamp_collection: SPECIFIC_COLLECTION [STAMP] will be valid if and only if STAMP inherits, directly or indirectly, from SPECIFIC. As a direct consequence of declaring G as constrained by SPECIFIC, class SPECIFIC_COLLECTION may manipulate entities of type G and apply to them any operation defined in class SPECIFIC. For example, it could include a routine some_operation (s: G) is do s.spec end where `spec' is a routine declared in class SPECIFIC. The only practical restriction on clients of such a collection class, then, is that if they want instances of a certain class (such as STAMP in the example) to appear in ``specific'' collections, they must add SPECIFIC to the list of parents of that class. This is a reasonable requirement: the ability to appear in such a collection is part of the abstract properties of these instances. Of course, the scheme only works if multiple inheritance is permitted, so that we can add SPECIFIC to the list of parents of a class which may already have other parents, describing other kinds of inherited properties. -- Bertrand Meyer bertrand@eiffel.uucp P.S. After writing this I saw an answer to a message by Erland Sommarskog; that answer appears to indicate that the above points may have been made already. I didn't see Mr. Sommarskog's message itself, however. My apologies if the above just repeats comments already presented by others.
pallas@eng.sun.com (Joseph Pallas) (03/28/91)
In <objtch.670045723@extro> objtch@extro.ucc.su.oz.au (Peter Goodall) writes about a collection of Objects in Smalltalk. But a collection of Objects is not a heterogeneous collection. This may be a little confusing because Object is a universal supertype in Smalltalk. Let's be concrete: A heterogeneous collection is one for which no single type can be safely assigned to all members of the collection. If all of the members of the collection have some common supertype, AND no operation is performed on any member of the collection that is not valid for that common supertype, then the collection is a homogeneous collection of members of that supertype. So if you have a collection of objects, you have to do something to those objects that you can't safely do to Objects in order to have a heterogeneous collection. joe
hoelzle@leland.Stanford.EDU (urs hoelzle) (03/28/91)
In article <pallas.670008199@red-dwarf>, pallas@eng.sun.com (Joseph Pallas) writes: |> |> > In a way, the problem exists because today's type systems are based |> > on what you *could* do to the list in someProc, not on what you actually |> > do. |> |> Indeed. If I could provide more information about someProc, such as |> the fact that it never attempts to modify its parameter (did I hear |> someone cough "const"?), then even a simple type checker would be |> happy to approve this operation. Urs is correct that subtyping is NOT |> the right way to express this relationship. Subtyping is too strict a |> conformance relation. The problem is (unfortunately) harder than "const": if you have a generic type (say List), e.g.: type List[T] = ...... procedure f(arg: T); then the above problem pops up, even if f doesn't change the List (e.g. "const arg: T" wouldn't change the problem a bit). The problem is contravariance: for a List[SubT], f's signature is "procedure taking a SubT", i.e. a more restricted type than T, violating contravariance. Before any Eiffel fans say "Gotcha!" :-), let me go on to say that contravariance isn't really the *problem*, just a (correct) formulation of it: if List[SubT] were a subtype of List[T], some variable v: List[T] could contain either a List[T] or a List[SubT]. However, the statement "v.f(t)" (with t:T) would be unsafe: if t holds a T, and v a List[SubT], we're passing only a T to f, not a SubT as expected (declared). So, again, the problem isn't contravariance, but how you apply it. -Urs ------------------------------------------------------------------------------ Urs Hoelzle hoelzle@cs.stanford.EDU Center for Integrated Systems, CIS 42, Stanford University, Stanford, CA 94305
chip@tct.uucp (Chip Salzenberg) (03/28/91)
According to hoelzle@leland.Stanford.EDU (urs hoelzle): >2. Here's why you want at least some form of heterogeneous collections: > > type T = "some type" > type SubT = "subtype of T" > > procedure someProc(c: List[T]) > > I think that you'll agree with me that you'd like to use someProc with > a Collection[SubT] ... Actually, I don't agree. And the burden of proof lay with the person who says "X is necessary." > In a way, the problem exists because today's type systems are based on > what you *could* do to the list in someProc, not on what you actually do. Without giving the compiler knowledge of the implementation of someProc, that restriction is rather difficult to escape. >3. At least for rapid prototyping, your argument that "the type hierarchy > isn't perfect if this situation occurs" is invalid ... Granted. Always tradeoffs... We here don't do rapid prototyping. -- Chip Salzenberg at Teltronics/TCT <chip@tct.uucp>, <uunet!pdn!tct!chip> "All this is conjecture of course, since I *only* post in the nude. Nothing comes between me and my t.b. Nothing." -- Bill Coderre
chip@tct.uucp (Chip Salzenberg) (03/28/91)
According to objtch@extro.ucc.su.oz.au (Peter Goodall): >I have written a Smalltalk application which will unload fairly arbitary >recursive objects to an append only Stream (pipe). But not _totally_ arbitrary objects, because the objects so dumped must understand a dumpTo: method, right? C++ can easily solve this problem using multiple inheritance, virtual functions, and vanilla homogenous lists. Next contestant? -- Chip Salzenberg at Teltronics/TCT <chip@tct.uucp>, <uunet!pdn!tct!chip> "All this is conjecture of course, since I *only* post in the nude. Nothing comes between me and my t.b. Nothing." -- Bill Coderre
cs450a03@uc780.umd.edu (03/28/91)
Urs Hoelzle writes: >Suppose you have two classes T and SubT, where SubT is a subtype of T >(in the strict sense of `subtype'). You also have the lists > ... >Now the problem: List[T] is not a subtype of List[SubT] because of the >insert method (contravariance). Thus, someProc(listB) is illegal even > ... That's not a problem, that's a slice of code. Raul Rockwell
hoelzle@leland.Stanford.EDU (urs hoelzle) (03/28/91)
In article <519@eiffel.UUCP>, bertrand@eiffel.UUCP (Bertrand Meyer) writes: |> From <pallas.669923769@red-dwarf> by pallas@eng.sun.com (Joseph Pallas) |> quoted by boissier@irisa.fr (franck boissiere) in |> <1991Mar26.101051.29527@irisa.fr>: |> |> > > |> Sooner or later, opponents of static typing bring out the |> > > |> heterogeneous collection. |> |> To handle heterogeneous collections without endangering static |> typing, use genericity (Eiffel syntax): |> |> class COLLECTION [G] ... |> |> [More details about Eiffel's generic classes] Yes, genericity *is* useful (and needed), but it is only a partial solution. At the risk of repeating myself, I'll restate the problem which originally started this discussion: ------- Hit 'n' if you've already seen this ------------- Suppose you have two classes T and SubT, where SubT is a subtype of T (in the strict sense of `subtype'). You also have the lists listA: List[A] listB: List[B] (where List[T] is a generic List including the method insert(elem: T)) Also suppose that there exists a procedure someProc(l: List[A]) which (among other things) may invoke the function a() on some elements of the list (a() is defined in A). Now the problem: List[T] is not a subtype of List[SubT] because of the insert method (contravariance). Thus, someProc(listB) is illegal even though it is perfectly safe since all of its elements are guaranteed to understand a(). Summary: instances of generic types are rarely subtypes of each other. Thus, code which takes an instance of a generic type as an argument cannot be reused for another instance of this generic type. This can seriously restrict reusability in programs which use many related instances of generic types, e.g. collections. ------------------------------------------------------------------------------ Urs Hoelzle hoelzle@cs.stanford.EDU Center for Integrated Systems, CIS 42, Stanford University, Stanford, CA 94305
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/28/91)
In article <1991Mar27.042219.18924@leland.Stanford.EDU> hoelzle@elaine13.Stanford.EDU (urs hoelzle) writes: > Really. I'm not sure I understand your solution, so could you please > post it? What list functions do you want? Most of the common ones are spelled out adequately in Knuth. You can translate from there directly into C. > Do you really want an "inlined" copy of that code at every > call site? No, so you hide the longer pieces behind function calls. ---Dan
bertrand@eiffel.UUCP (Bertrand Meyer) (03/29/91)
From <1991Mar28.030354.25051@leland.Stanford.EDU> by hoelzle@leland.Stanford.EDU [Order of paragraphs reversed]: > Suppose you have two classes T and SubT, where SubT is a subtype of T > (in the strict sense of `subtype'). You also have the lists > > listA: List[A] > listB: List[B] > > (where List[T] is a generic List including the method insert(elem: T)) > > Also suppose that there exists a procedure someProc(l: List[A]) which > (among other things) may invoke the function a() on some elements of the > list (a() is defined in A). > > Now the problem: List[T] is not a subtype of List[SubT] because of the > insert method (contravariance). Thus, someProc(listB) is illegal even > though it is perfectly safe since all of its elements are guaranteed to > understand a(). > Yes, genericity *is* useful (and needed), but it is only a partial > solution. [The discussion below uses LIST rather than List and some_proc rather than someProc.] Here constrained genericity does provide a solution. (Not necessarily *the* solution, but the best one that I know.) The reasoning (as sketched in a previous posting) is that if some_proc is to apply function a to objects of type T, it needs some reassurance that such objects indeed have a function a. It does not need to know what the function actually does, simply that it exists, has a certain signature (argument and result types) and, if so desired, certain semantic properties expressed by a precondition and/or a postcondition. The solution, then, is to introduce a deferred (i.e. abstract) class SPECIFIC, with a deferred (not implemented) function a: deferred class SPECIFIC feature a: SOME_TYPE is deferred end; ... end -- class SPECIFIC to request that any actual generic parameter LIST be a descendant of SPECIFIC: class LIST [T -> SPECIFIC] feature ... end -- class LIST and to make sure that A includes SPECIFIC among its parents. Of course, this means that B to must be a descendant of SPECIFIC, and Mr. Hoelzle's point is probably that this is inappropriate since some_proc will only be called with arguments of type LIST [A]. However the problem does not arise in this way in ``pure'' object-oriented programming of the Simula/Eiffel (and, unless I am mistaken, Smalltalk) style. In this world some_proc would not take an argument l of list type, as in Mr. Hoelzle's statement of the problem given above, but would be a procedure in a list class. Then two possibilities arise: - Either some_proc appears in the generic class LIST as given above, in which case it is legitimate to require that B be a descendant of SPECIFIC since some_proc will be applicable to targets of type B. - Or we do want some_proc to be applicable only to targets of type A. Then we do not need constrained genericity; we should declare some_proc not in the basic LIST class but in a descendant written specifically for that purpose: class LIST_OF_A inherit LIST [A] feature some_proc is local current_list_element: A x: SOME_TYPE do from ... loop ... x := current_list_element.a --<------ end ... end -- some_proc end -- class LIST_OF_A In the call marked --<-----, the application of function `a' to `current_list_element' is typewise valid since the function is assumed to be a feature of class A. In summary, static typing means that the software text must make explicit the assumptions about what operations are applicable to what entities, and then must not go beyond these assumptions in applying operations to entities. -- -- Bertrand Meyer bertrand@eiffel.uucp
boehm@parc.xerox.com (Hans Boehm) (03/29/91)
hoelzle@leland.Stanford.EDU (urs hoelzle) writes: [Me:] >> As someone who hasn't yet completely converted to the object oriented religion, >> this has always struck me as using the wrong tool for the job. I really don't >> want a "list of T or subtype of T". I want a "list of objects that understand >> foo". Once I take that view, I have no problems, at least in the few >> statically typed languages that allow this (e.g. Russell, and probably FX from >> MIT, and probably Scratchpad II from IBM). I also don't need to construct >> my types in such a way that all types that understand foo are "derived" from >> a common supertype; I can use inheritance purely where it simplifies the >> implementation. And I get full static checking, though elements of the list >> will, of course, somehow carry the "foo" function with them. (In Russell, I >> would build a list of pairs <x: T, T: [algebra containing foo]>.) >This sounds good. However, I suspect that these languages don't (didn't?) >have inheritance at all...? Plus, some people don't like functional languages. >Could you post some pointers to the relevant literature? I'd be glad to. An introduction to the ideas behind Russell is in Demers and Donahue, "Data Types are Values", TOPLAS 7, 3 (1985), pp. 426-445. A (the) Russell implementation is available by anonymous ftp from arisia.xerox.com:~ftp/russell.tar.Z. It includes some further documentation. There is a paper by Jouvelot anf Gifford in the 1991 POPL Proceedings that cites some of the earlier papers on FX. None of these languages are purely functional. They all contain assignment. (I don't like purely functional languages either.) As far as I know, these languages do not provide inheritance in the now conventional sense. (I know Russell does not.) They often get a similar effect by allowing the use of an algebra with many operations in a place where few operations are called for. But adding data fields (as opposed to functions or methods) to existing algebra implementations can be a bit clumsy. (You can fake it by adding an extra field whose type is a parameter to the implementation of the supertype, and instantiating that in the subtypes.) There are ways to avoid this. In the case of Russell, they were never implemented. I believe Cardelli's language "Quest" is flexible enough to implement inheritance, and to express the above notions. It is no doubt described in a DEC SRC report, though I don't have the reference handy. Hans (boehm@xerox.com)
pallas@eng.sun.com (Joseph Pallas) (03/29/91)
In <1991Mar27.183206.5506@leland.Stanford.EDU> hoelzle@leland.Stanford.EDU (urs hoelzle) writes: >The problem is (unfortunately) harder than "const": if you have a generic >type (say List), e.g.: >type List[T] = > ...... > procedure f(arg: T); >then the above problem pops up, even if f doesn't change the List (e.g. >"const arg: T" wouldn't change the problem a bit). The problem is >contravariance: for a List[SubT], f's signature is "procedure taking a SubT", >i.e. a more restricted type than T, violating contravariance. We've strayed far afield from the topic of heterogeneous collections, I'd say. The problem of the relationship between List[T] and List[U] when U is a subtype of T (which is definitely NOT a subtype relationship) is actively being researched. This problem doesn't go away in dynamically typed languages. joe
davidm@uunet.UU.NET (David S. Masterson) (03/29/91)
>>>>> On 26 Mar 91 23:17:31 GMT, peter@ficc.ferranti.com (Peter da Silva) said: Peter> In article <26714:Mar2602:52:1891@kramden.acf.nyu.edu> Peter> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: Dan> So: What use can anyone make of a heterogeneous list? Peter> Message queue for a real-time operating system? Every message in the queue would be a member of the class Message, no? Therefore, this would be a homogeneous queue. As Chip said, next contestant. ;-) -- ==================================================================== David Masterson Consilium, Inc. (415) 691-6311 640 Clyde Ct. uunet!cimshop!davidm Mtn. View, CA 94043 ==================================================================== "If someone thinks they know what I said, then I didn't say it!"
davidm@uunet.UU.NET (David S. Masterson) (03/29/91)
>>>>> On 26 Mar 91 10:10:51 GMT, boissier@irisa.fr (franck boissiere) said:
Franck> There is at least one kind of system which must allow heterogeneous
Franck> collections. It is often called Open System. Is these systems the
Franck> person who writes the kernel do not know anything about what objects
Franck> will be used by the persons who will extend the system.
What message would this OpenSystem send to the objects that it deals with?
What do those messages have in common? If they have nothing in common, then
how does the OpenSystem even know what messages to send to these collections
of objects?
Franck> Another exemple is for debugging, where you might collect any kind
Franck> of objects.
Wouldn't it all be of type DebugInformation? Therefore, same questions apply.
Next contestant. (I like that phrase, Chip :-)
--
====================================================================
David Masterson Consilium, Inc.
(415) 691-6311 640 Clyde Ct.
uunet!cimshop!davidm Mtn. View, CA 94043
====================================================================
"If someone thinks they know what I said, then I didn't say it!"davidm@uunet.UU.NET (David S. Masterson) (03/29/91)
>>>>> On 27 Mar 91 17:24:32 GMT, bertrand@eiffel.UUCP (Bertrand Meyer) said:
Bertrand> To handle heterogeneous collections without endangering static
Bertrand> typing, use genericity (Eiffel syntax):
Bertrand> class COLLECTION [G] ...
Is this a heterogeneous collection (one collection object containing many
objects of many types) or a generic collection class (a collection class that
may be defined to contain any *single* type of object [which may have multiple
parent types])?
Next contestant?
--
====================================================================
David Masterson Consilium, Inc.
(415) 691-6311 640 Clyde Ct.
uunet!cimshop!davidm Mtn. View, CA 94043
====================================================================
"If someone thinks they know what I said, then I didn't say it!"anw@maths.nott.ac.uk (Dr A. N. Walker) (03/30/91)
In article <1991Mar25.220525.11087@leland.Stanford.EDU> hoelzle@leland.Stanford.EDU (urs hoelzle) writes: > type T = "some type" > type SubT = "subtype of T" And here's where I start having difficulties. I wanted to reply to Urs's challenge using Algol 68 with the modal extensions (described by Charles Lindsey in Algol Bulletin #37, July 1974). But Algol doesn't have subtypes; you instead always build modes "upwards". Well, perhaps that's a problem with Algol; but Urs's challenge is based on a particular OO model, and it would help me to know whether I'm *really* missing out on something if he [or some other kind reader] could re-state the challenge in a more neutral way, eg as a real-world problem. > someProc just iterates through the > list and sends 'foo' OO again! > But as soon as > Lists are mutable (e.g. define insert(newElem: T)), the type system > won't let you do it because List[SubT] is *not* a subtype of List[T]. Why not? Because your particular OO language has this restriction? Or is there [or do you think there is!] something deeper that makes this a generic problem with static typing. I had other problems with Urs's challenge. He wanted to construct a list of "A" called "listA" and a list of "B" called "listB", and then to concatenate them into a "listC". But you can't concatenate lists of different types -- that's a *strong* typing, not a *static* typing restriction. I can construct a "listC" from *copies* of the elements of "listA" and "listB": mode list = (mode x) struct (x element, ref list (x) next); proc concatenate = (mode x, y, ref list (x) lx, ref list (y) ly) ref list (union (x, y)): if lx isnt nil then list (union (x, y)) := (element of lx, concatenate (x, y, next of lx, ly)) elif ly isnt nil then concatenate (y, x, ly, lx) else nil fi; ref list (a) lista := ...; ref list (b) listb := ...; ref list (union (a, b)) listc := concatenate (a, b, lista, listb); [untested! -- no doubt someone will tell me if I've got the reference levels wrong somewhere]. Is this what Urs wanted? Or have I constructed something quite other? Again, Urs wanted me to "send foo" to "listC" and to "display" the elements. The problem here is that, in Algol, any given identifier has a statically determined meaning, so a procedure cannot [unless I've missed something] decide at run-time which of several identically identified procedures is really meant. The following *is* possible: proc apply = (mode x, ref list (x) lx, op (ref x) void p) void: ( lx isnt nil | p element of lx; apply (x, next of lx, p) ); op jointdisplay = (union (a, b) this) void: case this in (a thisa): display thisa, (b thisb): display thisb esac; apply (union (a, b), listc, jointdisplay) comment where "display" is an operator, and "a" and "b" are assumed to be sufficiently different modes; otherwise, they might as well all be procedures with names like "displaya" and "displayb" comment but this may not be sufficiently generic for everyone's tastes. I'll think about the "foo" problem, but again I suspect there is no completely generic solution in Algol, and there must be different "fooa", "foob" "objects". This is, of course, where inheritance is nice; but you do then run into problems with multiple inheritance that have not, as far as I know, been solved in an aesthetically satisfying [ie, better than "this is what my compiler does about it"] way. -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
bertrand@eiffel.UUCP (Bertrand Meyer) (03/30/91)
From <CIMSHOP!DAVIDM.91Mar28192651@uunet.UU.NET> by cimshop!davidm@uunet.UU.NET (David S. Masterson): [Quoting from my earlier posting:] >> To handle heterogeneous collections without endangering static >> typing, use genericity (Eiffel syntax): >> class COLLECTION [G] ... [Mr. Masterson's reply:] > Is this a heterogeneous collection (one collection object > containing many objects of many types) or a generic collection > class (a collection class that may be defined to contain any > *single* type of object [which may have multiple parent types])? > > Next contestant? Although this is probably clear to most people reading this newsgroup, it may be worth confirming that the collection described by the above COLLECTION class is indeed heterogeneous (if so desired by clients). If a client declares tax_collection: COLLECTION [TAX] and then uses the routines of class COLLECTION to insert objects into `tax_collection' and retrieve them, these objects may be direct instances not just of class TAX but of any of its proper descendants. (``Proper descendant'' means direct or indirect heir, according to the inheritance relation.) This is a direct result of the type rules: if COLLECTION [G] has an insertion procedure put (new: G) is -- Add `new' to the collection do ... ensure has (new) end -- put then in a call of the form tax_collection.put (tx) the actual argument tx may be of any type which is a descendant of TAX. In different calls, we may use actual arguments of different types, inserting objects of different types into the same collection. -- -- Bertrand Meyer bertrand@eiffel.uucp
sommar@enea.se (Erland Sommarskog) (04/01/91)
Also sprach Urs Hoelzle (hoelzle@leland.Stanford.EDU): > type T = "some type" > type SubT = "subtype of T" > > procedure someProc(c: List[T]) > > I think that you'll agree with me that you'd like to use someProc with > a Collection[SubT], especially if someProc just iterates through the > list and sends 'foo' -- after all, every SubT "is a" T. But as soon as > Lists are mutable (e.g. define insert(newElem: T)), the type system > won't let you do it because List[SubT] is *not* a subtype of List[T]. In which type system? If you imply the type system in any statically typed language, I have news for you. The Eiffel code below compiles and executes just fine. For those of you who are unacquainted with the kernel library, I should add that STRING is an heir of COMPARABLE. (I assume when you talk of subtype you mean something like an heir.) CLASS Subtype FEATURE Some_proc(L : Linked_list[Comparable]) : boolean IS REQUIRE L.count >= 2; DO Result := L.first < L.last; END; CREATE IS LOCAL L : Linked_list[String]; X : boolean; DO L.create; L.Put_left("First"); L.Put_left("Last"); X := Some_proc(L); Io.putbool(X); END; END; -- Erland Sommarskog - ENEA Data, Stockholm - sommar@enea.se
carroll@cis.udel.edu (Mark Carroll) (04/01/91)
In article <27F11E1D.6354@tct.uucp> chip@tct.uucp (Chip Salzenberg) writes: >According to objtch@extro.ucc.su.oz.au (Peter Goodall): >>I have written a Smalltalk application which will unload fairly arbitary >>recursive objects to an append only Stream (pipe). > >But not _totally_ arbitrary objects, because the objects so dumped >must understand a dumpTo: method, right? > >C++ can easily solve this problem using multiple inheritance, virtual >functions, and vanilla homogenous lists. > >Next contestant? This article and its replies made me a bit angry. There's a rather huge degree of ignorance in them. All effective programming systems are equivalent. Anything that I can do in ANY language, I can do in any other language. There is absolutely no way that I can make an argument that a dynamic type system can do something that can't be done in a static system - because anything that I can do in language A, I can do in language B. Cutting down the arguments for dynamic typing because you can do the same job with static typing are vacuous. Obviously you can! No one has ever claimed that you couldn't! The question is: which does it BETTER? The argument shouldn't be: "I can do heterogeneous lists in a static system (using MI), so since you don't need dynamic typing to do it, dynamic typing is no good". The correct form of the argument is this: "My staticly typed solution is a BETTER solution than your dynamic one, and this is why:". Now, in the context of this argument, I think that the dynamic solution under which I can iterate ANY method over a heterogeneous lists is a better, cleaner solution that the static solution in which I have to create an artificial superclass for every method that I want to use to iterate over the list. Disagree? Please, tell me why. >Chip Salzenberg at Teltronics/TCT <chip@tct.uucp>, <uunet!pdn!tct!chip> <MC> -- ---------------------- Mark Craig Carroll: <MC> ------------------------ ------ U of Del. Grad Student in CIS ------ EE/CIS LabStaff Hacker ------ -- Resident Weirdo @ 105 E Cleveland Ave, Newark DE - carroll@udel.edu -- ---------------------- Shalom Achshav - Peace NOW! ----------------------
zeil@cs.odu.edu (Steven J. Zeil) (04/01/91)
In article <49413@nigel.ee.udel.edu> carroll@cis.udel.edu (Mark Carroll) writes: >This article and its replies made me a bit angry. There's a rather huge >degree of ignorance in them. > >All effective programming systems are equivalent. Anything that I can do >in ANY language, I can do in any other language. > >There is absolutely no way that I can make an argument that a dynamic >type system can do something that can't be done in a static system - >because anything that I can do in language A, I can do in language B. > The "all languages are equivalent power" argument applies only within the context of a single program execution. It does not apply when we begin to discuss the evolution of a set of programs as code is re-used and especially as as new programs manipulating previously-defined objects are conceived and implemented. The original poster was discussing the ability of a dynamically typed language to support a common I/O protocol. Yes, I can support his protocol easily in a static type system --IF-- I know all of the object classes ahead of time or am willing to rewrite portions of the I/O protocol each time that I define a new class. Otherwise, the original poster is correct in claiming that it "can't be done" over the history of the development of a related set of programs. Steve Z
peter@ficc.ferranti.com (Peter da Silva) (04/02/91)
In article <CIMSHOP!DAVIDM.91Mar28190551@uunet.UU.NET> cimshop!davidm@uunet.UU.NET (David S. Masterson) writes: > Every message in the queue would be a member of the class Message, no? That's an implementation detail. Really. The programming model is a queue you can stick varying objects into... how they're encapsulated so the guy at the other end can recover the type information is beside the point. -- Peter da Silva. `-_-' peter@ferranti.com +1 713 274 5180. 'U` "Have you hugged your wolf today?"
hoelzle@neon.Stanford.EDU (Urs Hoelzle) (04/02/91)
sommar@enea.se (Erland Sommarskog) writes: >Also sprach Urs Hoelzle (hoelzle@leland.Stanford.EDU): >> type T = "some type" >> type SubT = "subtype of T" >> >> [ List[SubT] is *not* a subtype of List[T] ] >In which type system? If you imply the type system in any statically >typed language, I have news for you. The Eiffel code below compiles >and executes just fine. > [Eiffel code] It is a well-known fact that Eiffel does not strictly enforce contravariance, and it is equally well-known that there are (very simple) programs which type-check in ISE's implementation but bomb at runtime because of a type error [programs available on request; you can find them yourself in the ECOOP'89 proceedings]. Thus, Eiffel (in its current implementation) is not a statically-typed language because there may be run-time type errors. There are two points that I should mention in Eiffel's defense: 1) Last year, Bertrand Meyer described a solution to the current type holes sometime last year. The newest Eiffel release might implement this. 2) Eiffel does indeed try to overcome the restrictions of contravariance (which is basically what I'm calling for), but it does it by totally abolishing contravariance, and I'm not sure this is the right way to go. Furthermore, the proposed fix to Eiffel's type holes is very strict. Informally speaking, you can have either assignments of the form aListOfComparable := aListOfString OR calls of aListOfComparable.append(aComparable) *in your entire system*. Since any non-trivial system (which actually uses covariance) will have both, the program will not type-check and we're back to contravariance. So: either Eiffel isn't type-safe, or any actual use of covariance in a realistic program will not type-check. Or, to put it differently: in *any* type system, one of the following two assertions is true: (I) List[SubT] is not a subtype of List[T] (i.e. you cannot *always* substitute a List[SubT] for a List[T]). (II) The type system is safe, i.e. there will be no run-time type errors if a program passes the type checking. Since (at least in the context of this discussion) we're only interested in type-safe languages where (II) is false, it follows that (I) must be true. -Urs -- ------------------------------------------------------------------------------ Urs Hoelzle hoelzle@cs.stanford.EDU Center for Integrated Systems, CIS 42, Stanford University, Stanford, CA 94305
davidm@uunet.UU.NET (David S. Masterson) (04/02/91)
>>>>> On 30 Mar 91 01:41:37 GMT, bertrand@eiffel.UUCP (Bertrand Meyer) said: > From <CIMSHOP!DAVIDM.91Mar28192651@uunet.UU.NET> by > cimshop!davidm@uunet.UU.NET (David S. Masterson): > [Quoting from my earlier posting:] > >> To handle heterogeneous collections without endangering static > >> typing, use genericity (Eiffel syntax): > >> class COLLECTION [G] ... > [Mr. Masterson's reply:] > > Is this a heterogeneous collection (one collection object > > containing many objects of many types) or a generic collection > > class (a collection class that may be defined to contain any > > *single* type of object [which may have multiple parent types])? > Although this is probably clear to most people reading this newsgroup, > it may be worth confirming that the collection described by the above > COLLECTION class is indeed heterogeneous (if so desired by > clients). I really hate the idea of contradicting Bertrand Meyer as I'm probably getting in over my head. However, I think there is a point that is being missed (and I'm probably the one missing it). I believe the original poster was looking for a use for a *truly* heterogeneous collection. From Mr. Meyer's description of COLLECTION (I don't know Eiffel), it still seems that this is more of a generic collection class in that all objects that can be contained in the collection are related through some (base) type and, therefore, follow some (base) protocol. Obviously, both C++ (through pointers to base class and polymorphism) and Smalltalk (because everything is ultimately an Object) have analogues to this. However, I think what is desired is something where objects in the collection are not related and, therefore, follow no set protocol. For instance, in the following: tax_collection: COLLECTION [TAX] users of the collection know that (at the very least) all objects obtained from the collection will follow the TAX object protocol. On the other hand: h_collection: COLLECTION [void] /* or is it 'void*'? */ might be a *truly* heterogeneous collection (assuming objects entered into the collection can be implicitly cast to VOID), but (going back to the original question) how useful would it be since all clues as to type and protocol of objects in the collection are removed? -- ==================================================================== David Masterson Consilium, Inc. (415) 691-6311 640 Clyde Ct. uunet!cimshop!davidm Mtn. View, CA 94043 ==================================================================== "If someone thinks they know what I said, then I didn't say it!"
edwardj@microsoft.UUCP (Edward JUNG) (04/03/91)
In article <CIMSHOP!DAVIDM.91Mar28191355@uunet.UU.NET> cimshop!davidm@uunet.UU.NET (David S. Masterson) writes: >>>>>> On 26 Mar 91 10:10:51 GMT, boissier@irisa.fr (franck boissiere) said: > >Franck> There is at least one kind of system which must allow heterogeneous >Franck> collections. It is often called Open System. Is these systems the >Franck> person who writes the kernel do not know anything about what objects >Franck> will be used by the persons who will extend the system. > >What message would this OpenSystem send to the objects that it deals with? >What do those messages have in common? If they have nothing in common, then >how does the OpenSystem even know what messages to send to these collections >of objects? > No, you are missing the point. An open system would interface with objects that conform to a certain interface. The notion in an "in the large" environment is that conformance is independent of the inheritance hierarchy -- that is, the conforming objects do not have to share the same inheritance graph or subclass from the same object, rather they implement the same protocol. This is encapsulation, an important and oft-overlooked aspect of object orientation (or object basis, depending upon your nomenclature). If I want to build an interface to a spell checker such that anyone could write a conforming spell checker, I write to an interface (or protocol, depending upon your terminology). This way I can send the right messages to the object without knowing about it (the thing is "type safe" at compile time, but would involve a run-time assertation if defensively programmed), and the implementation of that object is independent of the inheritance graph. Such interface or protocol-based implementations are not supported by most popular object-oriented languages, although some people are considering extensions to do so. This is part of the whole "inheritance breaks encapsulation" notion. -- Edward Jung Microsoft Corp. My opinions do not reflect any policy of my employer.
richieb@bony1.bony.com (Richard Bielak) (04/04/91)
In article <CIMSHOP!DAVIDM.91Apr1224716@uunet.UU.NET> cimshop!davidm@uunet.UU.NET (David S. Masterson) writes: [...] > >I really hate the idea of contradicting Bertrand Meyer as I'm probably getting >in over my head. Don't blame you! :-) [...] >On the other hand: > > h_collection: COLLECTION [void] /* or is it 'void*'? */ > >might be a *truly* heterogeneous collection (assuming objects entered into the >collection can be implicitly cast to VOID), but (going back to the original >question) how useful would it be since all clues as to type and protocol of >objects in the collection are removed? The generic collection should really be declared as: h_collection: COLLECTION [ANY]; as any class in Eiffel is an heir of ANY. The following trick can be used to do things with objects in such a collection. my_weird_object : MY_WEIRD_CLASS; .... my_weird_object ?= h_collection.next_item; -- above line gets the next item from the collection -- and does a "reverse" assigment to my variable. -- this assigment will only work, if the type on -- the right is of type MY_WEIRD_CLASS (or a descendant) -- otherwise, Void is returned. -- so, if not my_weird_object.Void then -- got a weird_object_here, do what you need to .... end; ...richie "What does a virtual void look like?" -- *-----------------------------------------------------------------------------* | Richie Bielak (212)-815-3072 | Programs are like baby squirrels. Once | | Internet: richieb@bony.com | you pick one up and handle it, you can't | | Bang: uunet!bony1!richieb | put it back. The mother won't feed it. |
ericco@ssl.berkeley.edu (Eric C. Olson) (04/04/91)
In the article Richard Bielak writes: > The generic collection should really be declared as: > > h_collection: COLLECTION [ANY]; > > as any class in Eiffel is an heir of ANY. I read an interesting paper that included a discussion of heterogeneous objects in an object-oriented database. The basic idea was to resolve the class heirarchy as late as possible, but during query semantic checking. That is, given a heterogeneous set of objects to work on, is it legal to apply a particular method on all of the objects? The set of classes (and superclasses) that define the objects are inspected. For each class, the method is resolved (in it or its superclasses). If this method exist in each of the classes, and has the same arity and type, then the query is semantically valid. To me, this seems to be a runtime class definition. For this task, you are defining a runtime superclass with a single method. The generalization would be, given any set of objects, define the runtime superclass which is the intersection of each object's methods (based on arity and type). This is guaranteed to at least be the root class. Hmmm, Eric -- Eric ericco@ssl.berkeley.edu
sakkinen@jyu.fi (Markku Sakkinen) (04/05/91)
In article <ERICCO.91Apr4095619@sdaf1.ssl.berkeley.edu> ericco@ssl.berkeley.edu (Eric C. Olson) writes: > ... >I read an interesting paper that included a discussion of >heterogeneous objects in an object-oriented database. > >The basic idea was to resolve the class heirarchy as late as >possible, but during query semantic checking. That is, given >a heterogeneous set of objects to work on, is it legal to >apply a particular method on all of the objects? > ... You probably mean "Type Consistency of Queries in an Object-Oriented Database System" by Straube and Ozsu (O"zsu), OOPSLA/ECOOP'90. Reply-To: sakkinen@jytko.jyu.fi (Markku Sakkinen) Markku Sakkinen Department of Computer Science and Information Systems University of Jyvaskyla (a's with umlauts) PL 35 SF-40351 Jyvaskyla (umlauts again) Finland SAKKINEN@FINJYU.bitnet (alternative network address)