This thesis has two independent parts concerned with different aspects of laziness in functional programs. The first part is a theoretical study of productivity for very restricted stream programs. In the second part we define a programming abstraction over a recursive pattern for defining circular traversals modularly. Productivity is in general undecidable. By restricting ourselves to mutually recursive polymorphic stream equations having only three basic operations, namely "head", "tail", and "cons", we aim to prove interesting properties about productivity. Still undecidable for this restricted class of programs, productivity of polymorphic stream functions is equivalent to the totality of their indexing function, which characterise their behaviour in terms of operations on indices. We prove that our equations generate all possible polymorphic stream functions, and therefore their indexing functions are all the computable functions, whose totality problem is indeed undecidable. We then further restrict our language by reducing the numbers of equations and parameters, but despite those constraints the equations retain their expressiveness. In the end we establish that even two non-mutually recursive equations on unary stream functions are undecidable with complexity $Π_2^0$. However, the productivity of a single unary equation is decidable. Circular traversals have been used in the eighties as an optimisation to combine multiple traversals in a single traversal. In particular they provide more opportunities for applying deforestation techniques since it is the case that an intermediate datastructure can only be eliminated if it is consumed only once. Another use of circular programs is in the implementation of attribute grammars in lazy functional languages. There is a systematic transformation to define a circular traversal equivalent to multiple traversals. Programming with this technique is not modular since the individual traversals are merged together. Some tools exist to transform programs automatically and attribute grammars have been suggested as a way to describe the circular traversals modularly. Going to the root of the problem, we identify a recursive pattern that allows us to define circular programs modularly in a functional style. We give two successive implementations, the first one is based on algebras and has limited scope: not all circular traversals can be defined this way. We show that the recursive scheme underlying attribute grammars computation rules is essential to combine circular programs. We implement a generic recursive operation on a novel attribute grammar abstraction, using containers as a parametric generic representation of recursive datatypes. The abstraction makes attribute grammars first-class objects. Such a strongly typed implementation is novel and make it possible to implement a high level embedded language for defining attribute grammars, with many interesting new features promoting modularity.

The Ruby programming language is dynamically typed, uses dynamic and late bound dispatch for all operators, method calls and many control structures, and provides extensive metaprogramming and introspective tooling functionality. Unlike other languages where these features are available, in Ruby their use is not avoided and key parts of the Ruby ecosystem use them extensively, even for inner-loop operations. This makes a high-performance implementation of Ruby problematic. Existing implementations either do not attempt to dynamically optimise Ruby programs, or achieve relatively limited success in optimising Ruby programs containing these features. One way that the community has worked around the limitations of existing Ruby implementations is to write extension modules in the C programming language. These are statically compiled and then dynamically linked into the Ruby implementation. Compared to equivalent Ruby, this C code is often more efficient for computationally intensive code. However the interface that these C extensions provides is defined by the non-optimising reference implementation of Ruby. Implementations which want to optimise by using different internal representations must do extensive copying to provide the same interface. This then limits the performance of the C extensions in those implementations. This leaves Ruby in the difficult position where it is not only difficult to implement the language efficiently, but the previous workaround for that problem, C extensions, also limits efforts to improve performance. This thesis describes an implementation of the Ruby programming language which embraces the Ruby language and optimises specifically for Ruby as it is used in practice. It provides a high performance implementation of Ruby's dynamic features, at the same time as providing a high performance implementation of C extensions. The implementation provides a high level of compatibility with existing Ruby implementations and does not limit the available features in order to achieve high performance. Common to all the techniques that are described in this thesis is the concept of specialisation. The conventional approach taken to optimise a dynamic language such as Ruby is to profile the program as it runs. Feedback from the profiling can then be used to specialise the program for the data and control flow it is actually experiencing. This thesis extends and advances that idea by specialising for conditions beyond normal data and control flow. Programs that call a method, or lookup a variable or constant by dynamic name rather than literal syntax can be specialised for the dynamic name by generalising inline caches. Debugging and introspective tooling is implemented by specialising the code for debug conditions such as the presence of a breakpoint or an attached tracing tool. C extensions are interpreted and dynamically optimised rather than being statically compiled, and the interface which the C code is programmed against is provided as an abstraction over the underlying implementation which can then independently specialise. The techniques developed in this thesis have a significant impact on performance of both synthetic benchmarks and kernels from real-world Ruby programs. The implementation of Ruby which has been developed achieves an order of magnitude or better increase in performance compared to the next-best implementation. In many cases the techniques are 'zero-overhead', in that the generated machine code is exactly the same for when the most dynamic features of Ruby are used, as when only static features are used.

