-
Notifications
You must be signed in to change notification settings - Fork 0
/
NEWS
2098 lines (1471 loc) · 79.2 KB
/
NEWS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Copyright (C) 2001-2010 Roberto Bagnara <[email protected]>
Copyright (C) 2010-2020 BUGSENG srl (http://bugseng.com)
Verbatim copying and distribution of this entire article is permitted
in any medium, provided this notice is preserved.
Parma Polyhedra Library NEWS -- history of user-visible changes
===============================================================
--------------------------------------------------------------------------
NEWS for version 1.3 (released date to be decided)
--------------------------------------------------------------------------
New and Changed Features
========================
o TBW
Bugfixes
========
o TBW
--------------------------------------------------------------------------
NEWS for version 1.2 (released on February 11, 2016)
--------------------------------------------------------------------------
New and Changed Features
========================
o Improved the efficiency of the conversion procedure for polyhedra
by adding a quick adjacency check.
o In the Java language interface, throw an exception when trying
to build a disequality Constraint.
Bugfixes
========
o Fixed a bug in the implementation of methods
Pointset_Powerset<PSET>::relation_with(const Constraint&) const;
and
Pointset_Powerset<PSET>::relation_with(const Congruence&) const;
whereby the computed result for relations strictly_intersects()
and saturates() could have been wrong.
o Fixed a bug in the implementation of dense rows.
o Portability improved.
--------------------------------------------------------------------------
NEWS for version 1.1 (released on October 28, 2013)
--------------------------------------------------------------------------
New and Changed Features
========================
o Added a new operator on polyhedra: the positive time elapse.
o In the Java language interface:
- The constraint/generator/... system classes now extend the ArrayList
generic container (rather than Vector);
- Variable objects are now built from a long (rather than int) value,
thereby matching the type used elsewhere for space dimensions;
- added new static method to Variable class
void setStringifier(Variable_Stringifier)
where Variable_Stringifier is an interface allowing for
customization of the output routine for variable's names
(see example in interfaces/Java/tests/Variable_Output_test1.java);
- added value NOT_EQUAL to enumeration Relation_Symbol.
Bugfixes
========
o Portability improved.
o Fixed a precision regression in Polyhedron method
void drop_some_non_integer_points(const Variables_Set&,
Complexity_Class);
o In the Java language interface, fixed a C++/Java conversion error
whereby the construction of a valid Variable object in JNI code
was leading to an exception being thrown. The bug has only been
observed on 32-bit builds.
o In the Java interface, fixed declaration of methods
void drop_some_non_integer_points(...);
so as to accept a Complexity_Class enum value.
o Fixed an issue in method MIP_Problem::OK() whereby the method
was trying to enforce a non-invariant condition.
--------------------------------------------------------------------------
NEWS for version 1.0 (released on June 28, 2012)
--------------------------------------------------------------------------
New and Changed Features
========================
o Significant improvements have been obtained in both time and space
resource usage by the definition of data structures and algorithms
for the case of "sparse rows", i.e., sequences of coefficients
where most of the values are zero.
o The library fully supports two different representations for rows:
the "dense" representation is an array-like representation tailored
to sequences having most of their coefficients different from zero;
the "sparse" representation saves memory space (as well as CPU
cycles) when most of the coefficients in the sequence are zero.
o A generic interface allows for a seamless interaction between the
dense and the sparse row representation. Most library entities
(linear expressions, constraints, generators, congruences, and
their systems) can be built using either representation, specified
as a constructor's argument.
o As a by-product of this sparse/dense refactoring work, efficiency
improvements have been obtained even for those computations that
are still based on the dense row representation.
o Reasonable default values for the row representation are provided
for each library entity, automatically leading to significant
memory space savings even in old client/library code, e.g., when
dealing with constraint systems describing weakly relational
abstractions such as boxes and octagonal shapes.
o If desired, these default values can be customized to user's needs
by changing just a few lines of library code. For instance, the
constraint systems stored inside C_Polyhedron and NNC_Polyhedron
objects can be made to use the sparse representation by just
changing the following line in Polyhedron.defs.hh:
static const Representation default_con_sys_repr = DENSE;
to become
static const Representation default_con_sys_repr = SPARSE;
Bugfixes
========
o Fixed a bug affecting methods
bool BD_Shape<T>::contains(const BD_Shape& y) const;
bool Octagonal_Shape<T>::contains(const Octagonal_Shape& y) const;
whereby the wrong result was obtained when *this is an empty
weakly-relational shape and y is not empty.
o Fixed a bug affecting the PIP solver whereby a wrong result could have
been obtained if the input constraint system contained multiple linear
equality constraints.
--------------------------------------------------------------------------
NEWS for version 0.12.1 (released on April 16, 2012)
--------------------------------------------------------------------------
New and Changed Features
========================
o In the C, Java, OCaml and Prolog interfaces, modified the signature
of the function/method/predicate for setting the deterministic timeout
threshold. The new interfaces take two input values, named `unscaled'
and `scale', that are used to compute the threshold value as
`unscaled * 2^scale'.
o Added new Box<ITV> methods
bool has_upper_bound(Variable var,
Coefficient& n, Coefficient& d, bool& closed) const;
bool has_lower_bound(Variable var,
Coefficient& n, Coefficient& d, bool& closed) const;
to query a non-empty box for the existence and value of its upper/lower
bound on variable `var'. The methods have been also added to all the
available language interfaces.
o Two BibTeX databases of papers related to the Parma Polyhedra Library
have been added to the distribution (in the `doc' directory).
Bugfixes
========
o Restored the support for deterministic timeouts in the PIP solver
(it was removed by accident in PPL 0.12).
o Minor documentation fixes.
o Portability improved.
--------------------------------------------------------------------------
NEWS for version 0.12 (released on February 27, 2012)
--------------------------------------------------------------------------
New and Changed Features
========================
o New configure options `--with-gmp=DIR', `--with-gmp-include=DIR' and
`--with-gmp-lib=DIR' supersede the (now removed) option
`--with-gmp-prefix'. (The old option never really worked; hopefully
this is the last change in this area.)
o New configuration option `--disable-documentation'. When specified
no new documentation is built: only the documentation already present
in the source tree is installed upon `make install'.
o The resolution process for PIP_Problem now better exploits the
integrality of parameters to simplify the newly generated tautological
constraints, the splitting constraints of decision nodes, and the
expressions defining artificial parameters.
o The implementations of the MIP and PIP solvers are based on a new
data structure leading to significant space and time savings when
the tableau matrix is sparse; the benchmarks of the ppl_lpsol demo
show an improvement on the average case, that grows when the toughest
tests in the benchmark suite are considered.
o When the `--check' option is used, the input data for demo ppl_lpsol
is perturbed the same way as GLPK does, thereby allowing for a
meaningful comparison of the results obtained.
o The input routine for PPL numeric datatypes has been extended to
accept the ISO9899 (C99) hexadecimal floating constant syntax.
o The Parma Watchdog Library has been merged into the
Parma Polyhedra Library.
Bugfixes
========
o Corrected a precision bug in methods
Box<ITV>::upper_bound_assign(const Box&)
Box<ITV>::upper_bound_assign_if_exact(const Box&)
whereby, provided any argument is an empty box and under other rather
specific conditions, the computed result was correct but unnecessarily
imprecise.
o Corrected a bug in method
Grid::relation_with(const Constraint&) const
whereby, under specific conditions, the method was creating invalid
Grid_Generator objects and providing an incorrect result.
--------------------------------------------------------------------------
NEWS for version 0.11.2 (released on February 27, 2011)
--------------------------------------------------------------------------
Bugfixes
========
o Fixed the semantics of the `--disable-fpmath' configure option
(which is equivalent to `--enable-fpmath=no'). It now disables all
floating point computations and, consequently, all numerical
abstractions based on floating point numbers.
o The PPL no longer overwrites the SIGILL signal handler.
o Minor documentation fixes.
o Portability improved.
--------------------------------------------------------------------------
NEWS for version 0.11.1 (released on February 20, 2011)
--------------------------------------------------------------------------
Bugfixes
========
o Corrected a problem in the simplification of PIP_Problem solution trees
whereby, under specific conditions, the node merging process produced
decision nodes that did not satisfy their class invariant.
o Corrected a precision bug in method
Octagonal_Shape<T>::affine_image()
whereby in the case of an invertible affine transformation implementing
a variable sign symmetry (and optional translation), the computed result
was correct but unnecessarily imprecise.
o Corrected a problem in the input method for checked integers whereby,
under specific conditions, the input stream state bits were not updated.
The bug was only affecting builds using checked integer coefficients.
o Corrected a bug in the OCaml interface, which was affecting functions
ppl_Pointset_Powerset_<INSTANCE>_get_disjunct.
o Corrected a couple of resource (re-)allocation problems that, under
specific conditions, could affect the correctness of Grid constructor
Grid::Grid(const Box<Interval>& box)
and NNC_Polyhedron method
Polyhedron::generalized_affine_image().
o Corrected an efficiency bug in the C language interface function
ppl_Linear_Expression_add_to_coefficient().
o Corrected an efficiency bug in method
MIP_Problem::compute_generator().
o Corrected a bug affecting the input routine of ppl_lpsol, whereby
the inhomogeneous term of the objective function was disregarded.
o Corrected a bug affecting methods
Box::CC76_widening_assign(const T&, Iterator, Iterator)
Interval::CC76_widening_assign(const From&, Iterator, Iterator)
whereby a lower bound would not be computed correctly when the two
iterators specify an empty list of stop points.
o Fixed a bug affecting
Interval::Interval(const char* s)
whereby a wrong interval would be constructed if `s' denotes a number
that can only be represented as an infinity.
o Fixed a bug whereby the argument of all the methods
unconstrain(Variable var)
was not checked correctly for space dimension compatibility.
o Portability improved.
--------------------------------------------------------------------------
NEWS for version 0.11 (released on August 2, 2010)
--------------------------------------------------------------------------
New and Changed Features
========================
o New class PIP_Problem provides a Parametric Integer Programming
(PIP) problem solver (mainly based on P. Feautrier's
specification). The implementation combines a parametric dual
simplex algorithm using exact arithmetic with Gomory's cut
generation.
o New "deterministic" timeout computation facilities: it is now
possible to set computational bounds (on the library calls taking
exponential time) that do not depend on the actual elapsed time and
hence are independent from the actual computation environment (CPU,
operating system, etc.).
o New support for termination analysis via the automatic synthesis of
linear ranking functions. Given a sound approximation of a loop,
the PPL provides methods to decide whether that approximation
admits a linear ranking function (possibly obtaining one as a
witness for termination) and to compute the space of all such
functions. In addition, methods are provided to obtain the space
of all linear quasi-ranking functions, for use in conditional
termination analysis.
o New support for approximating computations involving (bounded)
machine integers. A general wrapping operator is provided that is
parametric with respect to the set of space dimensions (variables)
to be wrapped, the width, representation and overflow behavior of
all these variables. An optional constraint system can, when
given, improve the precision.
o All the PPL semantic objects provide new methods
void drop_some_non_integer_points(Complexity_Class)
void drop_some_non_integer_points(const Variables_Set&,
Complexity_Class)
which possibly tighten the object by dropping some points with
non-integer coordinates (for the space dimensions corresponding to
`vars'), within a certain computational complexity bound.
o New Linear_Expression methods
bool is_zero() const
bool all_homogeneous_terms_are_zero() const
return true if and only if `*this' is 0, and if and only if all the
homogeneous terms of `*this' are 0, respectively.
o New Linear_Expression methods
void add_mul_assign(Coefficient_traits::const_reference c, Variable v)
void sub_mul_assign(Coefficient_traits::const_reference c, Variable v)
assign linear expression *this + c * v (resp., *this - c * v) to *this,
while avoiding the allocation of a temporary Linear_Expression.
o For the PPL semantic objects, other than the Pointset_Powerset and
Partially_Reduced Product, there is a new method:
bool frequency(const Linear_Expression& expr,
Coefficient& freq_n, Coefficient& freq_d,
Coefficient& val_n, Coefficient& val_d)
This operator computes both the "frequency" (f = freq_n/freq_d)
and a value (v = val_n/val_d) closest to zero so that every point
in the object satisfies the congruence (expr %= v) / f.
o New reduction operator "Shape_Preserving_Reduction" has been added
to the Partially_Reduced_Product abstraction. This operator is
aimed at the product of a grid and a shape domain, allowing the
bounds of the shape to shrink to touch the points of the grid,
such that the new bounds are parallel to the old bounds.
o The Java interface has to be explicitly initialized before use by
calling static method Parma_Polyhedra_Library.initialize_library().
Initialization makes more explicit the exact point where PPL
floating point rounding mode is set; it also allows for the caching
of Java classes and field/method IDs, thereby reducing the overhead
of native method callbacks.
o The C and Java interfaces now support timeout computation facilities.
o Implementation of general (C and NNC) polyhedra speeded up.
o Implementation of the MIP solver speeded up.
o When the PPL has been configured with
CPPFLAGS="-DPPL_ARM_CAN_CONTROL_FPU=1", the library initialization
procedure checks that the FPU can indeed be controlled and fails if
that is not the case.
o New configure option `--with-gmp-prefix' supersedes the (now removed)
options `--with-libgmp-prefix' and `--with-libgmpxx-prefix'.
o New configuration option `--with-gmp-build=DIR' allows to use a
non-installed build of GMP in DIR.
Deprecated and Removed Methods
==============================
o All methods having a name ending in `_and_minimize' (e.g.,
add_constraints_and_minimize, poly_hull_assign_and_minimize, ...)
have been removed (they were deprecated in version 0.10).
Bugfixes
========
o Corrected a bug in maximize and mininimize optimization methods of
class template Pointset_Powerset, whereby the Boolean value true
(indicating successful optimization) was returned for empty powersets.
o Corrected a bug in method
bool NNC_Polyhedron::poly_hull_assign_if_exact(const NNC_Polyhedron&);
whereby some inexact NNC hulls were incorrectly flagged as exact.
--------------------------------------------------------------------------
NEWS for version 0.10.2 (released on April 18, 2009)
--------------------------------------------------------------------------
Bugfixes
========
o Correctly detect GMP 4.3.0.
o Fixed the C interface library version information.
o Test program tests/Polyhedron/memory1 disabled on the zSeries s390x
platform.
o Makefiles fixed so as to avoid failure of `make -n check'.
--------------------------------------------------------------------------
NEWS for version 0.10.1 (released on April 14, 2009)
--------------------------------------------------------------------------
New and Changed Features
========================
o Added support for cross compilation.
o The configuration script now explicitly checks that a recent enough
version of GNU M4 is available if at least one non-C++ interface is
enabled (in previous versions this check was not performed and
building the library could fail in a mysterious way).
o Robustness improved.
o Some packaging issues have been fixed.
o New macro PPL_DIRTY_TEMP_COEFFICIENT allows users of the C++
interface to decrease memory allocation overhead and to improve
locality whenever they need a temporary variable of type
`Coefficient'.
o The C++, C, Java and OCaml interfaces now provide utility functions
to format the textual representations of constraints, congruences
and so on. This makes it easy to code debugging prints with line
indentation and wrapping.
o The C interface now provides functions of the form
int ppl_io_asprint_Polyhedron(char** strp, P x)
where `P' is any opaque pointer to a const PPL object. These
functions print `x' to a malloc-allocated string, a pointer to
which is returned via `strp'.
o The OCaml interface can now be compiled to native code using ocamlopt.
o New configuration option `--with-mlgmp=DIR' allows to specify the
installation directory of the ML GMP package.
o The OCaml interface now supports timeout computation facilities
through functions ppl_set_timeout and ppl_reset_timeout. Moreover,
new functions ppl_Coefficient_is_bounded, ppl_Coefficient_min,
ppl_Coefficient_max and ppl_max_space_dimension have been added.
o The Prolog interfaces are no longer enabled by default in the
release tarballs (they are enabled by default in the Git versions).
Bugfixes
========
o Fixed a bug whereby `make check' was failing when the library was
configured with the `--disable-watchdog' option.
o Fixed a bug in method
bool Polyhedron::contains_integer_point() const;
whereby, under very specific conditions, an empty polyhedron is
incorrectly said to contain an integer point.
o Fixed a bug in method
Partially_Reduced_Product<D1, D2, R>::time_elase_assign(y)
whereby, if the product y was not already reduced, the operation could
lose precision.
o Fixed a bug in the OCaml interface, which was affecting functions
ppl_Grid_generalized_affine_image_with_congruence
and
ppl_Grid_generalized_affine_preimage_with_congruence.
o Fixed a bug in the Grid class that affected the methods
Grid::bounds_from_above(), Grid::bounds_from_below(),
Grid::maximize() and Grid::minimize();
causing all of them to wrongly return true in certain cases where
the grid generators were not minimized.
o Fixed a bug whereby big-endian architectures were not properly
recognized by the configuration script.
o Fixed a bug in the Java/OCaml/Prolog interfaces, whereby
the method/function/predicate for dropping a disjunct from a
Pointset_Powerset object were returning an invalid iterator.
o Fixed a bug in method Octagonal_Shape<T>::affine_image(var, expr)
whereby a wrong result was computed under specific conditions.
o Fixed a bug in the OCaml interface, whereby functions of form
ppl_..._widening_assign_with_tokens
and
ppl_..._extrapolation_assign_with_tokens
could return a wrong number of tokens.
o Fixed a bug in the OCaml interface, whereby functions that returned
an OCaml 'unit' type were returning the wrong value.
o Fixed several garbage collection related bugs in the OCaml interface.
--------------------------------------------------------------------------
NEWS for version 0.10 (released on November 4, 2008)
--------------------------------------------------------------------------
New and Changed Features
========================
The license
-----------
o The Parma Polyhedra Library is now released under the terms of the
version 3 (or later) of the GNU General Public License.
New and renamed classes
-----------------------
o The new class Octagonal_Shape provides an implementation of the domain
of octagonal shapes (including optimized algorithms and a provably
correct widening) as proposed by Roberto Bagnara, Patricia Hill,
Elena Mazzi and Enea Zaffanella in their SAS 2005 paper.
o A new abstraction called Box has been added. Geometrically
speaking, a Box represents a not necessarily closed, iso-oriented
hyperrectangle. This can also be seen as the smash product of `n'
not necessarily closed and possibly unbounded intervals, where `n'
is the space dimension of the box. The Box template class is
parametric with respect to a class of intervals.
o A generic implementation of intervals has been added. The template
class Interval is parametric on the type used to represent the
interval boundaries (all native integer and floating point types
are supported as well as unbounded integers and rational numbers
provided by GMP). Another class template type parameter allows for
the control of a number of other features of the class (such as the
ability to represent: open as well as closed boundaries, empty
intervals in addition to nonempty ones, intervals of extended
number families that contain positive and negative infinities,
plain intervals of real numbers and intervals of integer numbers).
The Interval class still needs a lot of work and both its
implementation and its interface are likely to change significantly:
it is released now because it is needed for the Box class and as a
kind of technology preview.
o The class LP_Problem has been renamed MIP_Problem and now supports
the solution of Mixed Integer (Linear) Programming problems.
Support has been added for the incremental solution of MIP
problems: it is now possible to add new space dimensions or new
constraints to the feasible region, as well as change the objective
function and the optimization mode, while still exploiting some of
the computational work done before these changes. Support has also
been added to change control parameters for the pricing method.
This allows a choice between the steepest edge pricing method,
either implemented with floating point numbers (default) or with
integer coefficients, and the textbook pricing method.
o The PPL semantic object Polyhedra_Powerset has been replaced by the
templatic object template <typename PS> Pointset_Powerset that can
take any (simple) PPL semantic object for the domain of its
disjuncts. In addition to the methods common to all the PPL
semantic objects, methods specific to this domain include:
void add_disjunct(const PS&),
void pairwise_reduce(),
void omega_reduce() const,
bool geometrically_covers(const Pointset_Powerset&) const,
bool geometrically_equals(const Pointset_Powerset&) const, and
bool simplify_using_context_assign(const Pointset_Powerset&).
o A new abstraction called Partially_Reduced_Product (PRP) has been
added. A PRP is a pair of two PPL semantic objects that is
parametric on the component domains and on a reduction operator.
The PPL currently provides three reduction operators and hence,
three different kinds of products:
- a Direct_Product where the reduction operator is the identity;
- a Smash_Product where the reduction operator shares emptiness
information between the components; and
- a Constraints_Product where the reduction operator refines each
component with the constraints satisfied by the other component.
The PRP class still needs a lot of work and both its implementation
and its interface are likely to change significantly: it is released
now as a kind of technology preview and any feedback is welcome.
New and renamed methods
-----------------------
o All PPL semantic objects can now be constructed from other simple
PPL semantic objects. All these constructors have an optional complexity
argument with default value allowing algorithms with any complexity to be
used.
o New methods
void restore_pre_PPL_rounding() and
void set_rounding_for_PPL()
allow the FPU rounding mode to be set to what it was before the
initialization of the PPL, and to set it (again) so that the PPL
abstractions based on floating point numbers work correctly, respectively.
o All PPL semantic objects now provide methods
void refine_with_constraint(const Constraint&),
void refine_with_congruence(const Congruence&),
void refine_with_constraints(const Constraint_System&), and
void refine_with_congruences(const Congruence_System&).
These methods are similar to the corresponding `add_' methods.
The difference is in the reaction policy when the argument
constraint/congruence is not optimally supported by the semantic
domain: while the `add_' methods will throw an exception, the
`refine_with_' methods will apply an upward approximation semantics.
o Default widening operators of the form:
void widening_assign(const ABSTRACTION&, unsigned*)
are now provided for all abstractions except for the Pointset_Powerset
abstractions.
o All PPL semantic objects now provide the method
int32_t hash_code() const
returning a 32-bit hash code for *this. If x and y are such that
x == y evaluates to true, so does x.hash_code() == y.hash_code().
o All PPL semantic objects now provide the methods
memory_size_type total_memory_in_bytes() const
memory_size_type external_memory_in_bytes() const
returning, respectively, the total size in bytes of the memory
occupied by the PPL object and the size in bytes of the memory
managed by the PPL object.
o For all the PPL semantic objects there are new methods:
static bool can_recycle_constraint_systems() and
static bool can_recycle_congruence_systems()
that indicate whether or not a PPL semantic object is able to recycle
constraints and congruences, respectively.
o For all PPL semantic objects there is a new method:
bool contains_integer_point() const
which checks if a PPL semantic object contains an integer point;
Note that this is not currently provided for the Partially_Reduced_Product
classes.
o For all PPL semantic objects there is a new method:
bool constrains(Variable) const
which checks if a dimension is constrained by a PPL semantic object;
o For all PPL semantic objects there are new methods:
void unconstrain(Variable)
void unconstrain(const Variables_Set&)
which assign, to a PPL semantic object, the cylindrification
of the object with respect to one (resp., a set) of its dimensions,
as defined by L. Henkin, J. D. Monk, and A. Tarski in Cylindric Algebras:
Part I (published by North-Holland in 1971).
o Several methods
bool is_topologically_closed() const
void topological_closure_assign()
that were provided for just some of the PPL semantic objects are now
uniformly available for all the objects.
o Methods using the Congruence and Congruence_System classes
such as
Congruence_System congruences() const,
Congruence_System minimized_congruences() const,
void add_congruence(const Congruence&),
void add_congruences(const Congruence_System&),
void add_recycled_congruences(const Congruence_System&), and
Poly_Con_Relation relation_with(const Congruence&).
that were just provided for the Grid domain are now provided for
all the PPL semantic objects.
o For the Grid class, as it is not always possible to obtain a
Pointset_Powerset<Grid> object that is a finite linear partition of
the difference of two grids, we have added the method:
std::pair<Grid, Pointset_Powerset<Grid> >
approximate_partition(const Grid&, const Grid&, bool&)
where the third argument is set to false if there is no
finite linear partition.
o In the Congruence class, for consistency with the Constraint class,
the methods is_trivial_true() and is_trivial_false() have been renamed
as is_tautological() and is_inconsistent(), respectively.
o The methods
bool Constraint_System::empty() const,
bool Generator_System::empty() const,
bool Congruence_System::empty() const, and
bool Grid_Generator_System::empty() const
return true if and only if the system in question is empty
(i.e., it has no constraints, generators, congruences or grid-generators,
respectively).
Deprecated and Removed Methods
==============================
o As all PPL semantic objects can now be constructed from boxes,
the constructors
template <typename Box> C_Polyhedron(const Box&, From_Bounding_Box),
template <typename Box> NNC_Polyhedron(const Box&, From_Bounding_Box),
template <typename Box> Grid(const Box&, From_Bounding_Box)
have been removed. Similarly, as boxes can be constructed from other
PPL semantic objects, the method
template <typename Box>
void shrink_bounding_box(Box&, Complexity_Class) const
has been removed from all the classes.
o The use of methods having a name ending in `_and_minimize' (e.g.,
add_constraints_and_minimize, poly_hull_assign_and_minimize, ...)
is now deprecated (see the core library documentation for an
explanation); their complete removal is planned for version 0.11.
o Class BD_Shape and Grid no longer provide methods such as
bds_hull_*, join_*, bds_difference_* and grid_difference_*. The
uniformly named methods upper_bound_* and difference_assign should
be used instead. For (C and NNC) polyhedra, the poly_hull_* and
poly_difference_assign methods have been kept for backward
compatibility (users should anyway prefer adopting the uniformly
named variants).
o For Grids, the PPL no longer supports covering boxes; hence the constructor
template <typename Box> Grid(const Box&, From_Covering_Box)
and also the method
template <typename Box> void get_covering_box(Box&) const
have been removed.
Other changes for the C++ interface
-----------------------------------
o All identifiers containing the strings `less_than_or_equal' or
`greater_than_or_equal', any case, have been renamed so as to contain
`less_or_equal' or `greater_or_equal', respectively.
A similar change also applies to the C interface (see below).
o The `ppl.hh' header file no longer defines macros not prefixed
by "PPL_".
o Users of the C++ interface of the library can now decide to disable
the automatic initialization mechanism of the PPL. To do so, the
preprocessor symbol PPL_NO_AUTOMATIC_INITIALIZATION should be
defined before including the <ppl.hh> header file. When automatic
initialization is disabled it is imperative to explicitly call the
new function
void Parma_Polyhedra_Library::initialize()
before using the library. The new function
void Parma_Polyhedra_Library::finalize() and
should also be called (to release a small amount of memory) when
done with the library.
Changes to the other language interfaces
----------------------------------------
o Support for language interfaces has been expanded to include
OCaml and Java. Thus the PPL now supports interfaces to
C++, C, Java, OCaml, Ciao Prolog, GNU Prolog, SICStus Prolog,
SWI Prolog, XSB Prolog and YAP Prolog.
o Most of the PPL semantic objects provided by the C++ interface
are also supported by all the non-C++ language interfaces. A few
domains (in particular, many of the possible Box instantiations)
are only available via the C++ interface.
o Almost all the public methods for the PPL semantic objects are
provided as methods/functions/predicates in the non-C++ language
interfaces with a uniform naming policy. In particular:
* in the C interface, the methods named
ppl_Polyhedron_{constraints,generators,congruences}
ppl_Polyhedron_minimized_{constraints,generators,congruences}
have been renamed
ppl_Polyhedron_get_{constraints,generators,congruences}
ppl_Polyhedron_get_minimized_{constraints,generators,congruences},
respectively;
* in the Prolog interfaces, the predicates
ppl_Grid_generalized_image_lhs_rhs/5 and
ppl_Grid_generalized_preimage_lhs_rhs/5
ppl_Grid_generalized_image/6 and
ppl_Grid_generalized_preimage/6
have been renamed as
ppl_Grid_generalized_image_lhs_rhs_with_congruence/5
ppl_Grid_generalized_preimage_lhs_rhs_with_congruence/5
ppl_Grid_generalized_image_with_congruence/6
ppl_Grid_generalized_preimage_with_congruence/6
respectively, so as to allow for /4 and /5, resp., versions.
o As already reported for the C++ interface, in the C interface,
all identifiers containing the strings `less_than_or_equal' or
`greater_than_or_equal', any case, have been renamed so as to contain
`less_or_equal' or `greater_or_equal', respectively.
o In the C interface it is no longer an error to call ppl_initialize()
or ppl_finalize() multiple times (this matches the behavior of the
other non-C++ language interfaces).
Documentation changes
---------------------
o The documentation for the library has been deeply reorganized and
split into several documents: besides the user and developer manuals
for the core library and its C++ interface, we now provide separate
user and developer manuals for each one of the other available
language interfaces (namely, C, Java, OCaml, and Prolog). It is
also possible to produce "configuration dependent" variants of the
non-C++ language interface manuals, where the contents of the
manual take into account the value of configuration option
`--enable-instantiations'.
All the manuals are provided in HTML, PDF and PostScript formats.
o New man pages libppl(3) and libppl_c(3) have been added. These
give short overviews on how to use the PPL in C++ and C programs,
respectively, on Unix-like operating systems.
Configuration changes
---------------------
o Several options have been added to the configuration script. These
allow to control the generated language interfaces, the floating
point instruction set to be used, the use of Valgrind during `make
check', the exclusion of some PPL-based programs from the build.
The README.configure file has been updated consequently.
Bugfixes
========
o Fixed bugs that prevented building the library on systems not supported
by the Parma Watchdog Library or when the `--disable-watchdog' configure
was used.
o Fixed a bug in Grid::constraints() and Grid::minimized_constraints()
that caused an internal assertion to fail when the grid had 0 space
dimensions.
o Fixed a bug in Linear_System::insert(const Linear_Row&) whereby a
wrong result could have been obtained when inserting a not necessarily
closed constraint/generator in an empty system having a higher space
dimension.
--------------------------------------------------------------------------
NEWS for version 0.9 (released on March 12, 2006)
--------------------------------------------------------------------------
New and Changed Features
========================
o The class Grid provides a complete implementation of the relational
domain of rational grids. This can represent all sets that can
be expressed by the conjunction of a finite number of congruence
equations. Operations provided include everything that is needed
in the field of static analysis and verification, including affine
images, preimages and their generalizations, grid-difference and