Search

Software has become ubiquitous and its impact is still increasing. The more software is created, the more bugs get introduced into it. With software's increasing omnipresence, these bugs have a high probability of negative impact on everyday life. There are many efforts aimed at improving software correctness, among which symbolic execution, a program analysis technique that aims to systematically explore all program paths. In this thesis we present three techniques for enhancing symbolic execution. We first present a counterexample-guided inductive synthesis approach to summarise a class of loops, called memoryless loops using standard library functions. Our approach can summarize two thirds of memoryless loops we gathered on a set of open-source programs. These loop summaries can be used to: 1) enhance symbolic execution, 2) optimise native code and 3) refactor code. We then propose a technique that avoids expensive forking by using a segmented memory model. In this model, we split memory into segments using pointer alias analysis, so that each symbolic pointer refers to objects in a single segment. This results in a memory model where forking due to symbolic pointer dereferences is reduced. We evaluate our segmented memory model on benchmarks such as SQLite, m4 and make and observe significant decreases in execution time and memory usage. Finally, we present pending constraints, which can enhance scalability of symbolic execution by aggressively prioritising execution paths that are already known to be feasible either via cached solver solutions or seeds. The execution of other paths is deferred until no paths are known to be feasible without using the constraint solver. We evaluate our technique on nine applications, including SQLite3, make and tcpdump, and show it can achieve higher coverage for both seeded and non-seeded exploration.

Interviewing is an essential practice for the elicitation of requirements, and a significant phase of the system development life cycle that is used for in-depth discussions. However, professionals face difficulties in extracting tacit (hidden) knowledge from interviewees, which disturbs the practice of interviewing, and later, affects the success of software in terms of additional cost, delays, failure or cancellation. In this study, a new approach is introduced using four different modes of electronic communication tools, including 'Audio Podcast', 'E-mail', 'Online Chat Session' and 'Hybrid' (a combination of 'Audio Podcast' + 'E-mail' + 'Online Chat Session') to discuss the details of interview agenda with interviewees, before conducting semi-structured interviews for the requirements elicitation phase of software development. This research has used a concurrent triangulation design for mixed methods and compared the effects of the four electronic communication tools on the interview process, in relation to tacit knowledge elicitation. The total number of subjects was 120, divided into four equal groups of 30 subjects for 'Audio Podcast', 'E-mail', 'Online Chat Session' and 'Hybrid'. Two hypotheses were tested through quantitative data collection, to evaluate the effects, and differences in effectiveness among these four electronic tools towards six famous key areas including 'Friendly', 'Comfortable', 'Essential', 'Understanding', 'Learning', and 'Tacit Knowledge Elicitation', respectively. Grounded theory was used to address the research question through the elicitation of qualitative data, gathered by semi-structured interviews, and the outcomes are visualized through a 'Spider Chart' (a diagrammatic way of presenting multivariate data) towards four key areas of requirements ('General', 'Functionality', 'Usability', and 'Content') for the construction of a website. Prompting was calculated during the interviews, and its percentage is presented through 'Comparison Chart'. There were four steps for each group, concerning this study including (1) Participants' feedback through survey questionnaires before e-tool usage. (2) Use of an e-tool for detailed discussions of interview agenda. (3) Attending the interview (4) Post interview feedback through survey questionnaires after e-tool usage. Analysis has revealed that this research has produced state-of-the-art results. These four electronic communication tools have acted as moderating variables, and affected the process of interviewing positively, towards the elicitation of tacit knowledge, accompanied by a clear difference in the effectiveness of each electronic communication tool. This method can increase the success rate of upcoming software developments.

As most software requirements are written in natural language, they are unstructured and do not adhere to any formalism. Therefore, automatically processing these requirements in the context of Requirement Engineering (RE) is often difficult, complex and opaque. The problems fall under the remit of linguistic issues, such as ambiguity and incompleteness. Techniques and resources from Natural Language Processing (NLP) have been used for exploring natural language issues in unstructured requirement documents. The research in this hybrid area of RE studies has covered various tasks, including analysing, modelling and organising requirements, which generally referred as NLP for RE (or simply NLP4RE) research tasks. An essential linguistic process that is common in most of NLP4RE tasks is the process of identifying relationships between requirement statements, i.e., detecting semantic relatedness and similarity within a requirement document as a collection of software descriptions. By detecting such a complex and (mostly) hidden relationship in the natural description of requirements, we will end with more accurate and robust NLP4RE tools that could handle the lack of formalism in unstructured requirement documents. For example, to enable traceability between an arbitrary set of natural documents by linking their shared or common semantic relationships i.e. to trace requirements with specific concepts such as requirements that explain sending/receiving operations, verifying user credential for security purposes and more. This PhD thesis explores the potential of and adopts the semantic frames, embodied in the FrameNet lexicon, to provide unique insights and novel approaches (accompanied with several methods implemented into systems) for measuring and identifying semantic relationships in software descriptions expressed through unstructured, natural language. We follow a research methodology consists of collecting evidence of FrameNet's feasibility in RE, experimenting with various FrameNet-based solutions and critically appraising these solutions using real-world requirement documents. The first approach -- the knowledge-based approach -- is implemented based on the knowledge available in the FrameNet lexicon, through which we experiment with the various semantic similarity metrics used with different ontologies and lexica in FrameNet. The second approach -- the corpus-supported approach -- adapts FrameNet tagged corpora, one of which is the result of the earlier research method studying FrameNet's coverage of requirement documents. The corpus-supported approach utilises corpora features, such as frame frequencies and co-occurrences, to measure the relatedness between frames from the RE use context. The third and final approach -- the embedding-based approach -- is based on trained word embeddings for the RE domain. Thus, we propose new resources, i.e., embedding-based representations of semantic frames in FrameNet. We obtain motivational results from the corpus-based analysis, which has been conducted to study FrameNet's appropriateness for labelling software descriptions. Thus, this research creates the first RE corpus, consisting of 5,348 requirement statements, that is fully annotated with FrameNet frames. Afterwards, the proposed approaches to measure semantic frames' relatedness are evaluated based on their designated task -- identifying related semantic frames from the FrameNet while considering the RE context. The intrinsic evaluation is compared with a human-judgment dataset of frame-to-frame relationships. As a result, the embedding-based approach achieves more than a satisfactory overall performance rate in measuring and identifying semantic relationships between FrameNet frames from an RE perspective. For the extrinsic evaluation, we use the embedding-based approach in a requirement measurement technique to identify semantic relationships between natural language requirement statements. A satisfactory performance rate is obtained compared to lexically-founded baseline systems and the human-judgment dataset. The encouraging results of the embedding-based approach prove the adequacy of using encapsulated contextual information (represented by semantic frames) to trace requirements' relatedness.

During the past decades, the technology of the Near-Infrared Spectroscopy (NIRS) has been widely adopted as a non-destructive analytical tool in various fields. In agriculture and chemometrics, NIRS analysis at single kernel level can improve not only the sample uniformity and purity but also the quality and economic value of a seed batch. However, many limitations and challenges exist in the single kernel Near-Infrared Spectroscopy (SKNIRS) analysis and applications. The first contribution of this PhD thesis was to develop an integrated software system to support data collection, processing and analysis for single kernel sample. IDEF0 Functional Modelling has been used to guide the development and implementation of the integrated software system. Two real-world applications supported by the integrated software system were reported as the validation of the integrated software system. Another contribution of this PhD thesis was to provide a benchmark of chemometric methods for comparative single kernel near-infrared spectroscopy analysis based on the proposed stepwise process. Sixteen methods including two dataset partition methods, three pre-processing methods, eight variable selection methods and three calibration methods were assessed and compared based on two statistics: root mean squared error of prediction (RMSEP) and coefficient of determination (R2). Conclusions were discussed in detail based on the results of benchmarking analysis, which is appropriately general and may assist the choice of chemometric methods for SKNIRS.

Dynamic taint analysis is a fundamental technique in software security that tracks the flow of interesting or suspicious data during the execution of a target application. However, it is also known to suffer from excessively high runtime overhead which limits its overall practicality. The overhead is especially problematic when the taint analysis performed is generic. While this type of analysis is more powerful than standard taint status tracking, due to its support of user-defined custom taint policies, its versatility naturally implies that it cannot be optimized for a single task. Along these lines, this dissertation addresses the challenging problem of enhancing the performance of generic taint analysis. Our research focuses on taint engines implemented using dynamic binary instrumentation. Essentially, the performance bottleneck of these systems stems from complex taint propagation code that is dynamically instrumented, at the level of machine instructions, into the target application. In order to facilitate the implementation of generic taint analysis, instrumentation is typically achieved by inserting transparent calls, which conveniently invoke propagation routines without disrupting the execution behaviour of the analysed application. However, these calls perform expensive context-switching, and therefore degrade overall runtime performance significantly. We hypothesize that the overhead of generic taint analysis can be reduced in comparison to the slowdowns incurred by the analysis implemented with the use of transparent calls. This hypothesis is tested by investigating three optimizations. Firstly, call-free generic taint propagation is evaluated as a means to mitigate expensive context switching. Secondly, the idea of vectorized generic taint analysis is explored to determine the effectiveness of using SIMD features to propagate multiple taint labels simultaneously. Thirdly, dynamic fast path generation is proposed so that the execution of ineffective taint propagation can be adaptively elided. Our optimizations are presented with respect to a generic taint analysis driven by user-defined primitives, which act as building blocks for custom taint propagation. Crucially, this primitive based approach enables the user to focus on optimizing core pieces of functionality regarding the desired policy, without the need to delve into the complex internals of the system. The optimizations are integrated into a generic taint tracker called the Taint Rabbit, and their effectiveness is evaluated on various real-world software and CPU-bound benchmarks. With average speed-ups of around 42% on SPEC CPU benchmarks, and as high as 99% on data compression tools, our results demonstrate the advancement of optimized and generic taint analysis.

