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: constraint/2, constraint_range/2, variable/2, new_value/2, constraint/3, is_satisfied/3
• binary arithmetic operations: +, -, /, *, div, mod
• binary arithmetic comparisons: =, >=, >, <, <=
• heads of the rules defined in the query itself (allows recursion)
• 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