Joint SSaaPP/FATBIT Workshop 2012, Braga, September 17-18, 2012



September 17

FATBIT 0: Hugo Pacheco’s PhD defense (CP2-B2)

10h00 Hugo Pacheco: Bidirectional Data Transformation by Calculation
The advent of bidirectional programming, in recent years, has led to the development of a vast number of approaches from various computer science disciplines. These are often based on domain-specific languages in which a program can be read both as a forward and a backward transformation that satisfy some desirable consistency properties. Despite the high demand and recognized potential of intrinsically bidirectional languages, they have still not matured to the point of mainstream adoption. This dissertation contemplates some usually disregarded features of bidirectional transformation languages that are vital for deployment at a larger scale. The first concerns efficiency. Most of these languages provide a rich set of primitive combinators that can be composed to build more sophisticated transformations. Although convenient, such compositional languages are plagued by inefficiency and their optimization is mandatory for a serious application. The second relates to configurability. As update translation is inherently ambiguous, users shall be allowed to control the choice of a suitable strategy. The third regards genericity. Writing a bidirectional transformation typically implies describing the concrete steps that convert values in a source schema to values a target schema, making it impractical to express very complex transformations, and practical tools shall support concise and generic coding patterns.
13h00 Lunch

FATBIT 1: Foundations of Bidirectional Transformations (DI-A2)

Alcino Cunha & João Saraiva: Welcome Session
15h00 Zhenjiang Hu: Towards Deterministic Backward Transformations
Bidirectionalization is an automatic program transformation that derives a backward transformation from a given forward transformation. In general, more than one backward transformations exist and the problem is how to choose the “best” backward transformation that not only satisfies the roundtrip property but also meets the user’s intention. I would like to discuss the importance of determination of such backward transformation and explain some possible solutions.
15h30 Nuno Macedo: Relations as Executable Specifications: Taming Partiality and Non-determinism Using Invariants
The calculus of relations has been widely used in program specification and reasoning. It is very tempting to use such specifications as running prototypes of the desired program, but, even considering finite domains, the inherent partiality and non-determinism of relations makes this impractical and highly inefficient. To tame partiality we prescribe the usage of invariants, represented by coreflexives, to characterize the exact domains and codomains of relational specifications. Such invariants can be used as pre-condition checkers to avoid runtime errors. Moreover, we show how such invariants can be used to narrow the non-deterministic execution of relational specifications, making it viable for a relevant class of problems. In particular, we show how the proposed techniques can be applied to execute specifications of bidirectional transformations, a domain where partiality and non-determinism are paramount.
16h00 Coffee break

SSaaPP 1: Spreadsheet Engineering (DI-A2)

16h30 Felienne Hermans: Detecting Code Smells in Spreadsheet Formulas
Spreadsheets are used extensively in business processes around the world and just like software, spreadsheets are changed throughout their lifetime causing maintainability issues. This paper adapts known code smells to spreadsheet formulas. To that end we present a list of metrics by which we can detectsmelly formulas and a visualization technique to highlight these formulas in spreadsheets. We implemented the metrics and visualization technique in a prototype tool to evaluate our approach in two ways. Firstly, we analyze the Euses spreadsheet corpus, to study the occurrence of the formula smells. Secondly, we analyze ten real life spreadsheets, and interview the spreadsheet owners about the identified smells. The results of these evaluations indicate that formula smells are common and that they can reveal real errors and weaknesses in spreadsheet formulas.
17h00 Jácome Cunha & João Paulo Fernandes: Model-based Spreadsheet Engineering
Spreadsheets play an important role in software organizations. Indeed, in large software organizations, spreadsheets are not only used to define sheets containing data and formulas, but also to collect information from different systems, to adapt data coming from one system to the format required by another, to perform operations to enrich or simplify data, etc. In fact, over time many spreadsheets turn out to be used for storing and processing increasing amounts of data and supporting increasing numbers of users. Unfortunately, spreadsheet systems provide poor support for modularity, abstraction, and transformation, thus, making the maintenance, update and evolution of spreadsheets a very complex and error-prone task. We present techniques for model-driven spreadsheet engineering where we a ClassSheet model is inferred form legacy spreadsheets. We also present techniques to embedded such models in spreadsheet systems. Finally we employ bidirectional transformations to maintain spreadsheet models and instances synchronized. Our techniques are implemented as part of the MDSheet framework: an extension for a traditional spreadsheet system.
20h00 Workshop Dinner