The young generation is passionate about technology and the update of learning/teaching tools is a necessity to match their current interest. The existing literature on gamification supports its benefit on students' engagement, learning acquisition, skills and resilience. This research discusses gamification concept in a pedagogical context, in which there appears to be a lack of clarity about the meaning provided in the literature. The balance of gamification design to cultivate students' both extrinsic and intrinsic motivation. Then, it describes a focused interest in teachers' roles as key stakeholders in gamification design. A literature review carried out to investigate current practices of gamification design and identify the barriers. There is inadequate integration of learning that theories might preserve the pedagogical aspect of the design. However, these theories might not be reciprocated by game developers. Conversely, game design terminology could be challenging for some teachers. There is a need to find common ground where both parties can express their design decisions and communicate efficiently. Therefore, there is a need for a communication platform that includes the two stakeholders-teachers and game developers-in the design process. This would keep each of them focused on their area of expertise and avoid the disadvantage of taking up too much of their time (i.e. the teachers will not dive into programming or game design technicalities). The research developed an Agile Holistic Gamified Pedagogical Design (AH-GPD) Framework to support the synergy between teachers and game developers in the design process. The framework's high-level is based on two software design models: Analysis, Design, Development, Implementation, and Evaluation (ADDIE) and Usability-Software Development Life Cycle (U-SDLC). In this research, a comprehensive search was conducted to identify the gamification elements in a pedagogical context. The identified gamification elements are used to enhance the practicality of the framework and its adaptability by teachers. Then, the teachers' role was defined using in the design process using a quantitative approach to categorise the gamification aspects from a teacher's point of view. The supported categorisations are teacher-driven, game developers-driven or shared task. The next step of the research is the practical validation of the gamification elements utilising the think aloud interview protocol (qualitative approach) with teachers. Following that, a validation of the research with game developers through interviews to enable the collaboration with teachers and refining the framework. The validation of the research with both teachers and game developers concludes to building Pedagogical Game Design Document (Ped-GDD) as communication template. An evaluation of the Ped-GDD was conducted with a panel of experts representing the two stakeholders; teachers and game developers. The evaluation was conducted through a semi-structured interview, and the criteria is adopted from the Technology Acceptance Model (TAM). The features assessed are; Easy to learn, Easy to use, Usefulness, Comprehensiveness, Adaptability and Intention to use in the future.

Online reviews are an important channel for requirement elicitation. However, requirement engineers face challenges when analysing online user reviews, such as data volumes, technical supports, existing techniques, and legal barriers. This thesis proposes a framework solving user review analysis problems for the purpose of requirement elicitation that sets up a channel from downloading user reviews to structured analysis data. This framework is believed to be able to solve the problems because (a) the structure of this framework is composed of several loosely integrated components, which not only realize the flow of data from downloading raw user reviews to the structured analysis results, but also provide adaptability and flexibility for wider future applications; (b) the reasonable use of linguistic rules makes it possible to adjust and control the internal details of the system in this data flow; (c) natural language processing (NLP) technologies, such as chunking, regular expressions, and especially Stanford dependency trees, provide substantial technical support for this framework. Three mobile app user review datasets were used to evaluate the functionalities. 6081 user reviews from the first dataset is used for the development of linguistic rules. The first two datasets are used to enrich the popular opinions and the keywords list. The third dataset acts as a control group. The performance results of the prototype demonstrate that this framework is practical and usable. The main contributions of this work are: (1) this thesis proposed a framework to solve the user review analysis problem for requirement elicitation; (2) the prototype of this framework proves its feasibility; (3) the experiments prove the effectiveness and efficiency of this framework.

Higher-order constrained Horn clauses (HoCHC) are a fragment of higher-order logic modulo theories recently introduced by Cathcart Burn et al. (2018). This thesis explores the adequacy of HoCHC as a unifying framework for the algorithmic verification of higher-order programs, through links with existing approaches to program verification as well as a sound and refutationally complete solution method for HoCHC. We establish a continuous interpretation for HoCHC in which the semantic domains are restricted to Scott-continuous functions. We show that the continuous HoCHC decision problem is equivalent to the original problem. This continuous interpretation serves as a foundation for a sound and refutation-complete resolution proof system - based on SLD-resolution - for solving unsatisfiable instances of the HoCHC problem over a semi-decidable background theory. To address the relation between HoCHC and higher-order model checking, we introduce a coinductive version of HoCHC that is characterised by a greatest fixpoint construction. We define an encoding of higher-order recursion schemes into a HoCHC logic program, which can be used to reduce the open higher-order recursion scheme equivalence problem - and thus the lambdaY-calculus Böhm tree equivalence problem - to semi-decidability of coinductive HoCHC over Maher's complete and decidable background theory of trees (Maher, 1988; Djelloul et al., 2008). Finally, we develop an axiomatic basis for relations as higher-order program invariants in the form of a Hoare logic. Our approach to Hoare logic for higher-order programs distinguishes itself from the literature through the combination of a higher-order assertion logic and a relatively complete proof system.

Though some software development teams are highly effective at delivering security, others either do not care or do not have access to security experts to teach them how. Unfortunately, these latter teams are still responsible for the security of the systems they build: systems that are ever more important to ever more people. Yet many, perhaps most, security problems can be prevented with careful design, construction and configuration of the software and systems involved, so software developers have a major contribution to make. This research investigated how to help teams of software developers achieve better security. An initial qualitative survey of 15 secure software development professionals highlighted a range of security assurance and motivation techniques suitable for teams of developers, and emphasised the human interaction aspects. A further quantitative survey of 330 successful Android developers then identified a baseline of current security practices in software development. Based on these surveys, the author created an intervention package to help software developers. Action Research techniques were used to trial and improve it in two one-year cycles with a total of 19 development teams in 11 different organisations. The later development of the package concentrated on empowering the developers involved, and reducing the involvement required from the researchers. By proving that a set of structured workshops can have an impact on the security performance of a team for a reasonable cost and without the support of security professionals, this research offers a powerful means to enhance development security in the UK, creating more secure software and systems for all users.

Martin-Löf type theory is a formal language which is used both as a foundation for mathematics and the theoretical basis of a range of functional programming languages. Inductive types are an important part of type theory which is necessary to express data types by giving a list of rules stating how to form this data. In this thesis we we tackle several questions about different classes of inductive types. In the setting of homotopy type theory, we will take a look at higher inductive types based on homotopy coequalizers and characterize their path spaces with a recursive rule which looks like an induction principle. This encapsulates a proof technique known as ``encode-decode method''. In an extensional meta-theory we will then explore the phenomenon of induction-induction, specify inductice families and discuss how we can reduce each instance of an inductive-inductive type to an inductive family. Our result suggests a way to show that each type theory which encompasses inductive families can also express all inductive-inductive types.

This thesis furthers the ongoing study of devising faster algorithms for the learning problem of infinite-state systems. We examine the Hidden Probabilistic One-Counter Machine (HP1CA) model, a natural extension of both Probabilistic One-Counter Automata (P1CA) and Hidden Markov Model (HMM) in this thesis. HP1CAs allow for the quadratic time complexity of learning the parameters of the model based on observational data. This gives them a big advantage over other infinite-state systems, e.g., probabilistic pushdown automata for which the same task requires cubic time. An HP1CA is a P1CA where both the control states and the counter values are hidden, but the output sequence is not (note that there is no input sequence). Such a model has a non-negative counter whose value can change by at most one during a transition. The probability of a transition depends only on the current control state and whether the counter value is zero or not. The probability of a given output symbol depends on the current control state, but not on the value of the counter. A sequence of transitions is valid only if it starts and ends in a special initial control state and final control state, respectively, with the counter value equal zero. After introducing the model, we adapt Baum-Welch algorithm, which is a special case of the Expectation-Maximization algorithm used in unsupervised learning in HMM, to update the parameters of an HP1CA. Furthermore, we also adopted two dynamic programming algorithms which are called Forward algorithm and Backward algorithm, respectively to our new model. Our adapted algorithms have worst-case quadratic time complexity as compared to the linear time for HMM. At the same time, its complexity is linear if the maximum value of the counter is assumed to be bounded by a constant (as it is commonly in practice). After that, we look at other possible HP1CA models that differ depending on the semantic of what a valid transition sequence is. This can depend on the initial and final terminal state conditions as follows. First, an HP1CA can either start in (1) a fixed control state with counter zero or (2) have multiple initial control states, and some fixed probability distribution specifies the likelihood of starting in a given control state (with a counter value zero). Second, an HP1CA may be required to end with (A) a unique final control state with counter value zero, (B) a unique final control state with arbitrary counter value, (C) multiple final control states with zero counter value. This gives rise to six possible semantics, and only (1-A) semantic studied by us earlier. We adapt the learning and dynamic programming algorithms to the remaining five models. In the end, we demonstrate that our HP1CA model leads to better accuracy and lower fit error of observation sequences as compared to HMMs through an implementation.

We propose a new methodology for learning the structure of sparse networks from data; in doing so we adopt a dual perspective where we consider networks both as weighted graphs and as simplicial complexes. The proposed learning methodology belongs to the family of preferential attachment algorithms, where a network is extended by iteratively adding new vertices. In the conventional preferential attachment algorithm a new vertex is added to the network by adding a single edge to another existing vertex; in our approach a new vertex is added to a set of vertices by adding one or more new simplices to the simplicial complex. We propose the use of a score function to quantify the strength of the association between the new vertex and the attachment points. The methodology performs a greedy optimisation of the total score by selecting, at each step, the new vertex and the attachment points that maximise the gain in the score. Sparsity is enforced by restricting the space of the feasible configurations through the imposition of topological constraints on the candidate networks; the constraint is fulfilled by allowing only topological operations that are invariant with respect to the required property. For instance, if the topological constraint requires the constructed network to be be planar, then only planarity-invariant operations are allowed; if the constraint is that the network must be a clique forest, then only simplicial vertices can be added. At each step of the algorithm, the vertex to be added and the attachment points are those that provide the maximum increase in score while maintaining the topological constraints. As a concrete but general realisation we propose the clique forest as a possible topological structure for the representation of sparse networks, and we allow to specify further constraints such as the allowed range of clique sizes and the saturation of the attachment points. In this thesis we originally introduce the Maximally Filtered Clique Forest (MFCF) algorithm: the MFCF builds a clique forest by repeated application of a suitably invariant operation that we call Clique Expansion operator and adds vertices according to a strategy that greedily maximises the gain in a local score function. The gains produced by the Clique Expansion operator can be validated in a number of ways, including statistical testing, cross-validation or value thresholding. The algorithm does not prescribe a specific form for the gain function, but allows the use of any number of gain functions as long as they are consistent with the Clique Expansion operator. We describe several examples of gain functions suited to different problems. As a specific practical realisation we study the extraction of planar networks with the Triangulated Maximally Filtered Graph (TMFG). The TMFG, in its simplest form, is a specialised version of the MFCF, but it can be made more powerful by allowing the use of specialised planarity invariant operators that are not based on the Clique Expansion operator. We provide applications to two well known applied problems: the Maximum Weight Planar Subgraph Problem (MWPSP) and the Covariance Selection problem. With regards to the Covariance Selection problem we compare our results to the state of the art solution (the Graphical Lasso) and we highlight the benefits of our methodology. Finally, we study the geometry of clique trees as simplicial complexes and note how the statistics based on cliques and separators provides information equivalent to the one that can be achieved by means of homological methods, such as the analysis of Betti numbers, however with our approach being computationally more efficient and intuitively simpler. Finally, we use the geometric tools developed to provide a possible methodology for inferring the size of a dataset generated by a factor model. As an example we show that our tools provide a solution for inferring the size of a dataset generated by a factor model.

