Abstract
Tree automata are traditionally used to study properties of tree languages and tree transformations. In this paper, we consider tree automata as the basis for modular and extensible recursion schemes. We show, using well-known techniques, how to derive from standard tree automata highly modular recursion schemes. Functions that are defined in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which is illustrated with a number of examples.
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
Bahr, P., Hvitved, T.: Compositional Data Types. In: Proceedings of the Seventh ACM SIGPLAN Workshop on Generic Programming, WGP 2011, pp. 83–94. ACM, New York (2011)
Bahr, P., Hvitved, T.: Compdata (2012), http://hackage.haskell.org/package/compdata , module Data.Comp.Automata
Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007), http://www.grappa.univ-lille3.fr/tata (release October 12, 2007)
Day, L., Hutton, G.: Towards Modular Compilers For Effects. In: Proceedings of the Symposium on Trends in Functional Programming, Madrid, Spain (2011)
Eilenberg, S., Wright, J.B.: Automata in general algebras. Inform. Control. 11(4), 452–470 (1967)
Fokkinga, M.M.: Law and Order in Algorithmics. Ph.D. thesis, University of Twente, 7500 AE Enschede, Netherlands (1992)
Fülöp, Z., Vogler, H.: Syntax-Directed Semantics: Formal Models Based on Tree Transducers. Springer-Verlag New York, Inc. (1998)
Gibbons, J.: Upwards and Downwards Accumulations on Trees. In: Bird, R.S., Morgan, C.C., Woodcock, J.C.P. (eds.) MPC 1992. LNCS, vol. 669, pp. 122–138. Springer, Heidelberg (1993)
Gibbons, J.: Polytypic Downwards Accumulations. In: Jeuring, J. (ed.) MPC 1998. LNCS, vol. 1422, pp. 207–233. Springer, Heidelberg (1998)
Gibbons, J.: Generic downwards accumulations. Sci. Comput. Program. 37(1-3), 37–65 (2000)
Hasuo, I., Jacobs, B., Yu, H.-J.: Categorical Views on Computations on Trees (Extended Abstract). In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 619–630. Springer, Heidelberg (2007)
Hinze, R., Löh, A., Oliveira, B.C.d.S.: “Scrap Your Boilerplate” Reloaded. In: Hagiya, M. (ed.) FLOPS 2006. LNCS, vol. 3945, pp. 13–29. Springer, Heidelberg (2006)
Hinze, R., Löh, A.: “Scrap Your Boilerplate” Revolutions. In: Yu, H.-J. (ed.) MPC 2006. LNCS, vol. 4014, pp. 180–208. Springer, Heidelberg (2006)
Kiselyov, O., Lämmel, R., Schupke, K.: Strongly typed heterogeneous collections. In: Haskell 2004: Proceedings of the ACM SIGPLAN Workshop on Haskell, pp. 96–107. ACM Press (2004)
Knuth, D.E.: Semantics of context-free languages. Theory Comput. Syst. 2(2), 127–145 (1968)
Kühnemann, A.: Benefits of Tree Transducers for Optimizing Functional Programs. In: Arvind, V., Sarukkai, S. (eds.) FST TCS 1998. LNCS, vol. 1530, pp. 146–158. Springer, Heidelberg (1998)
Lämmel, R., Jones, S.P.: Scrap your boilerplate with class: extensible generic functions. In: Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming, pp. 204–215. ACM, New York (2005)
Lewis, J.R., Launchbury, J., Meijer, E., Shields, M.B.: Implicit parameters: dynamic scoping with static types. In: Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 108–118. ACM, New York (2000)
Marlow, S.: Haskell 2010 Language Report (2010)
Meijer, E., Fokkinga, M., Paterson, R.: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. In: Hughes, J. (ed.) FPCA 1991. LNCS, vol. 523, pp. 124–144. Springer, Heidelberg (1991)
Mitchell, N., Runciman, C.: Uniform boilerplate and list processing. In: Proceedings of the ACM SIGPLAN Workshop on Haskell, pp. 49–60. ACM, New York (2007)
Paakki, J.: Attribute grammar paradigmsa high-level methodology in language implementation. ACM Comput. Surv. 27(2), 196–255 (1995)
Swierstra, W.: Data types à la carte. J. Funct. Program. 18(4), 423–436 (2008)
Viera, M., Swierstra, S.D., Swierstra, W.: Attribute grammars fly first-class: how to do aspect oriented programming in Haskell. In: Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming, pp. 245–256. ACM, New York (2009)
Voigtländer, J.: Formal Efficiency Analysis for Tree Transducer Composition. Theory Comput. Syst. 41(4), 619–689 (2007)
Wadler, P.: Deforestation: Transforming Programs to Eliminate Trees. Theor. Comput. Sci. 73(2), 231–248 (1990)
Yakushev, A.R., Holdermans, S., Löh, A., Jeuring, J.: Generic programming with fixed points for mutually recursive datatypes. In: Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming, pp. 233–244. ACM, New York (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bahr, P. (2012). Modular Tree Automata. In: Gibbons, J., Nogueira, P. (eds) Mathematics of Program Construction. MPC 2012. Lecture Notes in Computer Science, vol 7342. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31113-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-31113-0_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31112-3
Online ISBN: 978-3-642-31113-0
eBook Packages: Computer ScienceComputer Science (R0)