Next: Type Check Optimization
Up: Type Inference
Previous: Operation Specific Type Inference
  Contents
  Index
Dynamic Type Inference
dynamic type inference
conditional type inference
dynamic
Python uses flow analysis to infer types in dynamically typed
programs. For example:
(ecase x
(list (length x))
...)
Here, the compiler knows the argument to length is a list,
because the call to length is only done when x is a
list. The most significant efficiency effect of inference from
assertions is usually in type check optimization.
Dynamic type inference has two inputs: explicit conditionals and
implicit or explicit type assertions. Flow analysis propagates these
constraints on variable type to any code that can be executed only
after passing though the constraint. Explicit type constraints come
from ifs where the test is either a lexical variable or a
function of lexical variables and constants, where the function is
either a type predicate, a numeric comparison or eq.
If there is an eq (or eql) test, then the compiler will
actually substitute one argument for the other in the true branch.
For example:
(when (eq x :yow!) (return x))
becomes:
(when (eq x :yow!) (return :yow!))
This substitution is done when one argument is a constant, or one
argument has better type information than the other. This
transformation reveals opportunities for constant folding or
type-specific optimizations. If the test is against a constant, then
the compiler can prove that the variable is not that constant value in
the false branch, or (not (member :yow!)) in the example
above. This can eliminate redundant tests, for example:
(if (eq x nil)
...
(if x a b))
is transformed to this:
(if (eq x nil)
...
a)
Variables appearing as if tests are interpreted as(not (eq var nil)) tests. The compiler also converts= into eql where possible. It is difficult to do
inference directly on = since it does implicit coercions.
When there is an explicit
or
test on
numeric
variables, the compiler makes inferences about the ranges the
variables can assume in the true and false branches. This is mainly
useful when it proves that the values are small enough in magnitude to
allow open-coding of arithmetic operations. For example, in many uses
of dotimes with a fixnum repeat count, the compiler
proves that fixnum arithmetic can be used.
Implicit type assertions are quite common, especially if you declare
function argument types. Dynamic inference from implicit type
assertions sometimes helps to disambiguate programs to a useful
degree, but is most noticeable when it detects a dynamic type error.
For example:
(defun foo (x)
(+ (car x) x))
results in this warning:
In: DEFUN FOO
(+ (CAR X) X)
==>
X
Warning: Result is a LIST, not a NUMBER.
Note that Common Lisp's dynamic type checking semantics make dynamic type
inference useful even in programs that aren't really dynamically
typed, for example:
(+ (car x) (length x))
Here, x presumably always holds a list, but in the absence of a
declaration the compiler cannot assume x is a list simply
because list-specific operations are sometimes done on it. The
compiler must consider the program to be dynamically typed until it
proves otherwise. Dynamic type inference proves that the argument tolength is always a list because the call to length is
only done after the list-specific car operation.
Next: Type Check Optimization
Up: Type Inference
Previous: Operation Specific Type Inference
  Contents
  Index
Peter Van Eynde
2001-03-08