Finding parallel functional pearls: Automatic parallel recursion scheme detection in Haskell functions via anti-unification

摘要

AbstractThis paper describes a new technique for identifying potentially parallelisable code structures in functional programs.Higher-order functionsenable simple and easily understood abstractions that can be used to implement a variety of commonrecursion schemes, such asmapsandfoldsover traversable data structures. Many of these recursion schemes have natural parallel implementations in the form ofalgorithmic skeletons. This paper presents a technique that detects instances of potentially parallelisable recursion schemes in Haskell 98 functions. Unusually, we exploitanti-unificationto expose these recursion schemes from source-level definitions whose structures match a recursion scheme, but which are not necessarily written directly in terms ofmaps,folds, etc. This allows us to automatically introduce parallelism, without requiring the programmer to structure their codea prioriin terms of specific higher-order functions. We have implemented our approach in the Haskell refactoring tool, HaRe, and demonstrated its use on a range of common benchmarking examples. Using our technique, we show that recursion schemes can be easily detected, that parallel implementations can be easily introduced, and that we can achieve real parallel speedups (up to23.79×the sequential performance on 28 physical cores, or32.93×the sequential performance with hyper-threading enabled).Highlights•We present a technique using anti-unification to discover recursion schemes in Haskell functions.•We present a new, specialised anti-unification algorithm.•We have implemented our approach using the Haskell refactoring tool HaRe.•We have demonstrated our approach on a range of standard examples.•Our technique is in principle completely general, able to discover arbitrary patterns in code.