Parallel prefix (aka scan) is one of the basic algorithms underlying parallel computing, regrouping associative operations as necessary to provide scalability. In this talk, I will demonstrate how to implement parallel prefix as a higher order function in Julia, offering generic scan operations using any user specified function, on any indexable type. Simply by changing the type of the input indexable allows the exact same code to run in parallel as well as in serial. The serialized equivalent program can be introspected in new ways - by passing in a customized array type that logs accesses in getindex and setindex! operations, the algorithm can be made to generate its own visualization. Finally, by passing in formal types that do not contain data, but rather store only the relevant program invariants, we can use multiple dispatch to prove or disprove the correctness of any claimed implementation of parallel prefix.
