Abstract
The usual definition facilities in theorem provers cannot handle all recursive functions on lazy lists; the filter function is a prime counterexample. We present two new ways of directly defining functions like filter by exploiting their dual nature as producers and consumers. Borrowing from domain theory and topology, we define them as a least fixpoint (producer view) and as a continuous extension (consumer view). Both constructions yield proof principles that allow elegant proofs. We expect that the approach extends to codatatypes with finite truncations.
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
Agerholm, S.: LCF examples in HOL. In: Melham, T.F., Camilleri, J. (eds.) HUG 1994. LNCS, vol. 859, pp. 1–16. Springer, Heidelberg (1994)
Agerholm, S.: Non-primitive recursive function definitions. In: Schubert, E.T., Alves-Foss, J., Windley, P. (eds.) HUG 1995. LNCS, vol. 971, pp. 17–31. Springer, Heidelberg (1995)
Benton, N., Kennedy, A., Varming, C.: Some domain theory and denotational semantics in Coq. In: Berghofer, S., Nipkow, T., Urban, C., Wenzel, M. (eds.) TPHOLs 2009. LNCS, vol. 5674, pp. 115–130. Springer, Heidelberg (2009)
Bertot, Y.: Filters on coInductive streams, an application to Eratosthenes’ sieve. In: Urzyczyn, P. (ed.) TLCA 2005. LNCS, vol. 3461, pp. 102–115. Springer, Heidelberg (2005)
Blanchette, J.C., Hölzl, J., Lochbihler, A., Panny, L., Popescu, A., Traytel, D.: Truly modular (co)datatypes for Isabelle/HOL. In: Klein, G., Gamboa, R. (eds.) ITP 2014. LNCS (LNAI), vol. 8558, pp. 93–110. Springer, Heidelberg (2014)
Breitner, J., Huffman, B., Mitchell, N., Sternagel, C.: Certified HLints with Isabelle/HOLCF-Prelude. In: Haskell and Rewriting Techniques, HART (2013)
Charguéraud, A.: The optimal fixed point combinator. In: Kaufmann, M., Paulson, L.C. (eds.) ITP 2010. LNCS, vol. 6172, pp. 195–210. Springer, Heidelberg (2010)
Devillers, M., Griffioen, D., Müller, O.: Possibly infinite sequences in theorem prov- ers: A comparative study. In: Gunter, E.L., Felty, A.P. (eds.) TPHOLs 1997. LNCS, vol. 1275, pp. 89–104. Springer, Heidelberg (1997)
Friedrich, S.: Topology. Archive of Formal Proofs, Formal proof development (2004), http://afp.sf.net/entries/Topology.shtml
Di Gianantonio, P., Miculan, M.: A unifying approach to recursive and co-recursive definitions. In: Geuvers, H., Wiedijk, F. (eds.) TYPES 2002. LNCS, vol. 2646, pp. 148–161. Springer, Heidelberg (2003)
Hölzl, J., Immler, F., Huffman, B.: Type classes and filters for mathematical analysis in Isabelle/HOL. In: Blazy, S., Paulin-Mohring, C., Pichardie, D. (eds.) ITP 2013. LNCS, vol. 7998, pp. 279–294. Springer, Heidelberg (2013)
Huffman, B.: HOLCF’11: A Definitional Domain Theory for Verifying Functional Programs. PhD thesis, Portland State University (2012)
Krauss, A.: Partial and nested recursive function definitions in higher-order logic. J. Autom. Reasoning 44(4), 303–336 (2010)
Krauss, A.: Recursive definitions of monadic functions. In: PAR 2010. EPTCS, vol. 43, pp. 1–13 (2010)
Lester, D.R.: Topology in PVS: continuous mathematics with applications. In: AFM 2007, pp. 11–20. ACM (2007)
Lochbihler, A.: Coinductive. Archive of Formal Proofs, Formal proof development (2010), http://afp.sf.net/entries/Coinductive.shtml
Lochbihler, A.: Making the Java memory model safe. ACM Trans. Program. Lang. Syst. 35(4), 12:1–12:65 (2014)
Matthews, J.: Recursive function definition over coinductive types. In: Bertot, Y., Dowek, G., Hirschowitz, A., Paulin, C., Théry, L. (eds.) TPHOLs 1999. LNCS, vol. 1690, pp. 73–90. Springer, Heidelberg (1999)
Müller, O., Nipkow, T., von Oheimb, D., Slotosch, O.: HOLCF = HOL + LCF. J. Funct. Program. 9, 191–223 (1999)
Paulson, L.C.: Mechanizing coinduction and corecursion in higher-order logic. J. Logic Comput. 7(2), 175–204 (1997)
Slind, K.: Function definition in higher-order logic. In: von Wright, J., Harrison, J., Grundy, J. (eds.) TPHOLs 1996. LNCS, vol. 1125, pp. 381–397. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Lochbihler, A., Hölzl, J. (2014). Recursive Functions on Lazy Lists via Domains and Topologies. In: Klein, G., Gamboa, R. (eds) Interactive Theorem Proving. ITP 2014. Lecture Notes in Computer Science, vol 8558. Springer, Cham. https://doi.org/10.1007/978-3-319-08970-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-08970-6_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08969-0
Online ISBN: 978-3-319-08970-6
eBook Packages: Computer ScienceComputer Science (R0)