  We present the first formalization and metatheory of language soundness for a
user-schedulable language, the widely used array processing language Halide.
User-schedulable languages strike a balance between abstraction and control in
high-performance computing by separating the specification of what a program
should compute from a schedule for how to compute it. In the process, they make
a novel language soundness claim: the result of a program should always be the
same, regardless of how it is scheduled. This soundness guarantee is tricky to
provide in the presence of schedules that introduce redundant recomputation and
computation on uninitialized data, rather than simply reordering statements. In
addition, Halide ensures memory safety through a compile-time bounds inference
engine that determines safe sizes for every buffer and loop in the generated
code, presenting a novel challenge: formalizing and analyzing a language
specification that depends on the results of unreliable program synthesis
algorithms. Our formalization has revealed flaws and led to improvements in the
practical Halide system, and we believe it provides a foundation for the design
of new languages and tools that apply programmer-controlled scheduling to other
domains.
