What Are Constraints in GNU Prolog and How Does the Finite Domain Solver Work?

Updated

In GNU Prolog, a constraint is a relation you state over finite-domain (FD) variables, and the built-in FD solver propagates that relation to prune the values each variable can still take. You write ordinary Prolog plus constraints; GNU Prolog accepts the combined "Prolog+constraint" program and can compile it to a stand-alone native binary. This page explains the mechanism and the workflow; for the exact list of predefined constraints and solver predicates, use the GNU Prolog manual linked from the site.

Constraint logic programming and finite domains

Constraint logic programming (CLP) extends logic programming by letting you state relations over variables rather than enumerate assignments yourself. In the finite-domain variant, each variable ranges over a finite set of integers. Instead of generating and testing candidate values, the solver reasons about the domains and removes values that cannot satisfy the posted constraints.

GNU Prolog includes "an efficient constraint solver over Finite Domains (FD)," which the site describes as opening constraint logic programming to the user by "combining the power of constraint programming to the declarativity of logic programming." The solver is characterized as "very efficient" and "comparable to commercial solvers."

How FD variables integrate with Prolog

The integration is deliberately transparent:

  • FD variables are "well integrated into the Prolog environment (full compatibility with Prolog variables and integers)."
  • There is "no need for explicit FD declarations" — you do not have to pre-declare a variable as finite-domain before constraining it.
  • High-level constraints "can be described in terms of simple primitives," and the system ships with "a lot of predefined constraints."

The practical consequence: you can mix FD variables with ordinary Prolog variables and integers in the same program, and add constraints as goals, without a separate declaration layer.

From a Prolog+constraint program to a native executable

GNU Prolog is a compiler, not only an interpreter. The workflow the site describes:

  1. Write a Prolog+constraint program — Prolog clauses plus FD constraints.
  2. Compile it with the command-line compiler, which accepts "a wide variety of files: Prolog files, C files, WAM files,..." and generates assembly code directly.
  3. Get a stand-alone executable. Because "most of unused built-in predicates are not linked," the binary "can be quite small."

Alongside native compilation, GNU Prolog offers "a classical interactive interpreter (top-level) with a debugger," so you can develop and test interactively before compiling.

What the Prolog side provides

The surrounding system matters because constraints live inside it:

  • Conformance to the ISO standard for Prolog (floating point numbers, streams, dynamic code, and more).
  • Extensions useful in practice: global variables, definite clause grammars (DCG), sockets interface, operating system interface.
  • More than 300 built-in predicates.
  • A Prolog debugger and a low-level WAM debugger.
  • A "powerful bidirectional interface between Prolog and C."

Reported performance: compiled (native-code) predicates are "as fast as wamcc on average," consulted (byte-code) predicates are "5 times faster than wamcc," and assembly generation is "15 times faster than wamcc + gcc."

Where to find the predefined constraints

The site's feature list states there are "a lot of predefined constraints" but does not enumerate them in the excerpt available here. The authoritative list of predefined constraints and solver predicates is in the Manual, which is a section of the GNU Prolog web site. Treat the manual as the reference for exact predicate names and semantics rather than inferring them from this overview.

Practical takeaways

  • Constraints in GNU Prolog are FD relations posted over variables that range over finite integer sets; the solver propagates them to reduce domains.
  • You do not declare FD variables explicitly — they are compatible with ordinary Prolog variables and integers.
  • You can develop in the interactive top-level and then compile to a stand-alone native binary.
  • Current stable version listed on the site: gprolog-1.5.0.
  • For the concrete constraint vocabulary, consult the Manual section of gprolog.org.