A high-level intermediate language and the algorithms for compiling finite-domain constraints
Neng‐Fa Zhou · 1998
In this paper, we present a high-level intermediate language, called delay-Prolog, for implementing CLP(FD), the constraint language over finite-domains. Delay-Prolog has a much stronger description power than indexical, the intermediate language widely used in current finite-domain constraint compilers. It is powerful enough for describing all kinds of constraint propagation procedures, which by now have been mostly written in low level languages. And, most importantly, delay-Prolog opens new ways to compiling constraints. Besides the indexical algorithm that compiles constraints into indexicals, we implemented two new algorithms: the wait algorithm that compiles a constraint as whole into a propagation procedure without splitting it into small pieces, and the incremental simplification algorithm that incrementally simplifies constraints into smaller ones. The results are noteworthy: The wait algorithm generates the fastest code, while the widely used indexical algorithm generates cod...