Joseph J. Hallett and Assaf J. Kfoury
Programming examples needing polymorphic
recursion
Technical Report BUCS-TR-2004-004, Department of Computer Science,
Boston University, January 2004
Inferring types for polymorphic recursive function definitions (abbreviated
to polymorphic recursion) is a recurring topic on the mailing lists
of popular typed programming languages. This is despite the fact that type
inference for polymorphic recursion using for all-types has been proved
undecidable. This report presents several programming examples involving
polymorphic recursion and determines their typability under various type
systems, including the Hindley-Milner system, an intersection-type system,
and extensions of these two. The goal of this report is to show that many
of these examples are typable using a system of intersection types as an
alternative form of polymorphism. By accomplishing this, we hope to lay
the foundation for future research into a decidable intersection-type inference
algorithm.
We do not provide a comprehensive survey of type systems appropriate
for polymorphic recursion, with or without type annotations inserted in the
source language. Rather, we focus on examples for which types may be
inferred without type annotations, with an emphasis on systems of
intersection-types.
[ bib |
.ps.gz |
.pdf ]
Back
This file has been generated by
bibtex2html 1.61
Copyright notice: The documents contained
in these pages are included by the contributing authors as a means to
ensure timely dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein are maintained
by the authors or by other copyright holders, notwithstanding that
they have offered their works here electronically. It is understood that all persons copying this information will
adhere to the terms and constraints invoked by each author's
copyright. These works
may not be reposted without the explicit permission of the copyright
holder.
If you experience problems downloading any of the files above,
it is most likely because your browser does not handle compressed
files correctly.
In particular, Netscape might save the file in the compressed
gz-format with extension .ps or
.pdf (indicating postscript or PDF, resp.). You can work around this by saving the file,
renaming it to .ps.gz or .pdf.gz, and then
uncrompress it.
