Design of a Mouldable Programming Language (DMPL)

DMPL is a research project of the Bergen Language Design Laboratory, and centres around exploring ideas of flexibility, adaptability, genericity and robustness (in short, mouldability) in programming languages. As part of the project, we are designing and implementing the prototype mouldable language Magnolia [Bag09], and also putting it to real life testing by developing applications using the language.

The Magnolia Language

Magnolia is designed to support a high level of abstraction, ease of reasoning (for both humans and computers), separation of concerns, and robustness.

Concepts are specifications of abstract data types in Magnolia. A concept consists of one or more abstract types, a set of operations on those types, and a set of axioms specifying the behaviour of the operations. Concepts can require (include) other concepts, and there are a number of operations available for combining and building concepts. A concept can be thought of as similar to an interface in Java (or other similar constructs in other languages) – basically defining the interface of a module – except that concepts also provides a way to give a (loose) formal specification of the module.

Axioms: Our main uses of axioms are in testing [BDH09] and rewriting [BH08], as a ‘light’ use of formal methods. Axiom-based testing employs axioms as test oracles, which are fed with (randomly) generated test data. If an axiom evaluates to false for some data, the implementation does not conform to the specification. With axiom-based rewriting, axioms are used as rewrite rules, allowing the compiler to do algebraic simplifications for any data type. More advanced optimisations can be done by combining rewrite rules with optimisation strategies.

Implementations: Multiple implementations can be provided for the same concept, and one implementation will typically rely on several concepts. For even more flexibility, the same implementation can satisfy different concepts depending on what concepts it is provided with. Implementations can be build and manipulated with operations similar to those available for concepts.

The algorithm-level of the language is similar to a simplified C++, and is used to provide code for implementations. We use a unified algebraic signature style [BH10] for both imperative and expression-style code. A clear distinction is made between procedures (which may change their arguments) and functions (which are ‘pure’, and may not change their arguments). Through the process of functionalisation, procedures are made available as pure functions. The pure function form is relates directly to the style found in specifications and axioms and is also close to the mathematic expression style underlying numerical programming. The inverse process of mutification is applied to the code to turn function calls into procedure calls, which typically require fewer intermediate temporaries and copying of values.

We are also working on the design of

• Constructs for data-dependency driven computation, based on Data-Dependency Algebras (DDAs) [BH09].
• Dependent typing.
• Macros, language extension and transformation facility [Bag10b].
• Error-handling with alerts, which separates the error reporting mechanism from the error handling mechanism, and allows us to deal with partiality in a clean way [BDHK06].

Language Design, Implementation and Specification

As part of the project we’re also working on tools and theory for the specification and implementation of languages. Compiler implementation is done using Rascal Meta Programming Language, Java, and generalised parsing techniques.

The syntax description is modular, allowing for language extension, or even replacing the algorithm-level language while keeping the concept-level language. Both syntax and semantics will be specified formally. To support this effort, we are building tools for generating a compiler frontend from the language specification [Bag10a].

However, merely specifying a language formally, once the golden standard of a well designed language, does not guarantee the language has features that will interact well with each other. Nor does it give any guidance on how to change those features if they become insufficient to solve the problems at hand. In order to meet these challenges, we will also develop a meta-theory for the programming language features. This theory will have to treat concepts and code as building blocks [Hav07].

Language Pragmatics

The language implementation is integrated into the Eclipse IDE, with an editor that supports syntax highlighting and language-specific operations.

We expect to be able to implement a wide range of editing facilities and refactorings, since Magnolia is designed to be easy to analyse and reason about.

Application Development and Maintenance - Validating the Language

The real test for a language, its design and tools, is how well it supports software development and maintenance. An integral part of the project is therefore the development of applications in Magnolia in order to gauge its usefulness and also provide feedback on the language design itself.

Through our earlier work on abstractions for computational science, the SAGA project, specifically the work on coordinate-free numerics [HF09], we have considerable experience in the high performance domain. This is one of our main application domains for Magnolia.

The high performance domain represents important challenges for a language. Its main data sets are huge arrays of simulation data, i.e., the data is not initial or generated in a simple way. The size of the data also challenges efficiency when handling it, and processing it benefits from large scale parallelism on challenging hardware architectures.

