Specification

NDL is a strongly-typed declarative language describing both constraint programming problem structure and neighbor operators.

Syntax

There are three types of atoms in the NDL language:

• integers, i.e. 0
• variables with Prolog syntax, i.e. X, Variable, _OtherVariable
• variable indexes, that are terms with arity depending on the variable dimensionality, i.e. for a 2-dimension array of variable named queen, the variable's index takes form queen(<integer>, <integer>), i.e. queen(1,1).

Additionaly string constants (lower case, as name) and the integer ranges (written as 0..10) are used as a syntax sugar in model definitions, but aren't used in the NDL query itself.

Type system

There are three kinds of types in the language:

• constants - named integers, represented as term const/1, i.e. const(size).
• ranges - named sets of integers, representes as term range/1, i.e. range(teams).
• variable indexes - where index may be 0-dimensional (singleton variable), 1-dimensional (1-d array of variables), 2-dimensional, up to 6-dimensional, represented as term var/1 i.e. var(queen). There exist subkinds of this kind: auxillary variables (avar/1), reified constraints rvar/1) and fixed variables (fvar/1).

Specific kinds are used in a different way in the systems. For every constraint programming problem, we define a set of types specific to the problem.

Model

NDL model defines structure of the constraint programming problem and is compiled to a typed Prolog program consisting of following predicates:

• Type related:

  • type_of(+Context:context, -Type:type) - contains typing information about variables and constraints, possible context include:
    • domain of a variable
    • indexing of a variable in a specific axis/dimension
    • 1st/2nd argument of the constraint
  • type_uses(+Type:type, -Contexts:list) - contain information about all the context, the type can bu used in

• Constant related:

  • constant_definition(+Name:string, -Constant:integer) - contains the constant definition. Constant should be understood as a type with only one possible value. The predicate should be used only using the compilation and shouldn't be used in the NDL queries.
  • constant(+Name:string, -Value:integer) - allows to get constant value by it's name. Used in the NDL query.

• Range related

  • range_definition(+Name:string, -Range:range) - analogically to the integer constant, this defines a type with a range of possible values.
  • range_element(+Name:string, -Value:integer) is nondet - allows to non-deterministically get one of the type inhibitants. Used in the NDL query.

• Variable related:

  • fixed(+Name:string) - variables with this name shouldn't be modified by the NDL query. Used only during compilation.
  • auxillary(+Name:string) - variables with this name should be calculated in run-time based on one-directional constrants, used to define complex constraints
  • depends(+Name:string, ?AVar:aux_variable_index, ?Var:variable_index) - specifies on which variable, the auxillary variable is defined
  • reified(+Name:string) - variables with this name reify constraints with the same name. Their domain is always boolean.
  • family of variable predicates allowing to non-deterministically get an indexed variable and it's index. Used in the NDL query.
    • variable(+Name:string, -Index:variable_index) is nondet - for 0-dimensional variable types.
    • variable(+Name:string, ?Index1:integer, -Index:variable_index) is nondet - for 1-dimensional variable types.
    • variable(+Name:string, ?Index1:integer, ?Index2:integer, -Index:variable_index) is nondet - for 2-dimensional variable types.
    • ...
    • variable(+Name:string, ?Index1:integer, ?Index2:integer, ?Index3:integer, ?Index4:integer, ?Index5:integer, ?Index6:integer -Index:variable_index) is nondet - for 6-dimensional variable types

