A1 Refereed original research article in a scientific journal
Specializing Planners for Hierarchical Multi-way Dataflow Constraint Systems
Authors: Järvi J, Foust G, Haveraaen M
Publisher: ASSOC COMPUTING MACHINERY
Publication year: 2015
Journal: ACM sigplan notices
Journal name in source: ACM SIGPLAN NOTICES
Journal acronym: ACM SIGPLAN NOTICES
Volume: 50
Issue: 3
First page : 1
Last page: 10
Number of pages: 10
ISSN: 0362-1340
DOI: https://doi.org/10.1145/2658761.2658762(external)
Abstract
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.
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.
UTU Research Portal