Abstract
Higher-order encodings use functions provided by one language to represent variable binders of another. They lead to concise and elegant representations, which historically have been difficult to analyze and manipulate.
In this paper we present the \(\nabla\)-calculus, a calculus for defining general recursive functions over higher-order encodings. To avoid problems commonly associated with using the same function space for representations and computations, we separate one from the other. The simply-typed λ-calculus plays the role of the representation-level. The computation-level contains not only the usual computational primitives but also an embedding of the representation-level. It distinguishes itself from similar systems by allowing recursion under representation-level λ-binders while permitting a natural style of programming which we believe scales to other logical frameworks. Sample programs include bracket abstraction, parallel reduction, and an evaluator for a simple language with first-class continuations.
This research has been funded by NSF grants CCR-0325808 and CCR-0133502.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Coquand, T.: An algorithm for testing conversion in type theory. In: Huet, G., Plotkin, G. (eds.) Logical Frameworks, pp. 255–279. Cambridge University Press, Cambridge (1991)
Gabbay, M., Pitts, A.: A new approach to abstract syntax involving binders. In: Longo, G. (ed.) Proceedings of the 14th Annual Symposium on Logic in Computer Science (LICS 1999), Trento, Italy, pp. 214–224. IEEE Computer Society Press, Los Alamitos (1999)
Honsell, F., Miculan, M., Scagnetto, I.: π-calculus in (Co)inductive-type theory. Theoretical Computer Science 253(2), 239–285 (2001)
Hofmann, M.: Semantical analysis for higher-order abstract syntax. In: Longo, G. (ed.) Proceedings of the 14th Annual Symposium on Logic in Computer Science (LICS 1999), Trento, Italy, pp. 204–213. IEEE Computer Society Press, Los Alamitos (1999)
Momigliano, A., Ambler, S., Crole, R.: A definitional approach to primitive recursion over higher order abstract syntax. In: Momigliano, A., Miculan, M. (eds.) Proceedings of the Merlin Workshop. ACM Press, Uppsala (2003)
Miller, D.: An extension to ML to handle bound variables in data structures: Preliminary report. In: Proceedings of the Logical Frameworks BRA Workshop, Nice, France (May 1990)
Paulin-Mohring, C.: Inductive definitions in the system Coq: Rules and properties. In: Bezem, M., Groote, J.F. (eds.) TLCA 1993. LNCS, vol. 664, pp. 328–345. Springer, Heidelberg (1993)
Poswolsky, A., Schürmann, C.: Elphin user’s manual. Technical report, Yale University (2005) (to appear), See also http://www.cs.yale.edu/~delphin
Schürmann, C.: Recursion for higher-order encodings. In: Fribourg, L. (ed.) CSL 2001 and EACSL 2001. LNCS, vol. 2142, pp. 585–599. Springer, Heidelberg (2001)
Schürmann, C., Despeyroux, J., Pfenning, F.: Primitive recursion for higher-order abstract syntax. Theoretical Computer Science 266, 1–57 (2001)
Schürmann, C., Poswolsky, A., Sarnat, J.: The \(\nabla\)-calculus. Functional programming with higher-order encodings. Technical Report YALEU/DCS/TR-1272, Yale University (October 2004)
Taha, W., Sheard, T.: MetaML: Multi-stage programming with explicit annotations. Theoretical Computer Science 248, 1–2 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schürmann, C., Poswolsky, A., Sarnat, J. (2005). The \(\nabla\)-Calculus. Functional Programming with Higher-Order Encodings. In: Urzyczyn, P. (eds) Typed Lambda Calculi and Applications. TLCA 2005. Lecture Notes in Computer Science, vol 3461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11417170_25
Download citation
DOI: https://doi.org/10.1007/11417170_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25593-2
Online ISBN: 978-3-540-32014-2
eBook Packages: Computer ScienceComputer Science (R0)