A Modular and Statically Typed Effectful Stack for Custom Graph Traversals

Norbert Tausch, Michael Philippsen

Abstract


Programmers often have to implement custom graph traversals by hand as either there are no suitable text-book algorithms for their tasks, or their problems are too complex for a pure querying language that lacks modularity or static typing. Our new Scala-based graph traversal language uses an effectful stack that adapts monads and type classes. Arbitrary graph effect computations and graph processing rules can be defined and composed in a modular and statically typed way. Custom graph traversals become expressible in a concise notation, run both in-memory and on graph databases, and also allow for parallelization. We evaluate the usability of our approach by detecting occurences of an anti-pattern in a Java source code archive. Our approach outperforms the well-known Gremlin approach due to parallelization.

Full Text:

PDF


DOI: http://dx.doi.org/10.14279/tuj.eceasst.68.952

DOI (PDF): http://dx.doi.org/10.14279/tuj.eceasst.68.952.939

Hosted By Universit├Ątsbibliothek TU Berlin.