Refereed journal article or data article (A1)

Specializing Planners for Hierarchical Multi-way Dataflow Constraint Systems

List of Authors: Järvi J, Foust G, Haveraaen M


Publication year: 2015

Journal: ACM sigplan notices

Journal name in source: ACM SIGPLAN NOTICES

Journal acronym: ACM SIGPLAN NOTICES

Volume number: 50

Issue number: 3

Number of pages: 10

ISSN: 0362-1340


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.

Last updated on 2021-24-06 at 09:58