Fernando Magno Quintão Pereira (Ed.) 1 Programming 7 7 8 S Languages C N L 18th Brazilian Symposium, SBLP 2014 Maceio, Brazil, October 2–3, 2014 Proceedings 123 Lecture Notes in Computer Science 8771 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Fernando Magno Quintão Pereira (Ed.) Programming Languages 18th Brazilian Symposium, SBLP 2014 Maceio, Brazil, October 2-3, 2014 Proceedings 1 3 VolumeEditor FernandoMagnoQuintãoPereira FederalUniversityofMinasGerais Av.AntônioCarlos BeloHorizonte,MinasGerais,Brazil E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-319-11862-8 e-ISBN978-3-319-11863-5 DOI10.1007/978-3-319-11863-5 SpringerChamHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2014949227 LNCSSublibrary:SL2–ProgrammingandSoftwareEngineering ©SpringerInternationalPublishingSwitzerland2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthePublisher’slocation, inistcurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Permissionsforuse maybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violationsareliabletoprosecution undertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface This volume contains the proceedings of the 18th Brazilian Symposium on Pro- graming Languages (SBLP 2014), held during October 2nd/3rd of 2014, in Ma- cei´o, Brazil. The Brazilian Symposium on Programing Languages had its first event in 1996, and since 2010, it has been part of the Brazilian Conference on Software(CBSoft).Thissymposiumisavenuewhereresearchers,developers,ed- ucators,andpractitionersexchangeinformationonboththetheoryandpractice related to all the aspects of programing languages and systems. Interest in the symposium has been confirmed by the submission of papers on the most diverse subjects. There were 31 submissions from authors from six different countries. Each submitted paper was reviewed by at least three mem- bers ofthe ProgramCommittee. The expertopinions ofmany outside reviewers were invaluable to ensure the high quality of the program. We express our sin- cere gratitude for the effort of these volunteers. The final programfeatured two invited talks, two tutorials, eleven full papers in English, and three papers in Portuguese.Thesethreepapers,whichwerepresentedattheconference,arenot part of these proceedings. We owea greatdealofthanks to the authors,reviewers,andthe members of the Program Committee for making the 18th SBLP a success. We thank Louis- Noel Pouchet for his invited talk on optimizing compilers for high-performance computing, andwe thank Fabrice Rastellofor his talk onthe duality thatexists betweenstaticanddynamicprogramanalyses.Finally,wethankMa´rcioRibeiro, Leandro Dias da Silva and Baldo´ıno Fonseca, the general organizers of CBSoft 2014 for all their help and support. August 2014 Fernando Magno Quint˜ao Pereira Organization Program Chair Fernando Pereira UFMG, Brazil Local Arrangement (co)-Chair(s) Baldo´ıno Fonseca UFAL, Brazil M´arcio Ribeiro UFAL, Brazil Leandro Dias da Silva UFAL, Brazil Program Committee Alberto Pardo Universidad de la Repu´blica, Uruguay Alex Garcia IME, Brazil A´lvaro Moreira FederalUniversityofRioGrandedoSul,Brazil A´ndre Rauber Du Bois Federal University of Pelotas, Brazil Carlos Camar˜ao Federal University of Minas Gerais, Brazil Christiano Braga Fluminense Federal University, Brazil Fa´bio Mascarenhas Federal University of Rio de Janeiro, Brazil Fabrice Rastello Inria, France Fernando Pereira Federal University of Minas Gerais, Brazil Fernando Castor Federal University of Pernambuco, Brazil Francisco Carvalho-Ju´nior Federal University of Ceara´, Brazil Hans-Wolfgang Loidl Heriot-Watt University, UK Joa˜o Saraiva University of Minho, Portugal Jo˜ao F. Ferreira Teesside University, UK Louis-Noel Pouchet University of California Los Angeles/Ohio State University, USA Lucil´ıa Figueiredo Federal University of Ouro Preto, Brazil Luis Barbosa University of Minho, Portugal Manuel A. Martins University of Aveiro, Portugal Marcello Bonsangue Leiden University, The Netherlands Marcelo Maia Federal University of Uberlaˆndia, Brazil Marcelo D’Amorim Federal University of Pernambuco, Brazil VIII Organization Mariza Bigonha Federal University of Minas Gerais, Brazil Martin Musicante Federal University of Rio Grande do Norte, Brazil Noemi Rodriguez PUC-Rio, Brazil Peter Mosses Swansea University, UK Rafael Lins Federal University of Pernambuco, Brazil Renato Cerqueira PUC-Rio, Brazil Roberto Bigonha Federal University of Minas Gerais, Brazil Rodrigo Geraldo Federal University of Ouro Preto, Brazil Sandro Rigo State University of Campinas, Brazil Sergio Medeiros Federal University of Rio Grande do Norte, Brazil Simon Thompson University of Kent, UK Varmo Vene University of Tartu, Estonia Invited Reviewers Cardoso, Elton Moraes, Bruno Rodrigues, Bruno Cunha, J´acome Neves, Renato Souza Neto, Pl´acido Madeira, Alexandre Ribeiro, Rodrigo Voidani, Vesal Table of Contents A Mixed Approach for Building Extensible Parsers................... 1 Leonardo Vieira dos Santos Reis, Vladimir Oliveira Di Iorio, and Roberto S. Bigonha A Security Types Preserving Compiler in Haskell .................... 16 Cecilia Manzino and Alberto Pardo Avoiding Code Pitfalls in Aspect-Oriented Programming.............. 31 P´ericles Alves, Eduardo Figueiredo, and Fabiano Ferrari Bounds Check Hoisting for AddressSanitizer......................... 47 Simon Moll, Henrique Nazar´e, Gustavo Vieira Machado, and Raphael Ernani Rodrigues Case of (Quite) Painless Dependently Typed Programming: Fully Certified Merge Sort in Agda................................. 62 Ernesto Copello, A´lvaro Tasistro, and Bruno Bianchi Detecting Anomalous Energy Consumption in Android Applications.... 77 Marco Couto, Tiago Carc¸˜ao, J´acome Cunha, Jo˜ao Paulo Fernandes, and Jo˜ao Saraiva Effect Capabilities for Haskell ..................................... 92 Ismael Figueroa, Nicolas Tabareau, and E´ric Tanter Fusion: Abstractions for Multicore/Manycore Heterogenous Parallel Programming Using GPUs ........................................ 109 Anderson Boettge Pinheiro, Francisco Heron de Carvalho Junior, Neemias Gabriel Pena Batista Arruda, and Tiago Carneiro Real-World Loops Are Easy to Predict.............................. 124 Raphael Ernani Rodrigues A Hybrid Framework to Accelerate Adaptive Compilation Systems..... 139 Gabriel Krisman Bertazi, Anderson Faustino da Silva, and Edson Borin Transactional Boosting for Haskell ................................. 145 Andr´e Rauber Du Bois, Maur´ıcio Lima Pilla, and Rodrigo Duarte Author Index.................................................. 161 A Mixed Approach for Building Extensible Parsers Leonardo Vieira dos Santos Reis1, Vladimir Oliveira Di Iorio2, and Roberto S. Bigonha3 1 Departamento deComputac¸˜ao e Sistemas, UniversidadeFederal deOuro Preto, Jo˜ao Monlevade, Brazil [email protected] 2 Departamento deInform´atica, UniversidadeFederal de Vi¸cosa, Vi¸cosa, Brazil [email protected] 3 Departamento deCiˆencia da Computa¸c˜ao, Universidade Federal deMinas Gerais, Belo Horizonte, Brazil [email protected] Abstract. Forlanguageswhosesyntaxisfixed,parsersareusuallybuilt withastaticstructure.Theimplementationoffeatureslikemacromech- anisms or extensible languages requires the use of parsers that may be dynamically extended. In this work, we discuss a mixed approach for building efficient top-down dynamically extensible parsers. Our view is based on the fact that a large part of the parser code can be statically compiled and only theparts that are dynamic should be interpreted for a more efficient processing. We propose the generation of code for the base parser, in which hooks are included to allow efficient extension of theunderlyinggrammar and activation of agrammar interpreterwhen- everitisnecessarytouseanextendedsyntax.Asaproofofconcept,we present a prototype implementation of a parser generator using Adapt- able Parsing Expression Grammars (APEG) as the underlying method for syntax definition. We show that APEG has features which allow an efficient implementation using theproposed mixed approach. 1 Introduction Parser generators have been used for more than 50 years. Tools like YACC [10] canautomatically build a parserfroma formal definition ofthe syntax of a lan- guage,usuallybasedoncontext-freegrammars(CFG). Themainmotivationfor automatic parser generation is compiler correctness and recognition complete- ness, since with manual implementation it is very difficult to guarantee that all programs in a given language will be correctly analysed. The parsers that are generated from the language formal definition usually consist of a fixed code driven by a parse table. Different languages are associated with distinct parse tables. With top-down parsers, it is common to produce the code directly as a recursive descent program instead of using parse tables. Extensibleparsers[28]imposenewchallengestoautomaticparsergeneration, since they have to cope with on-the-fly extensions of their own concrete syntax, F.M.Quinta˜oPereira(Ed.):SBLP2014,LNCS8771,pp.1–15,2014. ©SpringerInternationalPublishingSwitzerland2014 2 L.V.S. Reis, V.O. Di Iorio, and R.S.Bigonha requiring that the parser must be dynamically updated. If these changes are frequent, the use of interpretation techniques may be less time-consuming than to reconstruct the parser. Thus, at first, instead of building a fixed code for the parser,itmaybeinterestingtouseaninterpreterforparsingtheinputbasedona suitablerepresentationofthesyntaxofthelanguage,whichmaybedynamically updated. However, this solution is not entirely satisfactory. A mixed approach, compilation and interpretation, offers the best of both worlds. For automatically building a parser, either using code generation or inter- pretation, it is necessary to use a formal model that is powerful enough to ap- propriately describe the syntax of the language, including possible on-the-fly modifications. Adaptable Parser ExpressionGrammar (APEG) [17,18] is a new formalmodel that satisfiesthese requirements.It is basedonPEG(ParsingEx- pressions Grammars) [7], a formalism similar to CFG which formally describes a recursive descent parser. APEG extends PEG with the notion of adaptability, which is implemented by means of operations that allow the own syntax of the languagetobe extended. Inpreviouswork[19], wehaveshownthataprototype interpreterfor APEGallowsthe implementation ofextensible parserswhich are more efficient than the traditional approaches used by other tools. In this work, we discuss a mixed approach for building extensible parsers. Our view is based on the fact that a large part of the syntax of an extensible language is stable, so it is appropriate for a parser whose code can be statically generated. The parts of the syntax specification that are dynamically extended may use grammar interpretation for a more efficient processing. We propose the generation of code for the base syntax, including hooks that may allow an efficient extension, activating an interpreter whenever it is necessary to use the extended syntax. As a proof of concept, wepresent a prototype implementation of a parser generator for APEG. We show that APEG has features which allow an efficient implementation using the proposed mixed approach. Section 2 presents a definition of the APEG model to help understanding the concepts used in the following sections. Section 3 discusses our approach in detail, showing how it works with the APEG model. In Section 4, we describe someefficiencytestswithparsersgeneratedusingthemixedapproach.Section5 lists some works similar to ours. Section 6 presents our final conclusions and discusses future works. 2 Adaptable Parsing Expression Grammar Parsing Expression Grammar (PEG) [7] is a model for describing the syntax of programming languages using a recognition-based approach instead of the generative system typical of context-free grammars (CFG). Similar to CFG, formally a PEG is a 4-tuple (V ,V ,R,S), where V is the set of nontermi- N T N nal symbols, V is the set of terminal symbols and S is the initial symbol. T R is a rule function which maps nonterminals to parsing expressions. A pars- ing expression is very similar to the right hand side of a CFG production rule in the extended Backus-Naur form, except for the addition of two new oper- ators: the not-predicate and the prioritized choice. The not-predicate operator