Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!samsung!crackers!m2c!umvlsi!dime!dime.cs.umass.edu!moss From: moss@cs.umass.edu (Eliot Moss) Newsgroups: comp.object Subject: Re: Void references Message-ID: Date: 14 Nov 90 14:49:58 GMT References: <1990Nov7.220902.13393@Neon.Stanford.EDU> <1990Nov9.010930.26493@Neon.Stanford.EDU> <447@eiffel.UUCP> <1990Nov12.003645.26615@Neon.Stanford.EDU> Sender: news@dime.cs.umass.edu Reply-To: moss@cs.umass.edu Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) Lines: 79 In-reply-to: craig@Neon.Stanford.EDU's message of 12 Nov 90 00:36:45 GMT I have two things to add to this discussion: (1) First, the idea of multiple representations for individual objects of the same type, and specifically its application to situations such as the empty list, has already appeared in the literature, so let's give some authors credit: @INPROCEEDINGS{LTP86, AUTHOR = "Wilf R. {LaLonde} and Dave A. Thomas and John R. Pugh", TITLE = "An Exemplar Based {Smalltalk}", BOOKTITLE = oopsla, ADDRESS = "Portland, OR", YEAR = 1986, MONTH = sep, ORGANIZATION = acm, PAGES = "322--330", SERIES = sigplan, VOLUME = "21(11)" } It does seem like a reasonable idea in that it cleans up code and takes advantage of the implicit "type test" performed by the dynamic method lookup mechanisms of OO languages. And it does so without violate static type constraints. It is not clear if there is a performance difference between the techniques. With nil you can detect end of list without having to follow that last pointer (it has a distinguished magic value, frequently 0; in my Smalltalk implementation nil is also a static constant rather than a pointer to the Nil object precisely to speed up the code in a lot of places (we can still send messages to it, etc.)); without nil you eliminate a number of conditional checks (but will always have to do dynamic calls). A detailed study of the relative performance of the techniques would be interesting; I am not aware of its having been done. (2) Since I was in on the design of CLU and also participated in Trellis/Owl, perhaps I can add a little w.r.t. to them as well. First, variables can potentially be uninitialized; this is supposed to be detected by the run time system. A compiler can, with simple data flow analysis, sort the variables into three categories: definitely initialized before use, definitely *not* initialized before use (produce an error message and code to raise an exception if that point is reached in the program); and uncertain (requires run time check and possible exception at run time). The uncertain category will tend to be pretty rare if reasonable programming style is used. This does not directly relate to the void pointer question, but I thought it might help clarify things w.r.t. Bertrand's points about total/partial correctness analogies, etc. To do a linked list in CLU you use a "oneof" (or "variant"; the distinction is not all that relevant here) type, which is similar to a variant record in Pascal. Such an object has a tag, and there is a tagcase statement for testing the tag, which allows you to interpret the contents of the oneof according to its actual tag, in a type safe manner. This avoids the concept of a void pointer and replaces it with the concept of a void case in an object format. The CLU approach leads to a nicer type system, but the representation is not as compact and the coding perhaps more verbose than if we had void pointers. Some ML compilers are smart enough to use the actual void pointer representation for its analog of "oneof" when there are only two cases, one of them void. The exemplar approach does not exactly get around the data compactness problem -- the "tag" is the type field in the object, used by the run time for method lookup. Of course, if the type field *must* be there for other reasons, then there is no *additional* overhead. The end of list object must also be represented explicitly. But the main thing is that the code is compact. Personally, I would not call the end of list object a "don't care". Among other things, it probably says nasty things if you send car or cdr to it, but it *does* implement them, so it is type correct in the sense that the method is guaranteed to exist. If one had full signatures including exceptions, as in CLU, Trellis/Owl, Modula-3, etc., then car and cdr should be noted as possibly raising an exception. Well, I hope this was helpful to some of you anyway ..... -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206; Moss@cs.umass.edu