cDMN to FO(·) conversion

This page details the full cDMN to FO(·) conversion. This conversion is done in two steps; first from cDMN to Python objects, then from these objects to the IDP-Z3 system. In 1. cDMN to Python conversion, an explanation is given for the translation of cDMN to Python objects. In 2. Python to IDP conversion, the conversion of Python to FO(·) is explained. An example of what the result of the conversion looks like is given in 3. cDMN to IDP example.

The basic conversion can be seen in the following image.

_images/converter.png

1. cDMN to Python conversion

The first step in the conversion to Python objects, is for Python to open the .xlsx file. This is done using the OpenPyXL package.

The solver reads all the tables, organises them by type and then parses them in the following order:

  1. Sub-glossary tables
  2. Data tables
  3. Decision tables and Constraint tables
  4. The goal table

1.1 Glossarries

The glossaries are parsed in the following order:

  1. Type
  2. Function
  3. Constant
  4. Relation
  5. Boolean

The order of the latter four doesn’t really matter, but it is necessary to always parse the Type sub-glossary first. Parsing this sub-glossary creates Python type objects. These objects contain a name, their cDMN supertype and the possible values for that type.

After creating a type object for every row in the Type sub-glossary, the other sub-glossaries are parsed next. Functions and relations need to be able to know what types they contain in their name, hence the need to parse the types first.

1.2 Data tables

The values in data tables are stored in dictionaries, to make it easier to format them later on for the IDP system. When interpreting the values for a type in a data table, there exist two possiblities. Either the Values column of the type was filled out in the sub-glossary with values, or it contained a reference to a data table such as see Data Table x. In the former case, each value in the data table is checked on validity. If for instance value 4 is found for a type which defined its range as [5..10], the solver throws an error. In the latter case, every value found in the data table is added to the type’s list of possible values.

1.3 Decision tables and Constraint tables

Decision and constraint tables are represented in a simple way. They are converted into Table objects, which contain a list of inputs, a list of outputs, the list of rows, their name and their hit policy. No more information is necessary in order to represent these tables in Python.

1.4 Goal table

The goal table is the easiest of all: when it’s read, it simply creates a dict which contains the inference method (either model expand, minimize or maximize) and the amount of requested models.

2. Python to IDP conversion

Converting the Python objects to IDP is done in a certain order. For the IDP system, five different blocks of code need to be generated:

  1. Vocabulary
  2. Structure
  3. Theory
  4. Term
  5. Main

The order of this code does not really matter, as long as the main is at last code block.

2.1 Vocabulary

The vocabulary block contains the definitions for the types, functions and predicates used in the IDP model. To create this block, every relevant Python object has a to_idp_voc method to generate the relevant code. For instance, for Type objects, this returns the type name followed by its domain of values. Relations (and booleans) are formatted as name: (arg0 * arg1 * ...) -> Bool. Functions (and constants) are formatted as name: (arg0 * arg1 * ...): -> argn.

2.2 Structure

The structure defines all the possible values for the known types, as well as the satisfied predicates and fully known functions. For this, each Type and Predicate object has a to_idp_struct method. For types, this generates typename := values.

For relations, this is of the form relation_name := { }, with the sets of argument values separated by commas. For functions, each sets of arguments also lists another value separated by an ->.

2.3 Theory

The theory contains the different rules. To create the theory, each Table object is translated based on their hit policy.

Hit Policy IDP concept
U Definitions
F Definitions
A Definitions
C+, C#, C<, C> Aggregates
E* Constraints

2.4 Main

The main block is fully created from the goal table.

The main is mostly the same every time, except for two parameters: the inference task (model expansion, optimization or propagation) and the amount of models.

3. cDMN to IDP example

As an example, we show the conversion of the Who Killed Agatha challenge. First we start off with the translation of the glossary:

Type
Name Type Values
Number int [0..100]
Person string Agatha, Butler, Charles

Function
Name Type
Number hated persons of Person Number

Relation
Name
Person hates Person
Person richer than Person

Constant
Name Type
Killer Person

The glossary tables translate into Vocabulary block of the IDP system. The above tables would result in the following vocabulary:

Vocabulary V {
    type Person constructed from { Agatha, Butler, Charles }
    type Number = { 0..100 } isa int

    Hated_persons(Person): Number
    _Hated_persons(Person): Number

    Killer: Person

    Person_hates_Person(Person, Person)
    Person_richer_than_Person(Person, Person)
}

We can see that every row in the glossary results into a row in the vocabulary. The only exception to this are functions which are used in aggregates such as C#: they also need an auxiliary function to deal with a bug in the IDP system. This auxiliary function has the same name, but start with an underscore (as can be seen here by Hated_persons and _Hated_persons).

All the other glossary elements underwent obvious transformations:

  • String types are now types which use constructed from.
  • Int types use = {x..y} isa int as their definition.
  • Functions are translated into Func_name(Arg1, Arg2, ...): Return_Value.
  • Constants are translated into Const_name: Return_Value.
  • Relations are translated into Rel_name(Arg1, Arg2, ...).
  • Booleans are translated into Boolean_name.
Rule 1
E* Killer hates Agatha Killer richer than Agatha
1 Yes No

Constraint tables are also translated very clearly. As the table in 2.3 Theory shows, they are translated into implications. The above table translates to the following in the IDP system:

//A killer always hates, and is no richer than his victim
true => Person_hates_Person(Killer, Agatha) & ~(Person_richer_than_Person(Killer, Agatha)).

This is a very straightforward translation. Note that, because there is no input column, the implication is always true.

Agatha hates everybody but the butler
E* Person Agatha hates Person
1 Butler No
2 not(Butler) Yes

This is also a very straightforward table to translate. It translates into the following:

//Agatha hates everybody but the butler
!Person[Person]: Person ~= Butler => Person_hates_Person(Agatha, Person).

!Person[Person]: Person = Butler => ~(Person_hates_Person(Agatha, Person)).
The butler hates everyone not richer than Agatha
E* Person Person richer than Agatha Butler hates Person
1 - No Yes

Charles hates no one that Agatha hates
E* Person Agatha hates Person Charles hates Person Butler hates Person
1 - Yes No Yes

Count enemies
C# Person called p1 Person called p2 p1 hates p2 Number hated persons of p1
1 - - yes p2

The above table is a bit harder to translate than the constraint tables. Because of a bug in aggregates in the IDP system, we have to work using an auxiliary function. The actual count is done in the first line.

//Count enemies
!p1[Person]:  _Hated_persons(p1) = sum(#{  p2[Person] : Person_hates_Person(p1, p2) & p1 = p1 & true }).
{
    !p1[Person]: Hated_persons(p1) = _Hated_persons(p1).
}
Noone hates all
E* Person Number hated persons of Person
1 - < 3

The full translation of the entire cDMN implementation is shown next. Note how the Structure block is empty, because no data table was used.

Vocabulary V {
    type Person constructed from { Agatha, Butler, Charles }
    type Number = { 0..100 } isa int

    Hated_persons(Person): Number
    _Hated_persons(Person): Number

    Killer: Person

    Person_hates_Person(Person, Person)
    Person_richer_than_Person(Person, Person)
}

Structure S:V {
}
Theory T:V {
    //A killer always hates, and is no richer than his victim
    true => Person_hates_Person(Killer(), Agatha) & ~(Person_richer_than_Person(Killer(), Agatha)).

    //Agatha hates everybody but the butler
    !Person[Person]: Person ~= Butler => Person_hates_Person(Agatha, Person).

    !Person[Person]: Person = Butler => ~(Person_hates_Person(Agatha, Person)).

    //Charles hates no one that Agatha hates
    !Person[Person]: Person_hates_Person(Agatha, Person) => ~(Person_hates_Person(Charles, Person)) & Person_hates_Person(Butler, Person).

    //Butler hates everyone not richer than Agatha
    !Person[Person]: ~(Person_richer_than_Person(Person, Agatha)) => Person_hates_Person(Butler, Person).

    //Count enemies
    !p1[Person]:  _Hated_persons(p1) = sum(#{  p2[Person] : Person_hates_Person(p1, p2) & p1 = p1 & true }).
    {
        !p1[Person]: Hated_persons(p1) = _Hated_persons(p1).
    }
    //Noone hates all
    !Person[Person]: true => Hated_persons(Person) < 03.

}


procedure main(){
stdoptions.nbmodels = 1
printmodels(modelexpand(T,S))
}