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} $m$ &
 147 generate code for the given scattering function.
 148 This operation is only available if \ai[\tt]{CLooG}
 149 support was compiled in.
 150 \\
 151 $s_3$ := $s_1$ \ai[\tt]{cross} $s_2$ &
 152 Cartesian product of $s_1$ and $s_2$
 153 \\
 154 $m_3$ := $m_1$ \ai[\tt]{cross} $m_2$ &
 155 Cartesian product of $m_1$ and $m_2$
 156 \\
 157 $s$ := \ai[\tt]{deltas} $m$ &
 158 the set $\{\, y - x \mid x \to y \in m \,\}$
 159 \\
 160 $s$ := \ai[\tt]{dom} $m$ &
 161 domain of map $m$
 162 \\
 163 $s$ := \ai[\tt]{dom} $q$ &
 164 domain of piecewise quasipolynomial $q$
 165 \\
 166 $s$ := \ai[\tt]{dom} $f$ &
 167 domain of piecewise quasipolynomial fold $f$
 168 \\
 169 $s$ := \ai[\tt]{ran} $m$ &
 170 range of map $m$
 171 \\
 172 $s_2$ := \ai[\tt]{lexmin} $s_1$ &
 173 lexicographically minimal element of $s_1$
 174 \\
 175 $m_2$ := \ai[\tt]{lexmin} $m_1$ &
 176 lexicographically minimal image element
 177 \\
 178 $s_2$ := \ai[\tt]{lexmax} $s_1$ &
 179 lexicographically maximal element of $s_1$
 180 \\
 181 $m_2$ := \ai[\tt]{lexmax} $m_1$ &
 182 lexicographically maximal image element
 183 \\
 184 $o$ := \ai[\tt]{read} {\tt "}{\it filename}{\tt"} &
 185 read object from file
 186 \\
 187 $s_2$ := \ai[\tt]{sample} $s_1$ &
 188 a sample element of the set $s_1$
 189 \\
 190 $m_2$ := \ai[\tt]{sample} $m_1$ &
 191 a sample element of the map $m_1$
 192 \\
 193 $q_2$ := \ai[\tt]{sum} $q_1$ &
 194 sum $q_1$ over all integer points in the domain of $q_1$,
 195 or, if the domain of $q_1$ wraps a map, over all integer
 196 points in the range of the wrapped map.
 197 \\
 198 $l$ := \ai[\tt]{ub} $q$ &
 199 compute an
 200 upper bound on the piecewise quasipolynomial $q$ over
 201 all integer points in the domain of $q$
 202 and return a list containing the upper bound
 203 and a boolean that is true if the upper bound
 204 is known to be tight.
 205 If the domain of $q$ wraps a map, then the upper
 206 bound is computed over all integer points in
 207 the range of the wrapped map instead.
 208 \\
 209 $l$ := \ai[\tt]{vertices} $s$ &
 210 a list of vertices of the rational polytope defined by the same constraints
 211 as $s$
 212 \\
 213 $s_3$ := $s_1$ \ai{$+$} $s_2$ & union
 214 \\
 215 $m_3$ := $m_1$ \ai{$+$} $m_2$ & union
 216 \\
 217 $q_3$ := $q_1$ \ai{$+$} $q_2$ & sum
 218 \\
 219 $s_3$ := $s_1$ \ai{$-$} $s_2$ & set difference
 220 \\
 221 $m_3$ := $m_1$ \ai{$-$} $m_2$ & set difference
 222 \\
 223 $q_3$ := $q_1$ \ai{$-$} $q_2$ & difference
 224 \\
 225 $s_3$ := $s_1$ \ai{$*$} $s_2$ & intersection
 226 \\
 227 $m_3$ := $m_1$ \ai{$*$} $m_2$ & intersection
 228 \\
 229 $q_3$ := $q_1$ \ai{$*$} $q_2$ & product
 230 \\
 231 $m_2$ := $m_1$ \ai{$*$} $s$ & intersect domain of $m_1$ with $s$
 232 \\
 233 $q_2$ := $q_1$ \ai{$*$} $s$ & intersect domain of $q_1$ with $s$
 234 \\
 235 $f_2$ := $f_1$ \ai{$*$} $s$ & intersect domain of $f_1$ with $s$
 236 \\
 237 $s_2$ := $m$($s_1$) & apply map $m$ to set $s_1$
 238 \\
 239 $m_3$ := $m_1$ \ai[\tt]{.} $m_2$ & join of $m_1$ and $m_2$
 240 \\
 241 $m_3$ := $m_2$($m_1)$ & join of $m_1$ and $m_2$
 242 \\
 243 $q_2$ := $m$ \ai[\tt]{.} $q_1$ & join of $m$ and $q_1$, taking the sum
 244 over all elements in the intersection of the range of $m$ and the domain
 245 of $q_1$
 246 \\
 247 $m$ := $s_1$ \ai[\tt]{->} $s_2$ & universal map with domain $s_1$
 248 and range $s_2$
 249 \\
 250 $q_2$ := $q_1$ \ai{@} $s$ &
 251 evaluate the piecewise quasipolynomial $q_1$ in each element
 252 of the set $s$ and return a piecewise quasipolynomial
 253 mapping each of the individual elements to the resulting
 254 constant
 255 \\
 256 $q$ := $f$ \ai{@} $s$ &
 257 evaluate the piecewise quasipolynomial fold $f$ in each element
 258 of the set $s$ and return a piecewise quasipolynomial
 259 mapping each of the individual elements to the resulting
 260 constant
 261 \\
 262 $s_3$ := $s_1$ \ai[\tt]{\%} $s_2$ &
 263 simplify $s_1$ in the context of $s_2$, i.e., compute
 264 the gist of $s_1$ given $s_2$
 265 \\
 266 $m_3$ := $m_1$ \ai[\tt]{\%} $m_2$ &
 267 simplify $m_1$ in the context of $m_2$, i.e., compute
 268 the gist of $m_1$ given $m_2$
 269 \\
 270 $q_2$ := $q_1$ \ai[\tt]{\%} $s$ &
 271 simplify $q_1$ in the context of the domain $s$, i.e., compute
 272 the gist of $q_1$ given $s$
 273 \\
 274 $f_2$ := $f_1$ \ai[\tt]{\%} $s$ &
 275 simplify $f_1$ in the context of the domain $s$, i.e., compute
 276 the gist of $f_1$ given $s$
 277 \\
 278 $m_2$ := $m_1$\ai[\tt]{\^{}-1} & inverse of $m_1$
 279 \\
 280 $l$ := $m$\ai[\tt]{\^{}+} &
 281 compute an overapproximation of the transitive closure
 282 of $m$ and return a list containing the overapproximation
 283 and a boolean that is true if the overapproximation
 284 is known to be exact
 285 \\
 286 $o$ := $l$[$i$] &
 287 the element at position $i$ in the list $l$
 288 \\
 289 $b$ := $s_1$ \ai[\tt]{=} $s_2$ & is $s_1$ equal to $s_2$?
 290 \\
 291 $b$ := $m_1$ \ai[\tt]{=} $m_2$ & is $m_1$ equal to $m_2$?
 292 \\
 293 $b$ := $s_1$ \ai[\tt]{<=} $s_2$ & is $s_1$ a subset of $s_2$?
 294 \\
 295 $b$ := $m_1$ \ai[\tt]{<=} $m_2$ & is $m_1$ a subset of $m_2$?
 296 \\
 297 $b$ := $s_1$ \ai[\tt]{<} $s_2$ & is $s_1$ a proper subset of $s_2$?
 298 \\
 299 $b$ := $m_1$ \ai[\tt]{<} $m_2$ & is $m_1$ a proper subset of $m_2$?
 300 \\
 301 $b$ := $s_1$ \ai[\tt]{>=} $s_2$ & is $s_1$ a superset of $s_2$?
 302 \\
 303 $b$ := $m_1$ \ai[\tt]{>=} $m_2$ & is $m_1$ a superset of $m_2$?
 304 \\
 305 $b$ := $s_1$ \ai[\tt]{>} $s_2$ & is $s_1$ a proper superset of $s_2$?
 306 \\
 307 $b$ := $m_1$ \ai[\tt]{>} $m_2$ & is $m_1$ a proper superset of $m_2$?
 308 \\
 309 \end{supertabular}