doc/isl.tex

   1 \section{\protect\isl/ interface}
   2
   3 \subsection{Library}
   4
   5 The \barvinok/ library currently supports only a few
   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 __isl_give isl_union_pw_qpolynomial *isl_union_set_card(
  15         __isl_take isl_union_set *uset);
  16 \end{verbatim}
  17 Compute the number of elements in an \ai[\tt]{isl\_set}
  18 or \ai[\tt]{isl\_union\_set}.
  19 The resulting \ai[\tt]{isl\_pw\_qpolynomial}
  20 or \ai[\tt]{isl\_union\_pw\_qpolynomial} has purely parametric cells.
  21
  22 \begin{verbatim}
  23 __isl_give isl_pw_qpolynomial *isl_map_card(__isl_take isl_map *map);
  24 __isl_give isl_union_pw_qpolynomial *isl_union_map_card(
  25         __isl_take isl_union_map *umap);
  26 \end{verbatim}
  27 Compute a closed form expression for the number of image elements
  28 associated to any element in the domain of the given \ai[\tt]{isl\_map}
  29 or \ai[\tt]{isl\_union\_map}.
  30 The union of the cells in the resulting \ai[\tt]{isl\_pw\_qpolynomial}
  31 is equal to the domain of the input \ai[\tt]{isl\_map}.
  32
  33 \begin{verbatim}
  34 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sum(
  35         __isl_take isl_pw_qpolynomial *pwqp);
  36 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sum(
  37         __isl_take isl_union_pw_qpolynomial *upwqp);
  38 \end{verbatim}
  39 Compute the sum of the given piecewise quasipolynomial over
  40 all integer points in the domain.  The result is a piecewise
  41 quasipolynomial that only involves the parameters.
  42 If, however, the domain of the piecewise quasipolynomial wraps
  43 a relation, then the sum is computed over all integer points
  44 in the range of that relation and the domain of the relation
  45 becomes the domain of the result.
  46
  47 \begin{verbatim}
  48 __isl_give isl_pw_qpolynomial *isl_map_apply_pw_qpolynomial(
  49         __isl_take isl_map *map, __isl_take isl_pw_qpolynomial *pwqp);
  50 __isl_give isl_union_pw_qpolynomial *isl_union_map_apply_union_pw_qpolynomial(
  51         __isl_take isl_union_map *umap,
  52         __isl_take isl_union_pw_qpolynomial *upwqp);
  53 \end{verbatim}
  54 Compose the given map with the given piecewise quasipolynomial.
  55 That is, compute the sum over all elements in the intersection
  56 of the range of the map and the domain of the piecewise quasipolynomial
  57 as a function of an element in the domain of the map.
  58
  59 \subsection{Calculator}
  60
  61 The \ai[\tt]{iscc} calculator offers an interface to some
  62 of the functionality provided by the \isl/ and \barvinok/
  63 libraries.
  64 The supported operations are shown in \autoref{t:iscc}.
  65 Here are some examples:
  66 \begin{verbatim}
  67 P := [n, m] -> { [i,j] : 0 <= i <= n and i <= j <= m };
  68 card P;
  69
  70 f := [n,m] -> { [i,j] -> i*j + n*i*i*j : i,j >= 0 and 5i + 27j <= n+m };
  71 sum f;
  72 s := sum f;
  73 s @ [n,m] -> { [] : 0 <= n,m <= 20 };
  74
  75 f := [n] -> { [i] -> 2*n*i - n*n + 3*n - 1/2*i*i - 3/2*i-1 :
  76                 (exists j : 0 <= i < 4*n-1 and 0 <= j < n and
  77                             2*n-1 <= i+j <= 4*n-2 and i <= 2*n-1 ) };
  78 ub f;
  79 u := (ub f)[0];
  80 u @ [n] -> { [] : 0 <= n <= 10 };
  81
  82 m := [n] -> { [i,j] -> [i+1,j+1] : 1 <= i,j < n;
  83               [i,j] -> [i+1,j-1] : 1 <= i < n and 2 <= j <= n };
  84 m^+;
  85 (m^+)[0];
  86
  87 codegen [N] -> { A[i] -> [i,0] : 0 <= i <= N; B[i] -> [i,1] : 1 <= i <= N };
  88
  89 { [k] -> [i] : 1 <= i <= k } . { [n] -> 2 * n : n >= 1 };
  90
  91 { [m] -> [c] : 1 <= c <= m } . { [k] -> max((3 * k + k^2)) : k >= 1 };
  92 \end{verbatim}
  93
  94 \bottomcaption{{\tt iscc} operations.  The variables
  95 have the following types,
  96 $s$: set,
  97 $m$: map,
  98 $q$: piecewise quasipolynomial,
  99 $f$: piecewise quasipolynomial fold,
 100 $l$: list,
 101 $i$: integer,
 102 $b$: boolean,
 103 $o$: object of any type
 104 }
 105 \label{t:iscc}
 106 \tablehead{
 107 \hline
 108 Syntax & Meaning
 109 \\
 110 \hline
 111 }
 112 \tabletail{
 113 \multicolumn{2}{r}{\small\sl continued on next page}
 114 \\
 115 }
 116 \tablelasttail{}
 117 \begin{supertabular}{lp{0.7\textwidth}}
 118 $s_2$ := \ai[\tt]{aff} $s_1$ & affine hull of $s_1$
 119 \\
 120 $m_2$ := \ai[\tt]{aff} $m_1$ & affine hull of $m_1$
 121 \\
 122 $q$ := \ai[\tt]{card} $s$ &
 123 number of elements in the set $s$
 124 \\
 125 $q$ := \ai[\tt]{card} $m$ &
 126 number of elements in the image of a domain element
 127 \\
 128 $s_2$ := \ai[\tt]{coalesce} $s_1$ &
 129 simplify the representation of set $s_1$ by trying
 130 to combine pairs of basic sets into a single
 131 basic set
 132 \\
 133 $m_2$ := \ai[\tt]{coalesce} $m_1$ &
 134 simplify the representation of map $m_1$ by trying
 135 to combine pairs of basic maps into a single
 136 basic map
 137 \\
 138 $q_2$ := \ai[\tt]{coalesce} $q_1$ &
 139 simplify the representation of $q_1$ by trying
 140 to combine pairs of basic sets in the domain
 141 of $q_1$ into a single basic set
 142 \\
 143 $f_2$ := \ai[\tt]{coalesce} $f_1$ &
 144 simplify the representation of $f_1$ by trying
 145 to combine pairs of basic sets in the domain
 146 of $f_1$ into a single basic set
 147 \\
 148 \ai[\tt]{codegen} $s$ &
 149 generate code for the given domain.
 150 This operation is only available if \ai[\tt]{CLooG}
 151 support was compiled in.
 152 \\
 153 \ai[\tt]{codegen} $m$ &
 154 generate code for the given scattering function.
 155 This operation is only available if \ai[\tt]{CLooG}
 156 support was compiled in.
 157 \\
 158 $s_3$ := $s_1$ \ai[\tt]{cross} $s_2$ &
 159 Cartesian product of $s_1$ and $s_2$
 160 \\
 161 $m_3$ := $m_1$ \ai[\tt]{cross} $m_2$ &
 162 Cartesian product of $m_1$ and $m_2$
 163 \\
 164 $s$ := \ai[\tt]{deltas} $m$ &
 165 the set $\{\, y - x \mid x \to y \in m \,\}$
 166 \\
 167 $s$ := \ai[\tt]{dom} $m$ &
 168 domain of map $m$
 169 \\
 170 $s$ := \ai[\tt]{dom} $q$ &
 171 domain of piecewise quasipolynomial $q$
 172 \\
 173 $s$ := \ai[\tt]{dom} $f$ &
 174 domain of piecewise quasipolynomial fold $f$
 175 \\
 176 $s$ := \ai[\tt]{ran} $m$ &
 177 range of map $m$
 178 \\
 179 $s_2$ := \ai[\tt]{lexmin} $s_1$ &
 180 lexicographically minimal element of $s_1$
 181 \\
 182 $m_2$ := \ai[\tt]{lexmin} $m_1$ &
 183 lexicographically minimal image element
 184 \\
 185 $s_2$ := \ai[\tt]{lexmax} $s_1$ &
 186 lexicographically maximal element of $s_1$
 187 \\
 188 $m_2$ := \ai[\tt]{lexmax} $m_1$ &
 189 lexicographically maximal image element
 190 \\
 191 $o$ := \ai[\tt]{read} {\tt "}{\it filename}{\tt"} &
 192 read object from file
 193 \\
 194 $s_2$ := \ai[\tt]{sample} $s_1$ &
 195 a sample element of the set $s_1$
 196 \\
 197 $m_2$ := \ai[\tt]{sample} $m_1$ &
 198 a sample element of the map $m_1$
 199 \\
 200 $q_2$ := \ai[\tt]{sum} $q_1$ &
 201 sum $q_1$ over all integer points in the domain of $q_1$,
 202 or, if the domain of $q_1$ wraps a map, over all integer
 203 points in the range of the wrapped map.
 204 \\
 205 $l$ := \ai[\tt]{ub} $q$ &
 206 compute an
 207 upper bound on the piecewise quasipolynomial $q$ over
 208 all integer points in the domain of $q$
 209 and return a list containing the upper bound
 210 and a boolean that is true if the upper bound
 211 is known to be tight.
 212 If the domain of $q$ wraps a map, then the upper
 213 bound is computed over all integer points in
 214 the range of the wrapped map instead.
 215 \\
 216 $l$ := \ai[\tt]{vertices} $s$ &
 217 a list of vertices of the rational polytope defined by the same constraints
 218 as $s$
 219 \\
 220 $s$ := \ai[\tt]{wrap} $m$ &
 221 wrap the map in a set
 222 \\
 223 $m$ := \ai[\tt]{unwrap} $s$ &
 224 unwrap the map from the set
 225 \\
 226 $s_3$ := $s_1$ \ai{$+$} $s_2$ & union
 227 \\
 228 $m_3$ := $m_1$ \ai{$+$} $m_2$ & union
 229 \\
 230 $q_3$ := $q_1$ \ai{$+$} $q_2$ & sum
 231 \\
 232 $f_2$ := $f_1$ \ai{$+$} $q$ & sum
 233 \\
 234 $f_2$ := $q$ \ai{$+$} $f_1$ & sum
 235 \\
 236 $s_3$ := $s_1$ \ai{$-$} $s_2$ & set difference
 237 \\
 238 $m_3$ := $m_1$ \ai{$-$} $m_2$ & set difference
 239 \\
 240 $q_3$ := $q_1$ \ai{$-$} $q_2$ & difference
 241 \\
 242 $s_3$ := $s_1$ \ai{$*$} $s_2$ & intersection
 243 \\
 244 $m_3$ := $m_1$ \ai{$*$} $m_2$ & intersection
 245 \\
 246 $q_3$ := $q_1$ \ai{$*$} $q_2$ & product
 247 \\
 248 $m_2$ := $m_1$ \ai{$*$} $s$ & intersect domain of $m_1$ with $s$
 249 \\
 250 $q_2$ := $q_1$ \ai{$*$} $s$ & intersect domain of $q_1$ with $s$
 251 \\
 252 $f_2$ := $f_1$ \ai{$*$} $s$ & intersect domain of $f_1$ with $s$
 253 \\
 254 $s_2$ := $m$($s_1$) & apply map $m$ to set $s_1$
 255 \\
 256 $m_3$ := $m_1$ \ai[\tt]{.} $m_2$ & join of $m_1$ and $m_2$
 257 \\
 258 $m_3$ := $m_2$($m_1)$ & join of $m_1$ and $m_2$
 259 \\
 260 $f_3$ := $f_1$ \ai[\tt]{.} $f_2$ & join of $f_1$ and $f_2$, combining
 261 the lists of quasipolynomials over shared domains
 262 \\
 263 $q_2$ := $m$ \ai[\tt]{.} $q_1$ & join of $m$ and $q_1$, taking the sum
 264 over all elements in the intersection of the range of $m$ and the domain
 265 of $q_1$
 266 \\
 267 $f_2$ := $m$ \ai[\tt]{.} $f_1$ & join of $m$ and $f_1$, computing a bound
 268 over all elements in the intersection of the range of $m$ and the domain
 269 of $f_1$
 270 \\
 271 $m$ := $s_1$ \ai[\tt]{->} $s_2$ & universal map with domain $s_1$
 272 and range $s_2$
 273 \\
 274 $q_2$ := $q_1$ \ai{@} $s$ &
 275 evaluate the piecewise quasipolynomial $q_1$ in each element
 276 of the set $s$ and return a piecewise quasipolynomial
 277 mapping each of the individual elements to the resulting
 278 constant
 279 \\
 280 $q$ := $f$ \ai{@} $s$ &
 281 evaluate the piecewise quasipolynomial fold $f$ in each element
 282 of the set $s$ and return a piecewise quasipolynomial
 283 mapping each of the individual elements to the resulting
 284 constant
 285 \\
 286 $s_3$ := $s_1$ \ai[\tt]{\%} $s_2$ &
 287 simplify $s_1$ in the context of $s_2$, i.e., compute
 288 the gist of $s_1$ given $s_2$
 289 \\
 290 $m_3$ := $m_1$ \ai[\tt]{\%} $m_2$ &
 291 simplify $m_1$ in the context of $m_2$, i.e., compute
 292 the gist of $m_1$ given $m_2$
 293 \\
 294 $q_2$ := $q_1$ \ai[\tt]{\%} $s$ &
 295 simplify $q_1$ in the context of the domain $s$, i.e., compute
 296 the gist of $q_1$ given $s$
 297 \\
 298 $f_2$ := $f_1$ \ai[\tt]{\%} $s$ &
 299 simplify $f_1$ in the context of the domain $s$, i.e., compute
 300 the gist of $f_1$ given $s$
 301 \\
 302 $m_2$ := $m_1$\ai[\tt]{\^{}-1} & inverse of $m_1$
 303 \\
 304 $l$ := $m$\ai[\tt]{\^{}+} &
 305 compute an overapproximation of the transitive closure
 306 of $m$ and return a list containing the overapproximation
 307 and a boolean that is true if the overapproximation
 308 is known to be exact
 309 \\
 310 $o$ := $l$[$i$] &
 311 the element at position $i$ in the list $l$
 312 \\
 313 $b$ := $s_1$ \ai[\tt]{=} $s_2$ & is $s_1$ equal to $s_2$?
 314 \\
 315 $b$ := $m_1$ \ai[\tt]{=} $m_2$ & is $m_1$ equal to $m_2$?
 316 \\
 317 $b$ := $s_1$ \ai[\tt]{<=} $s_2$ & is $s_1$ a subset of $s_2$?
 318 \\
 319 $b$ := $m_1$ \ai[\tt]{<=} $m_2$ & is $m_1$ a subset of $m_2$?
 320 \\
 321 $b$ := $s_1$ \ai[\tt]{<} $s_2$ & is $s_1$ a proper subset of $s_2$?
 322 \\
 323 $b$ := $m_1$ \ai[\tt]{<} $m_2$ & is $m_1$ a proper subset of $m_2$?
 324 \\
 325 $b$ := $s_1$ \ai[\tt]{>=} $s_2$ & is $s_1$ a superset of $s_2$?
 326 \\
 327 $b$ := $m_1$ \ai[\tt]{>=} $m_2$ & is $m_1$ a superset of $m_2$?
 328 \\
 329 $b$ := $s_1$ \ai[\tt]{>} $s_2$ & is $s_1$ a proper superset of $s_2$?
 330 \\
 331 $b$ := $m_1$ \ai[\tt]{>} $m_2$ & is $m_1$ a proper superset of $m_2$?
 332 \\
 333 \end{supertabular}