Design of a dependency-directed compiler for constraint propagation
Roy Feldman · 1988
This paper describes COCO (COnstraint COmpiler), an optimizing compiler for a constraint language embedded within a frame system. The approach to constraint optimization is based on the following observation: when there are multiple inputs to a constraint network the order in which changes are propagated affects overall computational cost. Any uniform algorithm for propagating values through a network that does not take into account data dependencies will produce sub-optimal results. COCO performs a dependency-based partitioning of constraints, allowing it to group constraints to obtain efficiency gains by merging equivalent computations. This helps to produce code that propagates constraints with a minimum of run-time overhead. We will illustrate the design of COCO and its relationship to other work.