Specificiation

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
• 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
  • Generator's variables are available in the Query
  • queries are run in order, independently, it the query fails on the specific variable assignment, it continues with the next assignment
• 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
  • set_value(+Index:variable_index, +Value:integer) - set the variable's value to Value
  • swap_values(+Index1:variable_index, +Index2:variable_index) - swap values of two 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.

Extensions

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

Stochastic mode

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