Lambda calculus with algebraic simplification for reduction parallelisation: Extended study. (5th April 2021)

• Record Type: Journal Article
• Authors: MORIHATA, AKIMASA
• Is Part Of: Journal of functional programming. Volume 31(2021)
• Publication Date: 2021-04-05
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796821000058
• Languages: English
• ISSNs: 0956-7968

Abstract

Abstract: Parallel reduction is a major component of parallel programming and widely used for summarisation and aggregation. It is not well understood, however, what sorts of non-trivial summarisations can be implemented as parallel reductions. This paper develops a calculus named λ AS, a simply typed lambda calculus with algebraic simplification. This calculus provides a foundation for studying a parallelisation of complex reductions by equational reasoning. Its key feature is δ abstraction. A δ abstraction is observationally equivalent to the standard λ abstraction, but its body is simplified before the arrival of its arguments using algebraic properties such as associativity and commutativity. In addition, the type system of λ AS guarantees that simplifications due to δ abstractions do not lead to serious overheads. The usefulness of λ AS is demonstrated on examples of developing complex parallel reductions, including those containing more than one reduction operator, loops with conditional jumps, prefix sum patterns and even tree manipulations.