A Modular and Statically Typed Effectful Stack for Custom Graph Traversals

Authors

  • Norbert Tausch University Erlangen-Nuremberg Programming Systems Group
  • Michael Philippsen University Erlangen-Nuremberg Programming Systems Group

DOI:

https://doi.org/10.14279/tuj.eceasst.68.952

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.

Downloads

Published

2014-10-07

How to Cite

[1]
N. Tausch and M. Philippsen, “A Modular and Statically Typed Effectful Stack for Custom Graph Traversals”, eceasst, vol. 68, Oct. 2014.