Abstract
A type-based approach to termination uses sized types: an ordinal bound for the size of a data structure is stored in its type. A recursive function over a sized type is accepted if it is visible in the type system that recursive calls occur just at a smaller size. This approach is only sound if the type of the recursive function is admissible, i.e., depends on the size index in a certain way. To explore the space of admissible functions in the presence of higher-kinded data types and impredicative polymorphism, a semantics is developed where sized types are interpreted as functions from ordinals into sets of strongly normalizing terms. It is shown that upper semi-continuity of such functions is a sufficient semantical criterion for admissibility. To provide a syntactical criterion, a calculus for semi-continuous function is developed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abel, A.: Termination and guardedness checking with continuous types. In: Hofmann, M.O. (ed.) TLCA 2003. LNCS, vol. 2701, pp. 1–15. Springer, Heidelberg (2003)
Abel, A.: Termination checking with types. RAIRO – Theoretical Informatics and Applications 38, 277–319 (2004) (Special Issue: Fixed Points in Computer Science (FICS 2003))
Abel, A.: Polarized subtyping for sized types. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 381–392. Springer, Heidelberg (2006)
Abel, A.: A Polymorphic Lambda-Calculus with Sized Higher-Order Types. Ph.D. thesis, Ludwig-Maximilians-Universität München (2006)
Abel, A., Matthes, R.: Fixed points of type constructors and primitive recursion. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 190–204. Springer, Heidelberg (2004)
Amadio, R.M., Coupet-Grimal, S.: Analysis of a guard condition in type theory. In: Nivat, M. (ed.) FOSSACS 1998. LNCS, vol. 1378, pp. 48–62. Springer, Heidelberg (1998)
Barthe, G., Frade, M.J., Giménez, E., Pinto, L., Uustalu, T.: Type-based termination of recursive definitions. Mathematical Structures in Computer Science 14, 1–45 (2004)
Barthe, G., Grégoire, B., Pastawski, F.: Practical inference for type-based termination in a polymorphic setting. In: Urzyczyn, P. (ed.) TLCA 2005. LNCS, vol. 3461, pp. 71–85. Springer, Heidelberg (2005)
Blanqui, F.: A type-based termination criterion for dependently-typed higher-order rewrite systems. In: van Oostrom, V. (ed.) RTA 2004. LNCS, vol. 3091, pp. 24–39. Springer, Heidelberg (2004)
Blanqui, F.: Decidability of type-checking in the Calculus of Algebraic Constructions with size annotations. In: Ong, L. (ed.) CSL 2005. LNCS, vol. 3634, pp. 135–150. Springer, Heidelberg (2005)
Crary, K., Weirich, S.: Flexible type analysis. In: Proceedings of the Fourth ACM SIGPLAN International Conference on Functional Programming (ICFP 1999), Paris, France. SIGPLAN Notices, vol. 34, pp. 233–248. ACM Press, New York (1999)
Duggan, D., Compagnoni, A.: Subtyping for object type constructors. In: FOOL 6 (1999)
Giménez, E.: Structural recursive definitions in type theory. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 397–408. Springer, Heidelberg (1998)
Hughes, J., Pareto, L., Sabry, A.: Proving the correctness of reactive systems using sized types. In: 23rd Symposium on Principles of Programming Languages, POPL 1996, pp. 410–423 (1996)
Mendler, N.P.: Recursive types and type constraints in second-order lambda calculus. In: Proceedings of the Second Annual IEEE Symposium on Logic in Computer Science, Ithaca, NY, pp. 30–36. IEEE Computer Society Press, Los Alamitos (1987)
Pareto, L.: Types for Crash Prevention. Ph.D. thesis, Chalmers University of Technology (2000)
Paulin-Mohring, C.: Inductive definitions in the system Coq—rules and properties. Technical report, Laboratoire de l’Informatique du Parallélisme (1992)
Steffen, M.: Polarized Higher-Order Subtyping. Ph.D. thesis, Technische Fakultät, Universität Erlangen (1998)
Xi, H.: Dependent types for program termination verification. In: Proceedings of 16th IEEE Symposium on Logic in Computer Science, Boston, USA (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abel, A. (2006). Semi-continuous Sized Types and Termination. In: Ésik, Z. (eds) Computer Science Logic. CSL 2006. Lecture Notes in Computer Science, vol 4207. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11874683_5
Download citation
DOI: https://doi.org/10.1007/11874683_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45458-8
Online ISBN: 978-3-540-45459-5
eBook Packages: Computer ScienceComputer Science (R0)