We begin with a tour of different kinds of declarative programming and how to use them.  In each case we'll give you a version you can try out interactively in your browser; when you see a box around some code:

# Try: [Hello]
Hello: Hello world!

you can click it to experiment with it in a sandbox.  If you find declarative programming appealing, you can either include the systems here in your games — they're open source — or you can read Part II for a discussion of how to build your own solvers.

Types of declarative programming

Again, declarative programming is a family of techniques that let you describe how to recognize solutions to a problem rather than how to generate them.  The types vary based on how they let you describe problems:

• Grammars describe artifacts in terms of the pieces that comprise them, and options for the pieces which may themselves involve more pieces, which may have more pieces, etc.  The artifacts can be quests, NPC dialog, or 3D models of vegetation.
• Constraint programming involves specifying the problem in terms of a set of variables, their allowable values, and relationships between their values, called constraints.  For example, given a set of tasks to do for the week, choose what days you'll do them, subject to the constraints that you can only do three tasks a day and some tasks can only be done certain sets of days.
• Planning involves describing the current state of the world, the desired state of the world, and how different actions change the state of the world.  The solver — called a planner — then finds a sequence of actions that will leave the world in the desired state.
• Clairvoyant programming is the most general class of techniques.  It essentially lets you provide an arbitrary program to say “yes, this is what I want” or "no, not this."  The name for this in the academic literature is nondeterministic programming, but for reasons we'll explain momentarily, we'll refer to it as clairvoyant programming.

Generally speaking, the techniques early in the list are the most limited in the kinds of problems they can describe; grammars are very restrictive, whereas clairvoyant programming can be used to decribe any problem.¹  On the other hand, the narrow techniques, such as constraint programming, can take advantage of specialized solvers to solve them very efficiently.

Choice

Under the hood, all these techniques involve making a series of choices from prescribed options and recognizing when combinations of choices don't work.  The solver's job is to find a combination of choices that works.  For some types of declarative programming, the choices and the limitations on them are explicit parts of the problem description.  For example, in constraint programming, the choices are the values of the variables and the constraints directly specify how to recognize good and bad combinations.  For other types of systems, such as logic programming, the choices are implicit in structure of the program. 

Notes