René Haberland

René Haberland

This work proposes a Prolog-dialect for the found and prioritised problems on expressibility and automation. Given some given C-like program, if dynamic memory is allocated, altered and freed on runtime, then a description of desired dynamic memory is a heap specification. The check of calculated memory state against a given specification is dynamic memory verification. This contribution only considers formal specification and verification in a Hoare calculus. Issues found include: invalid assignment, (temporary) unavailable data in memory cells, excessive memory allocation, (accidental) heap alteration in unexpected regions and others. Excessive memory allocation is nowadays successfully resolved by memory analysers like Valgrind. Essentially, papers in those areas did not bring any big breakthrough. Possible reasons may also include the decrease of tension due to more available memory and parallel threads. However, starting with Apt, problems related to variable modes have not yet been resolved -- neither entirely nor in an acceptable way. Research contributions over the last decades show again and again that heap issues remain and remain complex and still important. A significant contribution was reached in 2016 by Peter O'Hearn, who accepted the Gödel prize for his parallel approach on a spatial heap operation.

René Haberland

This work examines how much template instantiation can narrow down schema validation for XML-documents. First, instantiation and validation are formalised. Properties towards their practical meaning are probed, an implementation is developed. Requirements for an unification are elaborated and a comparison is taken out. The semantics are formulated in terms of denotational semantics as well as rule-based referring to the data models chosen. Formalisation makes it clearer instantiation is adequately represented. Both semantics show, that the rules set for both, instantiation and validation, cannot totally be unified. However, reuse of simplified code also simplifies unification. Implementation allows unification of both processes on document-level. The validity of all implementations is guaranteed by a comprehensive test suite. Analysis shows the minimal XML template language has got regular grammar properties, except macros. An explanation was given, why filters and arrows are not best, especially towards a unified language to be variable and extensive. Recommendations for future language design are provided. Instantiation shows a universal gap in applications, for instance, as seen by XSLT. Lack of expressibility of arbitrary functions in a schema is one such example, expressibility of the command language is another basic restriction. Useful unification constraints are found out to be handy, such as typing each slot. In order to obtain most flexibility out of command languages adaptations are required. An alternative to introducing constraints is the effective construction of special NFAs. Comparison criteria are introduced regarding mainly syntax and semantics. Comparisons is done accordingly. Despite its huge syntax definitions XSD was found weaker than RelaxNG or XML template language. As template language the latter is considered universal.

René Haberland

Proponents of the programming language Prolog share the opinion Prolog is more appropriate for transforming XML-documents as other well-established techniques and languages like XSLT. In order to clarify this position this work proposes a tuProlog-styled interpreter for parsing XML-documents into Prolog-internal lists and vice versa for serialising lists into XML-documents. Based on this implementation a comparison between XSLT and Prolog follows. First, criteria are researched, such as considered language features of XSLT, usability and expressibility. These criteria are validated. Second, it is assessed when Prolog distinguishes between input and output parameters towards reversible transformation.

René Haberland

The processing of XML documents often includes creation and validation. These two operations are typically performed in two different nodes within a computer network that do not correlate with each other. The process of creation is also called instantiation of a template and can be described by filling a template with data from external repositories. Initial access to arbitrary sources can be formulated as an expression of certain command languages like XPath. Filling means copying invariant element nodes to the target document and unfolding variable parts from a given template. Validation is a descision problem returning true if a given XML document satisfies a schema and false otherwise. The main subject is to find a language that unions the template expansion and the validation. [..].

René Haberland, Igor L. Bratchikov

Transforming XML documents with conventional XML languages, like XSL-T, is disadvantageous because there is too lax abstraction on the target language and it is rather difficult to recognize rule-oriented transformations. Prolog as a programming language of declarative paradigm is especially good for implementation of analysis of formal languages. Prolog seems also to be good for term manipulation, complex schema-transformation and text retrieval. In this report an appropriate model for XML documents is proposed, the basic transformation language for Prolog LTL is defined and the expressiveness power compared with XSL-T is demonstrated, the implementations used throughout are multi paradigmatic.