Abstract
Expression Reduction Systems is a formalism for higher-order rewriting, extending Term Rewriting Systems and the lambda-calculus. Here we give an overview of results in the literature concerning ERSs. We review confluence, normalization and perpetuality results for orthogonal ERSs. Some of these results are extended to orthogonal conditional ERSs. Further, ERSs with patterns are introduced and their confluence is discussed. Finally, higher-order rewriting is translated into equational first-order rewriting. The technique develops an isomorphic model of ERSs with variable names, based on de Bruijn indices.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abadi, M., Cardelli, L., Curien, P.L., Lévy, J.-J.: Explicit substitutions. Journal of Functional Programming 4(1), 375–416 (1991)
The Alfa proof editor, http://www.cs.chalmers.se/~hallgren/Alfa/
Ariola, Z., Felleisen, M., Maraist, J., Odersky, M., Wadler, P.: A call-by-need lambda calculus. In: Proceedings of the 22nd Symposium on Principles of Programming Languages, pp. 233–246. ACM Press, New York (1995)
Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)
Barendregt, H.: The Lambda Calculus: Its Syntax and Semantics. Studies in Logic and the Foundations of Mathematics, vol. 103. North-Holland, Amsterdam (1984) (Revised Edition)
Barendregt, H., Bergstra, J.A., Klop, J.-W., Volken, H.: Some notes on lambda-reduction in “degrees, reductions, and representability in the lambda calculus”. Technical Report 22, Department of mathematics, University of Utrecht (1976)
Barendregt, H., Kennaway, R., Klop, J.-W., Sleep, M.R.: Needed reduction and spine strategies for the lambda calculus. Information and Computation 75(3), 191–231 (1987)
Benaissa, Z.E.A., Briaud, D., Lescanne, P., Rouyer-Degli, J.: λυ, a calculus of explicit substitutions which preserves strong normalisation. Journal of Functional Programming 6(5), 699–722 (1996)
Bergstra, J.A., Klop, J.-W.: Strong normalization and perpetual reductions in the lambda calculus. Journal of Information Processing and Cybernetics 18(7/8), 403–417 (1982)
Bergstra, J.A., Klop, J.-W.: Conditional rewrite rules: confluence and termination. Journal of Computer and System Science 32(3), 323–362 (1986)
Bloo, R., Rose, K.: Combinatory reduction systems with explicit substitution that preserve strong normalisation. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol. 1103, pp. 169–183. Springer, Heidelberg (1996)
Bonelli, E.: A normalization result for higher-order calculi with explicit substitutions. In: Gordon, A.D. (ed.) FOSSACS 2003. LNCS, vol. 2620, pp. 153–168. Springer, Heidelberg (2003)
Bonelli, E., Kesner, D., Ríos, A.: De Bruijn indices for metaterms. Journal of Logic and Computation (to appear)
Bonelli, E., Kesner, D., Ríos, A.: Relating higher-order and first-order rewriting. Journal of Logic and Computatio (to appear)
Bonelli, E., Kesner, D., Ríos, A.: A de Bruijn notation for higher-order rewriting. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol. 1833, pp. 62–79. Springer, Heidelberg (2000)
Bonelli, E., Kesner, D., Ríos, A.: From higher-order to first-order rewriting (extended abstract). In: Middeldorp, A. (ed.) RTA 2001. LNCS, vol. 2051, pp. 47–62. Springer, Heidelberg (2001)
Boudol, G.: Computational semantics of term rewriting systems. In: Nivat, M., Reynolds, J. (eds.) Algebraic methods in semantics, pp. 169–236. Cambridge University Press, Cambridge (1985)
Bourbaki, N.: Elements of Mathematics, Theory of Sets. Addison-Wesley, Reading (1968)
Briaud, D.: An explicit eta rewrite rule. In: Dezani-Ciancaglini, M., Plotkin, G. (eds.) TLCA 1995. LNCS, vol. 902, pp. 94–108. Springer, Heidelberg (1995)
Burstall, R., MacQueen, D., Sanella, D.: Hope: An experimental applicative language. In: Proceedings of the LISP Conference, pp. 136–143. Stanford University, Computer Science Department (1980)
Cerrito, S., Kesner, D.: Pattern matching as cut elimination. In: 14th Symposium on Logic in Computer Science, pp. 98–108. IEEE Computer Society Press, Los Alamitos (1999)
Cerrito, S., Kesner, D.: Pattern matching as cut elimination. Theoretical Computer Science 323, 71–127 (2004)
Cirstea, H., Kirchner, C.: ρ-calculus, the rewriting calculus. In: 5th International Workshop on Constraints in Computational Logics (1998)
The Coq Proof Assistant, http://coq.inria.fr/
Curien, P.-L.: Categorical combinators, sequential algorithms and functional programming, 1st edn. Progress in Theoretical Computer Science. Birkhäuser, Basel (1986)
Curien, P.-L.: Thérèse Hardin, and Jean-Jacques Lévy. Confluence properties of weak and strong calculi of explicit substitutions. Technical Report 1617, INRIA-Rocquencourt (1992)
de Bruijn, N.G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indag. Mathematicae 5(35), 381–392 (1972)
de Bruijn., N.G.: A namefree lambda calculus with facilities for internal definition of expressions and segments. Technical Report 78-WSK-03, Eindhoven University of Technology (1978)
Dershowitz, N., Okada, M., Sivakumar, G.: Canonical conditional rewrite systems. In: Lusk, E., Overbeek, R. (eds.) CADE 1988. LNCS, vol. 310, pp. 538–549. Springer, Heidelberg (1988)
Dowek, G., Hardin, T., Kirchner, C.: Higher-order unification via explicit substitutions. In: 10th Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos (1995)
Dowek, G., Hardin, T., Kirchner, C.: Unification via explicit substitutions: The case of higher-order patterns. Technical Report RR3591, INRIA (1998)
The ELAN system, http://elan.loria.fr/ .
Forest, J.: A weak calculus with explicit operators for pattern matching and substitution. In: Tison, S. (ed.) RTA 2002. LNCS, vol. 2378, pp. 174–191. Springer, Heidelberg (2002)
Forest, J., Kesnerp, D.: Expression reduction systems with patterns. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 107–122. Springer, Heidelberg (2003)
Glauert, J., Kennaway, R., Khasidashvili, Z.: Stable results and relative normalization. Journal of Logic and Computation 10(3), 323–348 (2000); Special Issue: Type Theory and Term Rewriting
Glauert, J., Khasidashvili, Z.: An abstract Böhm-normalization. In: 2nd International Workshop on Reduction Strategies in Rewriting and Programming. Electronic Notes in Theoretical Computer Science, vol. 70(6). Elsevier Science, Amsterdam (2002)
Gramlich, B.: Termination and confluence properties of structured rewrite systems. PhD thesis, Universität Kaiserslautern, Germany (1996)
Hanus, M., Prehofer, C.: Higher-order narrowing with definitional trees. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol. 1103, pp. 138–152. Springer, Heidelberg (1996)
Hardin, T.: η-reduction for explicit substitutions. In: Kirchner, H., Levi, G. (eds.) ALP 1992. LNCS, vol. 632, pp. 306–321. Springer, Heidelberg (1992)
Hardin, T., Lévy, J.-J.: A confluent calculus of substitutions. In: France-Japan Artificial Intelligence and Computer Science Symposium, Izu, Japan (1989)
Hardin, T., Maranget, L., Pagano, B.: Functional back-ends within the lambda-sigma calculus. In: Proceedings of the International Conference on Functional Programming, pp. 25–33. ACM Press, New York (1996)
Hudak, P., Peyton-Jones, S., Wadler, P.: Report on the programming language Haskell, a non-strict, purely functional language (version 1.2). Sigplan Notices (1992)
Huet, G., Lévy, J.-J.: Computations in orthogonal rewriting systems. In: Lassez, J.-L., Plotkin, G. (eds.) Computational Logic, Essays in Honor of Alan Robinson, pp. 394–443. MIT Press, Cambridge (1991)
The Isabelle theorem prover, http://isabelle.in.tum.de/
Barry Jay, C.: The pattern calculus. ACM Transactions on Programming Languages and Systems 26(6), 911–937 (2004)
Jouannaud, J.-P., Okada, M.: A computation model for executable higher-order algebraic specification languages. In: 6th Symposium on Logic in Computer Science, pp. 350–361. IEEE Computer Society Press, Los Alamitos (1991)
Kamareddine, F., Ríos, A.: A λ-calculus à la de Bruijn with explicit substitutions. In: Swierstra, S.D. (ed.) PLILP 1995. LNCS, vol. 982, pp. 45–62. Springer, Heidelberg (1995)
Kesner, D.: Confluence properties of extensional and non-extensional λ-calculi with explicit substitutions. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol. 1103, pp. 184–199. Springer, Heidelberg (1996)
Kesner, D.: Confluence of extensional and non-extensional lambda-calculi with explicit substitutions. Theoretical Computer Science 238(1-2), 183–220 (2000)
Kesner, D., Puel, L., Tannen, V.: A Typed Pattern Calculus. Information and Computation 124(1), 32–61 (1996)
Khasidashvili, Z.: β-reductions and β-developments of λ-terms with the least number of steps. In: Martin-Löf, P., Mints, G. (eds.) COLOG 1988. LNCS, vol. 417, pp. 105–111. Springer, Heidelberg (1990)
Khasidashvili, Z.: Expression reduction systems. Technical Report 36: 200-220, I. Vekua Institute of Applied Mathematics of Tbilisi State University (1990)
Khasidashvili, Z.: The church-rosser theorem in orthogonal combinatory reduction systems. Technical Report 1825, INRIA-Rocquencourt (1992)
Khasidashvili, Z.: The longest perpetual reductions in orthogonal expression reduction systems. In: Matiyasevich, Y.V., Nerode, A. (eds.) LFCS 1994. LNCS, vol. 813, pp. 191–203. Springer, Heidelberg (1994)
Khasidashvili, Z.: On higher order recursive program schemes. In: Tison, S. (ed.) CAAP 1994. LNCS, vol. 787, pp. 172–186. Springer, Heidelberg (1994)
Khasidashvili, Z.: Perpetuality and strong normalization in orthogonal term rewriting systems. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 163–174. Springer, Heidelberg (1994)
Khasidashvili, Z.: On the longest perpetual reductions in orthogonal expression reduction systems. Theoretical Computer Science 266(1/2), 737–772 (2001)
Khasidashvili, Z.: Optimal normalization in orthogonal term rewriting systems. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 243–258. Springer, Heidelberg (2003)
Khasidashvili, Z., Glauert, J.: Relating conflict-free stable transition and event models via redex families. Theoretical Computer Science 286(1), 65–95 (2002)
Khasidashvili, Z., Glauert, J.: An abstract concept of optimal implementation. In: 3rd International Workshop on Reduction Strategies in Rewriting and Programming. Electronic Notes in Theoretical Computer Science, vol. 84(4). Elsevier Science, Amsterdam (2003)
Khasidashvili, Z., Glauert, J.: Stable computational semantics of conflict-free rewrite systems (partial orders with erasure). In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 467–482. Springer, Heidelberg (2003)
Khasidashvili, Z., Glauert, J.: The geometry of conflict-free reduction spaces. Theoretical Computer Science (2005) (to appear)
Khasidashvili, Z., Ogawa, M., van Oostrom, V.: Perpetuality and uniform normalization in orthogonal rewrite systems. Information and Computation 164(1), 118–151 (2001)
Khasidashvili, Z., Piperno, A.: Perpetuality and uniform normalization. In: Hanus, M., Heering, J., Meinke, K. (eds.) ALP 1997 and HOA 1997. LNCS, vol. 1298, pp. 240–255. Springer, Heidelberg (1997)
Khasidashvili, Z., van Oostrom, V.: Context-sensitive conditional expression reduction systems. In: Workshop on Graph Rewriting and Computation. Electronic Notes in Theoretical Computer Science, vol. 2. Elsevier Science, Amsterdam (1995)
Khasidashvili, Z., van Oostrom, V.: Context-sensitive conditional rewrite systems. Technical Report SYS–C95–06, University of East Anglia (1995)
Klop, J.-W.: Combinatory Reduction Systems. PhD thesis, Mathematical Centre Tracts 127, CWI, Amsterdam (1980)
Klop, J.-W.: Term Rewriting Systems. Handbook of Logic in Computer Science, vol. 2, pp. 1–116. Oxford University Press, Oxford (1992)
Klop, J.-W., van Oostrom, V., van Raamsdonk, F.: Combinatory reduction systems: introduction and survey. Theoretical Computer Science 121(1/2), 279–308 (1993)
Lévy, J.-J.: Réductions correctes et optimales dans le lambda-calcul. PhD thesis, Université Paris VII, France (1978)
Lévy, J.-J.: Optimal reductions in the lambda-calculus. In: Hindley, J.R., Seldin, J.P., Curry, T.H.B. (eds.), pp. 159–192. Academic Press, London (1980)
Maranget, L.: Optimal derivations in weak lambda-calculi and in orthogonal term rewriting systems. In: Proceedings of the 18th Symposium on Principles of Programming Languages, pp. 255–269. ACM Press, New York (1991)
The MAUDE System, http://maude.cs.uiuc.edu/
Melliès, P.-A.: Description Abstraite des Systèmes de Réécriture. PhD thesis, Université Paris VII (1996)
Melliès, P.-A.: Axiomatic rewriting theory II: the lambda-sigma calculus enjoys finite normalisation cones. Journal of Logic and Computation 10(3), 461–487 (2000)
Middeldorp, A.: Call by need computations to root-stable form. In: Proceedings of the 24th Symposium on Principles of Programming Languages, pp. 94–105. ACM Press, New York (1997)
Milner, R.: Functions as processes. Mathematical Structures in Computer Science 2(2), 119–141 (2005)
Milner, R., Tofte, M., Harper, R.: The definition of Standard ML. MIT Press, Cambridge (1990)
Muñoz, C.: A left-linear variant of λσ. In: Join International Conference on Algebraic and Logic Programming and International Workshop on Higher-Order Algebra. LNCS, vol. 1298, pp. 224–239. Springer, Heidelberg (1997)
Nederpelt, R.: Strong normalization for a typed lambda-calculus with lambda structured types. PhD thesis, Technische Hogeschool Eindhoven, Netherlands (1973)
Nipkow, T.: Higher-order critical pairs. In: 6th Symposium on Logic in Computer Science, pp. 342–349. IEEE Computer Society Press, Los Alamitos (1991)
Nipkow, T.: Orthogonal higher-order rewrite systems are confluent. In: Bezem, M., Groote, J.F. (eds.) TLCA 1993. LNCS, vol. 664, pp. 306–317. Springer, Heidelberg (1993)
Nöcker, E.: Efficient Functional Programming: Compilation and Programming Techniques. PhD thesis, University of Nijmegen, Netherlands (1994)
The Objective Caml language, http://caml.inria.fr/
O’Donnell, M.J.: Computing in Systems Described by Equations. LNCS, vol. 58. Springer, Heidelberg (1977)
Pkhakadze, S.: Some problems of the notation theory. I. Vekua Institute of Applied Mathematics of Tbilisi State University (1977) (in Russian)
Pkhakadze, S.: An n. bourbaki-type general theory and the properties of contracting symbols and corresponding contracted forms. Georgian Mathematical Journal 6(2), 179–190 (1999)
Plaisted, D.: Polynomial time termination and constraint satisfaction tests. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 405–420. Springer, Heidelberg (2003)
The PVS system, http://pvs.csl.sri.com/
Ríos, A.: Contribution à l’étude des λ-calculs avec substitutions explicites. Thèse de doctorat, Université de Paris VII (1993)
Rose, K.: Explicit cyclic substitutions. In: Rusinowitch, M., Remy, J.-L. (eds.) CTRS 1992. LNCS, vol. 656, pp. 36–50. Springer, Heidelberg (1993)
Sørensen, M.H.: Normalization in λ-calculus and type theory. PhD thesis, University of Copenhagen, Denmark (1997)
Sørensen, M.H.: Properties of infinite reduction paths in untyped λ-calculus. In: 1st Tbilisi Symposium on Logic, Language and Computation, Selected papers, pp. 353–367. SiLLI Publications, CSLI, Stanford (1998)
Terese: Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, vol. 55. Cambridge University Press, Cambridge (2003)
Toyama, Y.: Confluent term rewriting systems with membership conditions. In: Kaplan, S., Jouannaud, J.-P. (eds.) CTRS 1987. LNCS, vol. 308, pp. 128–141. Springer, Heidelberg (1988)
Turner, D.: Miranda: A non-strict functional language with polymorphic types. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 1–16. Springer, Heidelberg (1985)
van Oostrom, V.: Confluence for Abstract and Higher-order Rewriting. PhD thesis, Vrije University, Amsterdam, Netherlands (1994)
van Oostrom, V., van Raamsdonk, F.: Weak orthogonality implies confluence: the higher-order case. In: Matiyasevich, Y.V., Nerode, A. (eds.) LFCS 1994. LNCS, vol. 813, pp. 379–392. Springer, Heidelberg (1994)
van Raamsdonk, F.: Confluence and superdevelopments. In: Kirchner, C. (ed.) RTA 1993. LNCS, vol. 690, pp. 168–182. Springer, Heidelberg (1993)
van Raamsdonk, F., Severi, P., Sørensen, M.H., Xi, H.: Perpetual reductions in λ-calculus. Information and Computation 149(2), 173–229 (1999)
Wolfram, D.: The Causal Theory of Types. Cambridge Tracts in Theoretical Computer Science, vol. 21. Cambridge University Press, Cambridge (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Glauert, J., Kesner, D., Khasidashvili, Z. (2005). Expression Reduction Systems and Extensions: An Overview. In: Middeldorp, A., van Oostrom, V., van Raamsdonk, F., de Vrijer, R. (eds) Processes, Terms and Cycles: Steps on the Road to Infinity. Lecture Notes in Computer Science, vol 3838. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11601548_22
Download citation
DOI: https://doi.org/10.1007/11601548_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30911-6
Online ISBN: 978-3-540-32425-6
eBook Packages: Computer ScienceComputer Science (R0)