URI permanente para esta colección:

Artículos en la categoría Lenguajes publicados en las Actas de las XVI Jornadas de Programación y Lenguajes (PROLE 2016).
Notificar un error en esta colección


Envíos recientes

Mostrando 1 - 3 de 3
  • Artículo
    Comparing MapReduce and Pipeline implementations for Counting Triangles
    Pasarella, Edelmira; Vidal, Maria Esther; Zoltan, Cristina. Actas de las XVI Jornadas de Programación y Lenguajes (PROLE 2016), 2016-09-02.
    A common method to define a parallel solution for a computational problem consists in finding a way to use the Divide & Conquer paradigm in order to have processors acting on its own data and scheduled in a parallel fashion. MapReduce is a programming model that follows this paradigm, and allows for the definition of efficient solutions by both decomposing a problem into steps on subsets of the input data and combining the results of each step to produce final results. Albeit used for the implementation of a wide variety of computational problems, MapReduce performance can be negatively affected whenever the replication factor grows or the size of the input is larger than the resources available at each processor. In this paper we show an alternative approach to implement the Divide & Conquer paradigm, named dynamic pipeline. The main features of pipeline are illustrated on a parallel implementation of the well-known problem of counting triangles in a graph. This problem is especially interesting either when the input graph does not fit in memory or is dynamically generated. To evaluate the properties of pipeline, a dynamic pipeline of processes and an ad-hoc version of MapReduce are implemented in the language Go, exploiting its ability to deal with channels and spawned processes. An empirical evaluation is conducted on graphs of different topologies, sizes, and densities. Observed results suggest that pipeline allows for the implementation of an efficient solution of the problem of counting triangles in a graph, particularly, in dense and large graphs, drastically reducing the execution time with respect to the MapReduce implementation.
  • Artículo
    Synthesizing Invariants for Arrays
    Montenegro, Manuel; Nieva, Susana; Peña Marí, Ricardo; Segura, Clara. Actas de las XVI Jornadas de Programación y Lenguajes (PROLE 2016), 2016-09-02.
    Liquid types can be seen as as a computer assisted verification system. Ordinary Hindley-Milner types are qualified by predicates expressing properties. In this way, the programmer may specify the preconditions and postconditions of functions. More importantly, the system infers the types of all the intermediate variables and checks that the verification conditions proving correctness hold. The predicates are currently expressed in a quantifier free decidable logic. Here, we extend Liquid types with quantified predicates of a decidable logic for arrays, propose a concept of an array refinement type, and provide an inference algorithm for this extension. By applying this ideas to several imperative algorithms dealing with arrays, we have been able to infer complex invariants.
  • Artículo
    Processing an Intermediate Representation Written in Lisp
    Peña Marí, Ricardo; Saavedra, Santiago; Sánchez-Hernández, Jaime. Actas de las XVI Jornadas de Programación y Lenguajes (PROLE 2016), 2016-09-02.
    In the context of designing the verification platform CAVI-ART, we arrived to the need of deciding a textual format for our intermediate representation of programs. After considering several options, we finally decided to use S-expressions for that textual representation, and Common Lisp for processing it in order to obtain the verification conditions. In this paper, we discuss the benefits of this decision. S-expressions are homoiconic, i.e. they can be both considered as data and as code. We exploit this duality, and extensively use the facilities of the Common Lisp environment to make different processing with these textual representations. In particular, using a common compilation scheme we show that program execution, and verification condition generation, can be seen as two instantiations of the same generic process.