warren@cbnewsh.att.com (warren.a.montgomery) (03/29/91)
In the discussion of statically and dynamically typed languages, there are two positions being asserted that I want to take exception with: "Run-time checks are unsuitable for high reliability systems, because you can't afford a run-time detected error". In fact, any high reliability system, like spacecraft control or telephone network control, must cope sensibly with run-time detected errors of all sorts. Just because your favorite tool throws up it's hands and coredumps because it got an error, don't assume that that is the only response possible. High reliability systems must have strategies for recovery from even "impossible" errors that keep the system running safely. "Compile time checking and certified compilers eliminate the need for run-time checking." As noted above, high reliability systems need to recover from impossible errors, because no error is really impossible. To do this, errors must be detected, preferably as soon as possible and before too much damage is done as the result of using erroneous data. Run time checks of type and data structure consistency are a major aid in early error detection, and in sensible recovery once the error is detected, and are a major strategy in building this kind of system. Optimizing compilers that throw away "redundant" information at run-time and restructure the text and data can be a problem in building systems like this, because the state the system reached before the error may not be easy to determine. I'm not arguing against eliminating as many errors as possible before the software winds up controling a reactor, but PLEASE design the software that does control the reactor under the assumption that anything, even impossible things, can go wrong, and design the language and compiler used for that software to leave enough information around at run-time to support defensive checks and effective error recovery procedures. -- Warren Montgomery att!ihlpf!warren
chip@tct.com (Chip Salzenberg) (04/02/91)
According to warren@cbnewsh.att.com (warren.a.montgomery): >"Run-time checks are unsuitable for high reliability systems, > because you can't afford a run-time detected error". That statement misrepresents the position of static typing partisans. Of course run-time errors will occur. However, any run-time error that could have been detected at compile-time is Evil and Rude to the user. Thus I choose static typing when possible. >"Compile time checking and certified compilers eliminate the need > for run-time checking." That statement is a straw man, and does not deserve rebuttal. -- 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
richieb@bony1.bony.com (Richard Bielak) (04/04/91)
In article <27F780E2.1872@tct.com> chip@tct.com (Chip Salzenberg) writes: >According to warren@cbnewsh.att.com (warren.a.montgomery): >>"Run-time checks are unsuitable for high reliability systems, >> because you can't afford a run-time detected error". > >That statement misrepresents the position of static typing partisans. >Of course run-time errors will occur. However, any run-time error >that could have been detected at compile-time is Evil and Rude to the >user. Thus I choose static typing when possible. > [...] Another argument for static type checking is that it is more efficient, since many checks need only to be done once - at compile time - and not millions of times at run time. Confucius says "It is more efficient to do something once, than to do it a thousand times". ...richie -- *-----------------------------------------------------------------------------* | 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. |
craig@leland.Stanford.EDU (Craig Chambers) (04/07/91)
In article <1991Apr3.203332.25348@bony1.bony.com>, richieb@bony1.bony.com (Richard Bielak) writes: |> Another argument for static type checking is that it is more |> efficient, since many checks need only to be done once - at compile |> time - and not millions of times at run time. I disagree. In a non-object-oriented language, type information does provide significant help to the compiler, since types map one-to-one with implementations/representations. However, in a non-object-oriented language (at least one with a good type system), types specify interfaces (plus possibly some behavioral specifications) to objects, but specifically attempt to abstract away from specifying anything about implementations/ representations of the objects of particular types (to support more reusability of code). This means that such interface-level types provide little information for a compiler to use to optimize messages sent to such objects. So the standard argument that static type information speeds execution of programs does not apply to object-oriented languages (or at least does not apply to anything near the degree it does in non-object-oriented languages). -- Craig Chambers
bertrand@eiffel.UUCP (Bertrand Meyer) (04/08/91)
From <1991Apr7.013813.23513@leland.Stanford.EDU> by craig@leland.Stanford.EDU (Craig Chambers): > In a non-object-oriented language (at least one with a good type system) > types specify interfaces (plus possibly some behavioral specifications) > to objects, but specifically attempt to abstract away from specifying > anything about implementations/representations of the objects of > particular types (to support more reusability of code). > This means that such interface-level types provide little information > for a compiler to use to optimize messages sent to such objects. > So the standard argument that static type information speeds execution > of programs does not apply to object-oriented languages > (or at least does not apply to anything near the degree it does > in non-object-oriented languages). This runs contrary to our experience. To handle a routine call x.f with polymorphism on x and dynamic binding on f, it helps the compiler considerably to have the type information resulting from the declaration x: SOME_TYPE which indicates that the objects to which x may be attached at the time of the call are not arbitrary, but must be instances of SOME_TYPE (that is to say, direct instances of SOME_TYPE itself or of one of its descendants). By restricting the scope of possible types (classes), this information enables the compiler to handle calls in a much more efficient way than otherwise. -- Bertrand Meyer Interactive Software Engineering Inc., Santa Barbara bertrand@eiffel.uucp
craig@leland.Stanford.EDU (Craig Chambers) (04/13/91)
In article <524@eiffel.UUCP>, bertrand@eiffel.UUCP (Bertrand Meyer) writes: |> From <1991Apr7.013813.23513@leland.Stanford.EDU> by craig@leland.Stanford.EDU |> (Craig Chambers): |> |> > In a non-object-oriented language (at least one with a good type system) |> > types specify interfaces (plus possibly some behavioral specifications) |> > to objects, but specifically attempt to abstract away from specifying |> > anything about implementations/representations of the objects of |> > particular types (to support more reusability of code). |> > This means that such interface-level types provide little information |> > for a compiler to use to optimize messages sent to such objects. |> > So the standard argument that static type information speeds execution |> > of programs does not apply to object-oriented languages |> > (or at least does not apply to anything near the degree it does |> > in non-object-oriented languages). |> |> This runs contrary to our experience. To handle a routine |> call |> |> x.f |> |> with polymorphism on x and dynamic binding on f, it helps the |> compiler considerably to have the type information resulting |> from the declaration |> |> x: SOME_TYPE |> |> which indicates that the objects to which x may be |> attached at the time of the call are not arbitrary, |> but must be instances of SOME_TYPE (that is to say, |> direct instances of SOME_TYPE itself or of one of its |> descendants). |> |> By restricting the scope of possible types (classes), this |> information enables the compiler to handle calls in a much |> more efficient way than otherwise. |> |> -- Bertrand Meyer |> Interactive Software Engineering Inc., Santa Barbara |> bertrand@eiffel.uucp What does your compiler generate to handle message sends? It is certainly possible to have a relatively inefficient scheme that gets faster as more information is provided. However, the efficient message passing schemes such as in-line caching or a polymorphic form of in-line caching we've recently developed (and will publish in ECOOP'91) are basically just as fast as the virtual function calls in C++ 2.0, for the case in which the in-line cache hits. I was under the impression that Eiffel uses a slower implementation of message passing than either in-line caching or indirect function calls, which (depending on how it's implemented) could get faster with more precise type information. Please correct my impression if I'm wrong; I've tried before to get someone at ISE to tell me how Eiffel implements things. Knowing that some code type checks provides the information to the compiler that no message-not-understoods could arise at some message send. In most situations there still will be several possible legal methods that could be invoked by a particular call site, and so some sort of run-time dispatch is required even in the statically-typed case. It can be a little faster with this knowledge, allowing implementations like C++'s, but not significantly faster. In a non-object-oriented language, such type information supports inlining away the function calls and data accessors, which is what I meant by significant performance improvement. -- Craig Chambers
bertrand@eiffel.UUCP (Bertrand Meyer) (04/15/91)
From <1991Apr12.190418.13128@leland.Stanford.EDU> by craig@leland.Stanford.EDU (Craig Chambers): > I was under the impression that [Interactive's implementation of] > Eiffel uses a slower > implementation of message passing than either in-line caching or indirect > function calls, which (depending on how it's implemented) could get faster > with more precise type information. Another case of misinformation about Eiffel and its implementation. As far as I know, the application of what Mr. Chambers calls ``indirect function calls'' to a language supporting multiple inheritance was invented by the Eiffel implementation team, and was part of the first commercial implementation of Eiffel released at the end of 1986. I remember that several people looked *very* studiously then at the form of our generated code. The implementation uses constant-time dynamic binding, with small overhead over the routine call mechanism in standard languages (static binding) by building the appropriate routine tables and indexing through them. Returning to the original topic of this discussion, it would be impossible to build these tables at compile time without the type information provided by the language. We looked at caching (a variant of which was sketched in Brad Cox's January 1984 IEEE Software article), but realized quickly that although it could make sense for a Smalltalk-like typeless language to decrease the cost of dynamic binding, it was useless for a typed language where type information made it possible to obtain a much more efficient implementation . -- -- Bertrand Meyer Interactive Software Engineering Inc., Santa Barbara bertrand@eiffel.uucp
objtch@extro.ucc.su.oz.au (Peter Goodall) (04/15/91)
>although it could make sense for a Smalltalk-like typeless language
^^^^^^^^
Variables in Smalltalk are untyped, Objects are. We could argue over what a
type i but I will assert that Smalltalk is strongly, typed at message send,
and I'mm not the only person to think so. Also Type is not equivalent to
class in Smalltalk.
Thanks,
--
Peter Goodall | INTERNET:bertrand@eiffel.UUCP (Bertrand Meyer) (04/15/91)
From <objtch.671666790@extro> by objtch@extro.ucc.su.oz.au (Peter Goodall): [Quoting me] >> although it could make sense for a Smalltalk-like typeless language [PG's comment] > Variables in Smalltalk are untyped, Objects are. We could argue over what a > type i but I will assert that Smalltalk is strongly, typed at message send, > and I'mm not the only person to think so. It is fairly common to use ``typed'' for ``statically typed'' and ``untyped'' for ``dynamically typed''. Indeed, by ``untyped'' I meant dynamically typed. (I don't think anyone will argue that Smalltalk is statically typed; this discussion addresses static vs. dynamic typing.) By the way, ``untyped'' or ``dynamically typed'' is not an insult; just not everybody's cup of tea. Sorry for using a somewhat simplistic terminology. -- -- Bertrand Meyer Interactive Software Engineering Inc., Santa Barbara bertrand@eiffel.uucp
craig@leland.Stanford.EDU (Craig Chambers) (04/16/91)
In article <526@eiffel.UUCP>, bertrand@eiffel.UUCP (Bertrand Meyer) writes: |> We looked at caching (a variant of which was sketched in Brad Cox's |> January 1984 IEEE Software article), but realized quickly that |> although it could make sense for a Smalltalk-like typeless language |> to decrease the cost of dynamic binding, it was useless for a typed |> language where type information made it possible to obtain a much more |> efficient implementation . I disagree that in-line caching is much less efficient than an indirect function call-based implementation. For our Self implementation on a SPARC using an advanced form of in-line caching, a dynamically-bound message (with no extra type information) takes 8 cycles plus 4 cycles per exact receiver type used at that call site, e.g. a monomorphic send takes 12 cycles, a send with 2 equally-likely receiver types takes on average 14 cycles, a send with 5 equally-likely receiver types takes on average 20 cycles. (These numbers are after initial start-up cache misses.) This sequence contains 1 load instruction, so there's the potential for more cycles if there's a hardware cache miss on this load. For C++ 2.0-style virtual function calls in the presence of multiple inheritance, the code generated by most C++ implementations takes a constant 7 cycles on a SPARC (8 cycles if in the presence of virtual base classes), but with 3 loads (4 loads for virtual base classes), so the likelihood of a hardware cache miss on some of the loads is greater than for the in-line caching scheme. This technique does not interact well with other system services such as garbage collection since it creates pointers into the middle of objects. Some recent work has developed techniques for reducing this cost to C++ 1.0 level with a lot of link-time analysis of the program. I don't know what Eiffel's techniques are; no one has described them publically that I know of, and you seem hesitant to do so here. But assuming it's as fast as C++ 2.0's scheme (which would be a stretch since Eiffel supports GC and other things that would make interior pointers a pain), then you could say that your/C++'s scheme is between 2 and 3 times faster on average than Self's form of in-line caching. However, these few cycles are a pretty low overhead compared to the total cost of calling an external procedure versus inlining a short operation. My original posting was attempting to distinguish between the difference in performance between a non-object-oriented language in which type information allows inlining of short operations and hence a big difference in performance, and an object-oriented language in which type information allows a savings of a few cycles per call but not the gross improvement of inlining. So I stand by my claim that static type information doesn't improve the performance of OO programs anywhere near the extent that it improves the performance of non-OO programs. A little improvement, yes, but not much. The right approach to dramatically improving performance of OO programs is not to add static interface-level type declarations but instead to pursue other techniques to infer low-level type information that support full inlining. -- Craig Chambers
diamond@jit345.swstokyo.dec.com (Norman Diamond) (04/16/91)
In article <528@eiffel.UUCP> bertrand@eiffel.UUCP (Bertrand Meyer) writes: >It is fairly common to use ``typed'' for ``statically typed'' and >``untyped'' for ``dynamically typed''. Yes, and this usage has a long history. However, it really does cause confusion. A Smalltalk variable really is dynamically typed by the language definition, because message sends have to reach the correct methods. However, a C variable of type "void *" really is untyped (well, almost) because everything is up to the programmer; the language does not provide for recovery of type information. -- Norman Diamond diamond@tkov50.enet.dec.com If this were the company's opinion, I wouldn't be allowed to post it.
bobatk@microsoft.UUCP (Bob ATKINSON) (04/19/91)
Bertrand Meyer writes:
-As far as I know, the application of what Mr. Chambers calls
-``indirect function calls'' to a language supporting multiple
-inheritance was invented by the Eiffel implementation team,
-and was part of the first commercial implementation of Eiffel
-released at the end of 1986.
-
-The implementation uses constant-time dynamic binding, with
-small overhead over the routine call mechanism in standard
-languages (static binding) by building the appropriate routine tables
-and indexing through them.
Has this dispatching technique been published anywhere?
Or is it (understandably, perhaps) considered proprietary by ISE?
Bob Atkinson
Microsoft