Sunday, February 15, 2015

Busy week: three new paper drafts!



After a busy week for me and my co-authors, I'm happy to share three new paper drafts.

Abstract:
Generic programming (GP) is a form of abstraction in programming languages that serves to reduce code duplication by exploiting the regular structure of algebraic datatypes. Several different approaches to GP in Haskell have surfaced, giving rise to the problem of code duplication across GP libraries. Given the original goals of GP, the is a rather unfortunate turn of events. Fortunately, we can convert between the different representations of each approach, which allows us to "borrow" generic functions from different approaches, avoiding the need to reimplement every generic function in every single GP library.

In previous work we have shown how existing GP libraries relate to each other. In this paper we go one step further and advocate "hierarchical GP": through proper design of different GP approaches, each library can fit neatly in a hierarchy, greatly minimizing the amount of supporting infrastructure necessary for each approach, and allowing each library to be specific and concise, while eliminating code duplication overall. We introduce a new library for GP in Haskell intended to sit at the top of the "GP hierarchy". This library contains a lot of structural information, and is not intended to be used directly. Instead, it is a good starting point for generating generic representations for other libraries. This approach is also suitable for being the only library with native compiler support; all other approaches can be obtained from this one by simple conversion of representations in plain Haskell code.



Abstract:
Applications which deal with editing of structured data over multiple iterations, such as structure editors, exercise assistants, or applications which support incremental computation, need to represent transformations between different versions of data. A general notion of "transformation" should be more informative than what is obtained by computing the difference between the old and the new term, as diff algorithms generally consider only insert, copy, and delete operations. Transformations, however, may involve swapping elements, or duplicating them, and a good representation of transformations should not involve unnecessary repetition of data, or lose shared structure between the old and new term. 

In this paper we take a detailed look at the notion of transformation on strongly-typed structures. Our transformations are datatype-generic, and thus can be applied to a large class of data structures. We focus on representing transformations in a way that maximally captures the common substructure between the old and new term. This is of particular importance to a specific class of applications: that of incremental computations which recompute information only for the parts of the tree that are affected by a transformation. 

We present a library for encoding such transformations over families of datatypes, together with an algorithm for computing a transformation from one term into another, while retaining shared common substructures. We provide practical examples of how to encode transformations, as well as a realistic application to computing transformations between different revisions of a program. 



Abstract:
The most widely used generic-programming system in the Haskell community, Scrap Your Boilerplate (SYB), also happens to be one of the slowest. Generic traversals in SYB are often an order of magnitude slower than equivalent handwritten, non-generic traversals. Thus while SYB allows the concise expression of many traversals, its use incurs a significant runtime cost. Existing techniques for optimizing other generic-programming systems are not able to eliminate this overhead. 

This paper presents an optimization that eliminates this cost. Essentially, it is a partial evaluation that takes advantage of domain-specific knowledge about the structure of SYB. It optimizes SYB traversals to be as fast as handwritten, non-generic code, and benchmarks show that this optimization improves the speed of SYB traversals by an order of magnitude or more. 

Tuesday, February 10, 2015

I got awarded a Marie Curie individual fellowship!

After over 5 months waiting, I heard back from the European Commission: my Marie Curie Individual Fellowship has been selected for funding! This means two years of funding for research at Utrecht University in my project. In case you're curious, here's an excerpt of the summary of my project proposal:
Music is an art form with a very long history, and continues to engage millions of people today. Music Information Retrieval (MIR), the exciting interdisciplinary science that brings together music and computer science, is a growing field of research with the potential to enrich pure computer science knowledge while creating real-world applications that the general public can benefit from. While the marriage of art and science is often troublesome, MIR has the benefit that many aspects of music are highly structural and have been subject to rigorous formalisation for a long time. Formalisation and computers go hand in hand, and MIR researchers have therefore been developing models of musical structure for many years, and putting them to use in several applications. However, such models, so far, have had limited impact; they are commonly restricted to one specific aspect of music (such as harmony or form), can be hard to implement computationally (due, for example, to the way ambiguity is handled), and are often too technical to be used directly by musicologists who are not familiar with programming language details.
However, models are valuable. Unlike machine learning approaches, model-based MIR provides a real insight about the underlying structure, and can benefit from the input of musicologist experts. Furthermore, a single model can be applied to multiple important MIR tasks (such as retrieval, analysis, and automatic composition). The research goal of this project is thus to give musical models the impact they deserve, advancing the practical embodiment of hierarchical musical structurein its various formsin computer science through the development of new, functional Models of Structure in Music (MoStMusic). Specifically, I intend to develop functional models of musical form, melody, and harmony that enable an easy, fast, and flexible way of creating model-enhanced MIR applications. Being executable, these models will pave the way for true content-based music analysis and retrieval---an underestimated and underexplored area. As a showcase of a model-enhanced application, I will create an online music analyser that automatically computes the structure present in a user-submitted piece, and displays it in an interactive interface that highlights the structural shape of music.

Monday, July 21, 2014

LaTeX template for the Marie Sklodowska-Curie Individual Fellowships application (H2020-MSCA-IF-2014)

I've created  a LaTeX template for the Marie Sklodowska-Curie Individual Fellowships application (H2020-MSCA-IF-2014). It's based on a version that I found online for the previous call; I've tried to update it for the 2014 call. I made this because I couldn't stand the idea of using the provided Word template (especially because of references). Hopefully it fits within the prescribed guidelines, but I cannot guarantee that. Pull requests to improve the template are welcome!

Thursday, January 30, 2014

POPL 2015 is in India, and I think that is a bad idea

POPL, one of the most important scientific conferences in the field of programming languages, will be held in Mumbai, India, in 2015. I find this rather unfortunate. As a SIGPLAN event, POPL ought to follow the SIGPLAN Conference Anti-Harassment Policy. Quoting from the policy: "Harassment in any form, including but not limited to harassment based on (...) sexual orientation (...) will not be tolerated". Unfortunately, India just recently reinstated a ban on gay sex, and rejected a petition for reconsidering its decision. The law dates from the period of the British rule of India, and is not unlike the British law that lead to the death of Alan Turing. This is a worrying development, and sends a clear message of intolerance and harassment to local or visiting homosexuals.
Personally, I do not feel welcome or even safe in India, and consequently will not attend POPL 2015. I find it regrettable that the POPL Steering Committee failed to keep to its own anti-harassment policy when choosing a venue for POPL 2015.

Monday, December 2, 2013

Media attention

I have had a lot of media attention in the past few days due to a press release from my undergrad university, featuring me as alumnus of the month, and highlighting my role in Chordify. For posterity, here are the places I could find (all in Portuguese): Público, Jornal de Notícias, Correio da Manhã, TSF, TMN, Jornal i, Sol, Minho University's Facebook page, canalsuperior.pt, maissuperior.com, boasnoticias.pt, xpressingmusic.com (interview), 4gnews.pt, pavablog.com.

I've also been interviewed on the Antena 1 radio; you can listen to the interview here (I show up around minute 34).