Two fundamental goals in programming are correctness and efficiency: we want our programs to produce the right results, and to do so using as few resources as possible. One of the key benefits of the functional programming paradigm is the ability to reason about programs as if they are pure mathematical functions. In particular, programs can often be proved correct with respect to a specification by exploiting simple algebraic properties akin to secondary school mathematics. On the other hand, program efficiency is not immediately amenable to such algebraic methods used to explore program correctness. This insight manifests as a reasoning gap between program correctness and efficiency, and is a foundational problem in computer science. Furthermore, it is especially pronounced in lazy functional programming languages such as Haskell, where the on-demand nature of evaluation makes reasoning about efficiency even more challenging. To aid Haskell programmers in their reasoning about program efficiency, the work in this thesis seeks to partially bridge the reasoning gap using three different approaches: automated testing, semi-formal verification, and formal verification.

This thesis presents a variety of models for probabilistic programming languages in the framework of concurrent games. Our starting point is the model of concurrent games with symmetry of Castellan, Clairambault and Winskel. We show that they form a symmetric monoidal closed bicategory, and that this can be turned into a cartesian closed bicategory using a linear exponential pseudo-comonad inspired by linear logic. Then, we enrich this with probability, relying heavily on Winskel's model of probabilistic concurrent strategies. We see that the bicategorical structure is not perturbed by the addition of probability. We apply this model to two probabilistic languages: a probabilistic untyped λ-calculus, and Probabilistic PCF. For the former, we relate the semantics to the probabilistic Nakajima trees of Leventis, thus obtaining a characterisation of observational equivalence for programs in terms of strategies. For the latter, we show a definability result in the spirit of the game semantics tradition. This solves an open problem, as it is notoriously difficult to model Probabilistic PCF with sequential game semantics. Finally, we introduce a model for measurable game semantics, in which games and strategies come equipped with measure-theoretic structure allowing for an accurate description of computation with continuous data types. The objective of this model is to support computation with arbitrary probability measures on the reals. In the last part of this thesis we see how this can be done by equipping strategies with parametrised families of probability measures (also known as stochastic kernels), and we construct a bicategory of measurable concurrent games and probabilistic measurable strategies.

Self-organisation is recognised as one of the fundamental principles of Agile software development since the introduction of the Agile Manifesto. In large-scale agile, self- organising teams must cooperate to produce a software product jointly. Previous research has identified barriers to self-organising autonomous teams in large-scale agile, such as lack of guidelines for how teams should be organised, and other challenges related to building autonomous teams and aligning them. The Spotify model is an example of a very large-scale agile approach, which is driven by creating loosely coupled, yet tightly aligned squads. However, there is a conflicting trade-off between squads autonomy and alignment. Too much alignment might hinder squad autonomy, but without alignment, the squads are autonomous but are not effective. This research aims to (1) explore how Agile practitioners, from a FinTech organisation, resolve the conflicting trade-offs between squads autonomy and alignment, and (2) develop and evaluate new architectural governance practices, in a FinTech organisation tailoring the Spotify model. To address these aims, a qualitative research design was utilised. This research comprises two parts, a longitudinal embedded case study and an intervention embedded case study, which were conducted in a FinTech organisation (i.e., FinTechOrg). The longitudinal embedded case study lasted over 21 months, during which 225 ceremonies were observed, 14 semi-structured open-ended interviews were conducted, and data were collected from different sorts of artefacts. The collected data were analysed using an approach informed by the Grounded Theory method. The analysis identified influential factors on different aspects of Spotify Tailoring, which contribute to resolving the conflicting trade-offs between squads autonomy and alignment. These aspects are (1) establishing and building autonomous squads, (2) aligning autonomous squads, and (3) performing B2B product development by tailoring the Spotify model. The first contribution is identifying factors influencing establishing and building autonomous squads. The second contribution is identifying factors influencing aligning autonomous squads. The third contribution is identifying the impact of product development on Spotify tailoring as well as factors influencing Spotify Tailoring for B2B product development. Each identified factor is supported by a set of practices and attributes, which can aid Agile practitioners in improving squad autonomy, aligning autonomous squads, or facilitating the conduct of B2B product development. The fourth contribution is identifying a novel approach to Agile tailoring, called Heterogeneous Tailoring. Three key features characterise this approach. Firstly, each autonomous squad is empowered to select and tailor its development method. Secondly, each squad is aligned with other squads and to common product development goals and objectives. Thirdly, the product steering committee draws the strategy of squads’ missions and aligns the product backlog among autonomous squads. This novel approach to Agile tailoring has improved the creativity for some squads and increased the productivity for others, as reported by the practitioners of FinTechOrg. The Spotify model and the revealed Heterogeneous Tailoring approach do not provide practices or guidelines for governing Agile architecture across autonomous squads. Thus, an embedded case study intervention was conducted to contribute to facilitating Agile architecture governance. In this intervention, a novel approach to architectural governance was developed and evaluated in FinTechOrg, which is considered the last contribution. This approach incorporates a structural change and an architecture change management process. The intervention lasted 3 months, during which 32 ceremonies were observed and 8 semi-structured open-ended interviews were conducted. The collected data was analysed using an approach informed by the Grounded Theory method. Based on the results of the intervention, the Heterogeneous Tailoring approach was adapted to accommodate the novel approach to architectural governance. This adaptation has impacted the key features of the Heterogeneous Tailoring approach. Establishing autonomous squads was impacted by the introduced structural change. The alignment of autonomous squads was impacted by governing Agile architecture. Product development was impacted by the needs for planning architecture based user stories. Also, the adaptation of the Heterogeneous Tailoring approach revealed a new key feature, called Release Strategy, which is concerned with the continuous delivery of architecture enablers.

The Behaviour Driven Development (BDD) technique enables teams to specify software requirements as example interactions with the system. Due to the use of natural language, these examples (usually referred to as scenarios) can be understood by most project stakeholders, even end users. The set of examples also acts as tests that can be executed to check the behaviour of the System Under Test (SUT). Despite BDD's benefits, large suites of examples can be hard to comprehend, extend and maintain. Duplication can creep in, leading to bloated specifications, which sometimes cause teams to drop the BDD technique. Current tools for detecting and removing duplication in code are not effective for BDD examples. Moreover, human concerns of readability and clarity can rise. Previous attempts to detect and remove duplication in BDD specifications have focused on textually similar duplicates, not on textually different scenarios that specify the same behaviour of the SUT. To fill this gap, this thesis does the following. First, we surveyed 75 BDD practitioners from 26 countries to understand the extent of BDD use, its benefits and challenges, and specifically the challenges of maintaining BDD specifications in practice. We found that BDD is in active use amongst respondents; and the use of domain specific terms, improving communication among stakeholders, the executable nature of BDD specifications, and facilitating comprehension of code intentions emerged as some of the main benefits of BDD. The results also showed that BDD specifications suffer the same maintenance challenges found in automated test suites more generally. We map the survey results to the literature, and propose 10 research opportunities in this area. Second, we propose and evaluate a framework for detecting duplicate scenarios based on the comparison of characteristics extracted from scenario execution traces. We focus on the patterns of production code exercised by each scenario, and consider two scenarios to be duplicates if they execute the same functionality in the SUT. In an empirical evaluation of our framework on 3 open source systems, the comparison of execution paths of scenarios recorded more recall and precision than the comparison of full execution traces, public API calls, or a combination of public API calls and internal calls. Also, the focus on essential characteristics in the execution traces of scenarios improved the recall and precision of the duplicate detection tool. Third, we propose four principles describing BDD suite quality that can be used to assess which of a pair of duplicate scenarios can be most effectively removed. All of the four principles were accepted by at least 75% of the practitioners we surveyed. An empirical evaluation of the four principles on 3 open source systems shows that each principle gave acceptable remove suggestions, and thus the principles can be used to guide human engineers in removing duplicate scenarios from BDD specifications.

As software testing is a laborious and error-prone task, automation is desirable. Search-based unit test generation applies evolutionary search algorithms to generate software tests and, in the context of unit testing object-oriented software, Genetic Algorithms (GAs) are frequently employed to generate unit tests that maximise code coverage. Although GAs are effective at generating tests that achieve high code coverage, they are still far from being able to satisfy all test goals (e.g., covering all branches). While some general limitations are known, there is still a lack of understanding of the search behaviour during the optimization, making it difficult to identify the factors that make a search problem difficult. Therefore, this thesis aims to investigate the search behaviour when GAs are applied to generate object-oriented unit tests and, more specifically, identify the reasons why the search fails to achieve the desired test goals. This is achieved by investigating (1) the fitness landscape structure and the impact of its features on the generation of unit tests and (2) the influence of population diversity on generating potential unit tests. Based on the outcome of this investigation, the impact of test case reduction on the landscape features and population diversity is also investigated. Our results reveal that classical indicators for rugged fitness landscapes suggest well searchable problems in the case of unit test generation, but the fitness landscape for most problem instances is dominated by detrimental plateaus. However, increasing diversity does not have a beneficial effect on coverage in general, but it may improve coverage when diversity is promoted adaptively. In fact, increasing diversity has a negative impact on the individual length, which can also be mitigated with the adaptive diversity. Applying the test case reduction seems to be promising in improving the landscape structure and reducing the negative side effects of diversity on length, but have no considerable impact on the search performance.

