Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!stanford.edu!neon.Stanford.EDU!brm From: brm@neon.Stanford.EDU (Brian R. Murphy) Newsgroups: comp.lang.misc Subject: Re: Dynamic typing (part 3) Keywords: type inference static dynamic lisp ml Message-ID: <1991Apr9.021700.2688@neon.Stanford.EDU> Date: 9 Apr 91 02:17:00 GMT References: <3073:Mar2820:38:5191@kramden.acf.nyu.edu> <1991Apr1.010526.26781@neon.Stanford.EDU> Sender: brm@cs.stanford.edu Organization: Computer Science Department, Stanford University, Ca , USA Lines: 103 In article boehm@parc.xerox.com (Hans Boehm) writes: >brm@neon.Stanford.EDU (Brian R. Murphy) writes: >>Unfortunately, given a statically-typed language with higher-order >>functions and an "all" type, type inference appears to be >>undecideable. Thus your statically-typed language _requires_ type >>declarations, whereas in a dynamically-typed language we can get by >>without them. > > I think this is getting into an area where we need a bit more precision. >The argument implied by Brian seems to be that with a dynamically typed >language and some automatic type inference, we can get similar performance >to a statically typed language. I think we are no longer addressing >reliability issues. I didn't say anything at all about performance. I would agree that with a statically typed language you can achieve higher performance than with a dynamic language, in general. Doing certain sorts of type inference can reduce the performance differential, but it's still true that statically typed programs will be more efficient in general. My complaint about statically typed languages is that I _can't_ do some things in them that I _do_ in dynamically typed languages (such as Lisp). For example, I can't I write a function which returns either a boolean or an integer in a complex way. I can't write my own Y combinator. I can't write a function which allows either a sequence of functions which range over numbers or a sequence of numbers as an argument. Let's consider what a type system might do for me: (1) It constrains the behavior of primitive functions so the program doesn't do undefined things. If "+" when applied to non-numbers has some undefined behavior, then such applications should be prevented, or else debugging programs becomes a nightmare. Any strongly typed language does this. [ This is essential, in my opinion, in either kind of type system. ] (1') In the case of overloaded primitives, a type system selects which underlying operation to use on given arguments. A static type system allows this to be done at compile time, a dynamic type system does it at run time, although analysis can do some at compile time. [ Static wins here. ] (2) It constrains the use of procedures that I write so that they aren't applied to things they weren't intended to apply to. Thus, I might declare an argument to have a particular type, and applications to objects not in that type are prevented. Statically typed languages usually _force_ me to make such declarations. The problem with this is that often a static type language is neither specific nor general enough to adequately describe the types in my programs. If I really want true safety here, I'd have to have a type language which allows me to express complex relationships (such as "sorted sequence", for example). Thus it must be very specific. In other cases, argument types (or certain parts of them) don't matter at all, and I'd like to be able to omit such declarations. Thus I want a type system which (a) allows me to omit many type declarations (where unnecessary) (b) allows me to be very specific in constraining some arguments With dynamic typing, I can simply write predicates to constrain arguments/variables (Common Lisp, FL, some implementations of Scheme do this). You static typing advocates claim that a static type system can do this for me, but I claim that it can't. A type language powerful enough to constrain arguments anywhere near as precisely as I need won't allow me to omit many types. Type inference is only possible for a limited class of type languages, and they tend to be fairly weak. In addition, certain programs are forbidden simply because they utilize types which can't be described by the type language used. [ dynamic wins here ] (3) It shows efficient representations of certain objects. A static type system allows this. Given sophisticated analyses, a dynamic type system allows this in some cases. [ static wins here ] IN Conclusion, I observe that static typing wins on points (1) and (3), which are merely performance issues. Dynamic typing wins big on point (2), which is a programming expressiveness issue. Neither is really adequate, but dynamic typing's problems are merely performance issues; improved compiler technology will gradually eat away the performance advantages of static typing (plus you can always just buy a faster machine). Static typing's problems seem a little harder to work around (required declarations, some valid programs forbidden, constraints on function use overly restrictive/unrestrictive), and trip up the way I write programs, by forcing me to do certain things in some ways. Thus, although I regret the loss of performance, I feel that dynamic typing is necessary and we should make the best of it. I'll observe one final point, which is that static type systems which satisfy point (2) generally allow such constraints to be resolved at compile time. This might reduce debugging time, but the expressible constraints in such systems aren't really powerful enough to provide any guarantee of program correctness, so thorough testing is still necessary. Thus I don't buy the argument that dynamically-typed languages aren't adequate for production code; the user won't get a run-time error message if you debugged your code well. Even if he does, better that than undefined behavior from a statically typed program whose producer put too much confidence in the type system to catch his errors. -Brian Murphy brm@cs.stanford.edu