Measuring Polymorphism in Python Programs [pdf]
people.dsv.su.se
people.dsv.su.se
The real use of this kind of work is studying how to best optimize dynamic programs. The conclusion is that a Python JIT optimizer can assume the first data type you see is likely to be what you'll always see, add a small sanity check for that case then goes down a fast path. This will correctly optimize 98% of the code. And there is nothing good to be done with the remaining 2%.
This is a concrete data point. JIT optimizers for other dynamic languages (particularly JavaScript) have discovered and taken advantage of similar things.
If 98% of the code has very basic types (i.e. function takes a Integer and returns a Decimal)... we could encode that in type hints with something like mypy, and get many of the type checking that statically typed languages get, without a crazy type system.
Hey I will take a 98% statically type checked language over 0%... if in so many cases I clearly know the types of stuff, let's put that info in there and detect and code time. So much of the standard library could use this to be cleaner.
Run a program while it is instrumented. The tool figures out what every type seems to be. Then goes back through the program and tries to prove that those types are correct.
It could then automatically annotate large chunks of code in a way that lets them run faster and will produce a warning if an unexpected type makes its way in in a future iteration. (An unexpected type, of course, being either a bug or a likely candidate for something that might expose latent bugs.)
Someone is already working on type inference using VM caches.
See http://forum.world.st/parameters-of-the-virtual-machine-td48...
If I understand the article, a similar assertion would be: "Because multiple inheritance is used so infrequently, the onus is on the designers to show that the complexity is worthwhile"
That's obviously not true, though - these things add complexity to a codebase and are best avoided until the benefits they provide outweigh the increased cognitive load necessary to deal with them when something breaks.
I would intuit that if the more complex features of a language get very little use, then that's the sign of a more mature and thoughtful developer community that emphasizes readability and simplicity.
I'm also curious as to what they consider "unbounded polymorphism". Calls like "len(s)" or "with cm" or "for x in s" work with many different types (though usually only on one type at a particular part of a program). Likewise, most of the collections types and classes are necessary generic (in one place you make make a set of integers and in another place you use a set of strings). The use of the collections is typically monomorphic but the collections themselves are necessarily generic.
Another thought is that when I write programs that use a single type for a given variable, I still place value on the duck-typing and polymorphism (to ease future maintenance, support debugging, and leave the code loosely coupled). For example, when I write a function that accepts a file object and the calling code only passes in file objects, I still value my ability to pass in a StringIO object instead.
Another thought is that I find the mechanical extraction of percent usage statistics to be dubious since the results are profoundly biased by the kind of code being sampled. For example, my data analytics code is nearly 100% monomorphic. However, code that uses ORMs like SQLAlchemy, Peewee, or Django or that uses templating engines (like Jinga2, Cheetah), or that does anything interesting would tend to have much different statistics. (Performance Guided Optimization in C has taught us that data and usage patterns greatly affect the statistics).
All that said, I don't disagree with the authors that a lot of Python code could be statically typed. Tracing JITs have already proven the value of call site specialization to a particular type.
val get: 'a dict -> 'a -> 'b option
val search: re -> string -> match option
If parametric polymorphism only helps with 0.5% of all call sites, then probably:
(0) You're relying too much on implementation details across module boundaries. This destroys opportunities for type abstraction.
(1) You're unwittingly repeating the same logic over and over for multiple types. Not likely the case in Python.
(2) You're relying too much on unenforced conventions.
> This doesn't mean that languages shouldn't include more complex type systems, but it does (or should) mean that the onus is on their designers to show that the complexity is worthwhile.
In general, the "complexity" of more advanced type systems is not presented to the programmer, with C++ being a notable exception.
Instead, the programmer benefits from ease of expression of types even when they are mostly writing monomorphic functions. For example, I would say that > 95% of the benefit I've ever derived from Haskell's static typing system has been due to the clarity of type expression and the codification of intentions in monomorphic functions! All the extra stuff with advanced type class features, higher order types, quantified types, etc., is nice and all, but it probably has only ever mattered to me for at most 5% of the cases.
Regardless though, in those other 95% of monomorphic cases, the clarity of the static type system, the way it has made me clarify my design and think about the type constraints in function call chains, the way it has made me codify my intentions for other developers to see, the way it has prevented silly bugs or highlighted misconceptions I wouldn't have otherwise caught -- this has all been very valuable, all without me ever having to really deal with any "complexity" of the Haskell type system. As a mere Haskell user, I don't have to fiddle with that. The existence of the fancier type options never gets in my way if I don't need it for anything.
Now, I love Python and I'm not saying static typing is always better. I'm just saying that if a language has a fancy and "complex" type system, that's not the same thing as saying that a day-to-day programmer will ever have to interact with that complexity in order to get benefits from it. They probably won't. They'll get lots of valuable benefits more or less for free even (perhaps especially) when their programs are mostly monomorphic.
For example a unit test framework might walk your class hierarchy, identify all classes whose name matches a particular pattern, and then start doing stuff with that.
Of course there is always a way to accomplish the same thing without abusing the type system. But as soon as you do so, it is a different program.
Again, this is different from using a type system to write an arbitrary program. But, it is true that type systems which allow you to write arbitrary programs are undecidable. Because it's possible that such programs written in the type system cannot finish, then they cannot be well-typed. Most programs will be okay, and can be verified to be well-typed, but there still exist some that cannot be.
Right, but my point is that it's not necessarily impossible to just express the program that figures out the type in the type system.
If you did model, say, Python's type system in that way, it wouldn't buy you much. The real problem with dynamic types is that they're trivially true: all dynamic programs are well-typed and semantically meaningful. Any term which a human might point at and say "error" or "meaningless", a dynamic language considers to be a perfectly valid, semantically meaningful value. Sometimes those values are of a particular form, maybe with a name like "exception" or "error message", other times they might be unpredictable artefacts of arbitrary implementation details. There's no mechanism to tell such values apart from "proper" values (if there were, we would call that mechanism a "static type system", and violate our premise of dynamic types); even those values of an "exception" or "error" form may be perfectly valid components of a program, since they may be accepted as arguments, returned from functions, branched on, selected between, "thrown" (in the case of exceptions), etc.
If you did want to restrict the particular form of values in particular places (e.g. "the return value of this function should not have the form of an exception"), you can do that with dependent types. It wouldn't be pretty though, as you would have to manually transform those guarantees on your outputs into preconditions for your inputs; supply proofs of the guarantees, assuming the preconditions; have your callers guarantee to satisfy your preconditions; then repeat the process, over and over, until you reach back to the input/data-creation part of your program.
In my experience, that's basically the hardest way to use dynamic types. It's far easier to write distinct types with "correct by construction" invariants, rather than passing around brittle proof objects. Doing that would mean you're no longer "dynamic" though.
For example, consider the infamous vector type, used as the "hello world" of dependent types:
data Vector (t : Type) : (n : Nat) -> Type where
Nil : Vector 0 t
Cons : (n : Nat) -> t -> (Vector t n) -> Vector t (1+n)
first : (t : Type) -> (n : Nat) -> Vector t (1+n) -> t
first (Cons _ x _) = x
data Tag : Type where
INT : Tag
STRING : Tag
BOOL : Tag
OBJECT : Tag
-- and so on for the fixed set of "dynamic types" our language has built-in
-- Turn "dynamic types" into static types
typeOf : Tag -> Type
typeOf INT = Int
typeOf STRING = String
typeOf Bool = Bool
-- and so on
-- Values of "dynamic type"
data Dynamic : Type where
Wrap : (t : Tag) -> (v : typeOf t) -> Dynamic
getTag : Dynamic -> Tag
getTag (Wrap t _) = t
getValue : (d : Dynamic) -> typeOf (getTag d)
-- Exercise for the reader
first : (d : Dynamic) -> getTag d = LIST -> (valueOf d = nil -> Void) -> Dynamic
-- Exercise for the reader
A similar trend with TypeScript emerged in JS land where it's gaining traction. (and flowtype to some extent although that is seeing a lot less adoption)