The engineering process of complex systems involves many stakeholders and development artefacts. Model-Driven Engineering (MDE) is an approach to development which aims to help curtail and better manage this complexity by raising the level of abstraction. In MDE, models are first-class artefacts in the development process. Such models can be used to describe artefacts of arbitrary complexity at various levels of abstraction according to the requirements of their prospective stakeholders. These models come in various sizes and formats and can be thought of more broadly as structured data. Since models are the primary artefacts in MDE, and the goal is to enhance the efficiency of the development process, powerful tools are required to work with such models at an appropriate level of abstraction. Model management tasks – such as querying, validation, comparison, transformation and text generation – are often performed using dedicated languages, with declarative constructs used to improve expressiveness. Despite their semantically constrained nature, the execution engines of these languages rarely capitalize on the optimization opportunities afforded to them. Therefore, working with very large models often leads to poor performance when using MDE tools compared to general-purpose programming languages, which has a detrimental effect on productivity. Given the stagnant single-threaded performance of modern CPUs along with the ubiquity of distributed computing, parallelization of these model management program is a necessity to address some of the scalability concerns surrounding MDE. This thesis demonstrates efficient parallel and distributed execution algorithms for model validation, querying and text generation and evaluates their effectiveness. By fully utilizing the CPUs on 26 hexa-core systems, we were able to improve performance of a complex model validation language by 122x compared to its existing sequential implementation. Up to 11x speedup was achieved with 16 cores for model query and model-to-text transformation tasks.

Concurrent Kleene Algebra (CKA) offers a set of axioms to reason about equivalence of concurrent programs, such that equivalent programs must have the same interpretation in any program semantics that respects the axioms of CKA. It builds on the well-known formalism of Kleene Algebra, which offers the same benefits for sequential programs. CKA is complete, that is, any valid equivalence can be proved from the axioms. Moreover, equivalence of programs according to CKA can be verified mechanically, i.e., equivalence is decidable. Crucial to the latter is the fact that programs can be represented as abstract machines, which admit equivalence checking. In this thesis, we investigate techniques to augment the reasoning power of CKA with additional truths particular to the program semantics at hand. Building on similar results about Kleene Algebra, we will show that for a large class of extensions, decidability and completeness can be recovered. In particular, our techniques will allow us to incorporate reasoning about interleaving, i.e., the partially sequential execution of concurrent programs, as well as control flow, such as the conditional branching and looping structures found in most programming languages. In the second half of this thesis, we will develop our own abstract machine model to represent programs modelled by Concurrent Kleene Algebra, and show that any such program can be modelled by a machine, and vice versa. We will then argue that equivalence of these automata is mechanisable, and that the correspondence between expressions and automata can be extended further to incorporate a more general form of concurrent program composition.

Monads are a central object of category theory and constitute crucial tools for many areas of Computer Science, from semantics of computation to functional programming. An important aspect of monads is their correspondence with algebraic theories (their ‘presentation’). As demonstrated by the history of this field, composing monads is a challenging task: the literature contains numerous mistakes and features no general method. One categorical construct, named ‘distributive law’ allows this composition, but its existence is not guaranteed. This thesis addresses the question of monad composition by presenting a method for the construction of distributive laws. For this purpose, we introduce a notion of preservation of algebraic features: considering an arbitrary algebra for the theory presenting a monad S, we examine whether its structure is preserved when applying another monad T . In the case of success, it allows us to construct a distributive law and to compose our monads into T S. In order to develop a general framework, we focus on the class of monoidal monads. If T is monoidal, the algebraic operations presenting S are preserved in a canonical fashion; it remains to examine whether the equations presenting S are also preserved by T . As it turns out, the preservation of an equation depends on the layout of its variables: if each variable appears once on each side, the considered equation is automatically preserved by a monoidal monad. On the other hand, if a variable is duplicated or only appears on one side, preservation is not systematic. The main results of this thesis connect the preservation of such equations with structural properties of monads. In the case where T does not preserve an equation presenting S, our distributive law cannot be built; we provide a series of methods to slightly modify our monads and overcome this issue, and we investigate some less conventional distributive laws. Finally, we consider the presentations of both S and T and revisit our construction of distributive laws, this time with an algebraic point of view. Overall, this thesis presents a general approach to the problem of monad composition by relating categorical properties of monads with preservation of algebras.

Search-Based Software Testing (SBST) methods are popular for improving the reliability of software. They do, however, suffer from challenges: poor representation, ineffective fitness functions and search landscapes, and restricted testing strategies. Neural Networks (NN) are a machine learning technique that can process complex data, they are continuous by design, and they can be used in a generative capacity. This thesis explores a number of approaches that leverage these properties to tackle the challenges of SBST. The first use case is for defining fitness functions to target specific properties of interest. This is showcased by first training an NN to classify an execution trace as crashing or non-crashing. The estimate is then used to prioritise previously unseen executions that are deemed more likely to crash by the NN. This fitness function yields more efficient crash discovery than a baseline. The second proposition is to use NNs to define a search space for a diversity driven testing strategy. The space is constructed by encoding execution traces into an n-dimensions, where distance represents the degree of feature similarity. This thesis argues that this notion of similarity can drive a diversification driven testing strategy. Finally, an application of a generative model for SBST is presented. Initially, random inputs are fed to the program and execution traces are collected and encoded. Redundant executions are culled, distinct ones are kept and the loop is repeated. Over time, this mechanism discovers new program behaviours and these are added to the ever more diverse training dataset. Although this approach does not yet compete with existing tools, experiments show that the notion of similarity is meaningful, the generated program inputs are sensible and faults are found. Much of the work presented in this thesis is exploratory and is meant to serve as basis for future research.

There is a plethora of software development practices. Practice adoption by a development team is a challenge by itself. This makes software process improvement very hard for organisations. I believe a key factor in successful practice adoption is proper incentives. Wrong incentives can lead a process improvement effort to failure. I propose to address this problem using game-theory. Game theory studies cooperation and conflict. I believe its use can speed the development of effective software processes. I surveyed game-theory applications to software engineering problems, showing the potential of this technique. By using game-theoretic models of software development practices, we can verify if the behaviour at equilibrium converges towards team cooperation. Modern software development is performed by large teams, working multiple iterations over long periods of time. Classic game representations do not scale well to model such scenarios, so abstraction is needed. In this thesis, I propose GTPI (game-theoretic process improvement), a software process improvement approach based on empirical game-theoretic analysis (EGTA) abstractions. EGTA enables the production of software process models of manageable size . I use GTPI to address technical debt, modelling developers that prefer quick and cheap solutions instead of high-quality time-consuming fixes. I have also approached bug prioritisation with GTPI, proposing the assessor-throttling prioritisation process, and developing a tool to support its adoption.

In this thesis, we present efficient techniques for satisfiability modulo theories-based model checking (SMT-based MC) of software where the model is too large or complicated to analyse; real-world software once represented as a mathematical model faces the danger of the state-explosion problem where the size of the model grows exponentially, thus analysing the whole model becomes a challenge. The SMT reasoning framework is one of the most successful approaches nowadays to deal with the state explosion problem when commonly combining additional techniques like symbolic algorithms, bounded model checking (BSMC), incremental modelling and reasoning, abstraction and counterexample-guided abstraction refinement (CEGAR). These approaches construct a model of the software with its specifications as a first-order formula while expressing domain-specific knowledge with first-order theories, thus creating smaller and simple models than with propositional logic modelling. The simplicity of the models improves the performance of the verification process and allows for reusing the model analysis for other tasks. However, finding a model that is sufficiently high-level to prevent reasoning from becoming prohibitively expensive but expressive enough to capture the software behaviour required for correctness, is a non-trivial task. We describe novel SMT-based MC approaches in which a model of a software system is automatically analysed using these techniques to verify if the model satisfies its specifications or to find a real counterexample. The verification process is incremental through SMT summaries based on the structure of the program. The summaries are either Craig interpolants of previous successful verification tasks or user-defined. To avoid spurious counterexamples, each of the approaches introduces a refinement technique that deals with the over-approximative nature of modelling software in SMT framework. The LB-CEGAR algorithm uses lattices for efficient representation of library functions and gradual refinement of this representation; the CEGAR-based theory refinement algorithm uses the partial order according to precision between SMT theories to gradually refine program statements required for proving correctness; and the function summarization modulo theories algorithm uses summaries between different theories when verifying a software with many requirements. We evaluate our approaches on benchmarks in C taken from SV-COMP (software verification competition), the robotics community, unimib (the University of Milano-Bicocca benchmarks), FunFrog tool benchmarks (the University of Lugano benchmarks), and our own. Our experimental results demonstrate that we can verify instances that existing model checking approaches failed to verify.

