Skip to main content

Programming errors in traversal programs over structured data

Thompson, Simon, Laemmel, Ralf, Kaiser, Markus (2013) Programming errors in traversal programs over structured data. Science of Computer Programming, . ISSN 0167-6423. (doi:10.1016/j.scico.2011.11.006) (KAR id:31505)

PDF Author's Accepted Manuscript
Language: English
Download (573kB) Preview
[thumbnail of 1-s2.0-S0167642311002061-main.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


Traversal strategies à la Stratego (also à la Strafunski and ‘Scrap Your Boilerplate’) provide an exceptionally versatile and uniform means of querying and transforming deeply nested and heterogeneously structured data including terms in functional programming and rewriting, objects in OO programming, and XML documents in XML programming.

However, the resulting traversal programs are prone to programming errors. We are specifically concerned with errors that go beyond conservative type errors; examples we examine include divergent traversals, prematurely terminated traversals, and traversals with dead code.

Based on an inventory of possible programming errors we explore options of static typing and static analysis so that some categories of errors can be avoided. This exploration generates suggestions for improvements to strategy libraries as well as their underlying programming languages. Haskell is used for illustrations and specifications with sufficient explanations to make the presentation comprehensible to the non-specialist. The overall ideas are language-agnostic and they are summarized accordingly.

Item Type: Article
DOI/Identification number: 10.1016/j.scico.2011.11.006
Uncontrolled keywords: Traversal strategies; Traversal programming; Term rewriting; Stratego; Strafunski; Generic programming; Scrap your boilerplate; Type systems; Static program analysis; Functional programming; XSLT; Haskell
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Simon Thompson
Date Deposited: 10 Oct 2012 19:40 UTC
Last Modified: 16 Feb 2021 12:42 UTC
Resource URI: (The current URI for this page, for reference purposes)
Thompson, Simon:
  • Depositors only (login required):


Downloads per month over past year