September 18

FATBIT 2: Applications of Bidirectional Transformations (DI-A2)

10h00 Nuno Macedo: An Implementation of QVT-R using Alloy
The QVT Relations language is widely used to specify transformations between models. However, due to ambiguities in its semantics, development and acceptance of tool support has been slow. Alloy is a lightweight formal specification language with support for automatic verification and model generation. By translating to Alloy both UML models and QVT transformations over them, both annotated with generic OCL constraints, we are able to provide a functional bidirectional transformation framework, whose supported language is more expressive than those of the existing tools. We take into consideration the QVT semantics as defined in the standard, and analyze and compare our results where the specification is incomplete or ambiguous.
10h30 TBA: Towards the Bidirectionalization of Spreadsheet Formulas
Bidirectional transformations have application in a wide number of computer science domains. Spreadsheets, on the other hand, are widely used for developing business applications, but their formulas are unidirectional, in the sense that their result can not be edited and propagated back to their input cells. In this poster, we propose the bidirectionalization of such formulas, by recasting them as lenses, a successful bidirectional transformation framework with instantiations in various data domains relevant for this endeavor.
10h45 Pedro Martins: Bidirectional Attribute Grammars
Bidirectionalization is the process of automatically generating a transformation on one direction, from a type of data A to a type B, given the opposite transformation (i.e.: given the transformation that goes from B to A). In this talk we will present a prototype of a bidirectionalization system that handles syntactic information described as Context-free Grammars. Our system is based on a set of mappings between grammar productions and is capable of dealing with situations where there are non-bijective mappings between Non Terminal elements of the Grammars, in any direction. We will also present a prototype implementation of a bidirectionalization engine.
11h00 Coffee break

SSaaPP 2: Fault Localization in Spreadsheets (DI-A2)

11h30 Daniel Kulesz: Which Types of Spreadsheets Faults are Responsible for Significant Failures?
Faults in spreadsheets are common, but seldom easy to spot. The results of our previous work - a controlled experiment with 42 subjects on the creation and modification of spreadsheets - indicated that violations of Best Practices such as “don’t put constants in formulae” are not dependable as indicators of correctness. <br /> Meanwhile, we have examined the actual faults and possible causes in more detail. In this talk, we would like to present a few of our findings and discuss possible approaches towards more effective detection strategies.
12h00 André Riboira & Rui Maranhão: Spreadsheet debugging using a Spectrum-based Fault Localization approach
Spectrum-based Fault Localization (SFL) approaches are proved to be effective in helping software developers during their debugging tasks. The same principles may also be used with spreadsheets. Traditional SFL approaches use matrices with the software’s hit-spectra, obtained from several test executions, as well as the resulting error vectors, denoting the result of each test execution. Although these techniques may not be directly applied to spreadsheets, they may be adapted to this new programming paradigm. Traditional software components considered by the hit-spectra may be replaced by the spreadsheet’s cells. The test executions may be replaced by the spreadsheet’s output cells (cells not used by any other cell). Thus, the error vector should be associated with the results of these output cells. Consequently we can produce the SFL’s input matrix and error vector, to allow the use of any of the existent similarity coefficients to pinpoint the most suspicious spreadsheet’s cells.
12h30 Lunch

FATBIT 3: Foundations of Bidirectional Transformations (DI-A2)