In this thesis, we present new algorithmic and complexity results for specific matching problems involving preferences. In particular we study the Stable Marriage problem (SM) and the Student-Project Allocation problem (SPA) and their variants. A matching in these scenarios is an allocation of men to women (SM) or students to projects (SPA). Primarily we are interested in finding matchings that are stable. A stable matching is a matching that admits no blocking pair, which is a pair of agents (not already allocated together) who would rather deviate from the given matching and become assigned to each other. In addition to stability, other objectives may be applied. We focus on finding either fair or large stable matchings in SM and SPA. In the Stable Marriage problem with Incomplete lists (SMI), the rank of a matched man or woman, with respect to a matching, is the position of their assigned partner on their preference list. The degree of the set of men in a matching is the rank of a worst-off man, over all matched men. A similar definition exists for the set of women. The cost of the set of men in a matching is sum of ranks of all matched men. Again a similar definition exists for the set of women. We introduce the following degree-based definitions of fairness in SMI. A stable matching is regret-equal if it minimises the difference in degree between the set of men and the set of women, over all stable matchings. Additionally, a stable matching is min-regret sum if it minimises the sum of the degree of men and the degree of women, over all stable matchings. We present polynomial-time algorithms to find these types of fair stable matchings, given an instance of SMI, and perform experiments to both test the performance of two algorithms to find a regret-equal stable matching, and to compare properties of several other types of fair stable matchings over both degree- and cost-based measures. Also in SMI, we investigate fairness in the form of profile-based stable matchings. The profile of a matching is a vector of integers, where the ith vector element indicates the number of agents assigned to their ith-choice partner. A stable matching is rank-maximal if its profile is lexicographically maximum taken over all stable matchings. A stable matching is generous if its reverse profile is lexicographically minimum taken over all stable matchings. A polynomial-time algorithm exists to find a rank-maximal stable matching, using weights that are exponential in the number of men or women [32]. We adapt this algorithm to work with polynomially-bounded weight vectors, and show using randomly-generated instances that our approach is significantly less costly in terms of space. Further experiments are carried out to compare these profile-based optimal matchings over several cost- and profile-based fairness properties. We additionally show that in the Stable Roommates problem, each of the problems of finding a rank-maximal stable matching or a generous stable matching is NP-hard. In the Student-Project Allocation problem with lecturer preferences over Students including Ties (SPA-ST) we study the problem of finding large stable matchings. A 3/2-approximation algorithm exists to find a maximum-sized stable matching in HRT, and we extend this to the SPA-ST case, developing a linear-time 3/2-approximation algorithm for the problem of finding a maximum-sized stable matching in SPA-ST. We test the performance of our approximation algorithm using the implementation of a new Integer Programming (IP) model that finds a maximum-sized stable matching, and show that in practice, our approximation algorithm produces stable matchings of size far closer to optimal than the 3/2 bound. Additionally, we give an example to show that this bound is tight. Finally, we look at fairness in the context of the Student-Project Allocation problem with lecturer preferences over Students including Ties and Lecturer targets (SPA-STL), an extension to SPA-ST in which each lecturer has an associated target, indicating their preferred number of allocations (or the number of allocations preferred by the matching scheme administrator). We first investigate load balancing without the presence of stability. A load-max-balanced matching is a matching in which the maximum difference between a lecturer’s target and their number of allocations is minimised. A load-sum-balanced matching is a matching in which the sum of differences between all lecturers’ targets and their number of allocations is minimised. Finally, a load-balanced matching is a matching that is both load-max-balanced and load-sum-balanced. We provide new polynomial-time algorithms to find matchings of these types. Additionally we show that in the presence of stability, each of the problems of finding a stable matching that is load-max-balanced, load-sum-balanced or load-balanced is NP-hard. Finally, we present new IP models for finding such types of optimal stable matching.

This thesis investigates the use of pure functional programming in Agent-Based Simulation (ABS) with the language Haskell. The central theme of this thesis is to do with purity, which identifies the lack of unrestricted side effects and referential transparency. Thematically, the research presented in this thesis is split into two parts. The first part deals with the approach to a pure functional ABS implementation and the second part with exploring benefits enabled through pure functional programming. First, the thesis explores how to implement ABS in a pure functional way, discussing both a time and event-driven approach. In each case Arrowized Functional Reactive Programming is used to derive fundamental abstractions and concepts. As use cases the well known agent-based SIR and the Sugarscape models are used. Additionally, the thesis focuses on why it is beneficial to implement ABS in a pure functional way. For this research topic, we explore both robust parallel and concurrent programming, where the main focus is on how to speed up the simulation while keeping it as pure as possible. In the parallel part, we rely on built-in language features and are able to speed the simulation up while retaining purity. In the concurrency part, Software Transactional Memory is used, sacrificing purity but still retaining certain guarantees about reproducibility. Finally, the thesis explores automated code testing of ABS implementations using property-based testing to show how to encode agent specifications and model invariants and perform model verification and hypothesis testing. The contribution of this thesis is threefold: 1. Development of pure functional implementation techniques for ABS through the use of Arrowized Functional Reactive Programming. 2. Development of techniques using Software Transactional Memory to implement robust concurrent ABS. 3. Development of a new testing approach to ABS using randomised propertybased testing for declarative and stochastic code testing. The results of the respective contributions support the view that pure functional programming indeed has its place in ABS. First, a pure functional approach leads to implementations which are more likely to be valid due to the focus on purity by avoiding computations with unrestricted side effects. Secondly, pure parallel computation and Software Transactional Memory (lockfree) based concurrency make it possible to gain substantial speedup, with the latter one dramatically outperforming traditional lock-based approaches. While pure parallel computation fully retains static guarantees, Software Transactional Memory is not pure, but is still able to retain certain guarantees regarding reproducibility. Finally, property-based testing is shown to be extremely useful, as it naturally maps to the stochastic nature of ABS and is therefore suitable to be integrated into the development process as an additional tool for testing specifications and hypotheses.

With the growth of globalisation and significant developments in science and technology, software development today requires the capability to deal with fast-paced changes, increased competition and higher customer expectations. In light of this, many organisations have moved away from traditional approaches to software development, preferring instead to adopt lightweight, iterative approaches commonly termed ‘agile methodologies'. Despite the popularity of agile practices and principles, adoption rates and success in using them vary. Few academic studies exist examining how agile practices and principles are adopted in practice, or why there is such variation in their use. This study addresses this gap by drawing on transformational-transactional leadership theory to understand how agile practices and principles are adopted, and what factors influence this adoption. It also draws on existing research highlighting a distinction between cognitive and behavioural change and applies this to agile adoption. A qualitative approach with an interpretive perspective was taken for this research, adopting a case study research method. A single case, SoftwareCorps, was chosen with data collected over three and a half years, predominantly through participant observation and two phases of semi-structured interviews. Overall, 29 individuals participated in 47 interviews. This study was undertaken in two phases. In the first phase, the journey of agile adoption at SoftwareCorps was explored, and factors that influenced agile adoption attempts considered. In the second phase, the focus was narrowed to explore how leadership influenced the adoption of agile practices and principles. A model of leadership for agile adoption was subsequently developed, combining leadership theory and insights from the empirical data in this study. Findings from phase one demonstrated that effective and open communication, coaching, understanding the existing system of working, removal of barriers, sponsorship and buy-in, piloting with volunteers, selection of Scrum, and leadership were all influential factors in the adoption of agile at SoftwareCorps. However, leadership was found to be the most dominant theme. Additionally, data analysis in phase one revealed a distinction between behavioural and cognitive changes required for the adoption of agile practices. Findings from phase two revealed that a leader's interpretation of agile and style of leadership shaped the type of change (i.e. behavioural or cognitive change) driven in software development teams at SoftwareCorps. A transformational leadership style, combined with an interpretation of agile as an approach to problem solving and a drive to create cognitive change, was found to be conducive to successful agile adoption. A transactional leadership style with an interpretation of agile as a process and a focus exclusively on behavioural change was inhibiting to agile adoption. The findings of this study suggest that successful agile adoption requires software development teams to be supported by individuals whose leadership style compliments agile values and principles (such as empowering, communicating and collaborating). Additionally, successful agile adoption is facilitated by leaders whose interpretation of agile is as an approach to problem-solving, rather than merely a set of procedures for developing software. This study contributes towards a greater understanding of factors influential to the adoption of agile practices and principles and provides a model to explain how leadership may influence agile adoption. In so doing, this study helps to explain why variation in agile adoption levels may occur.

Starting with a Fully Abstract denotational semantics for an Algol-like programming language, we investigate how we can use techniques of categorical algebra to adapt the semantics when the original language is extended with various nondeterministic effects. Our running example for the base denotational semantics is Abramsky and McCusker’s game semantics for Idealized Algol. We give a full presentation of this game semantics, including an alternative proof of Computational Adequacy that uses Laird’s concept of a sequoidal category rather than the combinatorial proof from Abramsky and McCusker’s original paper. We introduce the familiar concepts of monads and Kleisli categories, and prove a Full Abstraction result that shows how the process of passing to certain Kleisli categories corresponds to particular language extensions. We link these language extensions to may-and must-testing for finite and countable nondeterminism, showing how we can construct Fully Abstract models of these effects using Kleisli categories. We introduce a generalization of monads: lax actions, also known as parametric monads. We investigate various corresponding generalizations of Kleisli categories, and prove a Full Abstraction result for one such generalization, showing how it too can be used to construct a model of an extended version of our original Algol-like language. We show how a special case of this construction can be adapted to model a probabilistic language.

Modern Integrated Circuits (ICs) based system design have evolved over time to support the ever demanding complex use-cases. As more functionality is packed into these ICs, there are more deeply embedded components present in these ICs. The performance of these deeply embedded components are critical in ensuring the final system behaviour. By virtue of being deeply embedded they are intrinsically difficult to test - especially in system context. This thesis is focused on the task of 'stress testing' an IC in its operational environment with the goal of identifying any circumstances under which the circuit might suffer from performance issues. It addresses how search-based algorithms provide an automated approach in testing these ICs. Here it establishes that with a suitable search-space representation search-based approaches can be applied in stress-testing of complex ICs. Here it outlines how a simple hill-climbing based search algorithm is successfully used to generate tests in an automated manner. It also studies the application of more advanced search-based algorithms like random-restart hill-climbing and simulated annealing in addressing this testing challenge. As system behaviour of complex ICs can be affected in multiple ways, this research investigates the application of multiobjective algorithms in this context. It shows that a multi-objective algorithm like Strength Pareto Evolutionary Algorithm 2 (SPEA2) is able to generate better stress tests, maximising multiple objectives. The empirical studies performed as part of this thesis are conducted on ArmR Cache Coherent Interconnect (CCI), which provides cache coherency and interconnect functionality on modern Arm based systems. It concludes that search-based software testing approaches are indeed suitable for addressing testability challenges posed by modern ICs especially at system level and provide ways to generate better stress tests.

Enterprise data integration is the process of combining data from multiple sources to fulfil business and market needs. Traditional approaches such as shared databases and messaging-oriented systems fall short of new challenges to keep pace with the evolution of big data in changing markets. Such challenges can be observed at two levels. First, during integration design we need to establish a concise, visual and loosely-coupled mapping to support data integration without disturbing internal business process and applications. Second, at the execution level we need to support efficient bidirectional transformations and synchronisations to respond to evolving requirements in a cost-effective manner. Graph databases such as neo4j are designed to handle and integrate big data from heterogeneous sources using efficient navigation based query languages such as Gremlin. For flexibility and performance, they do not ensure data quality through schemata but leave it to the application level. They are built on top of a rich data model that can be utilised to realise the interconnectedness of real-world data domains. On the other hand, model-driven design and implementation techniques have been widely adopted to build systems at a high level of abstraction. They exploit visual relational models such as the Unified Modelling Language (UML) to describe systems at various stages of development and allow to automatically generate application logic. In this thesis, we present a model-driven approach to bidirectional transformations and synchronisations between relational sources in neo4j. We describe data sharing between relational sources using declarative Triple Graph Grammars (TGGs), then compile them into query and update operations in Gremlin to execute controlled transformations and synchronisations in neo4j using a Model-To-Text (M2T) transformation approach. To ensure the validity and the efficiency of our approach, we evaluate the correctness and the performance of generated Gremlin queries using well-known bidirectional transformations testing suites. The results show that our approach is valid and efficient to support enterprise data sharing and synchronisations. The approach combines the data quality of schema-based solutions while utilising the performance of Gremlin queries on neo4j to perform loosely coupled incremental data transformations for data driven applications.

