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
: ACM SIGPLAN NOTICES
: 50
: 3
: 1
: 10
: 10
: 0362-1340
DOI: https://doi.org/10.1145/2658761.2658762
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.