Package "modeling"

Title:	MiniZinc-inspired modeling predicates in Prolog.
Rating:	Not rated. Create the first rating!
Latest version:	1.1.4
SHA1 sum:	3649ef63969933b2c3c8a671779dd0031ef58140
Author:	Francois Fages <Francois.Fages@inria.fr>
Home page:	https://lifeware.inria.fr/wiki/Main/Software#modeling
Download URL:	https://lifeware.inria.fr/~fages/modeling-1.1.3.tgz

Reviews

No reviews. Create the first review!.

Details by download location

Version	SHA1	#Downloads	URL
1.0.0	3869cad3554891541a85ce628a75c8a85b3bf477	2	https://lifeware.inria.fr/~fages/modeling-1.0.0.tgz
1.0.1	e63722df5e532906cc544a7b58eb4dac57f050d0	4	https://lifeware.inria.fr/~fages/modeling-1.0.1.tgz
1.1.0	cd9474ded3d947ac9419668c7f8b075098dddfdc	6	https://lifeware.inria.fr/~fages/modeling-1.1.0.tgz
1.1.1	4ef5769b89dd3d1ad2bca1e77489e1ae1a78847b	2	https://lifeware.inria.fr/~fages/modeling-1.1.1.tgz
1.1.2	b7b05c4617720f10ba77fe14e5f04be09ca4a25b	3	https://lifeware.inria.fr/~fages/modeling-1.1.2.tgz
1.1.3	0cd413ac6e7672f1291fbdc4491503e6bab6b980	4	https://lifeware.inria.fr/~fages/modeling-1.1.3.tgz
1.1.4	3649ef63969933b2c3c8a671779dd0031ef58140	3	https://lifeware.inria.fr/~fages/modeling-1.1.4.tgz

Modeling pack

MiniZinc-inspired modeling predicates in Prolog.

