Monadic Typing and Overloading for ML-style Polymorphic References, Koji Kagawa


It is well-known that the ML-style {\sf ref} operator interferes badly with the Damas/Milner polymorphic type inference system. There have been a lot of proposals for the typing of references of ML as an extension of the Damas/Milner type inference system. Some of them are too complex for programmers to understand. Among them, Wright's proposal is simple but not too restrictive. His solution it to limit polymorphism to let-bindings whose right-hand-side is a value (an expression which can not syntactically involve computation). On the other hand, in the pure functional language community, monads are used more and more widely in writing programs with side-effect. In some Haskell implementations, a monad for stateful computations and a (monadic) operator which corresponds roughly to ML's {\sf ref} operator is offered. In such systems, since the result of the {\sf ref}-like operator is bound by $\lambda$ rather than by {\tt let}, we can basically get the same effect as Wright's proposal. However, this restriction is explained only syntactically. It relies on the fact that the monad of state transformers is an abstract type. But the primary reason to make state transformers abstract is to guarantee in-place updating. If we knew the implementation of state transformers, we could inline state transformers which contain {\sf ref}-like operators and make results of the {\sf ref} operator {\sf let}-bound. Then there would be no essential account why the result of the {\sf ref}-like operator should be given monomorphic types. In this paper, the implementation of the {\sf ref}-like operator in the monadic form is investigated and the need for $\lambda$-binding is explained using the notion of type classes (overloading) with multiple arguments.