Rewriting Concurrent Haskell programs to STM

Recentemente, a queda na taxa de crescimento da quantidade de transístores integráveis em processadores tem desacelerado o crescimento de poder computacional. A lei de Moore parece aproximar-se de seu fim. Com isso, é desafiada a premissa de que software escrito hoje terá melhor desempenho no futuro simplesmente devido à evolução dos processadores. Ainda assim, aplicações paralelas ainda podem se tornar mais eficientes ao se distribuir trabalho entre diferentes processadores para execução simultânea. Para permitir a paralelização, são necessários múltiplos núcleos de processamento, o que tem levado à popularização de arquiteturas multinúcleo. Entretanto, a escrita de aplicações paralelas não é trivial. Deve-se escrever um programa para execução paralela desde sua concepção, ou adaptá-lo posteriormente para execução paralela. O programador tem a difícil tarefa de paralelização da aplicação através do uso de construções de concorrência e paralelismo. Travas, a mais comum opção para concorrência, apresentam riscos para programadores inexperientes, tais quais os famosos problemas de Deadlock e Livelock. Ao adaptarem-se de arquiteturas de um único núcleo para as de multinúcleo, as linguagens de programação precisam facilitar o uso de concorrência para os programadores. Muitos pesquisadores têm indicado Memória Transacional em Software (STM, do inglês Software Transactional Memory) como a resposta para esse problema, por ser uma forma abstrata e não bloqueante para garantia de acesso isolado a recursos compartilhados. Mas adaptar para STM programas que usam travas não é simples. Além de ser uma atividade propensa a erros, detalhes técnicos da linguagem podem requerer cuidados para se preservar o comportamento do programa. Nesta dissertação, é proposto um conjunto de transformações de programas para construções de concorrência em Haskell, uma linguagem de programação puramente funcional. Elas podem ser usadas para refatorar travas de um programa para uso de construções transacionais da implementação de STM em Haskell. Isso permite ao programador aproveitar os benefícios do trabalho com STM mesmo para programas já desenvolvidos com uso de travas. Cada transformação é acompanhada de exemplos de execução e uma discussão sobre sua capacidade de preservar o comportamento do programa. Também é apresentado um estudo de apoio, no qual um experimento controlado foi usado para avaliar os benefícios do uso de travas ou STM no desenvolvimento de programas em Haskell. Apesar das opiniões dos participantes terem favorecido o uso de travas, aqueles que usaram STM cometeram em geral menos erros e em média precisaram de 12% a menos de tempo para terminar suas tarefas.In recent years, the diminishing rate with which we can increase the amount of transistors in a processor core has slowed down the increase of computers’ power. Moore’s Law appears to be drawing to an end. With it, the assumption that software written today will be more efficiently executed in the future simply due to processors’ evolution is being challenged. On the other hand, parallel applications can still be made more efficient by distributing work among different processors to be executed at the same time, thus reducing overall execution time. To enable parallelization, we must have multiple processor cores. This has led to the popularization of multicore architectures. However, writing parallel applications is not trivial. A program must be either written from the start to be executed in parallel, or later adapted for parallel execution. The programmer has the error-prone task of parallelizing the application through use of concurrency and parallelism constructs. Locking, the most common concurrency option, presents risks for inexperienced programmers, such as the famous Deadlock and Livelock problems. As we move from single core architectures to multicore, our programming languages need to make it easier for the programmers to use concurrency. Many researchers have pointed at Software Transactional Memory (STM) as an answer to that issue, as it is a lock-free, abstract way to guarantee isolated access to shared resources. But adapting for STM a program that uses lock is not simple. Besides being an error-prone task, technical details of the language might require special attention to preserve the program’s behavior. In this dissertation, we propose a set of program transformations for concurrency constructs in Haskell, a purely functional programming language. They may be used to refactor a program’s existing locks into transactional constructs from Haskell’s STM implementation. This allows a programmer to gain the benefits of working on STM even for programs which were already developed using locks. Each transformation is accompanied by execution examples and a discussion on its ability to preserve program behavior. We also present a supporting study, in which a controlled experiment was used to evaluate the benefits of locks or STM for the development of Haskell programs. Although subjects’ opinions tended to favor lock-based concurrency, those which used STM overall committed significantly fewer mistakes and required on average 12% less time to finish their assignments