Jeffrey Bosboom's Blog

[blog] [projects] [about]

PLDI 2013 trip report, part 4

There was no keynote on the third day.

Reconciling Exhaustive Pattern Matching with Objects

ACM DL, gratis PDF, JMatch Web page, my notes

JMatch is a Java extension supporting pattern-matching as in functional languages. This paper describes further development of JMatch to allow matching on types with multiple implementations (for example, both ArrayList and LinkedList can be able to match against nil() and cons(x, xs)). Using additional declarations of the relationships between constructors and the objects they produce, an SMT solver can verify the matches in a switch statement are exhaustive and non-redundant. (The paper presents quite a bit of machinery to make this work.)

I was left wondering why, once you include a language for expressing which objects a case will match, JMatch still uses named constructors for its matches. In the nil() and cons(x, xs) example, why not annotate List.isEmpty and List.subList to allow matches like

    switch (list) {
        case list.isEmpty():
            /* ... */
            break;
        case (x = list.get(0), xs = list.subList(1, list.size())):
            /* ... */
            break;
    }

The compiler can infer these cases are exhaustive and non-redundant just as well as nil() and cons(x, xs), without adding boilerplate named constructors to the List interface and all its implementations.

Halide: A Language and Compiler for Optimizing Parallelism, Locality and Recomputation in Image Processing Pipelines

ACM DL, gratis PDF, Halide Web page, my notes

Halide is a domain-specific language for image processing. Programs in this domain are stream programs whose actors are multidimensional stencils. Written by hand, these programs are very difficult and expensive to tune for performance due to the use of vectorization intrinsics and the importance of fusing adjacent actors for locality, and the resulting code is tuned for one architecture or instruction set only. To allow the same code to perform well on multiple architectures, Halide separates the algorithm (what to do) from the schedule (what order to do it in). Halide algorithms are written in a functional style with all data dependencies exposed, without vectorization or other optimizations. The schedule separately defines loop nests, tiling, and the granularity of vectorization or parallelism, trading off between parallelism, locality, and the introduction of redundant work (to remove synchronization). Schedules can be hand-tuned, but Halide also includes an autotuner for automatically generating schedules. The resulting autotuned schedules result in considerably higher performance compared to hand-tuned code written by Adobe programmers, with much less programmer effort.

The Halide paper explicitly compares the image processing domain with stream programming, noting that stream programs are primarily concerned with 1D stencils and don’t support higher dimensions well. I am interested in if and how introducing redundant work might be useful for stream programs, as it usually isn’t considered.

Notes from other talks

P: Safe Asynchronous Event-Driven Programming, Quipper: A Scalable Quantum Programming Language, Hybrid Context-Sensitivity for Points-To Analysis, Fast Algorithms for Dyck-CFL-Reachability with Applications to Alias Analysis, Static Analysis for Probabilistic Programs: Inferring Whole Program Properties from Finitely Many Paths, A General Constraint-centric Scheduling Framework for Spatial Architectures, Steal Tree: Low-Overhead Tracing of Work Stealing Schedulers

That’s all of the talks from PLDI proper, but there were a few interesting papers in the co-located workshops, which I’ll comment on next time.