Taming Effects with Monadic Typing

Abstract

The familiar Hindley-Milner type system of the ML language family is extended with monad annotations to account for possible side effects of expression evaluation. This also allows effects to be effectively encapsulated by lexical scopes Γ with enforcement provided by type checking. A type-and-effects analysis supports type inference. Type soundness and completeness theorems establish the coherence of monadic type inference with the reference semantics of a small ML-style language.