A typed parallel \(\lambda\)-calculus for graph-based communication

Abstract

We introduce \(\lambda_{\parallel}\) - a simple yet powerful parallel extension of simply typed \(\lambda\)-calculus. \(\lambda_{\parallel}\) is extracted by Curry-Howard correspondence from logics intermediate between classical and intuitionistic logic. Its types are liberal enough to allow arbitrary communication patterns between parallel processes, while guaranteeing that any reduction strategy is terminating. \(\lambda_{\parallel}\) is equipped with an algorithm to extract typing rules from any graph-specified communication topology in such a way that the typed terms can only communicate according to the topology. The expressive power of our language is showcased by examples of parallel programs, ranging from numeric computation to algorithms on graphs.