Zipper-Based Modular and Deforested Computations

详细信息    查看全文

• 作者：Pedro Martins (16)
  Jo茫o Paulo Fernandes (16) (17)
  Jo茫o Saraiva (16)
  
  16. High-Assurance Software Laboratory (HASLAB/INESC TEC) ; Universidade do Minho ; Braga ; Portugal
  17. Reliable and Secure Computation Group ((rel)ease) ; Universidade da Beira Interior ; Covilh茫 ; Portugal
  
• 关键词：Deforested computation ; Generic programming ; Functional programming
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8606
• 期：1
• 页码：407-427
• 全文大小：298 KB
• 参考文献：1. Bird, R (1984) Using circular programs to eliminate multiple traversals of data. Acta Informatica 21: pp. 239-250 CrossRef
  2. Moor, O, Backhouse, K, Swierstra, SD (2000) First-class attribute grammars. Informatica (Slovenia) 24: pp. 329-341
  3. 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鈥?06 (2007)
  4. 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鈥?56 (2009)
  5. Swierstra, D, Chitil, O (2009) Linear, bounded, functional pretty-printing. J. Func. Programm. 19: pp. 1-16 CrossRef
  6. Huet, G (1997) The zipper. J. Func. Programm. 7: pp. 549-554 CrossRef
  7. Martins, P, Fernandes, JP, Saraiva, J Zipper-based attribute grammars and their extensions. In: Bois, AR, Trinder, P eds. (2013) Programming Languages. Springer, Heidelberg, pp. 135-149 CrossRef
  8. 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鈥?4. ACM, New York (2010)
  9. 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鈥?7. ACM (2003)
  10. Kiselyov, O.: Tool demonstration: A zipper based file/operating system. In: Haskell Workshop. ACM Press, September 2005
  11. Stewart, D., Janssen, S.: XMonad: A tiling window manager. In: Haskell 2007: Proceedings of the 2007 ACM SIGPLAN Workshop on Haskell. ACM Press (2007)
  12. Johnsson, T.: Attribute grammars as a functional programming paradigm. In: Functional Programming Languages and Computer Architecture, pp. 154鈥?73 (1987)
  13. Kuiper, M., Swierstra, D.: Using attribute grammars to derive efficient functional programs. In: Computing Science in the Netherlands CSN 1987, November 1987
  14. Swierstra, SD, Azero Alcocer, PR, Saraiva, J Designing and implementing combinator languages. In: Swierstra, SD, Oliveira, JN eds. (1999) Advanced Functional Programming. Springer, Heidelberg, pp. 150-206 CrossRef
  15. Swierstra, D., Baars, A., L枚h, A.: The UU-AG attribute grammar system (2004)
  16. Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C.V., Loingtier, J.M., Irwin, J.: Aspect-oriented programming. In: ECOOP, pp. 220鈥?42 (1997)
  17. Saraiva, J.: Purely functional implementation of attribute grammars. Ph.D. Thesis, Department of Computer Science, Utrecht University, The Netherlands, December 1999
  18. Kastens, U, Pfahler, P, Jung, MT The eli system. In: Koskimies, K eds. (1998) Compiler Construction. Springer, Heidelberg, pp. 294-297 CrossRef
  19. Fernandes, J.P.: Design, implementation and calculation of circular programs. Ph.D. Thesis, Department of Informatics, University of Minho, Portugal, March 2009
  20. Okasaki, C (2000) Breadth-first numbering: lessons from a small exercise in algorithm design. ACM SIGPLAN Notices 35: pp. 131-136 CrossRef
  21. Uustalu, T., Vene, V.: Comonadic functional attribute evaluation. In: Trends in Functional Programming, Intellect Books, vol. 10, pp. 145鈥?62 (2005)
  22. Badouel, E., Fotsing, B., Tchougong, R.: Yet another implementation of attribute evaluation. Research Report RR-6315, INRIA (2007)
  23. Badouel, E, Fotsing, B, Tchougong, R (2011) Attribute grammars as recursion schemes over cyclic representations of zippers. Electron. Notes Theory Comput. Sci. 229: pp. 39-56 CrossRef
  24. 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鈥?44 (2009)
  25. Martins, P.: Embedding attribute grammars and their extensions using functional zippers. Ph.D. Thesis, Universidade do Minho (2014)
  26. Viera, M, Swierstra, SD, Swierstra, W (2009) Attribute grammars fly first-class: how to do aspect oriented programming in haskell. SIGPLAN Not. 44: pp. 245-256 CrossRef
  27. 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鈥?40. ACM, New York (2011)
  
• 作者单位：Central European Functional Programming School
• 丛书名：978-3-319-15939-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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.