This pack defines Prolog predicates in the spirit of the MiniZinc modeling language (https://www.minizinc.org/) for shorthand functional notations, subscripted variables with arrays, constraint quantifiers, aggregates, hybrid constraints, search tree tracing and drawing, combined with

• the full programming capabilities of Prolog for programming search, visualizing the search tree, and interfacing with external components;
• the constraint semantics of Prolog for computing non-ground symbolic solutions to constraint satisfaction problems;
• plus soon coming a MiniZinc parser.

The pack includes libraries shorthand.pl, comprehension.pl, arrays.pl, clp.pl, modeling.pl, drawtree.pl, tracesearch.pl and a benchmark file of examples showing the absence of significant overhead with respect to classical Prolog programs with lists and recursion, see

• François Fages. A Constraint-based Mathematical Modeling Library in Prolog with Answer Constraint Semantics. In 17th International Symposium on Functional and Logic Programming, FLOPS 2024, volume 14659 of LNCS. Springer-Verlag, 2024. [ preprint https://inria.hal.science/hal-04478132]

Install

swipl pack install modeling

or under Prolog

?- pack_install(modeling).

Example

The N-queens puzzle of placing N queens on a NxN chessboard such that they do not attack each other (i.e. they are not on same column, row or diagonal), which is classically solved by a recursive program on lists, can be modeled in this library using

• an array Queens with functional notation for subscripted variables Queens[I],
• bounded quantifier for_all with definition of the variables by list comprehension using in and where conditions,
• let bindings using shorthand notations for arrays and conditional expressions, as follows:

  :- use_module(library(modeling)).
  
  queens(N, Queens):-
    int_array(Queens, [N], 1..N),
    for_all([I in 1..N-1, D in 1..N-I],
            (Queens[I] #\= Queens[I+D],
             Queens[I] #\= Queens[I+D]+D,
             Queens[I] #\= Queens[I+D]-D)),
    satisfy(Queens).
  
  show(Queens):-
      array(Queens, [N]),
      for_all([I, J] in 1..N,
              let([Q = if(Queens[J] = I, 'Q', '.'),
                   B = if(J = N, '\n', ' ')],
                  format("~w~w",[Q,B]))).
  
  ?- queens(N, Queens), show(Queens).
  Q
  N = 1,
  Queens = array(1) ;
  . . Q .
  Q . . .
  . . . Q
  . Q . .
  N = 4,
  Queens = array(2, 4, 1, 3) ;
  . Q . .
  . . . Q
  Q . . .
  . . Q .
  N = 4,
  Queens = array(3, 1, 4, 2) ;
  Q . . . .
  . . . Q .
  . Q . . .
  . . . . Q
  . . Q . .
  N = 5,
  Queens = array(1, 3, 5, 2, 4) .

Main features

Library shorthand.pl defines

• a general purpose user-definable shorthand/3 metapredicate to define shorthand functional notations usable with expand/1, expand/2, evaluate/2 predicates,
• used there to define a conditional expression if(Condition, Expression1, Expression2) and suggested for global variables.

Library comprehension.pl defines

• for_all/2 constraint quantifier,
• let/2 metapredicate for binding existential variables to expressions with shorthand functional notation,
• a general purpose aggregate/6 metapredicate to constrain elements defined by comprehension by iteration (not backtracking), with expansion of shorthands in domains and conditions,
• used in clp.pl to define new global constraints.

Library arrays.pl provides an implementation of arrays in Prolog

• with Array[Indices] functional notation defined by shorthand/3.

Library clp.pl is a front-end to libraries clpfd and clpr allowing

• shorthand notations in domains and constraints,
• hybrid clpfd-clpr constraints on hybrid list and array arguments, plus some new clpfd global constraints,
• shorthand functional notations for constraints in which the last argument can be interpreted as a result, e.g. sum/2 function using sum/3 constraint
• reification of clpfd-clpr constraints with a clpfd Boolean using truth_value/2 predicate or truth_value/1 function in expressions,
• option trace added to labeling/2 predicate to visualize the search tree.

Library tracesearch.pl defines predicates for creating a search tree term, e.g. option trace added to labeling/3.

Library drawtree.pl defines predicates for drawing term and search trees in LaTeX tikz.

Library modeling.pl adds predicates for bool_array/2, int_array/3, float_array/3, satisfy/1, minimize/1.

Reification for clpr and clpfd constraints

Constraints of library(clpr) can be reified (checking variable instanciation rather than constraint entailment) with predicate truth_value/2 predicate defined in library clp:

?- array(A, [3]), truth_value({A[1] < 3.14}, B).
A = array(_A, _, _),
when((nonvar(_A);nonvar(B)), clp:clpr_reify(_A<3.14, _A>=3.14, B)).

?- array(A, [3]), truth_value({A[1] < 3.14}, B), {A[1]=2.7}.
A = array(2.7, _, _),
B = 1.

Together with shorthand functional notation for truth_value/2, this can be employed to solve the magic series puzzle by a direct transcription of the mathematical definition of magic series:

i.e. series of integers (X1,...,XN) satisfying for all i in 1..N, Xi = | { Xj = i-1 | j in 1..N} |

magic_series(N, X):-
    array(X, [N]),
    for_all(I in 1..N,
            X[I] #= int_sum(J in 1..N, truth_value(X[J] #= I-1))),
    satisfy(X).

?- magic_series(4, X).
X = array(1, 2, 1, 0) ;
X = array(2, 0, 2, 0) ;
false.


?- magic_series(N, X).
N = 4,
X = array(1, 2, 1, 0) ;
N = 4,
X = array(2, 0, 2, 0) ;
N = 5,
X = array(2, 1, 2, 0, 0) ;
N = 7,
X = array(3, 2, 1, 1, 0, 0, 0) ;
N = 8,
X = array(4, 2, 1, 0, 1, 0, 0, 0) ;
N = 9,
X = array(5, 2, 1, 0, 0, 1, 0, 0, 0) ;
N = 10,
X = array(6, 2, 1, 0, 0, 0, 1, 0, 0, 0) ;
...

Prolog files

prolog/arrays.pl prolog/comprehension.pl prolog/shorthand.pl

prolog/modeling.pl prolog/clp.pl

prolog/tracesearch.pl prolog/drawtree.pl

Contents of pack "modeling"

Pack contains 19 files holding a total of 161K bytes.