Abstract
In this paper we present a methodology to implement multiple traversal algorithms in a functional programming setting. The implementations we obtain s of highly modular and intermediate structure free programs, that rely on the concept of functional zippers to navigate on data structures.
Even though our methodology is developed and presented under Haskell, a lazy functional language, we do not make essential use of laziness. This is an essential difference with respect to other attribute grammar embeddings. This also means that an approach similar to ours can be followed in a strict functional setting such as Ocaml, for example.
In the paper, our technique is applied to a significant number of problems that are well-known to the functional programming community, demonstrating its practical interest.
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
Similar content being viewed by others
Notes
- 1.
We are not really checking for totality, otherwise we would have to test each function call against a set of possible results. For simplicity we are just assuming the function produced a result and we are directly unwrapping it with \(fromJust\).
- 2.
The Glasgow Haskell Compiler, http://www.haskell.org/ghc/.
- 3.
References
Bird, R.: Using circular programs to eliminate multiple traversals of data. Acta Informatica 21, 239–250 (1984)
de Moor, O., Backhouse, K., Swierstra, S.D.: First-class attribute grammars. Informatica (Slovenia) 24(3), 329–341 (2000)
Fernandes, J.P., Pardo, A., Saraiva, J.: A shortcut fusion rule for circular program calculation. In: Proceedings of the ACM SIGPLAN Haskell Workshop, pp. 95–106 (2007)
Viera, M., Swierstra, 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 (ICFP 2009), pp. 245–256 (2009)
Swierstra, D., Chitil, O.: Linear, bounded, functional pretty-printing. J. Func. Programm. 19(01), 1–16 (2009)
Huet, G.: The zipper. J. Func. Programm. 7(5), 549–554 (1997)
Martins, P., Fernandes, J.P., Saraiva, J.: Zipper-based attribute grammars and their extensions. In: Du Bois, A.R., Trinder, P. (eds.) SBLP 2013. LNCS, vol. 8129, pp. 135–149. Springer, Heidelberg (2013)
Adams, M.D.: Scrap your zippers: A generic zipper for heterogeneous types. In: Proceedings of the 6th ACM SIGPLAN Workshop on Generic Programming, WGP 2010, pp. 13–24. ACM, New York (2010)
Lämmel, R., Jones, S.P.: Scrap your boilerplate: A practical design pattern for generic programming. In: Proceedings of the 2003 ACM SIGPLAN International WorkShop on Types in Language Design and Implementation, (TLDI 2003), pp. 26–37. ACM (2003)
Kiselyov, O.: Tool demonstration: A zipper based file/operating system. In: Haskell Workshop. ACM Press, September 2005
Stewart, D., Janssen, S.: XMonad: A tiling window manager. In: Haskell 2007: Proceedings of the 2007 ACM SIGPLAN Workshop on Haskell. ACM Press (2007)
Johnsson, T.: Attribute grammars as a functional programming paradigm. In: Functional Programming Languages and Computer Architecture, pp. 154–173 (1987)
Kuiper, M., Swierstra, D.: Using attribute grammars to derive efficient functional programs. In: Computing Science in the Netherlands CSN 1987, November 1987
Swierstra, S.D., Azero Alcocer, P.R., Saraiva, J.: Designing and implementing combinator languages. In: Swierstra, S.D., Oliveira, J.N. (eds.) AFP 1998. LNCS, vol. 1608, pp. 150–206. Springer, Heidelberg (1999)
Swierstra, D., Baars, A., Löh, A.: The UU-AG attribute grammar system (2004)
Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C.V., Loingtier, J.M., Irwin, J.: Aspect-oriented programming. In: ECOOP, pp. 220–242 (1997)
Saraiva, J.: Purely functional implementation of attribute grammars. Ph.D. Thesis, Department of Computer Science, Utrecht University, The Netherlands, December 1999
Kastens, U., Pfahler, P., Jung, M.T.: The eli system. In: Koskimies, K. (ed.) CC 1998. LNCS, vol. 1383, pp. 294–297. Springer, Heidelberg (1998)
Fernandes, J.P.: Design, implementation and calculation of circular programs. Ph.D. Thesis, Department of Informatics, University of Minho, Portugal, March 2009
Okasaki, C.: Breadth-first numbering: lessons from a small exercise in algorithm design. ACM SIGPLAN Notices 35(9), 131–136 (2000)
Uustalu, T., Vene, V.: Comonadic functional attribute evaluation. In: Trends in Functional Programming, Intellect Books, vol. 10, pp. 145–162 (2005)
Badouel, E., Fotsing, B., Tchougong, R.: Yet another implementation of attribute evaluation. Research Report RR-6315, INRIA (2007)
Badouel, E., Fotsing, B., Tchougong, R.: Attribute grammars as recursion schemes over cyclic representations of zippers. Electron. Notes Theory Comput. Sci. 229(5), 39–56 (2011)
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 (2009)
Martins, P.: Embedding attribute grammars and their extensions using functional zippers. Ph.D. Thesis, Universidade do Minho (2014)
Viera, M., Swierstra, S.D., Swierstra, W.: Attribute grammars fly first-class: how to do aspect oriented programming in haskell. SIGPLAN Not. 44(9), 245–256 (2009)
Fernandes, J.P., Saraiva, J., Seidel, D., Voigtländer, J.: Strictification of circular programs. In: Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. PEPM 2011, pp. 131–140. ACM, New York (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Martins, P., Fernandes, J.P., Saraiva, J. (2015). Zipper-Based Modular and Deforested Computations. In: Zsók, V., Horváth, Z., Csató, L. (eds) Central European Functional Programming School. CEFP 2013. Lecture Notes in Computer Science(), vol 8606. Springer, Cham. https://doi.org/10.1007/978-3-319-15940-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-15940-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15939-3
Online ISBN: 978-3-319-15940-9
eBook Packages: Computer ScienceComputer Science (R0)