Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McMaster University

$20,000.00

Towards "Mouldable Code" as a Better Approach to Synthesis of Efficient and Correct Software

FY 2020-21

Summary
Important parts of the supporting infrastructure for optimising code generators, in particular in compilers, consist of analyses of graphs, especially control-flow graphs and data-flow graphs. In addition, many of the optimisations enabled by these analyses are usefully understood as graph transformations. Interestingly, the program transformation literature almost exclusively concentrates on transformation of (higher-order) abstract syntax trees. This corresponds to the usual approach in a compiler context to first parse the given programs into abstract syntax trees, and then extract from these the necessary information to construct the graphs to be used for data-flow and control-flow analyses, while still considering the abstract syntax trees as the internal representation of the program. However, many of the transformations that are used for code optimisation, in particular in the back-ends of compilers, act on patterns that can usefully be thought of as graph patterns, and the resulting transformations are frequently explained in the literature as graph transformations applied to control-flow graphs and data-flow graphs. In this research programme, I aim to create the theoretical justifications for control-flow graph transformation and data-flow graph transformations by linking the theories of control-flow and data-flow semantics with appropriate theories of graph transformation and build on these foundations a mechanised framework for nested code graph transformation. The goal of this framework is to be the first representative of a new class of mechanised environments in which experts can design special-purpose optimisation passes in a graph-based formalism that captures the intuitive graph-based descriptions of optimisation passes as they are customary in the compiler literature. However, while the graph-based descriptions in the literature are technically completely informal, the envisaged mechanised system will support not only capturing the design itself, but also proving the correctness of these optimisations at a level that is conceptually close to the design, and will finally also automatically generate correct-by-construction implementations of these optimisation passes.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-05684
Name nom
Kahl, Wolfram
Department département
Dept. of Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2017
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2706
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Software engineering
Research subject fr
Génie logiciel
Installment
inst:4-5
Partie
2
Nb partie
5
Application title
Towards "Mouldable Code" as a Better Approach to Synthesis of Efficient and Correct Software
Keyword
NSERC
Application summary
Important parts of the supporting infrastructure for optimising code generators, in particular in compilers, consist of analyses of graphs, especially control-flow graphs and data-flow graphs. In addition, many of the optimisations enabled by these analyses are usefully understood as graph transformations. Interestingly, the program transformation literature almost exclusively concentrates on transformation of (higher-order) abstract syntax trees. This corresponds to the usual approach in a compiler context to first parse the given programs into abstract syntax trees, and then extract from these the necessary information to construct the graphs to be used for data-flow and control-flow analyses, while still considering the abstract syntax trees as the internal representation of the program. However, many of the transformations that are used for code optimisation, in particular in the back-ends of compilers, act on patterns that can usefully be thought of as graph patterns, and the resulting transformations are frequently explained in the literature as graph transformations applied to control-flow graphs and data-flow graphs. In this research programme, I aim to create the theoretical justifications for control-flow graph transformation and data-flow graph transformations by linking the theories of control-flow and data-flow semantics with appropriate theories of graph transformation and build on these foundations a mechanised framework for nested code graph transformation. The goal of this framework is to be the first representative of a new class of mechanised environments in which experts can design special-purpose optimisation passes in a graph-based formalism that captures the intuitive graph-based descriptions of optimisation passes as they are customary in the compiler literature. However, while the graph-based descriptions in the literature are technically completely informal, the envisaged mechanised system will support not only capturing the design itself, but also proving the correctness of these optimisations at a level that is conceptually close to the design, and will finally also automatically generate correct-by-construction implementations of these optimisation passes.