An Approach to Overloading With Polymorphism

[摘要] One of the principal characterising features of a programming language is its type system. Many recent functional programming languages adopt a Hindley-Milner style type system facilitating parametric polymorphism. One of the forms of polymorphism found most commonly in programming languages is overloading. Whereas one may consider the Hindley-Milner system an off-the-shelf package for parametric polymorphism, there is no similar uniformity in the approaches taken to overloading. This thesis extends the standard Hindley-Milner system. A type system incorporating parametric polymorphism and overloading is presented both formally and informally, and it is shown to satisfy a principal type theorem. The Hindley-Milner type inference algorithm is extended for the new system. This algorithm is shown to be sound and complete. The characteristic feature of parametric polymorphism is that the same code can be used at many different types. The corresponding characterisation rule for overloading is that different code is used at different types. As such, meaning is assigned to terms on the basis of their typing. The semantics of the form of overloading described herein is assigned by means of a derivation to derivation translation scheme. This scheme is shown to be sound and, under certain well-defined conditions, coherent. This approach to overloading is closely related to the lazy functional programming language Haskell's type class mechanism. Some discussion of matters related to the current system, and arising through that project, is given.

[发布机构] University:University of Glasgow

[关键词] Computer science