But I’ve always had some thoughts in the back of my head about recording types at runtime of a program in order to help the type inference out (and to avoid having to annotate them manually yourself).
Note, that this technique is a different, but related thing to what is done in a tracing jit compiler.
I asked myself these questions.
- Can I store the types coming in and out of python functions, and the types assigned to variables in order to be useful for other things based on tracing the running of a program? (Yes)
- Can I “Type Trace” a complex program? (Yes, a flask+sqlalchemy app test suite runs)
- Is porting python 2 code quicker by Type Tracing combined with static type checking, documentation generation, and test generation? (Yes, refactoring is safer with a type checker and no manually written tests)
- Can I generate better documentation automatically with Type Tracing? (Yes, return and parameter types and example values helps understanding greatly)
- Can I use the types for automatic property testing? (Yes, hypothesis does useful testing just knowing some types and a few examples… which we recorded with the tracer)
- Can I use example capture for tests and docs, as well as the types? (Yes)
- Can I generate faster compiled code automatically just using the recorded types and Cython (Yes).
Benefits from Type Tracing.
Below I try to show that the following benefits can be obtained by combining Type Tracing with other existing python tools.
- Automate documentation generation, by providing types to the documentation tool, and by collecting some example inputs and outputs.
- Automate some type annotation.
- Automatically find bugs static type checking can not. Without full type inference, existing python static type checkers can not find many issues until the types are fully annotated. Type Tracing can provide those types.
- Speed up Python2 porting process, by finding issues other tools can’t. It can also speed things up by showing people types and example inputs. This can greatly help people understand large programs when documentation is limited.
- Use for Ahead Of Time (AOT) compilation with Cython.
- Help property testing tools to find simple bugs without manually setting properties.
Tools used to hack something together.
- coverage (extended the coverage checker to record types as it goes)
- mypy (static type checker for python)
- Hypothesis (property testing… automated test generator)
- Cython (a compiler for python code, and code with type annotations)
- jedi (another python static type checker)
- Sphinx (automatic documentation generator).
- Cpython (the original C implementation of python)
Type Tracing using ‘coverage’.
Originally I hacked up a set_trace script… and started going. But there really are so many corner cases. Also, I already run the “coverage” tool over the code base I’m working on.
Porting python 2 code with type tracing.
Steps to port to python 3 are usually these:
- Understand the code.
- Run the code in production (or on a copy of production data).
- With a debugger, look at what is coming in and out of functions.
- Write tests for everything.
- Write documentation.
- Run 2to3.
- Do lots of manual QA.
- Start refactoring.
- Repeat. Repeat manually writing tests, docs, and testing manually. Many times.
Remember that writing tests is usually harder than writing the code in the first place.
With type tracing helping to generate docs, types for the type checker, examples for human reading plus for the hypothesis property checker we get a lot more tools to help ensure quality.
- Run program under Type Tracing, line/branch coverage, and example capture.
- Look at generated types, example inputs and outputs.
- Look at generated documentation.
- Gradually add type checking info with help of Type Tracing recorded types.
- Generate tests automatically with Type Tracing types, examples, and hypothesis automated property testing. Generate empty test stubs for things you still need to test.
- Once each module is fully typed, you can statically type check it.
- You can cross validate your type checked python code against your original code. Under the Type Tracer.
- Refactoring is easier with better docs, static type checks, tests, types for arguments and return values, and example inputs and outputs.
- Everything should be ported to work with the new forwards compatibility functionality in python2.7.
- Now with your various quality checks in place, you can start porting to python3. Note, you might not have needed to change any of the original code – only add types.
Integer divide issue.
Here I will show that the 2to3 conversion tool makes a bug with. Also, mypy does not detect a problem with the code.
return x / 4
$ python2 int_issue.py
$ python3 int_issue.py
$ mypy –py2 int_issue.py
$ mypy int_issue.py
$ 2to3 int_issue.py
RefactoringTool: Skipping optional fixer: buffer
RefactoringTool: Skipping optional fixer: idioms
RefactoringTool: Skipping optional fixer: set_literal
RefactoringTool: Skipping optional fixer: ws_comma
RefactoringTool: Refactored int_issue.py
— int_issue.py (original)
+++ int_issue.py (refactored)
@@ -3,4 +3,4 @@
return x / 4
RefactoringTool: Files that need to be modified:
See how when run under python3 it gives a different result?
Can we fix it when Type Tracing adds types? (Yes)
So, how about if we run the program under type tracing, and record the input types coming in and out? See how it adds a python3 compatible comment about taking an int, and returning an int. This is so that mypy (and other type checkers) can see what it is supposed to take in.
# type: (int) -> int
return x / 4
$ mypy int_issue.py
int_issue.py:5: error: Incompatible return value type (got “float”, expected “int”)
I’m happy that Yes, Type Tracing combined with mypy can detect this issue whereas mypy can not by itself.
Binary or Text file issue?
Another porting issue not caught by existing tools is trying to do the right thing when a python file is in binary mode or in text mode. If in binary, read() will return bytes, otherwise it might return text.
In theory this could be made to work, however at the time of writing, there is an open issue with “dependent types” or “Factory Pattern” functions in mypy. More information on this, and also a work around I wrote see this issue: https://github.com/python/mypy/issues/2337#issuecomment-280850128
In there I show that you can create your own io.open replacement that always returns one type. eg, open_rw(fname) instead of open(fname, ‘rw’).
Once you know that .read() will return bytes, then you also know that it can’t call .format() in python 3. The solution is to use % string formatting on bytes, which is supported from python3.5 upwards.
x = f.read() # type: bytes
So the answer here is that mypy could likely solve this issue by itself in the future (once things are fully type annotated). But for now, it’s good to see combining type tracing with mypy could help detect binary and text encoding issues much faster.
Generating Cython code with recorded types.
def f(x): return x**2-x def integrate_f(a, b, N): s = 0 dx = (b-a)/N for i in range(N): s += f(a+i*dx) return s * dx
100000 loops, best of 3: 5.12 µs per loop
In : %load_ext Cython
In : %%cython
…: cdef double f(double x):
…: return x**2-x
…: def integrate_f_c(double a, double b, int N):
…: >>> integrate_f_c(10.4, 2.3, 17)
…: cdef int i
…: cdef double s, dx
…: s = 0
…: dx = (b-a)/N
…: for i in range(N):
…: s += f(a+i*dx)
…: return s * dx
In : %timeit integrate_f_c(10.4, 2.3, 17)
10000000 loops, best of 3: 117 ns per loop
Normal python was 5200 nanoseconds. The cython compiled version is 117 nanoseconds. The result is 44x faster code, and we have all the types annotated, with an example. This helps you understand it a little better than before too.
This was a great result for me. It shows that yes combining Type Tracing with Cython can give improvements over Cython just by itself. Note, that Cython is not only for speeding up simple numeric code. It’s also been used to speed up string based code, database access, network access, and game code.
So far I’ve made a simple mapping of python types to cython types. To make the code more useful would require quite a bit more effort. However, if you use it as a tool to help you write cython code yourself, then it’s very useful to speed up that process.
The best cases so far are when it knows all of the types, all of the types have direct cython mappings, and it avoids calling python functions inside the function. In other words, ‘pure’ functions.
Cross validation for Cython and python versions?
The most popular property testing framework Quickcheck from the Haskell world. However, python also has an implementation – Hypothesis. Rather than supply examples, as is usual with unit testing you tell it about properties which hold true.
Can we generate a hypothesis test automatically using just types collected with Type Tracing?
Below we can see some unit tests (example based testing), as well as some Hypothesis tests (property testing). They are for a function “always_add_something(x)”, which always adds something to the number given in. As a property, we would say that “always_add_something(x) > x”. That property will hold to be true for every value of x given x is an int.
Note, that the program is fully typed, and passes type checking with mypy. Also note that there is 100% test coverage if I remove the divide by zero error I inserted.
from hypothesis import given
from bad_logic_issue import always_add_something, always_add_something_good
def test_always_add_something():# type: () -> None
#type: () -> None
assert always_add_something(5) >= 5
assert always_add_something(200) >= 200
#type: () -> None
assert always_add_something_good(5) >= 5
assert always_add_something_good(200) >= 200
assert always_add_something(x) > x
# Here we test the good one.
assert always_add_something_good(x) > x
Here are two implementations of the function. The first one is a contrived example in order to show two types of logic errors that are quite common. Even 30 year old code used by billions of people has been shown to have these errors. They’re sort of hard to find with normal testing methods.
# type: (int) -> int
”’Silly function that is supposed to always add something to x.
But it doesn’t always… even though we have
– ‘complete’ test coverage.
– fully typed
r = x #type: int
if x > 0 and x < 10:
r += 20
elif x > 15 and x < 30:
r //= 0
elif x > 100:
r += 30
# type: (int) -> int
”’This one always does add something.
return x + 1
Now, hypothesis can find the errors when you write the property that the return value needs to be greater than the input. What about if we just use the types we record with Type Tracing to give hypothesis a chance to test? Hypothesis comes with a number of test strategies which generate many variations of a type. Eg, there is an “integers” strategy.
# Will it find an error just telling hypothesis that it takes an int as input?
It finds the divide by zero issue (when x is 16). However it does not find the other issue, because it still does not know that there is a problem. We haven’t told it anything about the result always needing to be greater than the input.
——————————————————– Hypothesis ——————————————————–
Falsifying example: test_always_add_something(x=16)
The result is that yes, it could find one issue automatically, without having to write any extra test code, just from Trace Typing.
For pure functions, it would be also useful to record some examples for unit test generation.
I’m happy with the experiment overall. I think it shows it can be a fairly useful technique for making python programs more understandable, faster, and more correct. It can also help speed up porting old python2 code dramatically (especially when that code has limited documentation and tests).
I think the experiment also shows that combining existing python tools (coverage, mypy, Cython, and hypothesis) can give some interesting extra abilities without not too much extra effort. eg. I didn’t need to write a robust tracing module, I didn’t need to write a static type checker, or a python compiler. However, it would take some effort to turn these into robust general purpose tools. Currently what I have is a collection of fragile hacks, without support for many corner cases
For now I don’t plan to work on this any more in the short term. (Unless of course someone wants to hire me to port some python2 code. Then I’ll work on these tools again since it speeds things up quite a lot).
Any corrections or suggestions? Please leave a comment, or see you on twitter @renedudfield