Multi-phase computation as an applicative functor [video]
youtube.com
youtube.com
> It is 50 years since Tony Hoare observed “certain close analogies between the methods used for structuring data and the methods for structuring a program which processes that data”. But programs have both static structure (following the data) and dynamic structure (execution), and these need not coincide. For example, breadth-first tree traversal should be executed across the grain of the tree structure. I will present a technique for resolving the tension between these conflicting forces: the static structure specifies a multi-phase computation, whose dynamic execution structure might be entirely different. The appropriate abstraction turns out to be an applicative functor - similar to but different from the free applicative.
> This is joint work with Oisin Kidney, Tom Schrijvers, and Nicolas Wu.
Related paper:
Phases in Software Architecture (architectural pearl) - The First ACM SIGPLAN Workshop on Functional Software Architecture - FP in the Large - http://www.cs.ox.ac.uk/jeremy.gibbons/publications/phases.pd... - https://icfp23.sigplan.org/details/funarch-2023/5/Phases-in-...
> The large-scale structure of executing a computation can often be thought of as being separated into distinct phases. But the most natural form in which to specify that computation may well have a different and conflicting structure. For example, the computation might consist of gathering data from some locations, processing it, then distributing the results back to the same locations; it may be executed in three phases—gather, process, distribute—but mostly conveniently specified orthogonally—by location. We have recently shown that this multi-phase structure can be expressed as a novel applicative functor (also known as an idiom, or lax monoidal functor). Here we summarize the idea from the perspective of software architecture. At the end, we speculate about applications to choreography and multi-tier architecture.
https://www.youtube.com/watch?v=D4BqCwck0s0
Really recommend this video playlist. Really well explained!