  From FORTRAN to NumPy, arrays have revolutionized how we express computation.
However, arrays in these, and almost all prominent systems, can only handle
dense rectilinear integer grids. Real world arrays often contain underlying
structure, such as sparsity, runs of repeated values, or symmetry. Support for
structured data is fragmented and incomplete. Existing frameworks limit the
array structures and program control flow they support to better simplify the
problem.
  In this work, we propose a new programming language, Finch, which supports
both flexible control flow and diverse data structures. Finch facilitates a
programming model which resolves the challenges of computing over structured
arrays by combining control flow and data structures into a common
representation where they can be co-optimized. Finch automatically specializes
control flow to data so that performance engineers can focus on experimenting
with many algorithms. Finch supports a familiar programming language of loops,
statements, ifs, breaks, etc., over a wide variety of array structures, such as
sparsity, run-length-encoding, symmetry, triangles, padding, or blocks. Finch
reliably utilizes the key properties of structure, such as structural zeros,
repeated values, or clustered non-zeros. We show that this leads to dramatic
speedups in operations such as SpMV and SpGEMM, image processing, graph
analytics, and a high-level tensor operator fusion interface.
