Abstract
An algorithm for a restricted form of higher-order matching is described. The intended usage is for rewrite rules that use function-valued variables in place of some unknown term structure. The matching algorithm instantiates these variables with suitable λ-abstractions when given the term to be rewritten. Each argument of one of the variables is expected to match some unique substructure. Multiple solutions are avoided by making fixed choices when alternative ways to match arise. The algorithm was motivated by correctness proofs of designs written in a hardware description language. The feature of the language's semantics that necessitates the higher-order rewriting is described.
Research supported by the Engineering and Physical Sciences Research Council (formerly the Science and Engineering Research Council) of Great Britain.
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
R. J. Boulton. A HOL semantics for a subset of ELLA. Technical Report 254, University of Cambridge Computer Laboratory, April 1992.
A. Church. A formulation of the simple theory of types. Journal of Symbolic Logic, 5(1):56–68, 1940.
M. J. C. Gordon and T. F. Melham, editors. Introduction to HOL: A theorem proving environment for higher order logic. Cambridge University Press, 1993.
G. P. Huet. A unification algorithm for typed λ-calculus. Theoretical Computer Science, 1(1):27–57, 1975.
G. Huet and B. Lang. Proving and applying program transformations expressed with 2nd order patterns. Acta Informatica, 11:31–55, 1978.
D. Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. In P. Schroeder-Heister, editor, Extensions of Logic Programming: International Workshop, Tübingen, FRG., volume 475 of Lecture Notes in Artificial Intelligence, pages 253–281. Springer-Verlag, December 1989.
R. Milner, M. Tofte, and R. Harper. The Definition of Standard ML. MIT Press, 1990.
J. D. Morison and A. S. Clarke. ELLA 2000: A Language for Electronic System Design. McGraw-Hill Book Company, 1994.
T. Nipkow. Higher-order unification, polymorphism, and subsorts. Technical Report 210, University of Cambridge Computer Laboratory, November 1990.
T. Nipkow. Higher-order critical pairs. In Proceedings of the 6th Annual IEEE Symposium on Logic in Computer Science, pages 342–349, Amsterdam, The Netherlands, July 1991. IEEE Computer Society Press.
C. Prehofer. Decidable higher-order unification problems. In A. Bundy, editor, Proceedings of the 12th International Conference on Automated Deduction, volume 814 of Lecture Notes in Artificial Intelligence, pages 635–649, Nancy, France, June/July 1994. Springer-Verlag.
D. Simon. A linear time algorithm for a subcase of second order instantiation. In Proceedings of the 7th International Conference on Automated Deduction, volume 170 of Lecture Notes in Computer Science, pages 209–223. Springer-Verlag, 1984.
D. A. Wolfram. The Clausal Theory of Types, volume 21 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boulton, R.J. (1995). A restricted form of higher-order rewriting applied to an HDL semantics. In: Hsiang, J. (eds) Rewriting Techniques and Applications. RTA 1995. Lecture Notes in Computer Science, vol 914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59200-8_66
Download citation
DOI: https://doi.org/10.1007/3-540-59200-8_66
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59200-6
Online ISBN: 978-3-540-49223-8
eBook Packages: Springer Book Archive