doc/isl.tex

   1 \section{\protect\isl/ interface}
   2
   3 \subsection{Library}
   4
   5 The \barvinok/ library currently supports just two
   6 functions that interface with the \isl/ library.
   7 In time, this interface will grow and is set to replace
   8 the \PolyLib/ interface.
   9 For more information on the \isl/ data structures, see
  10 the \isl/ user manual.
  11
  12 \begin{verbatim}
  13 __isl_give isl_pw_qpolynomial *isl_set_card(__isl_take isl_set *set);
  14 \end{verbatim}
  15 Compute the number of elements in an \ai[\tt]{isl\_set}.
  16 The resulting \ai[\tt]{isl\_pw\_qpolynomial} has purely parametric cells.
  17
  18 \begin{verbatim}
  19 __isl_give isl_pw_qpolynomial *isl_map_card(__isl_take isl_map *map);
  20 \end{verbatim}
  21 Compute a closed form expression for the number of image elements
  22 associated to any element in the domain of the given \ai[\tt]{isl\_map}.
  23 The union of the cells in the resulting \ai[\tt]{isl\_pw\_qpolynomial}
  24 is equal to the domain of the input \ai[\tt]{isl\_map}.
  25
  26 \begin{verbatim}
  27 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sum(
  28         __isl_take isl_pw_qpolynomial *pwqp);
  29 \end{verbatim}
  30 Compute the sum of the given piecewise quasipolynomial over
  31 all integer points in the domain.  The result is a piecewise
  32 quasipolynomial that only involves the parameters.
  33
  34 \subsection{Calculator}
  35
  36 The \ai[\tt]{iscc} calculator offers an interface to some
  37 of the functionality provided by the \isl/ and \barvinok/
  38 libraries.
  39 The supported operations are shown in \autoref{t:iscc}.
  40 Here are some examples:
  41 \begin{verbatim}
  42 P := [n, m] -> { [i,j] : 0 <= i <= n and i <= j <= m };
  43 card P;
  44
  45 f := [n,m] -> { [i,j] -> i*j + n*i*i*j : i,j >= 0 and 5i + 27j <= n+m };
  46 sum f;
  47 s := sum f;
  48 s @ [n,m] -> { [] : 0 <= n,m <= 20 };
  49
  50 f := [n] -> { [i] -> 2*n*i - n*n + 3*n - 1/2*i*i - 3/2*i-1 :
  51                 (exists j : 0 <= i < 4*n-1 and 0 <= j < n and
  52                             2*n-1 <= i+j <= 4*n-2 and i <= 2*n-1 ) };
  53 ub f;
  54 u := ub f;
  55 u @ [n] -> { [] : 0 <= n <= 10 };
  56
  57 m := [n] -> { [i,j] -> [i+1,j+1] : 1 <= i,j < n;
  58               [i,j] -> [i+1,j-1] : 1 <= i < n and 2 <= j <= n };
  59 m^+;
  60 (m^+)[0];
  61 \end{verbatim}
  62
  63 \bottomcaption{{\tt iscc} operations.  The variables
  64 have the following types,
  65 $s$: set,
  66 $m$: map,
  67 $q$: piecewise quasipolynomial,
  68 $f$: piecewise quasipolynomial fold,
  69 $l$: list,
  70 $i$: integer,
  71 $b$: boolean,
  72 $o$: object of any type
  73 }
  74 \label{t:iscc}
  75 \tablehead{
  76 Syntax & Meaning
  77 \\
  78 \hline
  79 }
  80 \tabletail{
  81 \multicolumn{2}{r}{\small\sl continued on next page}
  82 \\
  83 }
  84 \tablelasttail{}
  85 \begin{supertabular}{lp{0.7\textwidth}}
  86 $s_2$ := \ai[\tt]{aff} $s_1$ & affine hull of $s_1$
  87 \\
  88 $m_2$ := \ai[\tt]{aff} $m_1$ & affine hull of $m_1$
  89 \\
  90 $q$ := \ai[\tt]{card} $s$ &
  91 number of elements in the set $s$
  92 \\
  93 $q$ := \ai[\tt]{card} $m$ &
  94 number of elements in the image of a domain element
  95 \\
  96 $s_2$ := \ai[\tt]{coalesce} $s_1$ &
  97 simplify the representation of set $s_1$ by trying
  98 to combine pairs of basic sets into a single
  99 basic set
 100 \\
 101 $m_2$ := \ai[\tt]{coalesce} $m_1$ &
 102 simplify the representation of map $m_1$ by trying
 103 to combine pairs of basic maps into a single
 104 basic map
 105 \\
 106 $q_2$ := \ai[\tt]{coalesce} $q_1$ &
 107 simplify the representation of $q_1$ by trying
 108 to combine pairs of basic sets in the domain
 109 of $q_1$ into a single basic set
 110 \\
 111 $f_2$ := \ai[\tt]{coalesce} $f_1$ &
 112 simplify the representation of $f_1$ by trying
 113 to combine pairs of basic sets in the domain
 114 of $f_1$ into a single basic set
 115 \\
 116 $s_3$ := $s_1$ \ai[\tt]{cross} $s_2$ &
 117 Cartesian product of $s_1$ and $s_2$
 118 \\
 119 $m_3$ := $m_1$ \ai[\tt]{cross} $m_2$ &
 120 Cartesian product of $m_1$ and $m_2$
 121 \\
 122 $s$ := \ai[\tt]{deltas} $m$ &
 123 the set $\{\, y - x \mid x \to y \in m \,\}$
 124 \\
 125 $s$ := \ai[\tt]{dom} $m$ &
 126 domain of map $m$
 127 \\
 128 $s$ := \ai[\tt]{dom} $q$ &
 129 domain of piecewise quasipolynomial $q$
 130 \\
 131 $s$ := \ai[\tt]{dom} $f$ &
 132 domain of piecewise quasipolynomial fold $f$
 133 \\
 134 $s$ := \ai[\tt]{ran} $m$ &
 135 range of map $m$
 136 \\
 137 $s_2$ := \ai[\tt]{lexmin} $s_1$ &
 138 lexicographically minimal element of $s_1$
 139 \\
 140 $m_2$ := \ai[\tt]{lexmin} $m_1$ &
 141 lexicographically minimal image element
 142 \\
 143 $s_2$ := \ai[\tt]{lexmax} $s_1$ &
 144 lexicographically maximal element of $s_1$
 145 \\
 146 $m_2$ := \ai[\tt]{lexmax} $m_1$ &
 147 lexicographically maximal image element
 148 \\
 149 $o$ := \ai[\tt]{read} {\tt "}{\it filename}{\tt"} &
 150 read object from file
 151 \\
 152 $s_2$ := \ai[\tt]{sample} $s_1$ &
 153 a sample element of the set $s_1$
 154 \\
 155 $m_2$ := \ai[\tt]{sample} $m_1$ &
 156 a sample element of the map $m_1$
 157 \\
 158 $q_2$ := \ai[\tt]{sum} $q_1$ &
 159 sum $q_1$ over all integer points in the domain of $q_1$
 160 \\
 161 $f$ := \ai[\tt]{ub} $q$ &
 162 upper bound on the piecewise quasipolynomial $q$ over
 163 all integer points in the domain of $q$.
 164 This operation is only available if
 165 \ai[\tt]{GiNaC} support was compiled in.
 166 \\
 167 $s_3$ := $s_1$ \ai{$+$} $s_2$ & union
 168 \\
 169 $m_3$ := $m_1$ \ai{$+$} $m_2$ & union
 170 \\
 171 $q_3$ := $q_1$ \ai{$+$} $q_2$ & sum
 172 \\
 173 $s_3$ := $s_1$ \ai{$-$} $s_2$ & set difference
 174 \\
 175 $m_3$ := $m_1$ \ai{$-$} $m_2$ & set difference
 176 \\
 177 $q_3$ := $q_1$ \ai{$-$} $q_2$ & difference
 178 \\
 179 $s_3$ := $s_1$ \ai{$*$} $s_2$ & intersection
 180 \\
 181 $m_3$ := $m_1$ \ai{$*$} $m_2$ & intersection
 182 \\
 183 $q_3$ := $q_1$ \ai{$*$} $q_2$ & product
 184 \\
 185 $m_2$ := $m_1$ \ai{$*$} $s$ & intersect domain of $m_1$ with $s$
 186 \\
 187 $q_2$ := $q_1$ \ai{$*$} $s$ & intersect domain of $q_1$ with $s$
 188 \\
 189 $f_2$ := $f_1$ \ai{$*$} $s$ & intersect domain of $f_1$ with $s$
 190 \\
 191 $s_2$ := $m$($s_1$) & apply map $m$ to set $s_1$
 192 \\
 193 $m_3$ := $m_1$ \ai[\tt]{.} $m_2$ & join of $m_1$ and $m_2$
 194 \\
 195 $m_3$ := $m_2$($m_1)$ & join of $m_1$ and $m_2$
 196 \\
 197 $m$ := $s_1$ \ai[\tt]{->} $s_2$ & universal map with domain $s_1$
 198 and range $s_2$
 199 \\
 200 $q_2$ := $q_1$ \ai{@} $s$ &
 201 evaluate the piecewise quasipolynomial $q_1$ in each element
 202 of the set $s$ and return a piecewise quasipolynomial
 203 mapping each of the individual elements to the resulting
 204 constant
 205 \\
 206 $q$ := $f$ \ai{@} $s$ &
 207 evaluate the piecewise quasipolynomial fold $f$ in each element
 208 of the set $s$ and return a piecewise quasipolynomial
 209 mapping each of the individual elements to the resulting
 210 constant
 211 \\
 212 $s_3$ := $s_1$ \ai[\tt]{\%} $s_2$ &
 213 simplify $s_1$ in the context of $s_2$, i.e., compute
 214 the gist of $s_1$ given $s_2$
 215 \\
 216 $m_3$ := $m_1$ \ai[\tt]{\%} $m_2$ &
 217 simplify $m_1$ in the context of $m_2$, i.e., compute
 218 the gist of $m_1$ given $m_2$
 219 \\
 220 $q_2$ := $q_1$ \ai[\tt]{\%} $s$ &
 221 simplify $q_1$ in the context of the domain $s$, i.e., compute
 222 the gist of $q_1$ given $s$
 223 \\
 224 $f_2$ := $f_1$ \ai[\tt]{\%} $s$ &
 225 simplify $f_1$ in the context of the domain $s$, i.e., compute
 226 the gist of $f_1$ given $s$
 227 \\
 228 $m_2$ := $m_1$\ai[\tt]{\^{}-1} & inverse of $m_1$
 229 \\
 230 $l$ := $m$\ai[\tt]{\^{}+} &
 231 compute an overapproximation of the transitive closure
 232 of $m$ and return a list containing the overapproximation
 233 and a boolean that is true if the overapproximation
 234 is known to be exact
 235 \\
 236 $o$ := $l$[$i$] &
 237 the element at position $i$ in the list $l$
 238 \\
 239 $b$ := $s_1$ \ai[\tt]{=} $s_2$ & is $s_1$ equal to $s_2$?
 240 \\
 241 $b$ := $m_1$ \ai[\tt]{=} $m_2$ & is $m_1$ equal to $m_2$?
 242 \\
 243 $b$ := $s_1$ \ai[\tt]{<=} $s_2$ & is $s_1$ a subset of $s_2$?
 244 \\
 245 $b$ := $m_1$ \ai[\tt]{<=} $m_2$ & is $m_1$ a subset of $m_2$?
 246 \\
 247 $b$ := $s_1$ \ai[\tt]{<} $s_2$ & is $s_1$ a proper subset of $s_2$?
 248 \\
 249 $b$ := $m_1$ \ai[\tt]{<} $m_2$ & is $m_1$ a proper subset of $m_2$?
 250 \\
 251 $b$ := $s_1$ \ai[\tt]{>=} $s_2$ & is $s_1$ a superset of $s_2$?
 252 \\
 253 $b$ := $m_1$ \ai[\tt]{>=} $m_2$ & is $m_1$ a superset of $m_2$?
 254 \\
 255 $b$ := $s_1$ \ai[\tt]{>} $s_2$ & is $s_1$ a proper superset of $s_2$?
 256 \\
 257 $b$ := $m_1$ \ai[\tt]{>} $m_2$ & is $m_1$ a proper superset of $m_2$?
 258 \\
 259 \end{supertabular}