DROPS

Document

DOI: 10.4230/OASIcs.EVCS.2023.20

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

Authors: Markus Lepper and Baltasar Trancón y Widemann

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{lepper_et_al:OASIcs.EVCS.2023.20,
  author =	{Lepper, Markus and Tranc\'{o}n y Widemann, Baltasar},
  title =	{{Visitor Optimization Revisited - Realizing Traversal Graph Pruning by Runtime Bytecode Generation}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{20:1--20:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.20},
  URN =		{urn:nbn:de:0030-drops-177906},
  doi =		{10.4230/OASIcs.EVCS.2023.20},
  annote =	{Keywords: Visitor Pattern, Generative Programming, Control Flow Analysis, Reflection, Runtime Code Generation}
}

Document

DOI: 10.4230/LIPIcs.RTA.2015.350

A Simple and Efficient Step Towards Type-Correct XSLT Transformations

Authors: Markus Lepper and Baltasar Trancón y Widemann

Published in: LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015)

Abstract

XSLT 1.0 is a standardized functional programming language and widely used for defining transformations on XML models and documents, in many areas of industry and publishing. The problem of XSLT type checking is to verify that a given transformation, when applied to an input which conforms to a given structure definition, e.g. an XML DTD, will always produce an output which adheres to a second structure definition. This problem is known to be undecidable for the full range of XSLT and document structure definition languages. Either one or both of them must be significantly restricted, or only approximations can be calculated. The algorithm presented here takes a different approach towards type correct XSLT transformations. It does not consider the type of the input document at all. Instead it parses the fragments of the result document contained verbatim in the transformation code and verifies that these can potentially appear in the result language, as defined by a given DTD. This is a kind of abstract interpretation, which can be executed on the fly and in linear time when parsing the XSLT program. Generated error messages are located accurately to a child subsequence of a single result element node. Apparently the method eliminates a considerable share of XSLT programming errors, on the same order of magnitude as a full fledged global control-flow analysis.

Cite as

Markus Lepper and Baltasar Trancón y Widemann. A Simple and Efficient Step Towards Type-Correct XSLT Transformations. In 26th International Conference on Rewriting Techniques and Applications (RTA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 36, pp. 350-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{lepper_et_al:LIPIcs.RTA.2015.350,
  author =	{Lepper, Markus and Tranc\'{o}n y Widemann, Baltasar},
  title =	{{A Simple and Efficient Step Towards Type-Correct XSLT Transformations}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{350--364},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.350},
  URN =		{urn:nbn:de:0030-drops-52078},
  doi =		{10.4230/LIPIcs.RTA.2015.350},
  annote =	{Keywords: XSLT, type checking, abstract interpretation}
}

Search Results

Documents authored by Trancón y Widemann, Baltasar

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

Abstract

Cite as

A Simple and Efficient Step Towards Type-Correct XSLT Transformations

Abstract

Cite as

Thanks for your feedback!

Could not send message