Python from Wise Guy's Viewpoint

Andreas Rossberg rossberg at ps.uni-sb.de
Thu Oct 23 08:04:13 EDT 2003


Joachim Durchholz wrote:
> 
> The vast majority of practical programming languages use a type 
> inference system where the behavior is known to be O (N log N) or better 

Not true, unfortunately. Type inference for almost all FP languages is a 
derivative from the original Hindley/Milner algorithm for ML, which is 
known to have exponential worst-case behaviour. Interestingly, such 
cases never show up in practice, most realistic programs can be checked 
in subquadratic time and space. For that reason even the inventors of 
the algorithm originally believed it was polynomial, until somebody 
found a counterexample.

The good news is that, for similar reasons, undecidable type checking 
need not be a hindrance in practice.

	- Andreas

-- 
Andreas Rossberg, rossberg at ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
  as kids, we would all be running around in darkened rooms, munching
  magic pills, and listening to repetitive electronic music."
  - Kristian Wilson, Nintendo Inc.





More information about the Python-list mailing list