You are here: Home PIK Members Daniel Lincke A transformational approach to generic programming

A transformational approach to generic programming

Welcome

On this page, we provide tools, examples, and background material for a transformational approach to generic programming based on functional higher-order type specifications. The material can help you implementing (generic) libraries in C++ or other languages from functional prototypes.

 

Introduction

Functional languages, in particular Haskell, are known for their capabilities for rapid prototyping [1]. However, practitioners of high-performance scientific computing often are still in favor of languages like C++, which allow a high degree of abstraction as well as low-level implementations of performance-critical computations. An important task in scientific programming is therefore the re-implementation of prototype libraries in scientific-programming languages.

In the case of generic libraries, the coding of type signatures of functions proves to be rather difficult, especially in the case of higher-order typed signatures (which make use of higher-order functions and higher-order type constructors) as they often cannot directly be implemented in a non-functional language. One possibility for representing higher-order types in other languages provide concepts, which can be implemented, for example, as C++ concepts or Scala Interfaces.

To avoid the error-prone hand-coding of such signatures, we provide tools for a transformational approach. Function signatures like the following signature of the datatype-generic fold function

fold :: Bifunctor s => (s a b -> b) -> Fix s a -> b

 can be automatically translated into the following C++ class signatures:


template<class s, class a, class fun1>
requires
Bifunctor2<s>, Function<fun1>,
SameType<fun1::Domain1, s::Apply<a, fun1::Codomain> >,
TypeConstructor2<s>
struct Fold_codomain1 {

typedef Fix<s, a> Domain1;
typedef typename fun1::Codomain Codomain;

Codomain operator() (Domain1 fix_s_a) {
}
};


template<class s, class a, class fun1>
requires
Bifunctor2<s>,
Function<fun1>,
SameType<fun1::Domain1, s::Apply<a, fun1::Codomain> >,
TypeConstructor2<s>
struct Fold {

typedef fun1 Domain1;
typedef Fold_codomain1<s, a, fun1> Codomain;

Codomain operator() (Domain1 f) {
}
};

The transformation replaces higher-order functions in the domain type by type parameters and those in the codomain type by a new type that implements exactly the signature of the higher-order function. Other type constructors are uncurried and higher-order type constructors are encoded by concepts. A final optimization step ensures that the number of introduced type parameters is as small as possible.

The transformation is implemented in a signature compiler. While its input language is a simplified subset of Haskell, its target languages (currently) are concept-C++, generic Haskell, and Scala.

Once the type signatures are transformed (and implemented), the implementation of the function body itself (which has to be done by hand) is usually rather simple.

 

Applications

We used the transformation in several applications. In all these applications, we wrote a functional prototype of a generic library in Haskell and implemented it as a fully working generic library in C++.

Our first application concerns the C++-backend-library itself. This library, called Functional C++ with Concepts (FCPPC), provides the necessary concepts for function types and type constructors, and in addition some useful concepts for type classes like Functor and Monad. We used the transformation to generate the type signatures for additional useful operations like function composition and currying.

Our second application is a generic library for monadic dynamical systems, which are a useful model for socio-ecologic systems, which are a useful model for socio-ecologic systems and involved in various studies in sustainability research [2]. The prototypical implementation of the library was used to generate C++ type signatures for the functions involved into trajectory computations for monadic dynamical systems. We implemented the body of these functions by hand to obtain a fully operational generic C++ library.

In a third application, we implemented a generic library for recursive datatypes in C++.  We used a Haskell prototype of a library that provides a generic fix point type for recursive datatypes and recursion operators for them, better known as the Origami operators [3]. We generated the type signatures of these operators in C++ and implemented them. To provide a fully operational library, we also implemented some recursive datatypes in the library. While the Origami approach to generic programming is popular in the functional programming community, in C++ no such library was available before.

In the future, we will try to use our approach to re-implement other generic programming methods in C++, one promising example is the scrap-your-boilerplate approach [4].

 

Downloads 

The specification-compiler (coming soon)

FCPPC: Haskell type declarations, specification-compiler output and the library

MonSys: Haskell type declarations, specification-compiler output and the library

Origami++: Haskell type declarations, specification-compiler output and the library

 

Publications

D. Lincke, C. Ionescu, N. Botta: A generic library for earth system modeling based on monadic systems. Proceedings of the Digital Earth Summit on Geoinformatics 2008.

D. Lincke, P. Jansson, M. Zalewski, C. Ionescu: Generic Libraries in C++ with Concepts from High-Level Domain Descriptions in Haskell. A Domain-Specific Library for Computational Vulnerability Assessment. In: Taha, Walid Mohamed (Ed.), Domain-Specific Languages, Proceedings of the IFIP TC 2Working Conference, DSL 2009, Oxford, UK, July 15-17 2009.

D. Lincke, S. Schupp: The Function Concept in C++ - An Empirical Study. In: J. Gibbons, R. Paterson (Ed.), WGP’09: Proceedings of the 2009 ACM SIGPLAN workshop on Generic programming, Edinburgh, UK, August 30, 2009.

D. Lincke, S. Schupp: From HOT to COOL - Transforming Higher-Order Typed Languages to Concept-Constrained Object-Oriented Languages. In:  A. Sloane and S. Andova (Ed.), Proceedings of the12th Workshop on Language Descriptions, Tools and Applications, LDTA 2012, Tallinn, Estonia, March 31 - April 1, 2012.

 

License

Copyright © 2007-2011 by Daniel Lincke. Permission to use, copy, modify, and distribute this software and its documentation under the terms of the GNU General Public License is hereby granted. No representations are made about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty. See the GNU General Public License for more details.

 

References

[1] Paul Hudak and Mark P. Jones. Haskell vs. Ada vs. C++ vs awk vs ... An experiment in software prototyping productivity. Technical report (YALEU/DCS/RR-1049), Department of Computer Science, Yale University, 1994.

[2] Cezar Ionescu. Vulnerability modelling and monadic dynamical systems. Ph.D. thesis, Freie Universität Berlin, 2009. Available from http://www.diss.fuberlin.de/diss/receive/FUDISS_thesis_000000008403.

[3] Jeremy Gibbons. Datatype-generic programming. In Roland Backhouse, Jeremy Gibbons, Ralf Hinze, and Johan Jeuring, editors, Spring School on Datatype-Generic Programming, volume 4719 of Lecture Notes in Computer Science. Springer-Verlag, 2007.

[4] Ralf Laemmel and Simon Peyton Jones: Scrap your boilerplate: a practical approach to generic programming, Proc ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI 2003), New Orleans, pp26-37, Jan 2003.

Document Actions