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