main-content

This book constitutes the proceedings of the 19th Brazilian Symposium on Progamming Languages, SBLP 2015, held in Belo Horizonte, Brazil, in September 2015.

The 10 papers presented in this volume were carefully reviewed and selected from 26 submissions. They deal with fundamental principles and innovations in the design and implementation of programming languages and systems.

### Automatic Inference of Loop Complexity Through Polynomial Interpolation

Abstract
Complexity analysis is an important activity for software engineers. Such an analysis can be specially useful in the identification of performance bugs. Although the research community has made significant progress in this field, existing techniques still show limitations. Purely static methods may be imprecise due to their inability to capture the dynamic behaviour of programs. On the other hand, dynamic approaches usually need user intervention and/or are not effective to relate complexity bounds with the symbols in the program code. In this paper, we present a hybrid technique that solves these shortcomings. Our technique uses a numeric method based on polynomial interpolation to precisely determine a complexity function for loops. Statically, we determine: (i) the inputs of a loop, i.e., the variables that control its iterations; and (ii) an algebraic equation relating the loops within a function. We then instrument the program to plot a curve relating inputs and number of operations executed. By running the program over different inputs, we generate sufficient points for our interpolator. In the end, the complexity function for each loop is combined using an algebra of our own craft. We have implemented our technique in the LLVM compiler, being able to analyse 99.7 % of all loops available in the Polybench benchmark suite, and most of the loops in Rodinia. These results indicate that our technique is an effective and useful way to find the complexity of loops in high-performance applications.
Francisco Demontiê, Junio Cezar, Mariza Bigonha, Frederico Campos, Fernando Magno Quintão Pereira

### Type Inference for GADTs and Anti-unification

Abstract
Nowadays the support of generalized algebraic data types (GADTs) in extensions of Haskell allows functions defined over GADTs to be written without the need for type annotations in some cases and requires type annotations in other cases. In this paper we present a type inference algorithm for GADTs that is based on a closed-world approach to overloading and uses anti-unification and constraint-set satisfiability to infer the relationship between the types of function arguments and result. Through some examples, we show how the proposed algorithm allows more functions defined over GADTs to be written without the need for type annotations.
Adelaine Gelain, Cristiano Vasconcellos, Carlos Camarão, Rodrigo Ribeiro

### Preserving Lexical Scoping When Dynamically Embedding Languages

Abstract
There are various situations in which one may want to embed source code from one language into another, for example when combining relational query languages with application code or when performing staged meta-programming. Typically, one will want to transfer data between these languages. We propose an approach in which the embedded code shares variables with the host language, preserving lexical scoping rules even after the code is converted into an intermediate representation. We demonstrate this approach through a module for meta-programming using Lua as both embedded and host languages. Our technique supports dynamically generated code, requires no special annotation of functions to be translated and is implemented as a library, requiring no source pre-processing or changes to the host language execution environment.
Félix Ribeiro, Hisham Muhammad, André Murbach Maidl, Roberto Ierusalimschy

### The Dinamica Virtual Machine for Geosciences

Abstract
This paper describes DinamicaVM, the virtual machine that runs applications developed in Dinamica EGO. Dinamica EGO is a framework used in the development of geomodeling applications. Behind its multitude of visual modes and graphic elements, Dinamica EGO runs on top of a virtual machine. This machine - DinamicaVM - offers developers a rich instruction set architecture, featuring elements such as map and reduce, which are typical in the functional/parallel world. Ensuring that these very expressive components work together efficiently is a challenging endeavour. Dinamica’s runtime addresses this challenge through a suite of optimizations, which borrows ideas from functional programming languages, and leverages specific behavior expected in geo-scientific programs. As we show in this paper some of these optimizations deliver speedups of almost 50x, and are key to the industrial-quality performance of one of the world’s most widely used geomodeling tools.
Bruno Morais Ferreira, Britaldo Silveira Soares-Filho, Fernando Magno Quintão Pereira

### Go Model and Object Oriented Programming

Abstract
Go is a contemporary language aiming to support OO programming where the core OO feature, inheritance, is intentionally excluded. Go uses the concepts of embedding and interface to provide its object model. To understand the design of Go and its consequences, we develop a simple Go-like model language, mini-Go, which abstracts Go’s interface-based OO features. The formal defined type system and semantics are given. In addition, we propose an even simpler language $$\mu$$Go where the feature of pointers is further removed. We demonstrate that $$\mu$$Go is as expressive in OO as the original language with pointers, which provides a uniform model for Go-like OO programming. We investigate the OO model of the Go-like languages using $$\mu$$Go in detail, point out that the absence of open recursion brings difficulties in OO design, and then propose a novel design pattern to mimic the open recursion feature to overcome the difficulties.
Haiyang Liu, Zongyan Qiu

### An Intrinsic Denotational Semantics for a Lazy Functional Language

Abstract
In this paper we present a denotational semantics for a lazy functional language. The semantics is intrinsic in the sense that it defines meaning for typing derivations instead of language expressions. We contrast our semantics with the well-known evaluation rules defined by Sestoft [17] and show that these rules preserve types and meaning.
Leonardo Rodríguez

### Color Flipping

Abstract
Spill code minimization is an important problem in register allocation because it affects the quality of the code produced by the compiler and program performance. This work presents a new technique to reduce spill code, called color flipping. Differently of other techniques, color flipping prevents all load/store instructions insertion when avoiding spill. Nevertheless, color flipping can be used in combination with other spill minimization techniques to achieve an overall better result. To evaluate the impact of using color flipping, experiments with a set of interference graphs and with the benchmark SPEC CPU2006, showed over 12 % of spill reduction.
Felipe L. Silva, Marcelo F. Luna, Wesley Attrot

Abstract
Rafael Lobo, Fernando Castor

### Model-Driven Engineering Based on Attribute Grammars

Abstract
The Model-Driven Engineering (MDE) paradigm proposes the construction of software based on an abstraction from its complexity by defining models, and on a (semi)automatic construction process driven by model transformations. In this paper we propose the use of attribute grammars for the specification of QVT-like (Query/View/Transformation) relational model transformations. We also present how the syntax and semantics of models can be represented, and we discuss the practical implications of this approach through the development of a case study.
Daniel Calegari, Marcos Viera

### Composable Memory Transactions for Java Using a Monadic Intermediate Language

Abstract
Transactional memory is a new programming abstraction that simplifies concurrent programming. This paper describes the parallel implementation of a Java extension for writing composable memory transactions in Java. Transactions are composable i.e., they can be combined to generate new transactions, and are first-class values, i.e., transactions can be passed as arguments to methods and can be returned as the result of a method call. We describe how composable memory transactions can be implemented in Java as a state passing monad, in which transactional blocks are compiled into an intermediate monadic language. We show that this intermediated language can support different transactional algorithms, such as TL2 [9] and SWissTM [10]. The implementation described here also provides the high level construct retry, which allows possibly-blocking transactions to be composed in sequence. Although our prototype implementation is in Java using BGGA Closures, it could be implemented in any language that supports objects and closures in some way, e.g. C#, C++, and Python.
Rafael Bandeira, André R. Du Bois, Maurício Pilla, Juliana Vizzotto, Marcelo Machado