International Conference on Functional Programming 2017

Generic Functional Parallel Algorithms: Scan and FFT


Listen Later

Conal Elliott, Target, USA United States, gives the third presentation in the second panel, Functional Programming Techniques, in the ICFP 2017 conference. Parallel programming, whether imperative or functional, has long focused on arrays as the central data type. Meanwhile, typed functional programming has explored a variety of data types, including lists and various forms of trees. Generic functional programming decomposes these data types into a small set of fundamental building blocks: sum, product, composition, and their associated identities. Definitions over these few fundamental type constructions then automatically assemble into algorithms for an infinite set of data types--some familiar and some new. This paper presents generic functional formulations for two important and well-known classes of parallel algorithms: parallel scan (generalized prefix sum) and Fast Fourier Transform (FFT). Notably, arrays play no role in these formulations. Consequent benefits include a simpler and more compositional style, much use of common algebraic patterns--such as Functor, Applicative, Foldable, and Traversable--and freedom from possibility of run-time indexing errors. The functional generic style also clearly reveals deep commonality among what otherwise appears to be quite different algorithms. Instantiating the generic formulations to "top-down" and "bottom-up" trees as well as "bushes", two well-known algorithms for each of parallel scan and FFT naturally emerge, as well as two possibly new algorithms.
...more
View all episodesView all episodes
Download on the App Store

International Conference on Functional Programming 2017By Oxford University


More shows like International Conference on Functional Programming 2017

View all
Philosophy for Beginners by Oxford University

Philosophy for Beginners

330 Listeners

Approaching Shakespeare by Oxford University

Approaching Shakespeare

334 Listeners

General Philosophy by Oxford University

General Philosophy

71 Listeners

Aesthetics and Philosophy of Art lectures by Oxford University

Aesthetics and Philosophy of Art lectures

77 Listeners

Theoretical Physics - From Outer Space to Plasma by Oxford University

Theoretical Physics - From Outer Space to Plasma

57 Listeners

Critical Reasoning: A Romp Through the Foothills of Logic by Oxford University

Critical Reasoning: A Romp Through the Foothills of Logic

39 Listeners

The Secrets of Mathematics by Oxford University

The Secrets of Mathematics

41 Listeners

Critical Reasoning for Beginners by Oxford University

Critical Reasoning for Beginners

32 Listeners

Literature and Form by Oxford University

Literature and Form

18 Listeners

CortexCast - A Neuroscience Podcast by Oxford University

CortexCast - A Neuroscience Podcast

4 Listeners