Download Slides (PDF)

By Prof. Wolfram Kahl, McMaster University, Ontario, Canada

Abstract. "Code graphs, a kind of labelled directed hypergraphs, were originally introduced as generalisation of the ``jungle'' view of term graphs, to accommodate operations with multiple results. Our Coconut project uses nested code graphs as internal representation in a code generation backend, with data-flow graphs labelling control-flow edges. We show how nested code graph transformation rules induced by relation-algebraic laws can be used to justify complex code transformations like software pipelining, which we used to generate the ``Vector MASS'' library included in the Cell-BE SDK. We outline applications of the software pipelining idea to more complex control flow, and the use of a third level of nesting, with the outermost code graphs used as ``distributed-data-flow graphs'' with a semantics inspired by Petri nets.

Code graphs can also be used to represent interaction nets, which can be seen as obtained via simple restriction. This view re-emphasises the polarities originally assigned to interaction net ports by Lafont, restores readability to drawings of interaction nets, and provides an intuitively accessible basis for interaction net semantics. We report on some initial experiments with very direct, polarity-based implementations of interaction net reduction. Although they employ very fine-grained concurrency, they still achieve significant speed-ups. "

Keywords. Term graphs, control-flow graphs, code generation, interaction nets.

A short bio. Wolfram Kahl is an Associate Professor at the Department of Computing and Software, McMaster University, Ontario, Canada. He studied Computer Science in Munich and in Oxford; he obtained his PhD and habilitation from the Federal Armed Forces University Munich. His research interests are in high-level formalisms for correct-by-construction software development, including relation algebra, category theory, graph transformation, functional and dependently-typed programming, and their interactions. He was PC (co-)chair of the RAMiCS conference that just finished in Braga, and of the two preceding RAMiCS conferences. Prof. Khal is involved in RATH-Agda and CalcCheck research projects, and the HOPS project in the past. He has several peer-reviewed journals and conference papers, and he is also teaching several courses in his area of expertise.

Coffee session: at 1:30PM-2PM, Sala de Estar, 4th Floor

Talks session: at 2PM-3PM, Auditório A2, 1st Floor