Skip to main content
Register
Springer Professional
TOOLBAR 1 2 3 4
SEARCH
MENU 1 2 3 4
Close search form
EXTENDED SEARCH
main-content
Top
​
insite
Print
​
print
​
share

2015 | Book

Programming Languages

19th Brazilian Symposium SBLP 2015, Belo Horizonte, Brazil, September 24-25, 2015, Proceedings

Automatic Inference of Loop Complexity Through Polynomial Interpolation Read first chapter

Book Series: Lecture Notes in Computer Science

Editors: Alberto Pardo, S. Doaitse Swierstra

Publisher: Springer International Publishing

Print ISBN: 978-3-319-24011-4

Electronic ISBN: 978-3-319-24012-1

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Get access Table of Contents

About this book

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.

Table of Contents

Frontmatter

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

Deadlocks as Runtime Exceptions
Abstract
Deadlocks are a common type of concurrency bug. When a deadlock occurs, it is difficult to clearly determine whether there is an actual deadlock or if the application is slow or hanging due to a different reason. It is also difficult to establish the cause of the deadlock. In general, developers deal with deadlocks by using analysis tools, introducing application-specific deadlock detection mechanisms, or simply by using techniques to avoid the occurrence of deadlocks by construction. In this paper we propose a different approach. We believe that if deadlocks manifest at runtime, as exceptions, programmers will be able to identify these deadlocks in an accurate and timely manner. We leverage two insights to make this practical: (i) most deadlocks occurring in real systems involve only two threads acquiring two locks (TTTL deadlocks); and (ii) it’s possible to detect TTTL deadlocks efficiently enough for most practical systems. We conducted a study on bug reports and found that more than 90 % of identified deadlocks were indeed TTTL. We extended Java’s ReentrantLock class to detect TTTL deadlocks and measured the performance overhead of this approach with a conservative benchmark. For applications whose execution time is not dominated by locking, the overhead is estimated as below 6 %. Empirical usability evaluation in two experiments showed that students finished tasks 16.87 % to 30.7 % faster on the average using our approach with the lock being the most significant factor behind it, and, in one of the experiments answers were significantly more accurate (81.25 % more correct bugs found).
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

Backmatter

Additional information

Premium Partner

Neuer Inhalt
    Image Credits

    Version: 0.1257.0