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
new@ee.udel.edu (Darren New) (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. Hmm... How about a window with a hetrogeneous collection of buttons, sliders, text displays, etc, all of which respond to "redraw" and "is the mouse over you"? How about in GROPE (my project) in which each window has a hetrogeneous collection of graphical Estelle objects (modules, channels, states, transitions, queues, etc) which all respond to "redraw", "scale to parent", "select good default graphics", "is the mouse over you", and so on? I have also done simulation code where collections of hetrogenous objects are in "shopping carts" which all respond to "what is your price" and such things. Naturally, if all you have is a hammer, you never see the need for a screw. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+
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
cs450a03@uc780.umd.edu (03/26/91)
Darren New writes: >Hmm... How about a window with a hetrogeneous collection of buttons, >sliders, text displays, etc, all of which respond to "redraw" and "is >the mouse over you"? The way I look at things, I'd probably think of that as a homogenous collection. It's only when you get to taking the things apart that you can really see any distinction between them. (Or maybe, when you try to pass a paragraph of text through a slider.) Of course, I suppose that's a dynamic typing viewpoint... *shrug* Raul Rockwell
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
new@ee.udel.edu (Darren New) (03/27/91)
In article <25MAR91.22422777@uc780.umd.edu> cs450a03@uc780.umd.edu writes: >Darren New writes: >>Hmm... How about a window with a hetrogeneous collection of buttons, >>sliders, text displays, etc, all of which respond to "redraw" and "is >>the mouse over you"? > >The way I look at things, I'd probably think of that as a homogenous >collection. It's only when you get to taking the things apart that >you can really see any distinction between them. (Or maybe, when you >try to pass a paragraph of text through a slider.) Hmm... a homogenous collection that when you take it apart yields things with different types. Somehow, I think we are confused over terminology. Either that, or you are reaching for straws :-) The whole point of a hetrogeneous collection is that sometimes you treat everything the same and sometimes you treat each thing differently. Let's call a "hetrogeneous collection" something that holds multiple values of multiple types and over which some code iterates (hence the "collection" part) and over which other code applies different functions depending on the type (hence the "hetrogeneous" part). If this isn't a good enough definition, then all I can say is "When you drive screws with a hammer, *nothing* looks like a screwdriver." In the above case, the routine to refresh the screen will iterate over the entire collection, while the routine to actually do the redrawing (which clearly must be dynamically bound) will do different things based on the type (slider, button, ...) of the object. Looks like a hetrogeneous collection to me. Note that this definition rules out a bunch of things which I might call hetrogeneous collections. For example, the arguments to a C function, which I've never iterated over in spite of it being a collection and of hetro types. The same goes for argv[] in "cp -i a.out /bin", in which argv[0] is an executable, argv[1] is a control flag, argv[2] is a file, and argv[3] is a directory. This is kind of iffy, because some programs iterate over some or all of argv[] (like "echo") and others never iterate over argv[]. However, in AmigaDOS under the Workbench (i.e., the icon-based command interpreter), all four of these parameters would be passed separately and in different places (not argv[]); this leads me to believe that argv should be considered a hetro collection. (Note that in AmigaDOS, there is another type for argv[], namely file wildcard. This goes back to the globbing thread. :-) Take, for another example, PostScript procedures: { /moveit { 2 0.5 moveto } def } This is a procedure array (procedures are arrays in ps) containing a literal name, an array, and an executable name. The inner array contains an integer, a float, and an executable name. If bound, the executable names become operators. The "inner interpreter" iterates over the elements of the array and either pushes or calls, based on the type of the object. Looks like a hetrogeneous collection to me. What about the heap in C? Malloc iterates over the allocated blocks while seeking a free one, while other code indexes different blocks differently. Looks like a hetro collection to me. Memory itself is a hetrogeneous collection of integers, floats, pointers to code, pointers to data, etc. Block moves iterate over it, other instructions treat it differently depending on the instruction. If you pass the wrong type of value to an instruction, you get garbage out. !file /bin/a* /bin/acctcom: mc68020 demand paged dynamically linked executable /bin/adb: mc68020 demand paged dynamically linked executable /bin/addbib: mc68020 demand paged dynamically linked executable /bin/adjacentscreens: symbolic link to sunview1/adjacentscreens /bin/aedplot: mc68020 demand paged dynamically linked executable /bin/align_equals: symbolic link to sunview1/align_equals /bin/ar: mc68020 demand paged dynamically linked executable /bin/arch: executable shell script /bin/as: mc68020 demand paged dynamically linked executable /bin/at: mc68020 demand paged dynamically linked set-uid executable /bin/atoplot: mc68020 demand paged dynamically linked executable /bin/atq: mc68020 demand paged dynamically linked set-uid executable /bin/atrm: mc68020 demand paged dynamically linked set-uid executable /bin/awk: mc68020 demand paged dynamically linked executable Sure looks like "file" (or the shell) iterated over /bin. Sure looks like execv() is going to do different things depending on what element of the collection is passed to it. Before you convince me that directories are not hetrogeneous, you'll have to explain what EISDIR and ENOTDIR mean other than "dynamic type mismatch error". !cc -O2 main.c special.s prev.o lib.a Sure looks to me like a hetro list of file types passed as argv[]. The first is an integer parameter, the second is a C source, etc. Here, the "inner interpreter" selects based on first and last characters of argv[] to determine what to do. !ls ~new/tex/thesis biblio.bib darren.bst figures makeheads makeps outline.txt psfig.aux thesis.aux thesis.bbl thesis.blg thesis.dvi thesis.loe thesis.lof thesis.log thesis.ps thesis.tex thesis.toc Hmmm.... Looks like that directory has a hetrogeneous collection of bibliography files, bibliography styles, DVI files, lists of figures, log file, postscript files, tex files, etc. If I passed them all to lpr, do you think the same filter would be applied to each? printf("line %d percent complete %f file %s", ii, ff, ss); Sure looks like printf iterates over its arguments. Sure looks like the arguments are not all the same type. Isn't there an entire standard header file to handle hetrogeneous argument lists? C'mon people. I can't believe that you never used a hetrogeneous collection. I can't believe Dan B even tried to think of where he might have used a hetrogeneous list; he's too smart to have missed all these examples. Dynamic binding goes hand-in-hand with hetrogeneous collections. Any time you use or implement dynamic binding, you probably have a hetrogeneous collection in there somewhere, or you could have used static binding. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+
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)
cs450a03@uc780.umd.edu (03/27/91)
Darren New >> > or > Me >> >> >Hmm... How about a window with a hetrogeneous collection of buttons, >> >sliders, text displays, etc, all of which respond to "redraw" and "is >> >the mouse over you"? >>The way I look at things, I'd probably think of that as a homogenous >>collection. >Hmm... a homogenous collection that when you take it apart yields things >with different types. Somehow, I think we are confused over terminology. >Either that, or you are reaching for straws :-) The whole point of >a hetrogeneous collection is that sometimes you treat everything >the same and sometimes you treat each thing differently. Well.. my view is "type is a form of information", and you seem to be agreeing with me. For instance, consider a list of numbers: (0, 1, 2, 3, 4). Now consider a function, "f" which rounds a number up to the nearest even integer. Applying f to that list would yield (0, 2, 2, 4, 4). Voila! Hetrogenous data. (-: I believe you said "The whole point of a hetrogenous collection is that sometimes you treat everything the same and sometimes you treat each thing differently.") More generally, if your language allows you to encapsulate data, so that the encapsulated information is invisible to the user, then the type of that information should be invisible (until you "take it out of its box"). Anything less is not true encapsulation. At least, that's the way I look at things... >Let's call a "hetrogeneous collection" something that holds >multiple values of multiple types and over which some code iterates >(hence the "collection" part) and over which other code applies >different functions depending on the type (hence the "hetrogeneous" >part). Heh.. but type is just information, in my opinion. By the way, the way I'd write code to deal with the original challenge would be something like this: c =. a, b foo c display c or should that be c =. a, b display c foo c (I don't remember the particulars) Without some more detail on what the pieces were, I hesitate to write "foo" and "display". As a first cut though, I could make foo be an identity function, and display simply dump the data to standard output. >If this isn't a good enough definition, then all I can say is >"When you drive screws with a hammer, *nothing* looks like a >screwdriver." But I'm using neither a screwdriver nor a hammer. I'm using a computer ;-) >In the above case, the routine to refresh the screen will iterate over >the entire collection, while the routine to actually do the redrawing >(which clearly must be dynamically bound) will do different things >based on the type (slider, button, ...) of the object. Looks like a >hetrogeneous collection to me. It's ok. If I was writing the routine to actually do the redrawing, I'd probably think it was a hetrogenous collection too. And if you've seen some of my other postings, you might get the idea that I consider dynamic binding (of both functions and data) as pretty fundamental in general. Raul Rockwell
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?"
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/27/91)
In article <48805@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: > Hmm... How about a window with a hetrogeneous collection of buttons, sliders, > text displays, etc, all of which respond to "redraw" and "is the mouse > over you"? struct { any object; void (*redraw)(); int (*ismouseover)(); } *whatsinwindow(); Here ``any'' is a polymorphic type (e.g., void * in C), and *redraw takes an ``any'' argument. Naturally, languages like C++ encapsulate the above struct into a single ``class,'' but that's merely syntactic sugar. ---Dan
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?"
adam@visix.com (03/28/91)
In article <48805@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: >- Hmm... How about a window with a hetrogeneous collection of buttons, sliders, text displays, etc, all of which respond to "redraw" and "is the mouse over you"? >- In article <7689:Mar2623:28:5091@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >- struct { any object; void (*redraw)(); int (*ismouseover)(); } *whatsinwindow(); Here ``any'' is a polymorphic type (e.g., void * in C), and *redraw takes an ``any'' argument. Naturally, languages like C++ encapsulate the above struct into a single ``class,'' but that's merely syntactic sugar. >- Let me get this straight. To construct a heterogeneous list of M items each guaranteeing N operations, I need to waste space for M*N function pointers? Yes, we need to store ONE pointer to each function, but the above scheme wastes space if we have already stored that pointer, e.g. in a different kind of heterogeneous list. A large windowing application uses hundreds of different lists. And I need to write an explicit constructor for every kind of list? You can do better than that, even in C. Adam
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
new@ee.udel.edu (Darren New) (03/28/91)
In article <26MAR91.19392004@uc780.umd.edu> cs450a03@uc780.umd.edu writes: >>Hmm... a homogenous collection that when you take it apart yields things >>with different types. Somehow, I think we are confused over terminology. >Well.. my view is "type is a form of information", and you seem to be >agreeing with me. Well, heck, cowboy. Of course type is a form of information. But is it information only the compiler has, or is it information that comes into play at run-time. The question is essentially whether variables have types or not. If not, then you have dynamic typing. If so, then you have static typing, because each particular reference (variable, expression, etc) has a known type at compile time. Of course if you can apply different functions to different elements of the list based on their type, then "type" is a kind of information you can access, whether that information is accessed only by the runtime system or whether it is directly accessible to the programmer. When you say something is a homogenous collection, you seem to be saying that every element is a <type,value> pair and hence is all the same type. Naturally in a dynamically typed system, the types have to be carried along with the values in some way. However, variables and expressions (in this case, expressions accessing elements of the list) have different <type> tags. The fact that the type of the first element of <type,value> is of a fixed type does not mean that the elements all have the same type (did that make any sense?). Take, for example, Smalltalk. You can say "it's statically typed, because every variable and every value is an object." This, of course, is useless. Why? Because when you only have one type, the static/dynamic distinction becomes irrelevant. (I believe this is actually the case in older lisps, where everything was a cons cell.) Any Smalltalk programmer is going to think of the class of an object as its type. Since variables can hold objects from different classes and since expressions can return objects of different classes, Smalltalk is dynamically typed. Naturally, any object's class is going to be an instance of Behavour, so it will repond to anything Behavour's instances respond to. Hence, the type of a type (i.e., class) is always of a specific type (namely, Behavour). This does not alter the dynamicly-typed nature of Smalltalk. Arguing this from the wrong viewpoint is pointless, as at the lowest level, the only type in computer systems is the bit (and not even that, if you talk to an EE person). At the highest level (e.g., Vice President of Marketing), the only type is "information." Since most programmers work somewhere inbetween these two levels, it is necessary to pick the right level of abstraction for discussing types. (Kind of like saying "The halting problem is solvable in practice. All you have to do is treat every bit of storage ever accessed by the CPU running your program as a giant state machine." Nobody ever thinks about the problem this way, and nobody ever programs a computer as a 2^{8gig}-state finite state machine, so such a statement, while true, is pretty much useless.) At the lowest level, the machine can treat the <type> tag as an integer or pointer or whatever. However, that isn't usually how the programmer treats it. If you want to discuss various forms of dynamic typing, we would need a different level of abstraction than if we are discussing dynamic vs. static typing. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+ + When you drive screws with a hammer, screwdrivers are unnecessary +
new@ee.udel.edu (Darren New) (03/28/91)
In article <7689:Mar2623:28:5091@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <48805@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: >> Hmm... How about a window with a hetrogeneous collection of buttons, sliders, >> text displays, etc, all of which respond to "redraw" and "is the mouse >> over you"? > >struct { any object; void (*redraw)(); int (*ismouseover)(); } *whatsinwindow(); > >Here ``any'' is a polymorphic type (e.g., void * in C), and *redraw >takes an ``any'' argument. Naturally, languages like C++ encapsulate the >above struct into a single ``class,'' but that's merely syntactic sugar. Am I crazy, or isn't (void *) impossible to indirect? Don't you have to type-cast it first? Isn't this dynamic typing implemented on top of C? I never said that C does not Bernstein-have dynamic typing. All I said was that C doesn't have dynamic typing. (Actually, I probably didn't say that either, but I do believe it.) "void *" is not a polymorphic type; it is a pointer type. "object" is not dynamically typed; it is of type "any" (i.e., void *). The fact that you can typecast it does not make it a dynamic type, Dan. It merely means that the designers of C realised that they needed some way of allowing you to implement dynamic typing on top of C. But then, that's the Bernstein-has form of the word "has." Please, in my future posts, assume that I am using the English version of the word "has." Thank you. Dan, do you really think I'm so stupid that I don't know how to implement dynamic typing on top of a statically typed language? Do you really think that I, like you, willfully misinterpret what is being said to support a different point of view without trying either to make a point or learn something from somebody else? Do you really think I would have given the above example as a hetrogenous list if it could be represented in one line of code in a statically typed language? Of course, C is completely useless because it's all merely syntactic sugar for large finite state machines. That's how we can solve the halting problem for it. Of course, since every language is merely syntactic sugar for large finite state machines, discussing advantages and disadvantages of different languages is moot -- just write a macro expander. Actually, all computers are analog computers. Binary is just syntactic sugar on top of volatage differences. Since we can't have *real* digital computers, but merely illusions of them, then we can't solve the halting problem in the way you earlier proposed anyway. For any discussion, a level of detail and abstraction can be chosen which renders the discussion pointless. Thank you for finding that level in this particular discussion, so we might avoid it in the future. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+ + When you drive screws with a hammer, screwdrivers are unnecessary +
cs450a03@uc780.umd.edu (03/28/91)
Darren New writes: >Well, heck, cowboy. Of course type is a form of information. But is >it information only the compiler has, or is it information that comes >into play at run-time. The question is essentially whether variables >have types or not. If not, then you have dynamic typing. If so, then >you have static typing, because each particular reference (variable, >expression, etc) has a known type at compile time. Variables have types when I assign them values. That information is carried explicitly in interpreted code, and implicitly in compiled code. I don't have to variable declare types for the compiler any more than I have to declare the types of intermediate results. Of course, for ill-conditioned cases, the compiler generates lousy code. The simple solution is don't write bad code. >When you say something is a homogenous collection, you seem to be >saying that every element is a <type,value> pair and hence is all the >same type. Naturally in a dynamically typed system, the types have to >be carried along with the values in some way. Did I say that? hmm... If I have a bitmap, that's a homogenous collection, and I sure don't carry type information along with each bit. On the other hand, if for some reason I wanted a collection of bitmaps and strings, I'd have a list of pointers to data descriptors. One pointer (and descriptor) for each element of the list. Those data descriptors would carry "type" [and size], etc. But I deal with a homogenous collection: a list of pointers. Personally, if I have bitmaps and strings, I'd prefer to refer to them by separate names (that is, store them in separate variables). And as a general rule, this runs faster (than using indirection). Raul Rockwell
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
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/28/91)
In article <1991Mar27.164605.24547@visix.com> adam@visix.com writes: > Let me get this straight. To construct a heterogeneous list of M > items each guaranteeing N operations, I need to waste space for M*N > function pointers? No, because you can just have a single ``class'' structure with the N function pointers, and keep just one pointer per ``object.'' But this extra layer is pointless for small problems, and I didn't bother putting it in. > And I need to write an explicit constructor for every kind of list? That depends on what you mean by ``explicit.'' If you have several types each supporting some sort of redraw operation, and you want to set up a list of redrawable things, then you do have to say the correspondence between ``redrawable'' and the redrawing for each type. Other posters have mentioned how in object-oriented languages you can make the redrawing class either a superclass or a subclass of all the classes in question; either way provides the necessary correspondence, but I wouldn't say it's explicit. ---Dan
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
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/28/91)
In article <49087@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: > Am I crazy, or isn't (void *) impossible to indirect? Don't you have > to type-cast it first? Isn't this dynamic typing implemented on top of > C? YES. People are tossing around the term ``dynamic typing'' as if it were some truly important feature. ``Yeah, Bob, not only does the language have *loops*, but it has *dynamic typing*!'' ``Wow! *Dynamic typing*? Really?'' Dynamic typing isn't a semantic feature. It's a state of mind. If you want to use the pair (type,value) as a value with certain constraints, you can, whether the language supports it or not. It takes at most a good preprocessor to make this just as convenient as in any ``dynamically typed'' language. I accept that people want to use dynamic typing now and then. Fine! What I'm reacting to is this delusion that you need dynamic typing in the language to use it conveniently. Sure, I use associative arrays now and then, and I have an associative array library for the job. Why should I want the language to support associative arrays directly? > Do you > really think that I, like you, willfully misinterpret what is being > said to support a different point of view without trying either to make > a point or learn something from somebody else? Look, kid, I'm not misinterpreting what's being said here. People are saying that languages with built-in support for dynamic typing are somehow better than languages without such support. I'm reacting to that statement. On the occasions when I want dynamically typed variables, I can use them without trouble in C. Sure, this requires a void pointer type. SO WHAT? As I pointed out when I entered this discussion, the language does need *some* type that can represent *all* values if it's going to support dynamic typing. C has such a type, and adequate macros, and that's enough for me to get work done. *You* are misinterpreting my comments as something like ``Dynamic typing is useless. Anyone who wants to use dynamic typing is a fool.'' I'm just saying that it's pointless to have the compiler support dynamic typing, as it's just as easy to do in a library. ---Dan
peter@ficc.ferranti.com (Peter da Silva) (03/28/91)
In article <28436@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > We're going to write a real-time operating system in a language with > major run-time components? OK, a message queue for a non-real-time-but-pretty-fast operating system. "Real time" slipped out without thinking, because non-real-time systems don't seem to use things like message queues as basic primitives. Pity, because they are damned useful. -- Peter da Silva. `-_-' peter@ferranti.com +1 713 274 5180. 'U` "Have you hugged your wolf today?"
adam@visix.com (03/29/91)
In article <24673:Mar2802:15:1091@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: |> In article <1991Mar27.164605.24547@visix.com> adam@visix.com writes: |> > Let me get this straight. To construct a heterogeneous list of M |> > items each guaranteeing N operations, I need to waste space for M*N |> > function pointers? |> |> No, because you can just have a single ``class'' structure with the N |> function pointers, and keep just one pointer per ``object.'' But this |> extra layer is pointless for small problems, and I didn't bother putting |> it in. Okay, all objects of the same class can share a function table. But I would still have to make each "list of {fooable, barable}" and "list of {fooable, bazable}" use a new and different class, each with their own function table and constructor. And so a {fooable, barable, bazable} object is still classified twice, which is a waste. People want to use dynamic typing when they expect large numbers of different lists with different (and arbitrary) commonalities. |> > And I need to write an explicit constructor for every kind of list? |> |> That depends on what you mean by ``explicit.'' If you have several types |> each supporting some sort of redraw operation, and you want to set up a |> list of redrawable things, then you do have to say the correspondence |> between ``redrawable'' and the redrawing for each type. Other posters |> have mentioned how in object-oriented languages you can make the |> redrawing class either a superclass or a subclass of all the classes in |> question; either way provides the necessary correspondence, but I |> wouldn't say it's explicit. |> |> ---Dan As I see it, your form of dynamic typing requires a class heirarchy, with multiple inheritance yet. I think, for instance, the dynamic typing in GNU Emacs is better. Adam
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)
new@ee.udel.edu (Darren New) (03/29/91)
In article <27MAR91.22130574@uc780.umd.edu> cs450a03@uc780.umd.edu writes: >Did I say that? hmm... >If I have a bitmap, that's a homogenous collection, and I sure don't >carry type information along with each bit. Well, comparing it to the example of buttons and subviews and scrollbars in a list, yes you said that. Of course, there will be homogenous lists where you don't carry the types along. But that isn't what we were talking about. We were talking about seemingly-hetro lists which you said were actually homogeneous. >On the other hand, if for some reason I wanted a collection of bitmaps >and strings, I'd have a list of pointers to data descriptors. One >pointer (and descriptor) for each element of the list. Those data >descriptors would carry "type" [and size], etc. But I deal with a >homogenous collection: a list of pointers. And I deal with a hetrogeneous list of both strings and bitmaps. I look at how I use the data, and you look at how you implement hetrogeneous collections. I don't want to deal with pointers to descriptors; I want to deal with bitmaps and strings. How that gets implemented is secondary to the problem that needs strings and bitmaps to solve. Similarly, I want to deal with symbolic names for functions and variables and let the linker deal with resolving it instead of working with stack-frame offsets; where a variable is in the stack is not part of the solution to my problem. When I have a floating point number, I don't want to deal with a 3tuple of <sign, exponent, mantissa> and recode all the floating point operations in terms of this. I want to deal with a float directly. Of course, assembly language (or hardware) will have to deal with it as a 3tuple, but I don't want to. The closer a language can come to providing the data types required by my problem, the easier it will be to solve that problem. If the language lets me deal with hetrogeneous collections directly by allowing the type of a variable to change dynamically over time, then I have an easier time dealing with bitmaps and strings. If I have to implement bitmaps and strings as pointers to data descriptors carrying a type tag and then within my routines check the type tag, I have more work to do without any more solved problems. I also don't want to have to tell bitmaps and strings that they may both be put in a list together. The fact that a bitmap might appear in the same list as a string is completely irrelevant to the functionality of a bitmap. Requiring me to do so would be like requiring me to list all of the variables that may hold a bitmap *in*the*description*of*bitmaps* instead of in the descriptions of the variables; clearly, this reduces reusability. >Personally, if I have bitmaps and strings, I'd prefer to refer to them >by separate names (that is, store them in separate variables). And as >a general rule, this runs faster (than using indirection). I too. However, sometimes (like with a window containing a graphic view and a textual view and buttons and sliders and ...) you need to put things of different types that behave similarly in some way, together. I sometimes need to store them in a hetrogeneous collection. Just like sometimes I store both source and executables in the same directory. I don't want to have to tell 'ls' in advance what the possible types of files are in each directory. I don't deny that static typing is useful; I don't think anybody here has. I don't deny that dynamic typing can be implemented on top of static typing and typecasts/unions; objective-C does exactly this. I don't deny that hetrogeneous lists can be implemented by homogeneous lists of pointers to tagged data; I don't know of any dynamically-typed languages where this isn't how it's done. I deny that dynamic typing is useless: all dynamically-typed languages I've seen come with a large reusable class languages. I deny that hetrogeneous collections are never needed; I've provided many lists of hetrogeneous collections that people use every day. I deny that the best way to think about dynamic typing is by worrying about how one could implement it in C. >Raul Rockwell -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+ + When you drive screws with a hammer, screwdrivers are unrecognisable +
new@ee.udel.edu (Darren New) (03/29/91)
In article <25655:Mar2803:50:2491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Dynamic typing isn't a semantic feature. It's a state of mind. Exactly. Modularization is also a state of mind. So are local variables. So is recursion. So is separate compilation. So are libraries, for that matter. None of these can't be done in raw machine code (with suitable preprocessors ;-). However, when the language I use supports my "state of mind" then I find I can be much more productive. When I implement dynamic typing myself, I have to worry about type mismatches that aren't caught by the compiler. If I let the compiler/interpreter handle dynamic typing, it catches the errors for me. Just like when I implement modularization or local variables myself, I sometimes make mistakes which the compiler can't catch because I can't tell it that a particular variable is local. I would much rather adjust once the computer to match my state of mind than to adjust my state of mind to match the computer every time they disagree. >If you >want to use the pair (type,value) as a value with certain constraints, >you can, whether the language supports it or not. It takes at most a >good preprocessor to make this just as convenient as in any >``dynamically typed'' language. You mean a good preprocessor like Lisp, or Objective-C? Wow, heavy. I didn't realize I can do the Objective-C transformations by hand and get the same results :-O. Of course, without a good preprocessor (which most of the rest of us have been calling "a dynamicly-typed language compiler") it is damn inconvenient. >*You* are misinterpreting my comments as something like ``Dynamic typing >is useless. Anyone who wants to use dynamic typing is a fool.'' I'm just >saying that it's pointless to have the compiler support dynamic typing, >as it's just as easy to do in a library. I'm not interpreting your comments that way. I'm interpreting your stance as saying that dynamic typing implemented by the user on top of static typing is just as useful and convenient as dynamic typing in a language. I disagree that dynamic typing innards being visible to the user is a "good thing" any more than local variable management during recursion being managed by the user is a "good thing." I don't care what semantics the language supports. As you and I have both pointed out, all programs can be reduced to huge finite state machines. The question is not the semantics of the language, but rather how well the syntax I use to describe this huge fsm matches how I think about the problem. > >---Dan -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+ + When you drive screws with a hammer, screwdrivers are unrecognisable +
cs450a03@uc780.umd.edu (03/29/91)
Darren New >> Me > >>If I have a bitmap, that's a homogenous collection, and I sure don't >>carry type information along with each bit. > >Well, comparing it to the example of buttons and subviews and >scrollbars in a list, yes you said that. Of course, there will be >homogenous lists where you don't carry the types along. But that isn't >what we were talking about. We were talking about seemingly-hetro lists >which you said were actually homogeneous. Well, I guess I should pay attention, and find out what I was really saying... 8-) Or make yet another attempt to have what I think I'm saying the same thing as other people understand me to be saying. Maybe if I clarified my terms? A list which was made by sticking a string of bits onto the end of a string of characters would be hetrogenous. Each bit and each character would need a type tag. The list's type in this case is not "string of bits" and not "character string", but "hetrogenous". The language I use is dynamically typed. Each structure has size and type information associated with it. If I made a list which was made by catenating a list of structures onto a list of bits, then each element would have to have a type tag: either "structure" or "bit". You might call that silly. I call that hetrogenous. I was very careful, each time I called a list of structures homogenous, to point out that this was my point of view, and not an attempt to classify all problems for all people. I hope my statements are now understandable. Raul Rockwell
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
marcs@slc.com (Marc San Soucie) (03/30/91)
Joseph Pallas writes: > 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. This is pretty left-field thinking. A collection is an entity, not an activity. The collection exists regardless of what you do or whether you do anything with it. So argue the definition of the entity, not the operations that are to be performed on it or its members. Yes, in Smalltalk there is a base class from which everything inherits, so yes, you can claim that in Smalltalk there cannot ever be a truly heterogeneous collection. So in C++ every object is a bunch of bytes. Big deal. How about a more accurate but possibly meaningless definition of a heterogeneous collection: A collection on the types of whose members there are no explicit constraints. From which derives the possibly equally meaningless theorem: It is easier to construct such a collection in a Smalltalk-like language than in a C++-like language. Which leads me to wonder: Can this discussion lead to any meaningful insights? Marc San Soucie Servio Corporation Beaverton, Oregon marcs@slc.com
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
sommar@enea.se (Erland Sommarskog) (04/01/91)
Also sprach Darren New (new@ee.udel.edu): >Hmm... a homogenous collection that when you take it apart yields things >with different types. Somehow, I think we are confused over terminology. >Either that, or you are reaching for straws :-) The whole point of >a hetrogeneous collection is that sometimes you treat everything >the same and sometimes you treat each thing differently. I think no one questions the use of heterogeneous collections. But how common are the cases when the collections is heterogeneous that they don't even have a common inheritance structure which can't be described in a statically typed language. Static typing does not preclude dynamic binding. -- 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! ----------------------
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?"
chip@tct.com (Chip Salzenberg) (04/02/91)
According to carroll@cis.udel.edu (Mark Carroll): >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:". I cannot cast my argument in this form, because that's not the point of this thread. The original question was, "Why do you _need_ heterogenous collection?" I have enjoyed debunking some of the replies. However, the heterogenous/homogenous collection issue is really a side issue for me. I like static typing for its measure of safety from message-not-recognized errors. If that forces me to use the C++ preprocessor to make collection classes, I can live with that. >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. Agreed, as far as it goes. But I'm not willing to sacrifice type safety for that notational convenience. -- Chip Salzenberg at Teltronics/TCT <chip@tct.com>, <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
pallas@eng.sun.com (Joseph Pallas) (04/02/91)
In <b32pvj.em4@wang.com> marcs@slc.com (Marc San Soucie) writes of my definition of heterogeneous collections: >This is pretty left-field thinking. A collection is an entity, not an >activity. The collection exists regardless of what you do or whether >you do anything with it. So argue the definition of the entity, not >the operations that are to be performed on it or its members. Now, I have to admit that, at first glance, it may seem odd that the definition I offered has this dependency. But I think I can explain why it does. We all seem to agree that "heterogeneous" has something to do with the types of objects. The problem arises from the very nature of OOP in that it emphasizes inclusion polymorphism (usually in the form of subtypes). The consequence of this is that it is not possible in general to speak of "the type" of some object. Objects have many types, as the types are organized hierarchically in a containment relationship. Now, we can (as Marc pointed out) simply stop there and say that in Smalltalk, for example, there are no heterogeneous collections because there is a type of which all objects are members. But that clearly doesn't capture the notion we have in mind when we talk about heterogeneous collections. So, given a collection of objects and a desire to talk about the types of those objects, how do we decide which types to use? I claim that, in a dynamically typed language like Smalltalk, the only types we can sensibly use for this kind of discrimination are the types implied by the operations we actually perform. >How about a more accurate but possibly meaningless definition of a >heterogeneous collection: > A collection on the types of whose members there are no explicit > constraints. This isn't very interesting, since this definition makes all Smalltalk collections heterogeneous. It doesn't capture the common notion that collections are either homogeneous or heterogeneous. As for the question of whether this discussion is leading anywhere, I suspect not. joe
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!"
kers@hplb.hpl.hp.com (Chris Dollin) (04/02/91)
Dan Bernstein says: Dynamic typing isn't a semantic feature. It's a state of mind. If you want to use the pair (type,value) as a value with certain constraints, you can, whether the language supports it or not. It takes at most a good preprocessor to make this just as convenient as in any ``dynamically typed'' language. I call this ``designing a new language and compiling into [in this case] C''. C doesn't have [*1] dynamic typing, and the new language does. Look, kid, I'm not misinterpreting what's being said here. People are saying that languages with built-in support for dynamic typing are somehow better than languages without such support. I'm reacting to that statement. On the occasions when I want dynamically typed variables, I can use them without trouble in C. The last sentence merely highlights Dan's competence as a programmer; not all of us are so lucky. -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
new@ee.udel.edu (Darren New) (04/03/91)
In article <28MAR91.21053267@uc780.umd.edu> cs450a03@uc780.umd.edu writes: >Darren New >> >Me > >>>If I have a bitmap, that's a homogenous collection, and I sure don't >>>carry type information along with each bit. >> >>Well, comparing it to the example of buttons and subviews and >>scrollbars in a list, yes you said that. Of course, there will be >>homogenous lists where you don't carry the types along. But that isn't >>what we were talking about. We were talking about seemingly-hetro lists >>which you said were actually homogeneous. > >Well, I guess I should pay attention, and find out what I was really >saying... 8-) Or make yet another attempt to have what I think I'm >saying the same thing as other people understand me to be saying. Sorry. Looking back on it, I realize that my above-quoted material sounds quite rude. I didn't mean it that way, and I apologise. I think sometimes these language/flame wars go off because people take statements out of context and then change the context, and I suspect it is because of the passage of time between comments, and not on purpose. My interpretation of the conversation went as follows: I said "a window is hetrogeneous and thus you need dynamic typing" and you said "I treat that as a collection of pointers to tagged structures" and I said "I would implement it that way but I would treat it as a collection of buttons and texts and ..." and you said "but it would be silly to treat a bitmap as an array of pointers to tagged structures" and I said the above. (Or at least, that's how I interpreted it.) Anyway, my point is that I'm sorry if I sounded like you were weasling or if I was rude. I didn't mean it that way. I just meant that the point you were making was not the point I was arguing and that I agree with you in the case you were arguing. It sounded like you were changing context, and I merely wanted to say "in the context which you first made that statement, it seemed to me that you did not mean what you meant by the same context in the current statement." How's that? :-) >Maybe if I clarified my terms? > >A list which was made by sticking a string of bits onto the end of a >string of characters would be hetrogenous. Each bit and each >character would need a type tag. The list's type in this case is not >"string of bits" and not "character string", but "hetrogenous". Sounds like ASN.1: SEQUENCE OF { CHOICE {alpha OCTETSTRING, beta BITSTRING}} (modulo memory faults) Anyway, so why would you not call a list inside of a window structure that tells the window what buttons, scrollers, and other subviews it contains, a hetrogeneous list rather than a list of pointers to tagged structures? I see little difference between this list and a list of "string of bits or characters" except for the size of the structures. >The language I use is dynamically typed. Each structure has size and >type information associated with it. If I made a list which was made >by catenating a list of structures onto a list of bits, then each >element would have to have a type tag: either "structure" or "bit". >You might call that silly. I call that hetrogenous. I call that hetrogeneous also. Are you saying that because the elements of the window list are not stored inline then the list is not hetrogeneous? Or is it because the type tags in the window example are stored with the elements of the list rather than actually in the list? What about the case where the list, the types, and the bits are all physically stored disjointly? Or is it that in one case, you would mentally envision it in one way and in the other case you would mentally envision it the other way, regardless of implementation? In that case, I don't think there is much more to say except that a language that allows both visualizations is probably better than a language that allows only one such viewpoint. >I was very careful, each time I called a list of structures >homogenous, to point out that this was my point of view, and not an >attempt to classify all problems for all people. Again, I apologise if I sounded rude or nasty. That was not the intent. I also have trouble when people misinterpret what I was unable to state clearly enough. I believe at least one of my followups said something like "you prefer to treat it as a list of pointers and I prefer to treat it as a list of stings and bitmaps". I realize that it is *all* point-of-view because at the bottom level, it's all bits. I was merely trying to keep the discussion focused on hetrogeneous lists which could be interpreted as homogenous, and not on clearly-homogenous lists. >I hope my statements are now understandable. >Raul Rockwell Hmmm... Tell the truth, it didn't really clarify much, unless you mean that a list of two different types of structures will always be homogenous because you always store "pointers to tagged structures" but an intermixed list of bits and characters is hetro because they are physically stored ajacent to each other. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+ + When you drive screws with a hammer, screwdrivers are unrecognisable +
cs450a03@uc780.umd.edu (04/03/91)
Darren New writes: [big long apology] ((thanks, wasn't expecting that)) [recap of discussion thread] ((looks more-or-less correct)) >Anyway, so why would you not call a list inside of a window structure that >tells the window what buttons, scrollers, and other subviews it contains, >a hetrogeneous list rather than a list of pointers to tagged structures? >I see little difference between this list and a list of "string of bits >or characters" except for the size of the structures. > >Are you saying that because the elements of the window list are not >stored inline then the list is not hetrogeneous? Or is it because the >type tags in the window example are stored with the elements of the >list rather than actually in the list? What about the case where the >list, the types, and the bits are all physically stored disjointly? >Or is it that in one case, you would mentally envision it in one way >and in the other case you would mentally envision it the other way, >regardless of implementation? Hmm... (Why) Because I can operate on the list without checking the types. This occurs because I'm not writing the windowing code, you are :-) I suppose, also, it is because none of the information is stored inline is the reason I'd call the list homogenous. That is, perhaps, an arbitrary distinction. I don't put a whole lot of emphasis on the type-tags which the language uses to manage storage. I have to be aware of them because they have an impact on efficiency and speed, but... hmm... I look at "type" as meaning "x is in the domain of function f". So I might, for instance, consider even numbers to be a type, or maybe sets composed of unique elements from the ranges 1 .. 7, 1000...9999, and/or 100000...100999. Now if I had three functions, one of which took as arguments numbers in the range 1..7, another 1000...9999, etc., then maybe I'd consider those sequences of numbers to be hetrogenous lists. The point being that I had to write three separate functions to handle them, and I have the overhead of a conditional in front of each function application. Maybe that's an artificial distinction. If I wanted to make sure that these numbers weren't accidentally treated as arithmetic objects, I'd have to encapsulate them anyways (put them in structures and work with pointers to these structures). So you could say I'm being backwards... It boils down to: I like to think of "pointers" as a single type. It is only when I examine the data that they are pointing to that I like to think of the data as being typed. This is influenced by the primitives I normally work with. >>I hope my statements are now understandable. >>Raul Rockwell > >Hmmm... Tell the truth, it didn't really clarify much, unless you mean >that a list of two different types of structures will always be >homogenous because you always store "pointers to tagged structures" but >an intermixed list of bits and characters is hetro because they are >physically stored ajacent to each other. Ahh... It is not that I consider the structures to have the same type. It is that I consider the pointers to have the same type. All of my primitives that work on pointers (except the ones that extract information from the encapsulated structure) will work on any list of pointers. This is just an off-the-cuff sort of classification, I admit. If there is anything left to say on this topic, it is probably on the distinction between what a function can meaningfully operate on vs. what information can be meaningfully stored. Raul Rockwell
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)