Abstract
Algorithms like those for differentiating functional expressions manipulate the syntactic structure of mathematical expressions in a mathematically meaningful way. A formalization of such an algorithm should include a specification of its computational behavior, a specification of its mathematical meaning, and a mechanism for applying the algorithm to actual expressions. Achieving these goals requires the ability to integrate reasoning about the syntax of the expressions with reasoning about what the expressions mean. A syntax framework is a mathematical structure that is an abstract model for a syntax reasoning system. It contains a mapping of expressions to syntactic values that represent the syntactic structures of the expressions; a language for reasoning about syntactic values; a quotation mechanism to refer to the syntactic value of an expression; and an evaluation mechanism to refer to the value of the expression represented by a syntactic value. We present and compare two approaches, based on instances of a syntax framework, to formalize a syntax-based mathematical algorithm in a formal theory T. In the first approach the syntactic values for the expressions manipulated by the algorithm are members of an inductive type in T, but quotation and evaluation are functions defined in the metatheory of T. In the second approach every expression in T is represented by a syntactic value, and quotation and evaluation are operators in T itself.
This research was supported by NSERC.
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
Boulton, R., Gordon, A., Gordon, M., Harrison, J., Herbert, J., Van Tassel, J.: Experience with embedding hardware description languages in HOL. In: Stavridou, V., Melham, T.F., Boute, R.T. (eds.) Proceedings of the IFIP TC10/WG 10.2 International Conference on Theorem Provers in Circuit Design: Theory, Practice and Experience. IFIP Transactions A: Computer Science and Technology, vol. A-10, pp. 129–156. North-Holland (1993)
Carette, J., Farmer, W.M., O’Connor, R.: Mathscheme: Project description. In: Davenport, J.H., Farmer, W.M., Urban, J., Rabe, F. (eds.) Calculemus/MKM 2011. LNCS, vol. 6824, pp. 287–288. Springer, Heidelberg (2011)
Carnap, R.: Die Logische Syntax der Sprache. Springer (1934)
Contejean, E., Courtieu, P., Forest, J., Pons, O., Urbain, X.: Certification of automated termination proofs. In: Konev, B., Wolter, F. (eds.) FroCos 2007. LNCS (LNAI), vol. 4720, pp. 148–162. Springer, Heidelberg (2007)
Demers, F.-N., Malenfant, J.: Reflection in logic, functional and object-oriented programming: A short comparative study. In: IJCAI 1995 Workshop on Reflection and Metalevel Architectures and their Applications in AI, pp. 29–38 (1995)
Farmer, W.M.: Biform theories in Chiron. In: Kauers, M., Kerber, M., Miner, R., Windsteiger, W. (eds.) MKM/CALCULEMUS 2007. LNCS (LNAI), vol. 4573, pp. 66–79. Springer, Heidelberg (2007)
Farmer, W.M.: Chiron: A set theory with types, undefinedness, quotation, and evaluation. SQRL Report No. 38, McMaster University (2007), http://imps.mcmaster.ca/doc/chiron-tr.pdf (revised 2012)
Farmer, W.M.: The seven virtues of simple type theory. Journal of Applied Logic 6, 267–286 (2008)
Farmer, W.M., Larjani, P.: Frameworks for reasoning about syntax that utilize quotation and evaluation. McSCert Report No. 9, McMaster University (2013), http://imps.mcmaster.ca/doc/syntax.pdf
The F# Software Foundation
Grundy, J., Melham, T., O’Leary, J.: A reflective functional language for hardware design and theorem proving. Journal of Functional Programming 16 (2006)
Harrison, J.: Metatheory and reflection in theorem proving: A survey and critique. Technical Report CRC-053, SRI Cambridge (1995), http://www.cl.cam.ac.uk/~jrh13/papers/reflect.ps.gz
Koellner, P.: On reflection principles. Annals of Pure and Applied Logic 157, 206–219 (2009)
Mogensen, T.Æ.: Efficient self-interpretation in lambda calculus. Journal of Functional Programming 2, 345–364 (1994)
Rice University Programming Languages Team. Metaocaml: A compiled, type-safe, multi-stage programming language (2011), http://www.metaocaml.org/
Sheard, T., Jones, S.P.: Template meta-programming for Haskell. ACM SIGPLAN Notices 37, 60–75 (2002)
Spivak, M.: Calculus, 4th edn. Publish or Perish (2008)
Taha, W., Sheard, T.: MetaML and multi-stage programming with explicit annotations. Theoretical Computer Science 248, 211–242 (2000)
van der Walt, P.: Reflection in Agda. Master’s thesis, Universiteit Utrecht (2012)
Wildmoser, M., Nipkow, T.: Certifying machine code safety: Shallow versus deep embedding. In: Slind, K., Bunker, A., Gopalakrishnan, G.C. (eds.) TPHOLs 2004. LNCS, vol. 3223, pp. 305–320. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farmer, W.M. (2013). The Formalization of Syntax-Based Mathematical Algorithms Using Quotation and Evaluation. In: Carette, J., Aspinall, D., Lange, C., Sojka, P., Windsteiger, W. (eds) Intelligent Computer Mathematics. CICM 2013. Lecture Notes in Computer Science(), vol 7961. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39320-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-39320-4_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39319-8
Online ISBN: 978-3-642-39320-4
eBook Packages: Computer ScienceComputer Science (R0)