The Static Semantics of the Green-Marl Graph Analysis Language: Formal Specification, Declarative Implementation and Integration with a Compiler Back-end

The Static Semantics of the Green-Marl Graph Analysis Language: Formal Specification, Declarative Implementation and Integration with a Compiler Back-end

Smits, J.

Wachsmuth, G.H. (mentor)

Electrical Engineering, Mathematics and Computer Science

Software Technology

Software Engineering Research Group

2016-02-04

Green-Marl is a domain specific language for efficient graph analysis. In this thesis, we define the formal static semantics of the language and provide an implementation in the Spoofax language workbench. The type system of Green-Marl includes limited forms of name-dependent types, overloading, parametric polymorphism, and inference. We give a formal specification that covers all aspects of this type system. We also describe our implementation of the type system in the Spoofax language workbench, where we focus on the capabilities of Spoofax's meta-languages to describe the type system. Green-Marl provides several parallel language constructs, as well as constructs to mitigate data races that can occur in parallel regions. We give a formal description of a symbolic, tree-based dependence analysis that can check the invariants of the mitigation strategies and find potential data races. We employ a rewrite system for the implementation of this analysis in the Spoofax language workbench. Finally, we discuss the integration of these analyses with successive program transformation steps. Each transformation step is informed by the static analysis. However, transformation steps invalidate parts of the analysis results, which inhibits the successive steps. A naive approach to re-analyse the program after every transformation step does not scale. Therefore, we incrementally update analysis results after each transformation step.

Green-Marl
compiler
Spoofax
semantics
static semantics
analysis
graph
domain-specific language
dependence

http://resolver.tudelft.nl/uuid:4f07cbbb-d017-41e8-aba6-8ff0c19f258d

Student theses

master thesis

(c) 2016 Smits, J.