• Constraint related:

  • constraint(+Name:string, ?Arg1:type_of(arg1(Name)), ?Index2:type_of(arg2(Name)) is nondet - allows to non-deterministically check if two arguments (variables or range elements) are constrained with a constraint named Name. Also allows to find elements satisfying those requirements. Used in the NDL query.
  • reified_constraint(+Name:string, ?Arg1:arg1(Name)-?Arg2:arg2(Name), ?Rvar:rvariable_index) - maps constraint to its reificiation

• Semantics related:

  • constraint_semantics(+Name:string, +Body:query) - specifies a query checking if the constraint is satisfied
  • auxillary_semantics(+Name:string, +Body:query) - specifies a query that updates value of the auxillary variable

Query

NDL query is a Prolog like program, containing rules, with bodies consisting of goals from a predefined set of clauses:

• NDL model clauses: constant/2, variable/(2..6), constraint/3, range_element/2
• negated clause \+ constraint/3, when at least on of the constraint arguments is already instantiated
• binary arithmetic operations: +/2, //2, -/2, */2, mod/2, min/2, max/2, abs/1
  • uses Prolog is notation
  • only binary and unary expressions are allowed
  • dividing by 0 gives 0
  • at least one of the arguments has to be of type range, constants are promoted to ranges automatically
• binary arithmetic comparisons: =/2, >=/2, >/2, </2, <=/2
• loops in form of for_each(+Generator:model_clause, +Query:query)
  • first argument is a non-deterministic model clause, i.e. variable/(2..6), constraint/3, range_element/2
  • all Generator's variables are instantiated and available in the Query
  • queries are run in order, independently, it the query fails on the specific variables' instantiation, it continues with the next assignment
• breadth-first search walk over the constraint graph, in form walk_over(+Constraint:constraint_query, +Start:constrained_element, +Query:query), where:
  • Constraint is a model clause constraint/3 with no bound arguments
  • Start defines the point of walk start; it should be a value that appears as the first argument of Constraint in the model (there is a second operation walk_over_inverted/3 that inverts the edges direction)
  • Query can use variables introduced in the Constraint term
  • if Query fails during the walk, the failed branch gets cut, but the walk continues
  • BFS remembers all the visited edges, so no edge is visited twice
• conditions if(+Condition:query,+Then:query) and if(+Condition:test,+Then:query,+Else:query)
  • Condition contains only one term
  • if Condition succeeds, Then query is evaluated
  • if Condition fails and Else query is provided, then Else is evaluated
  • if Condition fails and Else query is not provided, then nothing happens and expression succeeds (non-standard in the Prolog world)
• operation operating on the current solution:
  • get_value(+Index:variable_index, -Value:integer) - gets the variable's current value. Supports only normal and fixed variables.
  • set_value(+Index:variable_index, +Value:integer) - set the variable's value to Value. Supports only normal variables.
  • swap_values(+Index1:variable_index, +Index2:variable_index) - swap values of two variables. Supports only normal variables.
  • flip_variable(+Index:variable_index, +HeadsValue:integer, +TailsValue:integer) - if variable has value HeadsValue or TailsValue, sets the value to the other one. Otherwise fails. Supports only normal variables.

Extensions

There are several extensions to the NDL query, that can be used in order to increase the language expressiveness.

Stochastic mode

Motivation: many meta-heuristics sample only a random subset of neighbohood. NDL Queries can be compiled as stochastic operator. The stochastic mode impacts ordering of the variable/(2..6), constraint/3, range_element/2 results, effectively returning them in a random fashion. It does not impact for_each generator.

Warning: stochastic ndl query always backtracks.

Memory

Motivation: often one would like to mark a variable as already moved, so the query won't try to change it again. It's not possible to query the memory. It's impossible to remove elements from the memory or query it in a generative manner. This extension adds three additional constructs:

• remember(+Arg) - stored argument in the global memory, argument can be any value
• in_memory(+Arg) - checks if the argument has ben remembered
• \+ in_memory(+Arg) - succeeds if the argument hasn't been remembered

Stack

Motivation: stack is a useful data structure, allowing to simulate primitive recursion. Comparing to the Memory extension, stacks are ordered (LIFO) and can be queried. This extension adds three additional constructs:

• push(+Type:type, +Arg:Type) - pushes value of Type on the stack
• pop(+Type:type, -Arg:Type) - pops value of Type from the stack, fails if there is no value of this type on the stack
• top(+Type:type, -Arg:Type) - gets the last added element of Type from the stack, but doesn't remove it from the stack
• while(pop(+Type:type, -Arg:Type), Query:query) - new loop that loops while the stack contains value of a type Type. It can be used to simulate recursion, there is no guarantee it finishes.

Semantics

Motivation: user can define constraint and auxiliary variables semantics in the model. Exploiting semantic part of the model often simplifies the operator. This extension adds additional constructs:

• get_value/2 support reified and auxiliary variables.
• is_satisfied(+Name:name, +Arg1:arg1(Name), +Arg2:arg2(Name)) - succeeds if the constraint named Name is satisfied for arguments Arg1 and Arg2
• is_violated(+Name:name, +Arg1:arg1(Name), +Arg2:arg2(Name)) - succeeds if the constraint named Name is not satisfied for arguments Arg1 and Arg2

Generative semantics

Motivation: the common strategy when implementing a neighborhood operator is to make a move and then fix constraints that got violated by the move.

The biggest difference between the normal and generative semantics is that in the latter case one can query the violated constraints in a generative manner. This extension adds additional constructs:

• all from the normal semantics
• violated(+Name:name, ?Arg1:arg1(Name), ?Arg2:arg2(Name)) is nondet - finds a violated constraint named Name if there is any. Otherwise it fails.
• loop for_each(violated(+Name:name, ?Arg1:arg1(Name), ?Arg2:arg2(Name)), +Query:query)
• loop while(violated(+Name:name, ?Arg1:arg1(Name), ?Arg2:arg2(Name)), +Query:query) - a common pattern used in the neighborhood operators.

Warning using generative semantics adds an overhead to all operations modifying the solution.

Custom predicates

Motivation: it's often desirable to group common query parts into named predicates. This extension allows to define custom (possibly recursive) predicates that can be used later in the query. Every predicate has to have defined name, arity and types of its' arguments, i.e. predicate/2 : [arg1type, arg2type]. Using this extension it is possible to replace all control structure (loops, conditional, stacks, memory) with recursion, making it a plain logic program suitable for logical induction approaches.