XML-Print: Addressing Challenges for Scholarly Typesetting

1 Introduction
At last year’s DH conference, we presented our Open Source project XML-Print live(Sievers, et al., 2012). The audience’s responses gave a strong impulse for the second project stage to extend and fine-tune the software and improved its technical architecture. The latest build is available for download from http://www.xmlprint.eu/.
While the former talk focused on the infrastructure and general ideas of XML-Print, this paper delivers insight into the challenges of the project’s development process, which are paradigmatic for the dual nature of the challenges faced by many DH development projects. This includes issues already solved as well as concepts for open ones. The following aspects will be discussed:
• 1. Typesetting critical editions is one of the major use cases for XML-Print. Apart from “standard” typesetting features we have implemented support for manging an arbitrary number of apparatuses (cf. Section 2.1).
• 2. The typesetting engine is written in the functional programming language F#, which — among other advantages — offers powerful parallelization techniques. However, we must use appropriate programming routines for that. The ideas behind parallelizing the typesetting are described in section 2.2.
• 3. Today’s typesetting world is global, meaning support for many writing systems including bidirectional scripts. Section 2.3 reports about the concepts for bidirectional typesetting within XML-Print.
• 4. Last, but not least software development needs sophisticated test concepts to recognize problems before new versions are published. This is important not only for obvious build or compilation errors, but especially for typesetting problems. The image-based test approach is presented in Section 2.4.
2 Challenges
2.1 Critical Apparatus
Typesetting a single footnote apparatus is not sufficient for scholarly purposes. We need a robust and generic algorithm to place any number of apparatuses to be grouped together on a page.
The user manages this grouping process by creating an appropriate mapping between a layout format and XML elements. The output position of the footnote apparat-uses on a page is determined by the order given in the footnote dialogue (cf. Figure 1). This information is coded into the XSL-FO+ [1] file as an XML attribute to the footnote element, e.g.<footnote place="0" fn-type="footnote">. [2] .
The typesetting engine sorts the footnotes corresponding to their place attribute and calculates the space needed on a concrete output page, including spacing between apparatuses. All this can already be done using XML-Print. An example is illustrated in Figure 2.
However, when typesetting critical editions, footnote apparatuses alone are not sufficient. There has to be a possibility to refer to the line number of a lemma or to use a user-defined reference schema as well. That reference is used instead of the common footnote sign. The typesetting engine must furnish the necessary references, which is only available at runtime and calculated in the output routines.

Figure 1:
The grouping and sorting of footnote apparatuses is done with the footnote dialog from the graphical user interface.

