Généricité | EPFL Graph Search

En programmation, la généricité (ou programmation générique), consiste à définir des algorithmes identiques opérant sur des données de types différents. On définit de cette façon des procédures ou des types entiers génériques. On pourrait ainsi programmer une pile, ou une procédure qui prend l'élément supérieur de la pile, indépendamment du type de données contenues. C'est donc une forme de polymorphisme, le « polymorphisme de type » dit aussi « paramétrage de type » : en effet, le type de donnée général (abstrait) apparaît comme un paramètre des algorithmes définis, avec la particularité que ce paramètre-là est un type. C'est un concept important pour un langage de haut niveau car il permet d'écrire des algorithmes généraux opérant sur toute une série de types : la généricité augmente donc le niveau d'abstraction des programmes écrits dans un langage qui possède cette fonctionnalité. Divers mécanismes ont été conçus pour permettre la programmation générique. Polymorphisme

Extending Safe C Support In Leon

Marco Adriano Antognini

As hardware designs get more robust and efficient, software can solve a wider range of challenges, each one more advanced than the previous one. The direct consequence is that software complexity grows continuously. Despite being used more frequently in development processes, traditional testing frameworks are not enough to avoid flaws in programs. Moreover, many company concerned by the security of their applications, especially in mission critical industries, spend a considerable effort and amount of money to write robust software certified by solid guidelines and standards. For embedded systems, MISRA C is a certification process commonly used which provides directives to write portable and maintainable C code while avoiding many pitfalls of the language. Leon takes an orthogonal approach by providing tools for formal verification of programs written in a subset of Scala. In a previous work we introduced GenC, a module for Leon that converts Scala applications into equivalent and safe C99 programs, allowing developers to leverage high-level feature of Scala to implement robust applications, even for embedded systems. The aim of this project is to augment Leon and GenC in order to support a larger fragment of Scala that includes inheritance, generic programming, additional numeric types, pattern matching and more. Additionally, we closely analyse the MISRA Guidelines and shape the generated C code to work towards compliance with its rules while taking advantage of the verification capabilities of Leon to automatically detect a variety of bugs. We discuss these improvements and new features by implementing the famous LZW compression/decompression algorithm as well as a kernel-based image processing algorithm and show that the produced native C programs are significantly more efficient both in terms of memory usage but also in terms of execution speed.

2017

Miniboxing: An Encoding for Specialization

Cristian Talau

In the presence of parametric polymorphism, erasure-based languages such as Java and Scala handle primitives (boolean values, integers and floating point numbers) in a suboptimal way: in order to provide a uniform representation on the low level, all primitive values are stored in heap objects, in a process known as boxing. This leads to access overheads, wasteful usage of the heap space and broken cache locality. Specialization enables Scala to optimally handle primitive values in the context of generic classes, but this is done at the expense of duplicating classes up to 10 times for each type parameter, for each of the 9 Scala primitive types and heap objects. This prevents specialization of key classes in the Scala library, such as Function2, List, Map and so on. This project aims at testing the hypothesis that encoding several primitive types into a larger stack-based primitive type can maintain the performance of specialized code, while dramatically decreasing the generated bytecode size.

2012

Compiling Scala for Performance

Iulian Dragos

Scala is a new programming language bringing together object-oriented and functional programming. Its defining features are uniformity and extensibility. Scala offers great flexibility for programmers, allowing them to grow the language through libraries. Oftentimes what seems like a language feature is in fact implemented in a library, effectively giving programmers the power of language designers. The downside of this flexibility is that familiar looking code may hide unexpected performance costs. It is important for Scala compilers to bring down this cost as much as possible. We identify several areas of impact for Scala performance: higher-order functions and closures, and generic containers used with primitive types. We present two complementary approaches for improving performance in these areas: optimizations and specialization. Compiler optimization can bring down the cost through a combination of aggressive inlining of higher-order functions, an extended version of copy-propagation and dead-code elimination. Both anonymous functions and boxing can be eliminated by this approach. We show on a number of benchmarks that these language features can be up to 5 times faster when properly optimized, on current day JVMs. We propose a new approach to compiling parametric polymorphism for performance at primitive types. We mix a homogeneous translation scheme with user-directed specialization for primitive types. Type parameters may be annotated to require specialization of code depending on them. We propose definition-site specialization for primitive types, achieving separate compilation and no boxing when both the definition and call site are specialized. Specialized classes are compatible with unspecialized code, and specialization agnostic code can work with specialized instances, meaning that specialization is opportunistic. We present a formalism of a small subset of Scala with specialization and prove that specialization preserves types. We implemented this translation in the Scala compiler and report on improvements on a set of benchmarks, showing that specialization can make programs more than two times faster.

EPFL2010

Compiling Scala for Performance

Iulian Dragos

EPFL2010