Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticle


This paper describes a new technique for identifying potentially parallelisable code structures in functional programs. Higher-order functions enable simple and easily understood abstractions that can be used to implement a variety of common recursion schemes, such as maps and folds over traversable data structures. Many of these recursion schemes have natural parallel implementations in the form of algorithmic skeletons. This paper presents a technique that detects instances of potentially parallelisable recursion schemes in Haskell 98 functions. Unusually, we exploit anti-unification to expose these recursion schemes from source-level definitions whose structures match a recursion scheme, but which are not necessarily written directly in terms of maps, folds, etc. This allows us to automatically introduce parallelism, without requiring the programmer to structure their code a priori in 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 to 23 . 79 × the sequential performance on 28 physical cores, or 32 . 93 × the sequential performance with hyper-threading enabled).


Original languageEnglish
Pages (from-to)669-686
JournalFuture Generation Computer Systems
Issue numberPart 2
Early online date27 Jul 2017
Publication statusPublished - Feb 2018

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. A hybrid approach to parallel pattern discovery in C++

    Brown, C. M., Janjic, V., Barwell, A. D., Thomson, J. D., Castañeda Lozano, R., Cole, M., Franke, B., Garcia-Sanchez, J. D., Del Rio Astorga, D. & MacKenzie, K., 1 Dec 2019, (Accepted/In press) 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). IEEE Computer Society

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. Reasoning about non-functional properties using compiler intrinsic function annotations

    Jadhav, S., Roth, M., Falk, H., Brown, C. M. & Barwell, A. D., 6 Nov 2019, Proceedings of the 13th Junior Researcher Workshop on Real-Time Computing. INP ENSEEIHT/IRIT, p. 25-28 4 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Type-driven verification of non-functional properties

    Brown, C. M., Barwell, A. D., Marquer, Y., Minh, C. & Zendra, O., 7 Oct 2019, Proceedings of the 21st International Symposium on Principles and Practice of Programming Languages 2019 (PPDP '19). New York: ACM, p. 1-15 15 p. 6

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Refactoring for introducing and tuning parallelism for heterogeneous multicore machines in Erlang

    Janjic, V., Brown, C., Barwell, A. & Hammond, K., 24 Jun 2019, In : Concurrency and Computation : Practice and Experience. Early View, p. 1-25 25 p., e5420.

    Research output: Contribution to journalArticle

  5. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V., Feb 2018, In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

Related by journal

  1. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y., Feb 2018, In : Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticle

  2. High-Performance Computing in Chemistry; NWChem

    Guest, M. F., Apra, E., Bernholdt, D. E., Fruchtl, H. A., Harrison, R. J., Kendall, R. A., Kutteh, R. A., Long, X., Nicholas, J. B., Nichols, J. A., Taylor, H. L., Wong, A. T., Fann, G. I., Littlefield, R. J. & Nieplocha, J., Dec 1996, In : Future Generation Computer Systems. 12, 4, p. 273-289

    Research output: Contribution to journalArticle

ID: 250572396