Gradual Typestate

Typestate reflects how the legal operations on imperative objects can change at runtime as their internal state changes. A typestate checker can statically ensure, for instance, that an object method is only called when the object is in a state for which the operation is well-defined. Prior work has shown how modular typestate checking can be achieved thanks to access permissions and state guarantees. However, static typestate checking is still too rigid for some applications. This paper formalizes a nominal object-oriented language with mutable state that integrates typestate change and typestate checking as primitive concepts. In addition to augmenting the types of object references with access permissions and state guarantees, the language extends the notion of gradual typing to account for typestate: gradual typestate checking seamlessly combines static and dynamic checking by automatically inserting runtime checks into programs. A novel flow-sensitive permission-based type system allows programmers to write safe code even when the static type checker can only partly verify it.