We present the data parallel programming library Petalisp — an
extension of Common Lisp for data parallel programming. The core of
Petalisp is deliberately simple. It features only a single data structure
— the strided array — and four operations on such strided arrays,
namely element-wise application of functions, reduction with a binary
function, fusion of several arrays and affine-linear reshaping.

The novelty of our approach is that the contents of each strided array
are subject to lazy evaluation and that we delay performance analysis,
optimization and code generation entirely to the run time. In doing so,
we considerably increase the ability of our compiler to make qualified
decisions, at the price of significant run time overhead. We show that
this overhead is manageable and that Petalisp is able to execute several
thousand explicit array evaluations per second.