Abstract
Previous methods have generally identified the location of a type error as a particular program point or the program subtree rooted at that point. We present a new approach that identifies the location of a type error as a set of program points (a slice) all of which are necessary for the type error. We describe algorithms for finding minimal type error slices for implicitly typed higher-order languages like Standard ML.
This work was partially supported by EPSRC grant GR/R 41545/01, EC FP5 grant IST-2001-33477, NATO grant CRG 971607, NSF grants CCR 9988529 and ITR 0113193, Sun Microsystems equipment grant EDUD-7826-990410-US.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Beaven, R. Stansifer. Explaining type errors in polymorphic languages. ACM Letters on Programming Languages and Systems, 2, 1993.
K. L. Bernstein, E. W. Stark. Debugging type errors (full version). Technical report, State University of New York, Stony Brook, 1995.
O. Chitil. Compositional explanation of types and algorithmic debugging of type errors. In Proc. 6th Int’l Conf. Functional Programming. ACM Press, 2001.
V. Chopella. Unification source-tracking with application to diagnosis of type inference. PhD thesis, Indiana University, 2002.
V. Chopella, C. T. Haynes. Diagnosis of ill-typed programs. Technical Report 426, Indiana University, 1995.
L. Damas, R. Milner. Principal type schemes for functional programs. In Conf. Rec. 9th Ann. ACM Symp. Princ. of Prog. Langs., 1982.
L. M. M. Damas. Type assignment in Programming Languages. PhD thesis, University of Edinburgh, Edinburgh, Scotland, 1985.
T. B. Dinesh, F. Tip. A slicing-based approach for locating type errors. In Proceedings of the USENIX conference on Domain-Specific Languages, Santa Barbara, California, 1997.
D. Duggan, F. Bent. Explaining type inference. Sci. Comput. Programming, 27, 1996.
C. Flanagan, M. Flatt, S. Krishnamurthi, S. Weirich, M. Felleisen. Catching bugs in the web of program invariants. In Proc. ACM SIGPLAN’ 96 Conf. Prog. Lang. Design & Impl., 1996.
B. Heeren, J. Hage. Parametric type inferencing for helium. Technical Report UU-CS-2002-035, University Utrecht, 2002.
B. Heeren, J. Hage, D. Swierstra. Generalizing Hindley-Milner type inference algorithms. Technical Report UU-CS-2002-031, University Utrecht, 2002.
B. Heeren, J. Jeuring, D. Swierstra, P. A. Alcocer. Improving type-error messages in functional languages. Technical Report UU-CS-2002-009, University Utrecht, 2002.
T. Jim. What are principal typings and what are they good for? In POPL’ 96 [22].
G. F. Johnson, J. A. Walz. A maximum flow approach to anomaly isolation in unification-based incremental type inference. In POPL’ 96 [22].
P. Kanellakis, H. Mairson, J. C. Mitchell. Unification and ML type reconstruction. In J.-L. Lassez, G. Plotkin, eds., Computational Logic: Essays in Honor of Alan Robinson. MIT Press, 1991.
A. J. Kfoury, J. Tiuryn, P. Urzyczyn. An analysis of ML typability. J. ACM, 41(2), 1994.
O. Lee, K. Yi. Proofs about a folklore let-polymorphic type inference algorithm. ACM Trans. on Prog. Langs. & Systs., 20(4), 1998.
B. J. McAdam. On the unification of substitutions in type inference. In K. Hammond, A. J. T. Davie, C. Clack, eds., Implementation of Functional Languages (IFL’98), vol. 1595 of LNCS, London, UK, 1998. Springer-Verlag.
B. J. McAdam. Generalising techniques for type debugging. In Trinder et al. [25].
R. Milner, M. Tofte, R. Harper, D. B. MacQueen. The Denition of Standard ML (Revised). MIT Press, 1997.
G. S. Port. A simple approach to finding the cause of non-unifiability. In Proc. Fifth International Conference on Logic Programming. MIT Press, 1988.
Z. Shao, A. Appel. Smartest recompilation. In Conf. Rec. 20th Ann. ACM Symp. Princ. of Prog. Langs., 1993.
P. Trinder, G. Michaelson, H.-W. Loidl, eds. Trends in Func. Programming. Intellect, 2000.
M. Wand. Finding the source of type errors. In Conf. Rec. 13th Ann. ACM Symp. Princ. of Prog. Langs., 1986.
D. A. Wolfram. Intractable unifiability problems and backtracking. In Proc. Third International Conference on Logic Programming, vol. 225 of LNCS, 1986.
J. YANG. Explaining type errors by finding the source of a type conflict. In Trinder et al. [25].
J. YANG, G. Michaelson, P. Trinder. Explaining polymorphic types. Computer Journal, 200X. to appear.
J. YANG, G. Michaelson, P. Trinder, J. B. Wells. Improved type error reporting. In [Draft] Proc. 12th Int’l Workshop Implementation Functional Languages, Aachen, Germany, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Haack, C., Wells, J.B. (2003). Type Error Slicing in Implicitly Typed Higher-Order Languages. In: Degano, P. (eds) Programming Languages and Systems. ESOP 2003. Lecture Notes in Computer Science, vol 2618. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36575-3_20
Download citation
DOI: https://doi.org/10.1007/3-540-36575-3_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00886-6
Online ISBN: 978-3-540-36575-4
eBook Packages: Springer Book Archive