Figure 2:
Example of two footnote apparatuses of a letter from the “Kurt-Schwitters-Briefe” (Wie Kritik zur Kunst wird). For a real critical apparatus references to line numbers of lemmata have to be implemented.
2.2 Parallelizing the Typesetting
Implementing a typesetting system with all its characteristics and subtleties is a chal-lenge concerning two technical aspects: efficiency and memory consumption. Both aspects can be satisfied by the data structures and algorithms used in the implementation. We need to parallelize the XML-Print typesetting engine as the rendering process is resource intensive. In particular, when pre-rendered pages have to be adapted to changes and need final rendering, the process is very time-consuming. This is the case if XML-Print typesets remaining footnotes from previous pages. The content of the current typeset page must be balanced with the contents of the remaining and the current footnotes. The described problem can be solved in mainly two ways: directly improving the typesetting of footnotes or/and improving the overall rendering process.
Improving the typesetting of footnotes can directly be achieved by a more sophisticated algorithm. That means not by balancing the contents line by line but by using binary cuts instead, i.e. starting with lines1, lines2, lines4, …, lineslines until the footnote and the current page’s contents are in balance. Unfortunately, this solution covers only one of several performance problems.
Therefore, improving the overall rendering process must be the final goal. The parallelization efforts are based on the dynamic programming idea by Bellman (1954). Thus, the rendering process is separated in typesetting single sequences, i.e. single XML fragments. For that the input XML file is read and then split into fragments representing such sequences. These are the basic elements in the XSL-FO (Anders 2006) structure that can be processed independently from other data. Afterwards, these sequences are typeset in parallel, are then concatenated and finally written into a single document.
Implementing the introduced parallelization mechanism requires the following characteristics:
• Resource-efficient XML processing, especially when reading the file and dividing it into fragments
• Isolated, side-effect free and generic rendering algorithms for separated sequences.
Indeed, F# as a functional programming language offers the possibilities to address these requirements.
2.3 Bidirectional Text
Like many other typeset editors (e.g. Texmaker, TeXstudio and TeXShop for LaTeX), XML-Print must support bidirectional (BiDi) texts. The implementation of this feature is part of the actual project phase, because we got many requests from scholars and projects to support BiDi. One of those projects is “RIR — Relationen im Raum” (https://dev2.dariah.eu/wiki/display/RIRPUB/RiR), which uses XML as an exchange format with “epidat”, a database of Jewish epigraphy (epidat — epigraphische Datenbank). The typesetting engine of XML-Print shall be used to automatically generate PDF documents with mixed Hebrew and German inscriptions and synoptically typeset German translations.
The Unicode standard provides the Unicode Bidirectional Algorithm (UBA) (Davis) to display BiDi texts correctly making it the industry standard for displaying such texts. The algorithm is well known and extensively tested. XML-Print therefore will base its support for Hebrew and Arabic texts on the UBA.
2.4 Testing and Quality Assurance
Testing is undoubtedly an important factor for any software project, but assuring the quality of a typesetting engine provides some additional challenges. As pointed out earlier, algorithms addressing different functions such as footnotes or bidirectional text are already very complex. Orchestrating multiple algorithms to produce a single document reaches a level of complexity, for which no developer can ultimately consider all side-effects and interoperability problems. Moreover, problems caused by errors in the source code often have minimal visual effects to the result so that a human tester cannot easily assess errors.
Therefore we have developed an automated system for functional testing. These functional tests are based on reference documents of varying complexity. For each test run, these documents are generated anew using the current version of the typesetting engine. In the next step each page of each document is split into regions. All regions are compared to the corresponding regions of the reference document pixel by pixel. This pixel comparison is performed using the Sikuli engine (Sikuli Script), which, in addition to comparing screen images, can be easily extended to display the proper documents and to simultaneously flip the pages of these documents. If any mismatch is detected between the generated and the reference document, a difference-image is created containing the differing section. Further, this image is enhanced with fragments of both documents to make it easier for a developer to recognize the problem (cf. Figure 3).

Figure 3:
Example of a pixel comparison of two documents.
3 Summary and Outlook
XML-Print tackles challenges on a number of levels:
• Handling the requirements of advanced scholarly typesetting, notably the handling of multiple apparatuses and bidirectional texts
• Responding to opportunities offered by heavily parallel hardware
• Guaranteeing consistent quality and absence of regressions in a very much visual domain
As we have seen, the project responds to these challenges by
• Creating a user interface that guides users through the complexity of advanced requirements
• Opting based on F# for a functional design of the typesetting engine that can easily be parallelized
• Developing testing techniques to automatically compare typesetting results in PDF to manually validated example documents
XML-Print’s version 1.0 release is already a viable option for simple typesetting needs. However, much remains to be done during the remaining project duration. In addition to fine-tuning the existing implementation for scholarly apparatuses and bidirectional texts, XML-Print still has to support multiple columns, synoptic typesetting, running headers and footers, interactive corrections and manual overrides to the automatic results, e.g. to manually set line breaks or hyphenation. New requirements and changes in the overall of features also result from direct user feedback, e.g. regarding horizontal alignments of phrases in addition to classical synoptic editions. These requests are themselves sign of an increasing and encouraging take-up of XML-Print amongst early adopters, keen to introduce the software into their projects.
References
Sievers, M., Burch, T., Küster, M. W., Moulin, C., Rapp, A., Schwarz, R., Gan, Y. (2012). XML-Print: an Ergonomic Typesetting System for Complex Text Structures. In Hamburg, S. Digital Humanities. Conference Abstracts.375–379.
Wie Kritik zur Kunst wird. Project website. http://www.avl.uni-wuppertal.de/forschung/projekte/wie-kritik-zu-kunst-wird.html [accessed 4 Mar 2013].
Bellman, R. (1954). Dynamic Programming and Modern Control Theory. Princeton, New Jersey.
Anders, B. (2006). Extensible Stylesheet Language (XSL) Version 1.1. W3C Recommendation.http://www.w3.org/TR/xsl11/ (accessed 4 Mar 2013).
Relationen im Raum — Visualisierung topographischer Klein(st)strukturen. Project website.https://dev2.dariah.eu/wiki/display/RIRPUB/RiR (accessed 4 Mar 2013).
epidat — epigraphische Datenbank. Project website.
Davis, M. Unicode Bidirectional Algorithm. http://www.unicode.org/reports/tr9/ (accessed 4 Mar 2013).
http://www.sikuli.org/ (accessed 4 Mar 2013).
Notes
1. XSL-FO+ is an extension of the XSL-FO standard [4] to meet the requirements of scholars in the Humanities. It has been especially designed for XML-Print.
2. This is a prominent example for extending the XSL-FO standard, which does not offer anything for using apparatuses yet.