Skip to main content

Über dieses Buch

This volume presents the revised lecture notes of selected talks given at the 6th Central European Functional Programming School, CEFP 2015, held in July 2015, in Budapest, Hungary.
The 10 revised full papers presented were carefully reviewed and selected. The lectures covered a wide range of functional programming and C++ programming subjects.



Watch Out for that Tree! A Tutorial on Shortcut Deforestation

Functional programmers are strong enthusiasts of modular solutions to programming problems. Since software characteristics such as readability or maintainability are often directly proportional to modularity, this programming style naturally contributes to the beauty of functional programs. Unfortunately, in return of this beauty we often sacrifice efficiency: modular programs rely, at runtime, on the creation, use and elimination of intermediate data structures to connect its components. In this tutorial paper, we study an advanced technique that attempts to retain the best of this two worlds: (i) it allows programmers to implement beautiful, modular programs (ii) it shows how to transform such programs, in a way that can be incorporated in a compiler, into programs that do not construct any intermediate structure.
João Paulo Fernandes, Jácome Cunha, João Saraiva, Alberto Pardo

Functional Reactive Programming in C++

Reactive programming is a relatively new discipline that teaches how to design and develop complex systems through the notion of data-flow. The main idea is that the system, and its components, are able to receive signals, and to react to them in some way. The signals can be seen as streams of messages that we can transform using the usual monadic functions (map, bind, filter, etc.) and that we can easily direct through our system.
Reactive programming removes the usual complexity of explicitly dealing with the shared mutable state, manual synchronization with mutexes, and alike.
We are presenting an approach for implementing reactive systems in the C++ programming language, by creating abstractions over the commonly used methods for achieving concurrency, like callbacks and signals and slots.
Ivan Čukić

Immutables in C++: Language Foundation for Functional Programming

The C++ programming language is a multiparadigm language, with a rich set of procedural, object-oriented, generative and, since C++11, functional language elements. The language is also well-known for its capability to map certain semantic features into the language syntax; therefore, the compiler can reason about them at compile time. Supporting functional programming with immutables is one of such aspects: the programmer can mark immutable components and the compiler checks potential violation scenarios and also optimizes the code according to the constant expectations.
The paper targets the non-C++ programmer audience less familiar with the technical details of C++ immutables and functional elements, as well as those C++ programmers who are interested in the development of the newest standard. We will survey the functional programming features of modern C++. The various types of constants and immutable memory storage will be discussed as well as the rules of const correctness to enable the static type system to catch const violations. Const and static const members of classes represent support for immutables in object-oriented programming. Specific programming tools, like mutable and const_cast enable the programmer changing constness for exceptional cases. Constexpr and relaxed constexpr (since C++14) objects and functions as well as lambda expressions have recently been added to C++ to extend the language support for functional programming. We also discuss the fundamentals of C++ template metaprogramming, a pure functional paradigm operating at compile time working with immutable objects.
Understanding the immutable elements and the rich set of functional language features with their interactions can help programmers to implement safe, efficient and expressive C++ programs in functional style.
Zoltán Porkoláb

Programming in a Functional Style in C++

C++ is a multiparadigm programming language. So the programmer may choose and combine between structural, procedural, object oriented, generic or functional features of C++ to solve his problem. Especially the functional aspect of C++ lambda functions with, type inference and the function std::bind and std::function has grown in modern C++ and is quietly evolving with the next C++ standard.
Rainer Grimm

Functional, Reactive Web Programming in F#

In these lecture notes, we present the basics of functional and reactive web programming through WebSharper, a mature web development framework for F# [7], and its UI.Next [9] library for constructing reactive markup with two-way data binding. You will learn the theory behind similar technologies, discover its advantages, and develop simple applications using the concepts learned.
Adam Granicz, Loic Denuziere

Functional Languages in Design of Coloured Petri Nets Models

Coloured Petri nets are a formal method that allows to create sophisticated event-driven models. In addition, there exists a software tool, called CPN Tools, which provides a support for creation, simulation and state space-based verification of CPN models. An interesting feature of CPN Tools is that it uses CPN ML, a slightly modified version of the SML functional language, for data manipulation. In this chapter we describe basic concepts of Coloured Petri nets (CPN), SML and CPN ML and by means of an example illustrate how CPN ML can be used to build a concrete, timed CPN model from an abstract, low-level Petri net model in such a way that the structure of the abstract model is preserved. We also explore possibilities of already existing SML code utilization in CPN models.
Štefan Korečko

Single Assignment C (SAC)

