Seminar CogniGron - Dr. S.J.C. Joosten

Title: Graph based programming

Abstract:

When writing computer code, the way you choose to structure data has a profound impact on the program you write. Sometimes, a data structure needs to be changed, especially since it might not be known what the right data structure is until the program has been written. To improve this situation, some programmers favor abstractions around your data to allow flexibility in how the data is structured. On the other hand, maintainable code needs to be simple, and using abstractions increases its complexity. Can we have an easy way to change between data structures without introducing abstractions? The work I present provides a way forward.

I show how to describe information with as little structure as possible: as a labeled directed graph (‘the graph’). This simple formalism is expressive enough to describe information that is typically represented as a conventional data structure. The relationship between the conventional data structure and the graph can be described as a tree structure. As evidence for this, I present a tool which generates conversion functions from and to conventional data types using these tree structures. The generated conversion functions change representations, and the presented approach improves code maintainability.

The prime use case of our approach is to chain conversions: take a conventional data structure, convert it into a graph representation, and then back into a different conventional data structure. In such chained conversions, we can sometimes generate the composition directly, without using an intermediate graph representation. This improves the performance of the resulting code. We implemented our ideas using Template Haskell.

We look at two directions for future work. One is to use this approach to generate parsers, which is possible by seeing text as yet another data structure. Another is to add the possibility to specify properties about the graph, which can be used in several ways: to validate data as a runtime verification method, and to augment partial information in the style of logic programming. For both of these ideas, a proof of concept exists as an independent implementation, also written in Haskell.