Inferring useful static types for duck typed languages
Author(s)
Lamaison, Alexander
Type
Thesis or dissertation
Abstract
Complete and precise identification of types is essential to the effectiveness
of programming aids such as refactoring or code completion. Existing approaches
that target dynamically typed languages infer types using flow
analysis, but flow analysis does not cope well with heavily used features
such as heterogeneous containers and implicit interfaces.
Our solution makes the assumption that programs that are known to work
do not encounter run-time type errors which allows us to derive extra type
information from the way values are used, rather than simply where those
values originate. This is in keeping with the “duck typing” philosophy of
many dynamically typed languages.
The information we derive must be conservative, so we describe and formalise
a technique to ‘freeze’ the duck type of a variable using the features,
such as named methods, that are provably present on any run of the program.
Development environments can use these sets of features to provide
code-completion suggestions and API documentation, amongst other things.
We show that these sets of features can be used to refine imprecise flow analysis
results by using the frozen duck type to perform a structural type-cast.
We first formalise this for an idealised duck-typed language semantics and
then show to what extent the technique would work for a real-world language,
Python. We demonstrate its effectiveness by performing an analysis
of several real-world Python programs which shows that we can infer the
types of method-call receivers more precisely than can flow analysis alone.
of programming aids such as refactoring or code completion. Existing approaches
that target dynamically typed languages infer types using flow
analysis, but flow analysis does not cope well with heavily used features
such as heterogeneous containers and implicit interfaces.
Our solution makes the assumption that programs that are known to work
do not encounter run-time type errors which allows us to derive extra type
information from the way values are used, rather than simply where those
values originate. This is in keeping with the “duck typing” philosophy of
many dynamically typed languages.
The information we derive must be conservative, so we describe and formalise
a technique to ‘freeze’ the duck type of a variable using the features,
such as named methods, that are provably present on any run of the program.
Development environments can use these sets of features to provide
code-completion suggestions and API documentation, amongst other things.
We show that these sets of features can be used to refine imprecise flow analysis
results by using the frozen duck type to perform a structural type-cast.
We first formalise this for an idealised duck-typed language semantics and
then show to what extent the technique would work for a real-world language,
Python. We demonstrate its effectiveness by performing an analysis
of several real-world Python programs which shows that we can infer the
types of method-call receivers more precisely than can flow analysis alone.
Date Issued
2012-09
Online Publication Date
2014-01-17T16:45:38Z
Date Awarded
2013-09
Advisor
Wolf, Alexander
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)