Motivated by experience in programming and in the teaching of programming, we make another assault on the longstanding problem of debugging. Having explored why debuggers are not used as widely as one might expect, especially in functional programming environments, we define the characteristics of a debugger which make it usable and thus likely to be widely used. We present work on a new debugger for the functional programming language OCaml which operates by direct interpretation of the program source, allowing the printing out of individual steps of the program's evaluation, and discuss its technical implementation and practical use. It has two parts: a stand-alone debugger which can run OCaml programs by interpretation and so allow their behaviour to be inspected; and an OCaml syntax extension, which allows the part of a program under scrutiny to be interpreted in the same fashion as the stand-alone debugger whilst the rest of the program runs natively. We show how this latter mechanism can create a source-level debugging system that has the characteristics of a usable debugger and so may eventually be expected to be suitable for widespread adoption.

Software product line engineering (SPLE) is a paradigm for developing a family of software products from the same reusable assets rather than developing individual products from scratch. In many SPLE approaches, a feature is often used as the key abstraction to distinguish between the members of the product family. Thus, the sets of products in the product line are said to have ’common’ features and differ in ’variable’ features. Consequently, reusable assets are developed with variation points where variant features may be bound for each of the diverse products. Emerging deployment environments and market segments have been fuelling demands for adaptable reusable assets to support additional variations that may be required to increase the usage-context of the products of a product line. Similarly, feature binding time - when a feature is included in a product and made available for use - may vary between the products because of uncertain market conditions or diverse deployment environments. Hence, variations of feature binding time should also be supported to cover the wide-range of usage-contexts. Through the execution of action research, this thesis has established the following: Language-based implementation techniques, that are specifically proposed to implement variations in the form of features, have better modularity but are not better than the existing classical technique in terms of modifiability and do not support variations in feature binding time. Similarly, through a systematic literature review, this thesis has established the following: The different engineering approaches that are proposed to support variations of feature binding time are limited in one of the following ways: a feature may have to be represented/implemented multiple time, each for a specific binding time; The support is only to execution context and therefore limited in scope; The support focuses on too fine-grained model elements or too low-level of abstraction at source-codes. Given the limitations of the existing approaches, this thesis presents binding time aware modelling language that supports variations of feature binding time by design and improves the modifiability of reusable assets of a product line.

The requirements and responsibilities assumed by software have increasingly rendered it to be large and complex. Testing to ensure that software meets all its requirements and is free from failures is a difficult and time-consuming task that necessitates the use of large test suites, containing many test cases. Time needed to compile and execute large test suites has become prohibitive. Current optimization techniques aim to reduce the test suite size by removing redundant test cases. However, as systems become larger, the number of essential test cases is still very large and affects the software life-cycle. In this thesis, we explore techniques for reducing the compilation and the execution time of test suites without removing any test cases or changing computing infrastructure. All of our proposed techniques can be used in conjunction with existing test suite optimisations. 1. For test suite compilation, we propose a data transformation that reduces the number of instructions in the test code, which in turn reduces compilation time. Using two well known compilers, GCC and Clang, we conduct empirical evaluations using subject programs from industry standard benchmarks and an industry provided program. We evaluate compilation speedup, execution time, scalability and correctness of the proposed test code transformation. 2. For test suite execution, we propose a novel approach to improve instruction locality across test case executions. Our approach measures the distance between test case executions (number of different instructions). We then schedule the test cases for execution so that the distance between neighboring test cases is minimised. We empirically evaluate our approach with 20 subject programs and test suites from the SIR repository, EEMBC suite and LLVM Symbolizer to compare execution times and cache misses with test case orderings using our approach versus a traditional ordering maximising coverage and random permutations. We also assess overhead of algorithms in generating orderings that optimise instruction cache locality. 3. In our final contribution, we target execution time of heterogeneous test suites and assess the effect of device-based test case scheduling. We propose a test case scheduling algorithm which improves the load balancing between multiple devices of a heterogeneous system in an attempt to reduce the overall test suite execution time. We conduct empirical evaluation on a large-scaled, industrial test suite targeting implementations of the SYCL standard which has been developed by Codeplay Software. The outcome of our research can be summarized as follows: 1. Our data transformation approach resulted in significant compilation speedups in the range of 1.3×to 69×. Our experiments show that the gains in compilation time allow significantly more test cases to be included in test suites, improving scalability of test code compilation. 2. Our instruction-based test case scheduling algorithms were able to achieve a maximum execution speedup of 29.48%. Performance gains were considerable for programs and test suites where the average number of different instructions executed between test cases was high. 3. Finally, we found that a maximum of 25.42% speed-up is achieved by our device based test scheduling algorithm when compared to parallel test case execution of a heterogeneous test suite without test scheduling. Our proposed techniques are able to significantly reduce the compilation as well as the execution time of test suites without eliminating any test cases or upgrading computing infrastructure. Our data transformation results in faster test code compilation while our test case scheduling algorithms achieve significant speed-ups for programs executing on single-CPU, multi-CPU as well as heterogeneous architectures. As systems get more complex, they require frequent and extensive testing. Our techniques provide safe and efficient means of compiling and executing test suites which, in combination with existing test suite optimisations, can significantly reduce the cost of software testing.

Session types are a well-established approach to ensuring protocol conformance and the absence of communication errors such as deadlocks in message passing systems. Implicit parameters, introduced by Haskell and popularised in Scala, are a mechanism to improve program readability and conciseness by allowing the programmer to omit function call arguments, and have the compiler insert them in a principled manner at compile-time. Scala recently gave implicit types first-class status (implicit functions), yielding an expressive tool for handling context dependency in a type-safe manner. DOT (Dependent Object Types) is an object calculus with path-dependent types and abstract type members, developed to serve as a theoretical foundation for the Scala programming language. As yet, DOT does not model all of Scala's features, but a small subset. Among those features of Scala not yet modelled by DOT are implicit functions. We ask: can type-safe implicit functions be generalised from Scala's sequential setting to message passing computation, to improve readability and conciseness of message passing programs? We answer this question in the affirmative by generalising the concept of an implicit function to an implicit message, its concurrent analogue, a programming language construct for session-typed concurrent computation. We explore new applications for implicit program constructs by integrating theminto four novel calculi, each demonstrating a new use case or theoretical result for implicits. Firstly, we integrate implicit functions and messages into the concurrent functional language LAST, Gay and Vasconcelos's calculus of linear types for asynchronous sessions. We demonstrate their utility by example, and explore use cases for both implicit functions and implicit messages. We integrate implicit messages into two pi calculi, further demonstrating the robustness of our approach to extending calculi with implicits. We show that implicit messages are possible in the absence of lambda calculus, in languages with concurrency primitives only, and that they are sound not only in binary session-typed computation, but also in multi-party context. Finally we extend DOT to include implicit functions. We show type safety of the resulting calculus by translation to DOT, lending a higher degree of confidence to the correctness of implicit functions in Scala. We demonstrate that typical use cases for implicit functions in Scala are typably expressible in DOT when extended with implicit functions.

In the online k-server problem, an algorithm controls k mobile servers in a metric space. One by one, requests arrive at points of the space, and the algorithm must serve each request by selecting a server to visit it. The goal is to minimize the total distance traveled by all servers. In the framework of competitive analysis, we study two variants of the k-server problem, the infinite server problem and the k-taxi problem, and the more general metrical task systems problem. The infinite server problem is the variant of the k-server problem where the number of servers is infinite, initially all starting at the same point. We obtain a surprisingly tight connection between the infinite server problem and the resource augmentation version of the k-server problem. Using this connection, we also improve the known lower bounds for the resource augmented k-server problem. The k-taxi problem generalizes the k-server problem in that a request consists not of one point, but two points s and t, representing the start and destination of a taxi request. To serve such a request, a server (taxi) must move first to s and then to t. This problem becomes particularly difficult when the cost is defined as the distance of empty runs only. Indeed, we show an exponential gap between the competitive ratio of the k-taxi problem and that of the k-server problem. A main positive result is an O(2k log n)-competitive algorithm for arbitrary n-point metrics. Metrical task systems are a general framework subsuming many other online problems, including the k-server problem. Here, the algorithm suffers two kinds of costs, movement and service costs. For HST metrics, using an entropy regularization approach, we obtain tight bounds on the refined guarantees, i.e., movement and service costs are simultaneously optimally competitive against the optimal total cost. This also improves the refined guarantees for general metrics.

