Specializing Planners for Hierarchical Multi-way Dataflow Constraint Systems

: Järvi J, Foust G, Haveraaen M

Publisher: ASSOC COMPUTING MACHINERY

: 2015

: ACM sigplan notices

: ACM SIGPLAN NOTICES

: 50

: 3

: 1

: 10

: 0362-1340

DOI: https://doi.org/10.1145/2658761.2658762(external)

A constraint system consists of variables and a set of constraints on those variables. To solve a constraint system is to find a valuation that satisfies all constraints; or the "best" subset of constraints if not all can simultaneously be satisfied. In a multi-way dataflow constraint system, solving requires selecting a set of user-defined functions which, when executed, will enforce the constraints. The task of selecting these functions is called planning. The planner has two kinds of input: the specification of the constraints and an order of priority for those constraints. The former typically changes seldom, while the latter frequently, making constraint planning a potential application for program specialization. This paper shows how to generate specialized planners for hierarchical multi-way dataflow constraint systems when the constraints are known in advance. The specialized planners are DFAs; they can be an order of magnitude or more faster than a general purpose planner for the same system. Our applications for constraint systems are in user interface programming, where constraint systems determine how a GUI should react to user interaction-specialized planners can help to ensure that GUIs' responses to user interaction are instantaneous.