One of the important tasks during software testing is the generation of appropriate test data. Various techniques have been proposed to automate this task. The techniques available, however, often have problems limiting their use. In the case of dynamic test data generation techniques, a frequent problem is that a large number of iterations might be necessary to obtain test data. This article proposes a novel technique for automated test data generation based on binary search. Binary search conducts searching tasks in logarithmic time, as long as its assumptions are fulfilled. This article shows that these assumptions can also be fulfilled in the case of path-oriented test data generation and presents a technique which can be used to generate test data covering certain paths in class methods.

In ubiquitous environments, users are exposed to public spaces and places where they are supposed to interact and provide also private information. In order to enhance user acceptance of such ubiquitous appliances they have to be designed to consider trust and trustworthiness already in the design phase. We focus on regarding trust in early phases and provide tools for designers by describing trust issues through patterns which are made available through design repositories. Such patterns help designers of ubiquitous applications to create designs quicker based on the availability of already proven solutions they can rely on.

Information systems for the support of complex business processes are often equipped with web-based front-ends to allow convenient user access. To produce executable specifications of the users’ interactions with such web-based applications, we use a visual language that enables developers to model their complex dialog structures. In this paper, we introduce the formal semantics of the core constructs of this Dialog Flow Notation: We define its syntax in terms of invariants about the permitted elements and their relations, and show how any words of the language (i.e. any syntactically correct dialog flow specifications) can be mapped to a deterministic pushdown automaton whose behavior defines the notation’s semantics. This gives us and other tool developers a formal basis for the design and implementation of tools and frameworks that mirror the precise meaning of all DFN constructs.

The hype surrounding Web 2.0 and technologies such as AJAX shows: The future of distributed application development lies in Rich Internet Applications (RIAs), which are based on highly distributed components and characterized by the intensive use of communication networks, complex interaction patterns and advanced GUI capabilities. As service providers begin to tap into the mobile market by extending the reach of their established e-commerce systems to mobile devices, a core challenge is the choice of a runtime environment and middleware that adapts well to the existing architecture, yet is a safe investment for the years to come. This paper surveys the current state and the future of runtime environments suitable for developing RIAs for mobile clients.

XMach-1 was the first XML data management benchmark designed for general applicability [1]. It is still the only benchmark supporting a multiuser performance evaluation of XML database systems. After a brief review of XMach-1 we summarize three additionally proposed benchmarks (XMark, XOO7, Mbench) and provide a comparison between these benchmarks. We then present experiences and performance results from evaluating XML database systems with XMach-1.

We propose a scaleable multi-user benchmark called XMach-1 (XML Data Management benchmark) for evaluating the performance of XML data management systems. It is based on a web application and considers different types of XML data, in particular text documents, schema-less data and structured data. We specify the structure of the benchmark database and the generation of its contents. Furthermore, we define a mix of XML queries and update operations for which system performance is determined. The primary performance metric, Xqps, measures the query throughput of a system under response time constraints. We will use XMach-1 to evaluate both native XML data management systems and XML-enabled relational DBMS.

We present a new approach for accelerating the execution of XPath expressions using parameterized materialized XPath views (PXV). While the approach is generic we show how it can be utilized in an XML extension for relational database systems. Furthermore we discuss an algorithm for automatically determining the best PXV candidates to materialize based on a given workload. We evaluate our approach and show the superiority of our cost based algorithm for determining PXV candidates over frequent pattern based algorithms.

Today, we are seeing an increasing number of software applications that users want to use anywhere, anytime. Such mobile applications often deliver their user interfaces (UIs) to client devices over the World Wide Web. However, Web-based UIs cannot provide the same level of usability as window-based UIs on mobile devices with their small screens and occasional network dropouts. To address this challenge, we present a UI framework that combines the usability of a full-featured UI with the flexibility of a thin presentation logic: We exchange interface specifications and events between the application logic on the server and a generic UI rendering engine on the client device using an instant messaging infrastructure. The paper gives an overview of the framework architecture and the features of the communication protocol, and discusses performance measurements obtained on a public network.