Though challenging enough, developing applications in one domain is not sufficient to fully investigate the expressiveness of a language. We are therefore actively seeking partners in new domains that are willing to commit know-how and resources in experimenting with Magnolia.

People and Partners

Staff

• Prof. Magne Haveraaen, project leader
• Dr Anya Helene Bagge, postdoc
• Dr Eva Burrows, postdoc
• Tero Hasu, PhD student
• Dr Helmer André Friis, IRIS - International Research Institute of Stavanger, Stavanger, Norway.

Related People

• Dr Valentin David – language tools and grammars
• Adis Hodzic – language theory
• Master student Lasse Vanebo
• Master student Alexander Rosbach

Partners

• Professor Paul Klint, Dr. Jurgen Vinju
  SEN1 (Software Analysis and Transformation), Centrum Wiskunde en Informatica (CWI), Amsterdam, The Netherlands
• Dr. Eelco Visser
  The Software Engineering Research Group, Department of Software Technology, Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, The Netherlands

References

[Bag09]

Anya Helene Bagge. Constructs & Concepts: Language Design for Flexibility and Reliability. PhD thesis, Research School in Information and Communication Technology, Department of Informatics, University of Bergen, Norway, PB 7803, 5020 Bergen, Norway, 2009. [ www | bib ]

[Bag10a]

Anya Helene Bagge. Language description for front end implementation. In Claus Brabrand and Pierre-Etienne Moreau, editors, Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications, LDTA '10, pages 9:1-9:8, March 2010. ACM. [ bib  | DOI ]

[Bag10b]

Anya Helene Bagge. Yet another language extension scheme. In Mark van den Brand, Dragan Gašević, and Jeff Gray, editors, SLE '09: Proceedings of the Second International Conference on Software Language Engineering, volume 5969 of LNCS, pages 123-132. Springer, March 2010. [ bib | DOI ]

[BDH09]

Anya Helene Bagge, Valentin David, and Magne Haveraaen. The axioms strike back: Testing with concepts and axioms in C++. In GPCE '09: Proceedings of the eighth international conference on Generative programming and component engineering, pages 15-24, New York, NY, USA, 2009. ACM. [ bib | DOI ]

[BDHK06]

Anya Helene Bagge, Valentin David, Magne Haveraaen, and Karl Trygve Kalleberg. Stayin' alert: moulding failure and exceptions to your needs. In GPCE '06: Proceedings of the 5th international conference on Generative programming and component engineering, pages 265-274, New York, NY, USA, 2006. ACM. [ bib | DOI ]

[BH08]

Anya Helene Bagge and Magne Haveraaen. Axiom-based transformations: Optimisation and testing. In Jurgen J. Vinju and Adrian Johnstone, editors, Eighth Workshop on Language Descriptions, Tools and Applications (LDTA 2008), volume 238 of Electronic Notes in Theoretical Computer Science, pages 17-33, Budapest, Hungary, 2009. Elsevier. [ bib | DOI ]

[BH09]

Eva Burrows and Magne Haveraaen. A hardware independent parallel programming model. Journal of Logic and Algebraic Programming, 78:519-538, 2009. [ bib | DOI ]

[BH10]

Anya Helene Bagge and Magne Haveraaen. Interfacing concepts: Why declaration style shouldn't matter. In Torbjörn Ekman and Jurgen J. Vinju, editors, Proceedings of the Ninth Workshop on Language Descriptions, Tools and Applications (LDTA '09), volume 253 of Electronic Notes in Theoretical Computer Science, pages 37-50, York, UK, 2010. Elsevier. [ bib | DOI ]

[Hav07]

Magne Haveraaen. Institutions, property-aware programming and testing. In LCSD '07: Proceedings of the 2007 Symposium on Library-Centric Software Design, pages 21-30, New York, NY, USA, 2007. ACM [ bib | DOI ]

[HF09]

Magne Haveraaen and Helmer André Friis. Coordinate-free numerics: all your variation points for free?. International Journal of Computational Science and Engineering, 4(4):223–230, 2009. [ bib | DOI ]