A software product family is a cluster of related software systems that are used for similar purposes. In order to construct a software product family, product line engineering (PLE) implements the domain artefacts piece by piece, and builds an `assembly line' that is capable to assemble the artefacts for a product based on its configuration. As a result, there is no executable product to be tested before the final generation. Therefore, a product line with non-trivial size is impossible to be tested due to the everlasting problem of combinatorial explosion of variants. Our approach offers a new possibility to construct a product family by constructing a family architecture that captures and realises all the commonalities and variabilities in a feature-oriented component-based manner. As a proof of concept, we implement our approach by developing a web-based tool, which can visualise the process of family construction and automatically generate any number of family members afterwards. Moreover, in this thesis, we will present the major advantage our approach can bring, which is the support of family-based testing. Finally, we evaluate our work by comparison with existing PLE approaches to show some extra potential advantages of our approach, such as scalability, maintainability and evolvability.

In today's world parallelism is ubiquitous, and different types of parallel models and processors are becoming increasingly common. Moreover, while our programs become increasingly heterogeneous in the parallelism they employ, user-visible parallelism in our languages becomes increasingly homogeneous, with the parallelization onus put more and more on the compiler or runtime. This increasing divide between what is seen and what happens in our languages makes being able to determine the costs of running the same program on different types of hardware evermore important. And, in such a world, having the means to profile programs by their underlying semantic properties is crucial. However, while there are means of semantically profiling parallel programs written for the CPU, there are still no means to profile and reason about parallel programs that use multiple types of parallel processor based upon their underlying semantics. In this dissertation, we set out to solve this problem by presenting a cost semantic theory that allows profiling for both time and space in heterogeneous parallel programs, while also allowing higher-order constructs on the GPU. Specifically, in this dissertation we develop cost semantics for region-based heterogeneous parallel functional programming languages. We do so by developing it for a core calculus that is readily extendable to other functional programming languages. In order to develop a cost semantics for such a language, we first develop a novel cost semantics for a region-based homogeneous-parallel functional language residing on the CPU, along with a novel trace-based cost semantics for a similarly region-based homogeneous-parallel functional language residing on the GPU. We then develop and present a way to glue together these two languages that reside on different computational realms---statically, semantically, and operationally---to arrive at a region-based heterogeneous parallel language, and a cost theory that is able to profile programs written in that language. We then implement and evaluate our theory and show that it accurately reflects the real-world runtime characteristics of source programs.

Dynamic trees, originally described by Sleator and Tarjan, have been studied in detail for non persistent structures providing O(log n) time for update and lookup operations as shown in theory and practice by Werneck. However, there are two gaps in current theory. First, how the most common dynamic tree operations (link and cut) are computed over a purely functional data structure has not been studied in detail. Second, even in the imperative case, when checking whether two vertices u and v are connected (i.e. in the same component), it is taken for granted that the corresponding location indices (i.e. pointers, which are not allowed in purely functional programming) are known a priori and do not need to be computed, yet this is rarely the case in practice. In this thesis we address these omissions by formally introducing two new data structures, Full and Top, which we use to represent trees in a functionally efficient manner. Based on a primitive version of finger trees – the de facto sequence data structure for the purely lazy-evaluation programming language Haskell – they are augmented with collection (i.e. set-based) data structures in order to manage efficiently k-ary trees for the so-called linearisation case of the dynamic trees problem. Different implementations are discussed, and their performance is measured. Our results suggest that relative timings for our proposed structures perform sublinear time per operation once the forest is generated. Furthermore, Full and Top implementations show simplicity and preserve purity under a common interface.

Usability is now a well-established concept in software engineering resulting in a major shift in the design, development, and deployment of software applications. Moreover, the appreciation of usability, as an important aspect in managing the potentials risks caused by inappropriate outcomes of the interaction between systems and their users, is rapidly increasing. It is, nevertheless, critical for the developed software to be able to assist users in carrying out their intended tasks without unnecessary effort or frustration on the part of users. This is what usability evaluation strives to achieve. Better decisions relating to usability at any stage of the Software Development Life Cycle (SDLC) can be captured by taking user experience into consideration. Many methods have been developed for capturing the user perspective of software, such as questionnaires, checklists, and laboratory tests. However, due to the different, rapid and competitive development of systems, the huge variety of usability definitions and evaluation types and multiple expectations from different stakeholders, evaluating software usability has become a very challenging task. Additionally, the new expansion of the techniques applicable to the evaluation of usability in recent years caused an issue amongst software development teams with choosing the right ones under different software development project's circumstances. To many developers within software development teams, incorporating user-centred techniques for enhancing software usability remains relatively unknown, unclear, or is otherwise inaccessible, difficult or underused, especially by developers in small to medium-sized software development teams. The main hypothesis proposed by this thesis is that there exists a lack of proper managerial tools to assist developers and/or project managers within software development teams in the decision-making processes involved in the selection of appropriate usability testing tools. The focus is on particularly small- to medium-sized software development projects, where usability expertise may be more limited resulting in inappropriate implementation of usability evolution methods within software development projects. Consequently, negatively influencing the appropriate application of software usability evaluation methods and generating higher ratios of usability risks. A framework will be defined in this thesis as a solution to this problem in which a different approach to usability evaluation is proposed. It introduces a bottom-up approach to usability focusing on software projects by identifying their constraints to suggest appropriate usability evaluation techniques. The framework developed works as an enabler for bringing usability closer to software engineering by enhancing the interaction between these two disciplines particularly in small- to medium-sized software development projects. A literature review was carried out to discuss and investigate the related topics to usability definitions, usability focused software development lifecycles, usability evaluation methods (UEMs) and current techniques in selecting UEMs. Additionally, initial data to investigate the current gap between usability application in real scenarios and theories was carried out in the form of interviewing small development team members who were actively developing an application and carrying out usability evaluations. The analysis of the data contributed to designing the framework this study suggested as an approach to solving the problem. The framework then is tested and evaluated after being developed into an expert system that uses logical reasoning and fuzzy logics to produce results. However, the initial evaluation of the system suggested further implementation of risk assessment model leading to the second phase of the system development. The risk assessment model was afterwards evaluated separately. Both evaluations were conducted through incorporating several qualitative methods and analyzed thematically to ensure coherence and allow relational interpretations across the data sets gathered through different methods by recognizing common themes. Finally the thesis concludes with discussing the suggestions for future work for the tool developed and the theories of usability and its evaluations methods.

Domain-Specific Aspect Languages (DSALs) are a valuable tool for separating cross-cutting concerns, particularly within fields with endemic cross-cutting practices. Agent-Based Modelling (ABM) runtime inspection, which cuts across the core concern of model development, serves as a prime example. Despite their usefulness, DSALs face multiple adoption issues: the literature regarding their development and use is incohesive, coupling to a weave target hinders re-use, and available tooling is immature compared to Domain-Specific Languages (DSLs). We believe these issues can be aided by furthering DSL middle-out techniques for DSALs. We first define the background of what a DSAL is and how they may be used, moving onto how we can use DSL techniques to further DSALs. We develop a middle-out semantic model approach for developing domain-level DSALs with transparent aspect orientation using adaptions of DSL techniques. We have implemented the approach for model-specific DSALs for the in-house framework Animaux, and as middleware-specific DSAL for agent messages in the JADE framework, which can be specialised to models using extension DSALs. We give illustrative result cases using our implementations to provide a base of the user development costs and performance of this approach. In conclusion, we believe the adoption of these technologies aids ABM applications and encourage future work in similar fields. This thesis has given a base philosophy toward DSLs, a novel approach for the development of middle-out DSALs and illustrative cases of this approach.

A reference architecture can be defined as a generic architecture for a set of information systems that is used as a basis to a software system architecture. It provides the foundation for the design of concrete architectures in terms of architectural design guidelines and architectural elements. In addition, it can be used by many software developers and architects to design software system architectures' instances that best fit their customers' requirements. Software system architectures play an essential role in defining the achievement of software systems. Therefore, it can be derived efficiently from a well-structured reference architecture. There is a lack of a well-defined methodology that instantiates the knowledge of the reference architecture to a clear and customised software system architecture. Consequently, the instantiation process of the software system architecture from the reference architecture is a difficult task because the reference architecture includes a huge amount of knowledge. This knowledge is not organised and not structured. In addition to that, there is no standard terminology used to describe the knowledge of the reference architecture. To tackle this issue, a mixed method research approach has been adopted in this research. In order to achieve the aim and objectives of the research, a qualitative approach, utilising multiple case studies, has been adopted to collect the qualitative data, and a quantitative approach, utilising survey questionnaires, has been adopted to collect the quantitative data. This thesis aims at facilitating the instantiation process of the software system architecture from the reference architecture by using an ontology. The ontology has been used as a tool to present the artefacts of a reference architecture in an organised and structured way. General vocabularies have been defined based on understanding the domain and the literature and by using multiple case studies from the literature. These vocabularies have been utilised as a basis to construct an ontological model. The ontological model will be utilised to organise and structure the artefacts of the reference architecture. It aims at providing vocabularies to software architects and developers to reduce the misunderstanding between them. Furthermore, to enable clear communication between software architects and developers and to achieve the unique representation of concepts by avoiding redundancies. User study has been adopted to evaluate the usability of the proposed methodology in term of the simplicity of the instantiation process of the software system architecture from the reference architecture. The results achieved in the evaluation study offered an evidence that the ontological model can positively affect the development of software system architectures. In addition to that, it can reduce the development time. Based on the final evaluation results, it can be concluded that our research has been successful in introducing the proposed methodology as a new idea to reduce complexity in the development process.

Narrowing is one of the primary methods for implementing functional logic programming languages. Property-based testing is an automatic approach to assuring the correctness of software systems. In recent years, a number of systems have been developed that seek to apply the benefits of narrowing in the area of property-based testing. This thesis considers two limitations with these systems. First of all, most of the existing narrowing-based testing tools have focused on practical issues, and lack supporting theory. And secondly, these tools typically only perform well on properties that have particular forms. We address these limitations by developing an approach to narrowing that is both practical and principled, and demonstrate how this can be used to expand the range of properties that can be automatically tested using a narrowing-based approach.

Program transformations have various applications, such as in compiler optimizations. These transformations are often effect-dependent: replacing one program with another relies on some restriction on the side-effects of subprograms. For example, we cannot eliminate a dead computation that raises an exception, or a duplicated computation that prints to the screen. Effect-dependent program transformations can be described formally using effect systems, which annotate types with information about the side-effects of expressions. In this thesis, we extend previous work on effect systems and correctness of effect-dependent transformations in two related directions. First, we consider evaluation order. Effect systems for call-by-value languages are well-known, but are not sound for other evaluation orders. We describe sound and precise effect systems for various evaluation orders, including call-by-name. We also describe an effect system for Levy's call-by-push-value, and show that this subsumes those for call-by-value and call-by-name. This naturally leads us to consider effect-dependent transformations that replace one evaluation order with another. We show how to use the call-by-push-value effect system to prove the correctness of transformations that replace call-by-value with call-by-name, using an argument based on logical relations. Finally, we extend call-by-push-value to additionally capture call-by-need. We use our extension to show a classic example of a relationship between evaluation orders: if the side-effects are restricted to (at most) nontermination, then call-by-name is equivalent to call-by-need. The second direction we consider is non-invertible transformations. A program transformation is non-invertible if only one direction is correct. Such transformations arise, for example, when considering undefined behaviour, nondeterminism, or concurrency. We present a general framework for verifying noninvertible effect-dependent transformations, based on our effect system for call-by-push-value. The framework includes a non-symmetric notion of correctness for effect-dependent transformations, and a denotational semantics based on order-enriched category theory that can be used to prove correctness.

Gradual typing aims to improve the correctness of dynamically typed programs by incrementally adding type information. Sound gradual typing performs static type checking and inserts run-time checks when a type cannot be guaranteed statically. This form of gradual typing offers many features, but also requires that the programmer uses a language with a specialised gradual type system. A lightweight form of gradual typing uses contracts to enforce types at run-time, assigning blame when a type assertion fails. Contracts can be implemented as a library, without requiring a specialised gradual type system. Contracts provide a lower barrier of entry into sound gradual typing. This thesis investigates the design and evaluation of contracts for gradual typing, focusing on bridging the gap between JavaScript (dynamic) and TypeScript (static). There are two key outcomes regarding theory and practice. Contracts for higher-order intersection and union types can be designed in a uniform way, using blame to derive the semantics of contracts satisfaction. Contracts and gradual typing can be evaluated using the DefinitelyTyped repository, where JavaScript libraries are annotated with TypeScript definition files. Contract composition is the fundamental method for building complex type assertions. Intersection and union types are well suited for describing patterns common to dynamically typed programs. Our first contribution is to present a calculus of contracts for intersection and union types with blame assignment, giving a uniform treatment to both operators. A correct model of contracts must include a definition of contract satisfaction. Our second contribution is to show that contract satisfaction can be defined using blame: satisfying programs are those that do not elicit blame when monitored. We define a series of properties mandating how contract satisfaction should compose, ensuring that a contract for a type behaves as one would expect for that type. Building on our technical developments, our third contribution is a practical evaluation of gradual typing using the DefinitelyTyped repository. We show that contracts can be used to enforce conformance to a definition file, detecting errors in the specification. Our evaluation also reveals that technical concerns associated with implementing contracts using JavaScript proxies are a problem in practice.

The age of writing single-threaded applications is over. To develop scalable applications, developers must make use of concurrency and parallelism. Nonetheless, introducing concurrency and parallelism is difficult: naïvely implemented, concurrent code is prone to issues such as race conditions and deadlocks. Moving to the distributed setting introduces yet more issues, in particular the possibility of failure. To cope with many of the problems of concurrent programming, language designers have proposed a class of programming languages known as communication-centric programming languages, which provide lightweight processes which do not share memory, but instead communicate using explicit message passing. The focus of this thesis is on typed communication-centric functional programming languages, using type systems to provide static guarantees about the runtime behaviour of concurrent programs. We investigate two strands of work: the relationship between typed channel- and actor-based languages, and the integration of asynchrony, exception handling, and session types in a functional programming language. In the first strand, we investigate two particular subclasses of communication-centric languages: channel-based languages such as Go, and languages based on the actor model, such as Erlang. We distil the essence of the languages into two concurrent λ-calculi: λch for simply-typed channels, and lact for simply-typed actors, and provide type- and semantics-preserving translations between them. In doing so, we clear up confusion between the two models, give theoretical foundations for recent implementations of type-parameterised actors, and also provide a theoretical grounding for frameworks which emulate actors in channel-based languages. Furthermore, by extending the core calculi, we note that actor synchronisation drastically simplifies the translation from channels into actors, and show that Erlang's selective receive mechanism can be implemented without specialised constructs. In the second strand, we integrate session types, asynchrony, and exception handling in a functional programming language. Session types are a behavioural type system for communication channel endpoints, allowing conformance to protocols to be checked statically. We provide the first integration of exception handling and asynchronous session types in a core functional language, Exceptional GV, and prove that it satisfies preservation, global progress, and that it is confluent and terminating. We demonstrate the practical applicability of the approach by extending the Links tierless web programming language with exception handling, in turn providing the first implementation of exception handling in the presence of session types in a functional language. As a result, we show the first application of session types to web programming, providing examples including a two-factor authentication workflow and a chat application.

Collective Adaptive Systems (CAS) are composed of individual agents with internal knowledge and rules which organize themselves into ensembles. These ensembles can often be observed to exhibit behaviour resembling that of a single entity with a clear goal and a consistent internal knowledge, even when the individual agents within the ensemble are not managed by any outside, globally-accessible entity. Because of their lack of a need for centralized control which results in high robustness, CAS are commonly observed in nature - and for similar reasons are often reflected in human engineered systems. Researching the patterns of operation observed in such systems provides meaningful insight into how to design and optimise stable multiagent systems capable of withstanding adverse conditions. Formal modelling provides valuable intellectual tools which can be applied to the problem of analysis of systems by means of modelling and simulation. In this thesis we explore the modelling of CAS in which space (topology and distances) plays a significant role. Working with CARMA (Collective Adaptive Resource-sharing Markovian Agents) a formal feature-rich language for modelling stochastic CAS, we investigate a number of spatial CAS scenarios from the realm of urban planning. When components operate in a spatial context, their behaviour can be affected by where they are located in that space. For example, their location can influence the speed at which they move, and their ability to communicate with other components. Components in CARMA have internal store, and behaviour expressed by Markov processes. They can communicate with each other through sending messages on state transitions in a unicast or broadcast fashion. Simulation with pseudo-random events can be used to obtain values of measures applied to CARMA models, providing a basis for analysis and optimisation. The CARMA models developed in the case studies are data-driven and the results of simulating these models are compared with real-world data. In particular, we explore two scenarios: crowd-routing and city transportation systems. Building on top of CARMA, we also introduce CGP (CARMA Graphical Plugin), a novel graphical software tool for graphically specifying spatial CAS systems with the feature of automatic translation into CARMA models. We also supply CARMA with additional syntax structures for expressing spatial constructs.

This work proposes a deductive reasoning approach to the automatic verification of temporal properties of pointer programs, based on cyclic proof. We present a proof system whose judgements express that a program has a certain temporal property, given a suitable precondition, and whose rules operate directly on the temporal modalities as well as symbolically executing programs. Cyclic proofs in our system are, as elsewhere, finite rooted proof graphs subject to a natural, decidable sound ness condition, encoding a form of proof by infinite descent. We present two variants of our proof system, one for CTL (branching time) properties and one for LTL (linear time) properties, and show them both to be sound. We have implemented both variants in the C YCLIST theorem prover, yielding an automated tool that is capable of automatically discovering proofs of temporal properties of our programs. Evaluation of our tool on well-known benchmarks in the model checking community indicates that our approach is viable, and offers an interesting alternative to traditional model checking techniques.

Orca is a novel garbage collection protocol for actor-based, object-oriented programming languages for multicore machines. It supports fully concurrent garbage collection, where an actor can trigger garbage collection at any time without synchronising with any other actor. It does so while supporting copy-less message passing and sharing of mutable state. By leveraging a type system's guarantees of actor isolation, Orca can perform GC fully concurrently, without any form of barrier synchronisation in mutator threads, as commonly found in state-of-the-art concurrent collectors. Although Orca has been successfully implemented in Pony and in Encore, it had never been evaluated nor proven correct. Indeed, these are the two main contributions of this thesis. In this thesis, we model Orca and prove that it will never collect reachable objects (i.e., execution of programs managed by Orca will never result in dangling pointers) and that it will eventually deallocate all unreachable objects (i.e., execution of programs managed by Orca will never result in memory leaks). We model Orca in three steps: firstly, we define a set of requirements that must be ensured by the host language; secondly, assuming these requirements are in place, we model all the garbage collection related operations atomically; and thirdly, we extend our model to take into consideration that, in fact, in a fully concurrent system every instruction is interleaved with the execution of other operations. Moreover, we evaluate Orca 's performance by measuring scalability, footprint, responsiveness and its overhead in the execution of a program. We perform this evaluation in the context of Pony, the language with which Orca was co-designed, and compare it against the JVM, BEAM and Boehm-Demers-Weiser.

Online platforms, transaction processing systems, mobile sensors and other novel sources of data have shaped many areas of social research. The emerging discipline of social data science is subject to questions of epistemology, politics, ethics and responsibility, while the practice of doing social data science raises significant project management issues that include logistics, team communication, software system integration and stakeholder engagement. Keeping track of such a multitude of individual concerns while maintaining an overview of a social data science project as a whole is not trivial. This calls for provision of appropriate guidance for holistic project management. The project management issues in social data science are strikingly similar to those arising in software engineering. In this thesis, I adapt a particular software engineering project management tool - the SEMAT Essence model (Jacobson et al., 2013) - to the needs of social data science. This model offers a holistic management approach by addressing key project aspects, including the often overlooked yet crucially important ones such as maintaining stakeholder engagement and establishing the ways of working. The SEMAT Essence is a progress tracking model and does not assume any specific work process, which is valuable given the great diversity of social data science projects. To achieve this goal, I study the practice of doing social data science through participant observation of social data science projects and by providing ethnographic accounts for those. Using the ethnographic findings and the basic content and structure of the SEMAT model, I develop the Social Science Scorecard Deck - an agile project management tool for social data science. To assess the Scorecard Deck, I use the tool in management of a social data science project and then subject the tool to external validation by interviewing experts in social data science.

Creative artefacts, from concert posters to architectural plans, are often created in entirely software-based workflows. Software tools can be easily made to record all user interactions, thereby capturing the observable part of creative practice. Although recording software-based creative practice is easy, analysing it is much harder. This is especially true if one wishes to analyse the cognitive process that underlies the recorded creative practice. There are currently no clear methods for the analysis of recorded creative practice, nor are there any suitable theories of the cognition underlying creative practice that can serve as the basis for the development of such methods. This thesis develops a formal descriptive theory of the cognition underlying software-based creative practice, with the aim of informing the development of analysis of recorded creative practice. The theory, called the Software-based Creative Practice Framework (SbCPF), fits with extended and predictive views of cognition. It characterises creative practice as a process of iteratively working from an abstract idea to a concrete artefact, whereby the required lowlevel detail to decide on action is imagined in flight, during practice. Furthermore, it argues that this iterative just-in-time imagination is necessary, because of the predictive nature of the mind. The SbCPF was developed through the use of a novel method for the analysis of creative practice displayed in video tutorials. This method is based on Grounded Theory, Rhetorical Structure Theory, Gesture Theory, Category Theory, and a novel taxonomy describing the relation of action to speech. The method is applied to produce a grounded theory of the creative practice of 3D modelling and animation with the Blender software. The grounded theory forms the basis of the aforementioned formal theory. Finally, the formal theory is further illustrated, evaluated, and explored by way of implementing a computational model.