14h30 Jeremy Gibbons (joint work with Richard Bird): The Un of Programming
A recent paper by Graham Hutton and Diana Fulger (“Reasoning about Effects: Seeing the Wood through the Trees”, in the preproceedings of Trends in Functional Programming 2008) addresses the problem of reasoning about effectful functional programs, introducing a relabelling function on binary trees as a representative illustration. The example is a very fruitful one, but we argue that their approach is less effective than it might be, because they miss two opportunities for higher-level reasoning: abstraction from the particular kinds of effect (the choice of monad) and from the pattern of recursion (the flow of computation). We present an alternative approach using properties of idiomatic traversals, which cleanly separate the twin concerns of the kinds of effect and the pattern of recursion. In particular, we approach the problem by considering its inverse; and we argue that this is an important approach which has so far been missing from discussions of idiomatic traversal.
15h00 Alcino Cunha: A Taxonomy of Bidirectional Transformations
The recent rise of interest in bidirectional transformations (BX) has led to the development of many BX frameworks, originating in diverse computer science disciplines. However, due to lack of a universal classifying system, existing frameworks are still difficult to compare in terms of expressiveness and robustness. In this paper, we analyze the defining features of BX frameworks, namely their scheme, properties and deployment technique, and propose a generic taxonomy that can be used to classify and compare them. Moreover, we applied this taxonomy to a vast number of existing BX frameworks, thus providing a detailed panorama of the current BX state of the art.
15h30 Janis Voigtländer: Ideas for Connecting Inductive Program Synthesis and Bidirectionalization
We share a vision of connecting the topics of bidirectional transformation and inductive program synthesis, by proposing to use the latter in approaching problematic aspects of the former. This research perspective does not present accomplished results, rather opening discussion and describing experiments designed to explore the potential of inductive program synthesis for bidirectionalization (the act of automatically producing a backwards from a forwards transformation), in particular to address the issue of integrating programmer intentions and expectations.
15h45 Hugo Pacheco: Functional Logic Semantic Bidirectionalization for free
Nowadays, many bidirectional approaches exist, but most depend on some syntactic analysis of a specification in order to equip it with a bidirectional semantics. An interesting alternative, coined semantic bidirectionalization by Voigtländer, allows to bidirectionalize an arbitrary transformation almost for free by inspecting not its syntax but its shape, i.e., the types over which it is defined. In this talk, we attempt to overcome the limitations of Voigtländer’s pioneering approach, that relies on the parametric polymorphism of Haskell functional programs. Concretely, we propose first steps for a functional logic bidirectionalization approach that is nearly a superset of its functional parent and resorts to program inversion techniques that enable a more precise non-deterministic bidirectional semantics on-the-fly. We show that the additional computation cost of a prototype Curry implementation is bearable for many interesting examples, demonstrating the potential of our approach.
16h00 Coffee break

SSaaPP 3: Model Driven Spreadsheets (DI-A2)

16h30 Pedro Faria: Security in Model Driven Spreadsheets
Loss of secrecy, theft or fraud are problems regarding the lack of confidentiality and privacy on shared spreadsheets. There are numerous examples in which an inappropriate share of a spreadsheet, due to hacking, negligence, or even a lost pen-drive, causes a leak in private data, which may result in economic and personal disasters. Such problems can be reduced with access control mechanisms over a model-driven paradigm. Each mechanism has its own pros and cons, and even different implementations according to the sharing environment. This presentation will talk about those problems, in particular the ones regarding the update and change of spreadsheets, and possible solutions, as well the next research paths.
16h45 Jorge Mendes: Evolution of Model Driven Spreadsheets
Spreadsheets are the most used programming environment, mostly because they are very flexible. This is due to the lack of restrictions imposed on them which can lead to lots of errors. A first approach to Model-Driven Engineering was already suggested to improve spreadsheets, providing them with specifications and checking tools. However, users have to learn how to use these tools on top of their existing spreadsheet host system. To remove that difficulty, the work for this thesis describes an embedding of spreadsheet models within spreadsheet themselves. This embedding enables users to create models in the same environment that they use for spreadsheet development and that they are familiar with. Moreover, a set of operations that can be performed on these models and respective instances is defined. This way, users interact with models and spreadsheets in the same environment with the objective to improve work performance and reduce errors. Resulting from this work, a prototype was created and is also discussed in this dissertation. This prototype can be used to validate the approach taken in this thesis and to provide a base framework for future developments.
17h15 Jorge Mendes’s MSc defense