The Compilation Technology Perspective
Single Assignment C (SaC) is a data parallel programming language that combines an imperative looking syntax, closely resembling that of C, with purely functional, state-free semantics. Again unlike the functional programming mainstream, that puts the emphasis on lists and trees, the focus of SaC as a data-parallel language is on (truly) multi-dimensional arrays. SaC arrays are not just loose collections of data cells or memory address ranges as in many imperative and object-oriented languages. Neither are they explicitly managed, stateful data objects as in some functional languages, may it be for language design or for performance considerations. SaC arrays are indeed purely functional, immutable, state-free, first-class values.
The array type system of SaC allows functions to abstract not only from the size of vectors or matrices but even from the number of array dimensions. Programs can and should be written in a mostly index-free style with functions consuming entire arrays as arguments and producing entire arrays as results. SaC supports a highly generic and compositional programming style that composes applications in layers of abstractions from universally applicable building blocks. The design of SaC aims at combining high productivity in software engineering of compute-intensive applications with high performance in program execution on today’s multi- and many-core computing systems.
These CEFP lecture notes provide a balanced introduction to language design and programming methodology of SaC, but our main focus is on the in-depth description and illustration of the associated compilation technology. It is literally a long way down from state-free, functional program code involving multi-dimensional, truly state-free arrays to efficient execution on modern computing machines. Fully compiler-directed parallelisation for symmetric multi-socket, multi-core, hyper-threaded server systems, CUDA-enabled graphics accelerators, workstation clusters or heterogeneous systems from a single architecture-agnostic source program adds a fair deal of complexity. Over the years, we have developed an intricate program transformation and optimisation machinery for this purpose. These lecture notes provide the first comprehensive presentation of our compilation technology as a whole.
Clemens Grelck

Type-Safe Functions and Tasks in a Shallow Embedded DSL for Microprocessors

The Internet of Things, IoT, brings us large amounts of connected computing devices that are equipped with dedicated sensors and actuators. These computing devices are typically driven by a cheap microprocessor system with a relatively slow processor and a very limited amount of memory. Due to the special input-output capabilities of IoT devices and their connections it is very attractive to execute (parts of) programs on these microcomputers.
Task-oriented programming, as introduced in the iTask framework, offers a very convenient abstraction level to construct distributed programs at a high level of abstraction. The task concept basically introduces lightweight threads. Tasks can be composed to more powerful tasks by a flexible set of combinators. These tasks can communicate with each other via shared data sources and inspect intermediate task values of other tasks.
The IoT devices considered here are far from powerful enough to execute programs made within the standard iTask system. To facilitate the execution of simple tasks using the special capabilities of the IoT devices from the iTask environment, we introduce a type-safe multi-view extendable domain-specific language to specify tasks for IoT devices. This domain specific language is embedded in the iTask system to facilitate the integration of both systems, but those systems are very useful on their own.
Pieter Koopman, Rinus Plasmeijer

Static and Dynamic Visualisations of Monadic Programs

iTasks is a shallowly embedded monadic domain-specific language written in the lazy, functional programming language Clean. It implements the Task-Oriented Programming (TOP) paradigm. In TOP one describes, on a high level of abstraction, the tasks that distributed collaborative systems and end users have to do. It results in a web application that is able to coordinate the work thus described. Even though iTasks is defined in the common notion of “tasks”, for stake holders without programming experience, textual source code remains too difficult to understand. In previous work, we introduced Tonic (Task-Oriented Notation Inferred from Code) to graphically represent iTasks programs using blueprints. Blueprints are designed to bridge the gap between domain-expert and programmer. In this paper, we add the capability to graphically trace the dynamic behaviour of an iTasks program at run-time. This enables domain experts, managers, end users and programmers to follow and inspect the work as it is being executed. Using dynamic blueprints we can show, in real-time, who is working on what, which tasks are finished, which tasks are active, and what their parameters and results are. Under certain conditions we can predict which future tasks are reachable and which not. In a way, we have created a graphical tracing and debugging system for the TOP domain and have created the foundation for a tracing and debugging system for monads in general. Tracing and debugging is known to be hard to realize for lazy functional languages. In monadic contexts, however, the order of evaluation is well-defined, reducing the challenges Tonic needs to overcome.
Jurriën Stutterheim, Peter Achten, Rinus Plasmeijer

Analyzing Scale-Free Properties in Erlang and Scala

The optimal modularization and the right level of coupling between components are important for the overall quality of software systems. Although the generic suggestion is to minimize the coupling between modules, earlier research on object-oriented programming showed that there is a natural limit to eliminating dependencies between classes. In our research we extend these findings for non-OOP systems and show that this limitation seems to be paradigm-independent. For this purpose we define paradigm-agnostic metrics for coupling and evaluate them. Our results, measuring Scala and Erlang sources, prove that the coupling behavior shows scale-free properties. Our contribution could be useful to avoid unnecessary or harmful code refactors to chase overall low coupling in systems.
Gábor Oláh, Gergely Nagy, Zoltán Porkoláb


Weitere Informationen

Premium Partner