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 \end{verbatim}
  91
  92 \bottomcaption{{\tt iscc} operations.  The variables
  93 have the following types,
  94 $s$: set,
  95 $m$: map,
  96 $q$: piecewise quasipolynomial,
  97 $f$: piecewise quasipolynomial fold,
  98 $l$: list,
  99 $i$: integer,
 100 $b$: boolean,
 101 $o$: object of any type
 102 }
 103 \label{t:iscc}
 104 \tablehead{
 105 \hline
 106 Syntax & Meaning
 107 \\
 108 \hline
 109 }
 110 \tabletail{
 111 \multicolumn{2}{r}{\small\sl continued on next page}
 112 \\
 113 }
 114 \tablelasttail{}
 115 \begin{supertabular}{lp{0.7\textwidth}}
 116 $s_2$ := \ai[\tt]{aff} $s_1$ & affine hull of $s_1$
 117 \\
 118 $m_2$ := \ai[\tt]{aff} $m_1$ & affine hull of $m_1$
 119 \\
 120 $q$ := \ai[\tt]{card} $s$ &
 121 number of elements in the set $s$
 122 \\
 123 $q$ := \ai[\tt]{card} $m$ &
 124 number of elements in the image of a domain element
 125 \\
 126 $s_2$ := \ai[\tt]{coalesce} $s_1$ &
 127 simplify the representation of set $s_1$ by trying
 128 to combine pairs of basic sets into a single
 129 basic set
 130 \\
 131 $m_2$ := \ai[\tt]{coalesce} $m_1$ &
 132 simplify the representation of map $m_1$ by trying
 133 to combine pairs of basic maps into a single
 134 basic map
 135 \\
 136 $q_2$ := \ai[\tt]{coalesce} $q_1$ &
 137 simplify the representation of $q_1$ by trying
 138 to combine pairs of basic sets in the domain
 139 of $q_1$ into a single basic set
 140 \\
 141 $f_2$ := \ai[\tt]{coalesce} $f_1$ &
 142 simplify the representation of $f_1$ by trying
 143 to combine pairs of basic sets in the domain
 144 of $f_1$ into a single basic set
 145 \\
 146 \ai[\tt]{codegen} $s$ &
 147 generate code for the given domain.
 148 This operation is only available if \ai[\tt]{CLooG}
 149 support was compiled in.
 150 \\
 151 \ai[\tt]{codegen} $m$ &
 152 generate code for the given scattering function.
 153 This operation is only available if \ai[\tt]{CLooG}
 154 support was compiled in.
 155 \\
 156 $s_3$ := $s_1$ \ai[\tt]{cross} $s_2$ &
 157 Cartesian product of $s_1$ and $s_2$
 158 \\
 159 $m_3$ := $m_1$ \ai[\tt]{cross} $m_2$ &
 160 Cartesian product of $m_1$ and $m_2$
 161 \\
 162 $s$ := \ai[\tt]{deltas} $m$ &
 163 the set $\{\, y - x \mid x \to y \in m \,\}$
 164 \\
 165 $s$ := \ai[\tt]{dom} $m$ &
 166 domain of map $m$
 167 \\
 168 $s$ := \ai[\tt]{dom} $q$ &
 169 domain of piecewise quasipolynomial $q$
 170 \\
 171 $s$ := \ai[\tt]{dom} $f$ &
 172 domain of piecewise quasipolynomial fold $f$
 173 \\
 174 $s$ := \ai[\tt]{ran} $m$ &
 175 range of map $m$
 176 \\
 177 $s_2$ := \ai[\tt]{lexmin} $s_1$ &
 178 lexicographically minimal element of $s_1$
 179 \\
 180 $m_2$ := \ai[\tt]{lexmin} $m_1$ &
 181 lexicographically minimal image element
 182 \\
 183 $s_2$ := \ai[\tt]{lexmax} $s_1$ &
 184 lexicographically maximal element of $s_1$
 185 \\
 186 $m_2$ := \ai[\tt]{lexmax} $m_1$ &
 187 lexicographically maximal image element
 188 \\
 189 $o$ := \ai[\tt]{read} {\tt "}{\it filename}{\tt"} &
 190 read object from file
 191 \\
 192 $s_2$ := \ai[\tt]{sample} $s_1$ &
 193 a sample element of the set $s_1$
 194 \\
 195 $m_2$ := \ai[\tt]{sample} $m_1$ &
 196 a sample element of the map $m_1$
 197 \\
 198 $q_2$ := \ai[\tt]{sum} $q_1$ &
 199 sum $q_1$ over all integer points in the domain of $q_1$,
 200 or, if the domain of $q_1$ wraps a map, over all integer
 201 points in the range of the wrapped map.
 202 \\
 203 $l$ := \ai[\tt]{ub} $q$ &
 204 compute an
 205 upper bound on the piecewise quasipolynomial $q$ over
 206 all integer points in the domain of $q$
 207 and return a list containing the upper bound
 208 and a boolean that is true if the upper bound
 209 is known to be tight.
 210 If the domain of $q$ wraps a map, then the upper
 211 bound is computed over all integer points in
 212 the range of the wrapped map instead.
 213 \\
 214 $l$ := \ai[\tt]{vertices} $s$ &
 215 a list of vertices of the rational polytope defined by the same constraints
 216 as $s$
 217 \\
 218 $s$ := \ai[\tt]{wrap} $m$ &
 219 wrap the map in a set
 220 \\
 221 $m$ := \ai[\tt]{unwrap} $s$ &
 222 unwrap the map from the set
 223 \\
 224 $s_3$ := $s_1$ \ai{$+$} $s_2$ & union
 225 \\
 226 $m_3$ := $m_1$ \ai{$+$} $m_2$ & union
 227 \\
 228 $q_3$ := $q_1$ \ai{$+$} $q_2$ & sum
 229 \\
 230 $s_3$ := $s_1$ \ai{$-$} $s_2$ & set difference
 231 \\
 232 $m_3$ := $m_1$ \ai{$-$} $m_2$ & set difference
 233 \\
 234 $q_3$ := $q_1$ \ai{$-$} $q_2$ & difference
 235 \\
 236 $s_3$ := $s_1$ \ai{$*$} $s_2$ & intersection
 237 \\
 238 $m_3$ := $m_1$ \ai{$*$} $m_2$ & intersection
 239 \\
 240 $q_3$ := $q_1$ \ai{$*$} $q_2$ & product
 241 \\
 242 $m_2$ := $m_1$ \ai{$*$} $s$ & intersect domain of $m_1$ with $s$
 243 \\
 244 $q_2$ := $q_1$ \ai{$*$} $s$ & intersect domain of $q_1$ with $s$
 245 \\
 246 $f_2$ := $f_1$ \ai{$*$} $s$ & intersect domain of $f_1$ with $s$
 247 \\
 248 $s_2$ := $m$($s_1$) & apply map $m$ to set $s_1$
 249 \\
 250 $m_3$ := $m_1$ \ai[\tt]{.} $m_2$ & join of $m_1$ and $m_2$
 251 \\
 252 $m_3$ := $m_2$($m_1)$ & join of $m_1$ and $m_2$
 253 \\
 254 $q_2$ := $m$ \ai[\tt]{.} $q_1$ & join of $m$ and $q_1$, taking the sum
 255 over all elements in the intersection of the range of $m$ and the domain
 256 of $q_1$
 257 \\
 258 $m$ := $s_1$ \ai[\tt]{->} $s_2$ & universal map with domain $s_1$
 259 and range $s_2$
 260 \\
 261 $q_2$ := $q_1$ \ai{@} $s$ &
 262 evaluate the piecewise quasipolynomial $q_1$ in each element
 263 of the set $s$ and return a piecewise quasipolynomial
 264 mapping each of the individual elements to the resulting
 265 constant
 266 \\
 267 $q$ := $f$ \ai{@} $s$ &
 268 evaluate the piecewise quasipolynomial fold $f$ in each element
 269 of the set $s$ and return a piecewise quasipolynomial
 270 mapping each of the individual elements to the resulting
 271 constant
 272 \\
 273 $s_3$ := $s_1$ \ai[\tt]{\%} $s_2$ &
 274 simplify $s_1$ in the context of $s_2$, i.e., compute
 275 the gist of $s_1$ given $s_2$
 276 \\
 277 $m_3$ := $m_1$ \ai[\tt]{\%} $m_2$ &
 278 simplify $m_1$ in the context of $m_2$, i.e., compute
 279 the gist of $m_1$ given $m_2$
 280 \\
 281 $q_2$ := $q_1$ \ai[\tt]{\%} $s$ &
 282 simplify $q_1$ in the context of the domain $s$, i.e., compute
 283 the gist of $q_1$ given $s$
 284 \\
 285 $f_2$ := $f_1$ \ai[\tt]{\%} $s$ &
 286 simplify $f_1$ in the context of the domain $s$, i.e., compute
 287 the gist of $f_1$ given $s$
 288 \\
 289 $m_2$ := $m_1$\ai[\tt]{\^{}-1} & inverse of $m_1$
 290 \\
 291 $l$ := $m$\ai[\tt]{\^{}+} &
 292 compute an overapproximation of the transitive closure
 293 of $m$ and return a list containing the overapproximation
 294 and a boolean that is true if the overapproximation
 295 is known to be exact
 296 \\
 297 $o$ := $l$[$i$] &
 298 the element at position $i$ in the list $l$
 299 \\
 300 $b$ := $s_1$ \ai[\tt]{=} $s_2$ & is $s_1$ equal to $s_2$?
 301 \\
 302 $b$ := $m_1$ \ai[\tt]{=} $m_2$ & is $m_1$ equal to $m_2$?
 303 \\
 304 $b$ := $s_1$ \ai[\tt]{<=} $s_2$ & is $s_1$ a subset of $s_2$?
 305 \\
 306 $b$ := $m_1$ \ai[\tt]{<=} $m_2$ & is $m_1$ a subset of $m_2$?
 307 \\
 308 $b$ := $s_1$ \ai[\tt]{<} $s_2$ & is $s_1$ a proper subset of $s_2$?
 309 \\
 310 $b$ := $m_1$ \ai[\tt]{<} $m_2$ & is $m_1$ a proper subset of $m_2$?
 311 \\
 312 $b$ := $s_1$ \ai[\tt]{>=} $s_2$ & is $s_1$ a superset of $s_2$?
 313 \\
 314 $b$ := $m_1$ \ai[\tt]{>=} $m_2$ & is $m_1$ a superset of $m_2$?
 315 \\
 316 $b$ := $s_1$ \ai[\tt]{>} $s_2$ & is $s_1$ a proper superset of $s_2$?
 317 \\
 318 $b$ := $m_1$ \ai[\tt]{>} $m_2$ & is $m_1$ a proper superset of $m_2$?
 319 \\
 320 \end{supertabular}