Document Open Access Logo

Visitor Optimization Revisited - Realizing Traversal Graph Pruning by Runtime Bytecode Generation

Authors Markus Lepper , Baltasar Trancón y Widemann

PDF
Thumbnail PDF

File

OASIcs.EVCS.2023.20.pdf
  • Filesize: 0.72 MB
  • 12 pages

Document Identifiers

Author Details

Markus Lepper
  • semantics gGmbH Berlin, Germany
Baltasar Trancón y Widemann
  • Nordakademie Elmshorn, Germany
  • semantics gGmbH Berlin, Germany

Cite AsGet BibTex

Markus Lepper and Baltasar Trancón y Widemann. Visitor Optimization Revisited - Realizing Traversal Graph Pruning by Runtime Bytecode Generation. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/OASIcs.EVCS.2023.20

Abstract

Visitors and Rewriters are a well-known and powerful design pattern for processing regular data structures in a declarative way, while still writing imperative code. The authors' "umod" model generator creates Java data models from a concise and algebraic notation, including code for visitor skeleton classes according to traversal annotations. User visitors are derived from these, overriding selected generated methods with payload code. All branches of the visiting trajectory that are not affected can thus be safely pruned according to control flow analysis. In the first version [Markus Lepper and Baltasar Trancón y Widemann, 2011], the pruning was implemented by dynamic case distinction. Here we have developed a new solution employing code generation at runtime.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Software performance
  • Mathematics of computing → Paths and connectivity problems
  • Theory of computation → Program analysis
Keywords
  • Visitor Pattern
  • Generative Programming
  • Control Flow Analysis
  • Reflection
  • Runtime Code Generation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Emilie Balland, Paul Brauner, Radu Kopetz, Pierre-Etienne Moreau, and Antoine Reilles. Tom: Piggybacking rewriting on java. In Franz Baader, editor, Term Rewriting and Applications, 18th International Conference, RTA 2007, Paris, France, June 26-28, 2007, Proceedings, volume 4533 of Lecture Notes in Computer Science, pages 36-47. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73449-9_5.
  2. Tim Bray, Jean Paoli, C.M. Sperberg-McQueen, Eve Maler, François Yergeau, and John Cowan. Extensible Markup Language (XML) 1.1 (Second Edition). W3C, 2006. URL: http://www.w3.org/TR/2006/REC-xml11-20060816/.
  3. Alcino Cunha and Joost Visser. Transformation of structure-shy programs: applied to xpath queries and strategic functions. In G. Ramalingam and Eelco Visser, editors, Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007, pages 11-20. ACM, 2007. URL: https://doi.org/10.1145/1244381.1244385.
  4. Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995. Google Scholar
  5. Ralf Lämmel. Scrap your boilerplate with xpath-like combinators. In Martin Hofmann and Matthias Felleisen, editors, Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2007, Nice, France, January 17-19, 2007, pages 137-142. ACM, 2007. URL: https://doi.org/10.1145/1190216.1190240.
  6. Ralf Lämmel, Eelco Visser, and Joost Visser. Strategic programming meets adaptive programming. In William G. Griswold and Mehmet Aksit, editors, Proceedings of the 2nd International Conference on Aspect-Oriented Software Development, AOSD 2003, Boston, Massachusetts, USA, March 17-21, 2003, pages 168-177. ACM, 2003. URL: https://doi.org/10.1145/643603.643621.
  7. Markus Lepper and Baltasar Trancón y Widemann. Optimization of visitor performance by reflection-based analysis. In Jordi Cabot and Eelco Visser, editors, Theory and Practice of Model Transformations, ICMT 2011, volume 6707 of LNCS, pages 15-30. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-21732-6_2.
  8. Markus Lepper and Baltasar Trancón y Widemann. Rewriting object models with cycles and nested collections. In ISoLA 2014, Part I, volume 8802 of Lecture Notes in Computer Science, pages 445-460. Springer-Verlag, 2014. URL: https://doi.org/10.1007/978-3-662-45234-9_31.
  9. Karl Lieberherr, Boaz Patt-Shamir, and Doug Orleans. Traversals of object structures: Specification and efficient implementation. ACM Trans. Program. Lang. Syst., 26(2):370-412, 2004. URL: https://doi.org/10.1145/973097.973102.
  10. Ralf Lämmel, Eelco Visser, and Joost Visser. The essence of strategic programming. Unpublished, January 2002. URL: https://www.researchgate.net/publication/277289331_The_Essence_of_Strategic_Programming.
  11. Aziz Nanthaamornphong and Rattana Wetprasit. Evaluation of the visitor pattern to promote software design simplicity. Jurnal Teknologi, 77(9):61-77, November 2015. URL: https://doi.org/10.11113/jt.v77.6186.
  12. Johan Ovlinger and Mitchell Wand. A language for specifying recursive traversals of object structures. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '99, pages 70-81, New York, NY, USA, 1999. Association for Computing Machinery. URL: https://doi.org/10.1145/320384.320391.
  13. Jens Palsberg and C. Barry Jay. The essence of the visitor pattern. In International Computer Software and Applications Conference (Compsac '98). ieee, 1998. URL: https://doi.org/10.1109/CMPSAC.1998.716629.
  14. Tanumoy Pati and James H. Hill. A survey report of enhancements to the visitor software design pattern. Software Practice and Experience, 44(6), 2014. URL: https://doi.org/10.1002/spe.2167.
  15. Dmitry Petrashko, Ondrej Lhotak, and Martin Odersky. Miniphases: compilation using modular and efficient tree transformations. In Proc. PLDI 2017, pages 201-216. ACM, 2017. URL: https://doi.org/10.1145/3062341.3062346.
  16. Baltasar Trancón y Widemann and Markus Lepper. Improving the performance of the Paisley pattern-matching EDSL by staged combinatorial compilation. In Declarative Programming and Knowledge Management, volume 12057 of LNAI, pages 268-285. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-46714-2.
  17. Baltasar Trancón y Widemann and Markus Lepper. LLJava live at the loop - a case for heteroiconic staged meta-programming. In Proc. MPLR 2021, pages 113-126, 2021. URL: https://doi.org/10.1145/3475738.3480942.
  18. Thomas VanDrunen and Jens Palsberg. Visitor-oriented programming. In Proc. FOOL-11, 2004. Google Scholar
  19. W3C. Scalable Vector Graphics (SVG) 1.1, 2nd edition, 2011. URL: http://www.w3.org/TR/SVG11/.
  20. W3C HTML Working Group. XHTML 1.0 The Extensible HyperText Markup Language, 2 edition, 2002. W3C Recommendation. URL: http://www.w3.org/TR/2002/REC-xhtml1-20020801.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact