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.