# Generic Selective Independent Families

Vera Fischer  Institute of Mathematics, University of Vienna, Kolingasse
14-16, 1090 Vienna, Austria<EMAIL_ADDRESS>and  Corey Bacal
Switzer  Institute of Mathematics, University of Vienna, Kolingasse 14-16,
1090 Vienna, Austria<EMAIL_ADDRESS>
###### Abstract.

We prove that the generic maximal independent family obtained by iteratively
forcing with the Mathias forcing relative to diagonalization filters is
densely maximal. Moreover, by choosing the filters with some care one can
ensure the family is selective and hence forcing indestructible in a strong
sense. Using this we prove that under $\mathfrak{p}=2^{\aleph_{0}}$ there are
selective independent families and also we show how to add selective
independent families of any desired size.

###### Key words and phrases:

###### 2010 Mathematics Subject Classification:

03E17, 03E35, 03E50

_Acknowledgments:_ The authors would like to thank the Austrian Science Fund
(FWF) for the generous support through grant number Y1012-N35.

##  1\. Introduction

Recall that a family $\mathcal{I}\subseteq[\omega]^{\omega}$ is _independent_
if for all finite, disjoint $\mathcal{A},\mathcal{B}\subseteq\mathcal{I}$ the
set $\bigcap\mathcal{A}\setminus\bigcup\mathcal{B}$ is infinite. Such a family
is a _maximal_ independent family or a m.i.f. if it is maximal with this
property. Denote by $\mathsf{FF}(\mathcal{I})$ the collection of finite
functions $h:\mathcal{I}\to 2$ and for all $h\in\mathsf{FF}(\mathcal{I})$ let
$\mathcal{I}^{h}:=\bigcap_{A\in{\rm dom}(h)}A^{h}$ where $A^{h}=A$ if $h(A)=0$
and $A^{h}=\omega\setminus A$ if $h(A)=1$. Thus $\mathcal{I}$ is independent
if for all $h\in\mathsf{FF}(\mathcal{I})$ $\mathcal{I}^{h}$ is infinite. The
sets of the form $\mathcal{I}^{h}$ are called Boolean combinations.

Maximal independent families are one of several important examples of maximal
combinatorial sets of reals studied in set theory. Other examples include MAD
families, MED families and ultrafilter bases. In each case there is an
associated cardinal characteristic: the least size of a maximal family of that
type. In the case of m.i.f.’s this cardinal is denoted $\mathfrak{i}$. See [3]
for more information on $\mathfrak{i}$ and related cardinals. When trying to
prove that such a cardinal can be consistently less than the continuum one
often needs to construct witnesses which satisfy a stronger maximality
condition which can be preserved by iterations of appropriate forcing notions.

In the case of independent families the associated “strongly maximal” families
are called selective independent families (defined below). These were first
investigated by Shelah in his proof of the consistency of
$\mathfrak{i}<\mathfrak{u}$ in [12], and further studies can be found in e.g.
[4, 5, 7, 13]. See in particular [8] where the authors proved that such
families can be preserved by any countable support iteration of Cohen
preserving, proper forcing notions for which each iterand preserves the dense
maximality of the family111All undefined terms which we will use will be
defined in Section 2 of this article.. However several aspects of the
combinatorics of such families remain unknown including exactly when such
families exist. In particular, it is open whether it is consistent with
$\mathsf{ZFC}$ that there are no selective independent families. In this paper
we begin the investigation into such questions. Our first main theorem is the
following.

######  Theorem 1.1 (see Theorem 4.1 below).

$\mathfrak{p}=2^{\aleph_{0}}$ implies there are selective maximal independent
families.

This result actually follows as a corollary of the main result of the paper.
To each independent family $\mathcal{I}$, maximal or not, there is an
associated diagonalization filter, $\mathcal{F}_{\mathcal{I}}$, the choice of
which is not unique, so that forcing with the associated Mathias forcing
$\mathbb{M}(\mathcal{F}_{\mathcal{I}})$ adds a real $m$ so that
$\mathcal{I}\cup\\{m\\}$ is independent but $\mathcal{I}\cup\\{m,y\\}$ is not
independent for any ground model $y\in[\omega]^{\omega}$. It follows that a
finite support iteration of such Mathias forcing notions of any length of
uncountable cofinality, adding the generic real to the independent family at
each step, generically adds a maximal independent family. Now we can state the
main result of this paper.

######  Theorem 1.2.

In the finite support iteration described above, the diagonalization filters
can be chosen so that the m.i.f. produced at the end is selective. More
explicitly, any finite support iteration of diagonalization filters produces a
densely maximal family whose density filter is a $P$-filter, and the
diagonalization filters can be chosen so that the density filter is a
$Q$-filter as well.

While the the wording above is somewhat technical, the moral is that the
obvious way of producing a m.i.f. generically actually produces one which
satisfies a stronger maximality condition making its maximality forcing
invariant (for appropriate forcing notions). An immediate corollary of Theorem
1.2 is the following.

######  Theorem 1.3 (see Theorem 4.2 below).

Let $\kappa\leq\lambda$ be cardinals of uncountable cofinality. It is
consistent that $\lambda=2^{\aleph_{0}}$ and there is a selective independent
family of size $\kappa$. If moreover $\kappa$ is regular then we can arrange
$\mathfrak{i}=\kappa$ as well.

Prior to the current work, the above was only known for the special case
$\kappa=\aleph_{1}$.

The rest of this paper is organized as follows. In the next section we recall
some preliminaries we will need. Section 3 provides the proof of Theorem 1.2.
Section 4 proves some corollaries and additional results including the proof
of Theorems 1.1 and 1.3. The paper closes with some relevant questions and
lines for further research. Throughout our notation is mostly standard,
conforming to that of [11]. For all undefined notions involving cardinal
characteristics and set theory of the real line we refer the reader to [3] or
the monograph [1].

Acknowledgements. The authors thank Juris Stēprans for many helpful
conversations on the content relating to this paper as well as allowing us to
inlcude Proposition 2.9. They also thank Oswaldo Guzmán for pointing out
Lemmas 6.6 and 6.7 of [9].

##  2\. Preliminaries

Let $\mathcal{I}$ be an independent family. We say that $\mathcal{I}$ is
_densely maximal_ if for every $X\in[\omega]^{\omega}$ and every
$h\in\mathsf{FF}(\mathcal{I})$ there is an $h^{\prime}\supseteq h$ in
$\mathsf{FF}(\mathcal{I})$ so that either $\mathcal{I}^{h^{\prime}}\setminus
X$ or $\mathcal{I}^{h^{\prime}}\cap X$ is finite. In other words,
$\mathcal{I}$ is densely maximal if for any $X\notin\mathcal{I}$ the
collection of $h\in\mathsf{FF}(\mathcal{I})$ witnessing that $X$ cannot be
added to $\mathcal{I}$ while preserving maximality is dense in the partial
order $(\mathsf{FF}(\mathcal{I}),\supseteq)$.

The density filter of an independent family is the collection of all
$X\in[\omega]^{\omega}$ so that for every $h\in\mathsf{FF}(\mathcal{I})$ there
is an $h^{\prime}\supseteq h$ in $\mathsf{FF}(\mathcal{I})$ so that
$\mathcal{I}^{h^{\prime}}\setminus X$ is finite. Denote this filter by ${\rm
fil}(\mathcal{I})$. Densely maximal independent families are characterized by
the partition property, explained below.

######  Fact 2.1 (The Partition Property).

Let $\mathcal{I}$ be an independent family. The following are equivalent:

  1. (1)

$\mathcal{I}$ is densely maximal.

  2. (2)

$P(\omega)={\rm
fil}(\mathcal{I})\cup\langle\omega\setminus\mathcal{I}^{h}\;|\;h\in\mathsf{FF}(\mathcal{I})\rangle_{dn}$
where $\langle\mathcal{X}\rangle_{dn}$ denotes the downward closure of
$\mathcal{X}\subseteq[\omega]^{\omega}$ under $\supseteq^{*}$.

Some more facts about the density filter are listed below. The following are
easily verified, see [2, Lemma 5.5].

######  Lemma 2.2.

  1. (1)

If $\mathcal{I}^{\prime}$ is an independent family and
$\mathcal{I}\subseteq\mathcal{I}^{\prime}$ then
$\mathrm{fil}(\mathcal{I})\subseteq\mathrm{fil}(\mathcal{I}^{\prime})$;

  2. (2)

If $\kappa$ is a regular uncountable cardinal and
$\langle\mathcal{I}_{\alpha}\mid\alpha<\kappa\rangle$ is a continuous
increasing chain of independent families then
$\mathrm{fil}(\bigcup_{\alpha<\kappa}\mathcal{I}_{\alpha})=\bigcup_{\alpha<\kappa}\mathrm{fil}(\mathcal{I}_{\alpha})$;

  3. (3)

If $\mathcal{I}$ is an independent family then
$\mathrm{fil}(\mathcal{I})=\bigcup\\{\,\mathrm{fil}(\mathcal{J})\mid\mathcal{J}\in[\mathcal{I}]^{\leq\omega}\\}$.

We will need another type of filter associated to an independent family as
well, which we define now.

######  Definition 2.3.

Let $\mathcal{I}$ be an independent family. A diagonalization filter for
$\mathcal{I}$ is any filter $\mathcal{F}$ on $\omega$ which is maximal with
respect to the property that all $X\in\mathcal{F}$ have infinite intersection
with every $\mathcal{I}^{h}$.

Note that in general diagonalization filters will not be unique. For instance,
if $\mathcal{I}$ is not maximal then there is some real $y\notin\mathcal{I}$
so that $\mathcal{I}\cup\\{y\\}$ is independent and, by the definition of
independence it follows that both $y$ and $\omega\setminus y$ have infinite
intersection with every Boolean combination of $\mathcal{I}$. As such there
are diagonalization filters containing both $y$ and $\omega\setminus y$ (which
obviously therefore cannot be the same). However, it is an easy but key
observation that any $y$ which has infinite intersection with every Boolean
combination of a given independent family $\mathcal{I}$ must have infinite
intersection with $\mathcal{I}^{h}\cap Z$ for every element $Z\in{\rm
fil}(\mathcal{I})$ and every $h\in\mathsf{FF}(\mathcal{I})$. Hence if
$\mathcal{F}$ is a diagonalization filter then ${\rm
fil}(\mathcal{I})\subseteq\mathcal{F}$. In the case of dense maximality we
have the converse.

######  Lemma 2.4 (Essentially Fischer-Montoya, see [7]).

Let $\mathcal{I}$ be independent. The following are equivalent.

  1. (1)

$\mathcal{I}$ is densely maximal.

  2. (2)

The diagonalization filter is unique and equals the density filter.

###### Proof.

Item (1) implies item (2) is Corollary 36 of [7]. Let us show that (2) implies
(1). Thus suppose that ${\rm fil}(\mathcal{I})$ is a diagonalization filter.
Note that it must be the unique one since any other diagonalization filter
extends it but, being a diagonalization filter it is maximal. We will show
that $\mathcal{I}$ is densely maximal. By the partition property, Fact 2.1, it
suffices to show that

$P(\omega)={\rm
fil}(\mathcal{I})\cup\langle\omega\setminus\mathcal{I}^{h}\;|\;h\in\mathsf{FF}(\mathcal{I})\rangle_{dn}$

Suppose that $X\notin{\rm fil}(\mathcal{I})$. Since ${\rm fil}(\mathcal{I})$
is the unique diagonalization filter for $\mathcal{I}$, it follows that $X$ is
not in any diagonalization filter. This means in particular that it does not
have infinite intersection with every Boolean combination of $\mathcal{I}$
(otherwise we could apply Zorn’s Lemma to the filter generated by $X$ to get a
diagonalization filter which contains $X$). Therefore there is an
$h\in\mathsf{FF}(\mathcal{I})$ so that $X$ is almost disjoint from
$\mathcal{I}^{h}$. But then $X$ is almost included in
$\omega\setminus\mathcal{I}^{h}$ as needed. ∎

We will need to force with the Mathias forcing of diagonalization filters so
we recall this now.

######  Definition 2.5.

Let $\mathcal{I}$ be an independent family and let $\mathcal{F}$ be a
diagonalization filter for $\mathcal{I}$. Denote by $\mathbb{M}(\mathcal{F})$
the Mathias forcing relativized to $\mathcal{F}$. A condition for this forcing
notion is a pair $(s,A)$ so that

  1. (1)

$s\in 2^{<\omega}$ is the characteristic function of a finite set of natural
numbers.

  2. (2)

$A\in\mathcal{F}$

  3. (3)

${\rm min}(A)\geq{\rm dom}(s)$.

If $(s,A)$ and $(t,B)$ are conditions in $\mathbb{M}(\mathcal{F})$ then we let
$(s,A)\leq(t,B)$ just in case:

  1. (1)

$s\supseteq t$

  2. (2)

$A\subseteq B$

  3. (3)

If $n\in{\rm dom}(s)\setminus{\rm dom}(t)$ and $s(n)=1$ then $n\in B$.

If $\mathcal{F}$ is clear from context, or unimportant we often write
$\mathbb{M}(\mathcal{I})$ to emphasize the independent family. If
$G\subseteq\mathbb{M}(\mathcal{I})$ is generic then the real
$m_{G}:=\\{n\;|\;\exists(s,A)\in G\,s(n)=1\\}$ is denoted the Mathias real for
$\mathcal{I}$ (or $\mathcal{F}$ depending on the context). It is readily
checked that $m$ is an infinite set of natural numbers which diagonalizes
$\mathcal{F}$ i.e. $m\subseteq^{*}A$ for each $A\in\mathcal{F}$ where
$X\subseteq^{*}Y$ means that $X\setminus Y$ is finite. Also $V[G]=V[m_{G}]$.
Moreover we have that $\mathcal{I}\cup\\{m_{G}\\}$ is independent but for any
ground model $y\in[\omega]^{\omega}\cap V$ we have
$\mathcal{I}\cup\\{m_{G},y\\}$ is not independent, see [7]. It follows that an
iteration with finite support of Mathias forcing relativized to the increasing
independent families obtained by adjoining the generic Mathias reals (of
length an uncountably cofinal ordinal) will result in a model with a m.i.f. of
length the iteration. Let us call such a m.i.f. a _generic m.i.f._. That such
a filter exists, and produces a maximal independent family was first observed
by Brendle, see [10]. Indeed by performing such an iteration of length
$\aleph_{1}<2^{\aleph_{0}}$ Brendle obtained the first model of
$\mathfrak{i}<2^{\aleph_{0}}$.

As stated in the introduction, the main goal of this paper is to improve this
result by showing that such an iteration produces a selective maximal
independent family. Selectivity is a further strengthening of dense
maximality. We recall some more definitions.

######  Definition 2.6.

Let $\mathcal{F}$ be a family of subsets of $\omega$. We say that:

  1. (1)

$\mathcal{F}$ is a $P$-set if every countable family
$\\{A_{n}\;|\;n<\omega\\}\subseteq\mathcal{F}$ has a psuedointersection
$B\in\mathcal{F}$, i.e. $B\subseteq^{*}A_{n}$ for all $n<\omega$,

  2. (2)

$\mathcal{F}$ is a $Q$-set if given every partition of $\omega$ into finite
sets $\\{I_{n}\;|\;n<\omega\\}$ there is a semiselector $A\in\mathcal{F}$ i.e.
$|A\cap I_{n}|\leq 1$ for all $n<\omega$,

  3. (3)

$\mathcal{F}$ is Ramsey if it is both a $P$-set and a $Q$-set.

If $\mathcal{F}$ is a filter and a $P$-set (respectively a $Q$-set, Ramsey
set) we call $\mathcal{F}$ a $P$-filter (respectively a $Q$-filter, Ramsey
filter).

We can now give the definition of a selective maximal independent family.

######  Definition 2.7.

An independent family $\mathcal{I}$ is _selective_ if it is densely maximal
and $\mathrm{fil}(\mathcal{I})$ is Ramsey.

Selective independent families were first introduced by Shelah in [12], where
it is shown in the course of his proof of the consistency of
$\mathfrak{i}<\mathfrak{u}$ that under $\mathsf{CH}$ there is a selective
independent family. Since then the following results have been shown
concerning the forcing indestructibility of selective independent families.

######  Fact 2.8.

Let $\mathcal{I}$ be a selective independent family. Then $\mathcal{I}$ is
remains selective (and hence maximal) after forcing with a countable support
product of Sacks forcing (Shelah, see [4, Theorem 4.6] or [7, Corollary 37]).
Moreover, $\mathcal{I}$ remains selective independent after forcing with the
countable support iteration of any of the following:

  1. (1)

Sacks forcing (Shelah, see [4, Theorem 4.6] or [7, Corollary 37]);

  2. (2)

forcing notions of the form $\mathbb{Q}_{\mathcal{I}}$ from Shelah’s [12];

  3. (3)

Miller partition forcing (see [6]);

  4. (4)

$h$-Perfect Tree Forcing Notions for different functions $h:\omega\to\omega$
with $1<h(n)<\omega$ for all $N<\omega$ (see [13]);

  5. (5)

Coding with perfect trees (see [2]);

  6. (6)

Miller lite forcing, (see [8, Theorem 4.1]);

  7. (7)

any mix of the above (a consequence of [8, Theorem 3.8]).

Obviously all the forcing constructions described above produce a model where
the selective independent family is of size $\aleph_{1}$. As stated in the
introduction, the purpose of this paper in part is to show that consistently
there are selective families of other sizes.

We finish these preliminaries by remarking that there are in fact maximal,
non-densely maximal independent families. This is due to Juris Steprāns and is
included with his kind permission.

######  Proposition 2.9 (Steprāns).

For any cardinal $\kappa$ for which there is a maximal independent family
there is a maximal, non densely maximal independent family of size $\kappa$.
In particular there is always one of size $\mathfrak{i}$.

###### Proof.

Fix a cardinal $\kappa$ for which there is a maximal independent family. Let
$Z\subseteq\omega$ be an infinite, co-infinite set. By translation there is a
maximal independent family $\mathcal{I}=\\{A_{\alpha}\;|\;\alpha<\kappa\\}$ on
$Z$ (so all the $A_{\alpha}$’s are subsets of $Z$). Let
$\mathcal{J}=\\{B_{\alpha}\;|\;\alpha<\kappa\\}$ be an independent, but not
maximal independent family on $\omega\setminus Z$. Note that there is always
an independent family of size continuum ([3, Proposition 8.9]) so in
particular there is one of size $\kappa$. Finally let
$\mathcal{K}=\\{A_{\alpha}\cup B_{\alpha}\;|\;\alpha<\kappa\\}\cup\\{Z\\}$. It
is routine to check that this is independent. Moreover if $X\notin\mathcal{K}$
then either $X\cap Z$ is almost disjoint, in which case
$\mathcal{K}\cup\\{X\\}$ is not independent or $X\cap Z=A_{\alpha}$ for some
$\alpha$ in which case $\mathcal{K}\cup\\{X\\}$ is not independent or else
there is a Boolean combination $h$ on $\mathcal{I}$ witnessing that $X\cap Z$
cannot be added to $\mathcal{I}$ and hence $\mathcal{K}\cup\\{X\\}$ is not
independent. Therefore $\mathcal{K}$ is maximal.

Finally let $Y\subseteq\omega\setminus Z$ be a set so that
$Y\notin\mathcal{J}$ but $\mathcal{J}\cup\\{Y\\}$ is independent. Observe that
as a result no Boolean combination $h\in\mathsf{FF}(\mathcal{K})$ extending
$\langle Z,1\rangle$ will be such that $\mathcal{K}^{h}\setminus Y$ or
$\mathcal{K}^{h}\cap Y$ is finite. Thus $\mathcal{K}$ is not densely maximal.
∎

This counterexample should be contrasted with the combined content of Lemmas
6.6 and 6.7 of [9] where it is shown that every maximal independent family is
densely maximal below some Boolean combination i.e. for each m.i.f.
$\mathcal{I}$ there is an $h\in\mathsf{FF}(\mathcal{I})$ so that the set
$\\{A\cap\mathcal{I}^{h}\;|\;A\in\mathcal{I}\setminus{\rm dom}(h)\\}$ is
densely maximal as a family on $\mathcal{I}^{h}$. Note that as a corollary of
this it follows that in $\mathsf{ZFC}$ there are densely maximal independent
families and indeed they exist in every cardinality for which there is a
maximal independent family.

##  3\. The Selectivity of the Generic Maximal Independent Family

Next we prove Theorem 1.2. Let us fix some notation for the rest of this
section. Let $\kappa$ be an ordinal of uncountable cofinality. Let
$\mathcal{I}_{0}$ be some fixed independent family and $\mathcal{F}_{0}$ be a
diagonalization filter. Now inductively let
$\langle\mathbb{P}_{\alpha},\dot{\mathbb{Q}}_{\alpha}\;|\;\alpha<\kappa\rangle$
be a finite support iteration and $\dot{\mathcal{I}}_{\alpha}$ and
$\dot{\mathcal{F}}_{\alpha}$ be $\mathbb{P}_{\alpha}$-names defined as
follows.

  1. (1)

$\mathbb{P}_{0}$ is the trivial forcing, $\dot{\mathbb{Q}}_{0}$ is the trivial
name for $\mathbb{M}(\mathcal{F}_{0})$.

  2. (2)

$\mathbb{P}_{\alpha}$ forces that $\dot{\mathcal{I}}_{\alpha}$ is an
independent family with a diagonalization filter $\dot{\mathcal{F}}_{\alpha}$.

  3. (3)

$\mathbb{P}_{\alpha+1}=\mathbb{P}_{\alpha}*\mathbb{M}(\dot{\mathcal{F}}_{\alpha})$.

  4. (4)

$\mathbb{P}_{\alpha+1}$ forces that
$\dot{\mathcal{I}}_{\alpha+1}=\dot{\mathcal{I}}_{\alpha}\cup\\{\dot{m}_{\alpha}\\}$
where $\dot{m}_{\alpha}$ is the name for the
$\mathbb{M}(\dot{\mathcal{F}}_{\alpha})$-generic real.

  5. (5)

If $\beta$ is a limit ordinal then $\mathbb{P}_{\beta}$ forces that
$\dot{\mathcal{I}}_{\beta}=\bigcup_{\gamma<\beta}\dot{\mathcal{I}_{\gamma}}$.

Let $\dot{\mathcal{I}}_{\kappa}$ be the $\mathbb{P}_{\kappa}$-name for the
union of the $\dot{\mathcal{I}}_{\alpha}$’s. Let
$G_{\kappa}\subseteq\mathbb{P}_{\kappa}$ be generic over $V$ and, in
$V[G_{\kappa}]$ let $\mathcal{I}_{\alpha}$, $\mathcal{F}_{\alpha}$,
$m_{\alpha}$ etc refer to the evaluation of all of the corresponding names
with the dots. Finally let for each $\alpha<\kappa$ the generic
$G_{\alpha}=G_{\kappa}\cap\mathbb{P}_{\alpha}$ as usual. For the rest of this
section we fix all such objects. We refer to $\mathcal{I}_{\kappa}$ (in
$V[G_{\kappa}]$) as the generic m.i.f.. Let us now restate Theorem 1.2 more
precisely.

######  Theorem 3.1.

$\mathbb{P}_{\kappa}$ forces that the generic m.i.f. is densely maximal and
its density filter is a $P$-point. Moreover, if $\kappa$ is a cardinal and
$\kappa^{{<}\kappa}=\kappa$ in the ground model then the
$\dot{\mathcal{F}}_{\alpha}$’s can be chosen so that the generic mif is
selective.

It is unclear whether the above can be improved so as to eliminate the need to
choose the filters so as to ensure that ${\rm fil}(\mathcal{I}_{\kappa})$ is a
$Q$-filter. We will discuss this more later. To prove Theorem 3.1 we need to
show three things: that $\mathcal{I}_{\kappa}$ is densely maximal, that its
density filter is a $P$-point and that its density filter is a $Q$-point given
good enough bookkeeping. We will prove each of these separately, beginning
with dense maximality.

###  3.1. Dense Maximality

Again, we fix the notation described in the first paragraph of this section.

######  Lemma 3.2.

$\mathbb{P}_{\kappa}$ forces that the generic m.i.f. is densely maximal.

###### Proof.

By Lemma 2.4 it suffices to show that if $X\in V[G_{\kappa}]$ has infinite
intersection with every Boolean combination then it is in the density filter
of $\mathcal{I}_{\kappa}$ as this implies that the density filter is the
unique diagonalization filter and hence $\mathcal{I}_{\kappa}$ is densely
maximal. So suppose that $X\in V[G_{\kappa}]$ has infinite intersection with
every Boolean combination and let $h\in\mathsf{FF}(\mathcal{I})$. We need to
find an $h^{\prime}\supseteq h$ so that
$\mathcal{I}^{h^{\prime}}_{\kappa}\setminus X$ is finite. Let $\alpha<\kappa$
be such that $X,h\in V[G_{\alpha}]$.

Case 1: There is a $\beta\geq\alpha$ so that $X$ is forced to be in
$\dot{\mathcal{F}}_{\beta}$, the diagonalization filter used at stage $\beta$.
Now the generic real $m_{\beta}\in\mathcal{I}_{\kappa}$ is a
pseudointersection of this filter and in particular $m_{\beta}\subseteq^{*}X$.
But then we get that if $h^{\prime}=h\cup\langle m_{\beta},0\rangle$ then
$\mathcal{I}_{\beta}^{h^{\prime}}\subseteq^{*}m_{\beta}\subseteq^{*}X$ so
$h^{\prime}$ is as needed. Note that this was valid since $h\in V[G_{\alpha}]$
and so in particular $\beta\notin{\rm dom}(h)$.

Case 2: $X$ is not forced to be in any diagonalization filter at any stage
$\beta\geq\alpha$. Work $V[G_{\alpha}]$ and let $\mathcal{F}_{\alpha}$ be the
choice of diagonalization filter for $\mathcal{I}_{\alpha}$. Note that the
assumption implies in particular that $X$ is not in $\mathcal{F}_{\alpha}$.
Since $\mathcal{F}_{\alpha}$ is maximal with the property that every element
has infinite intersection with every Boolean combination of
$\mathcal{I}_{\alpha}$, there must be a $Y\in\mathcal{F}_{\alpha}$ and a
Boolean combination $g\in\mathsf{FF}(\mathcal{I}_{\alpha})$ so that $X\cap
Y\cap\mathcal{I}^{g}_{\alpha}$ is finite. But now note that $\dot{m}_{\alpha}$
is forced to be an almost subset of $Y$ thus we get that
$V[G_{\alpha+1}]\models$“$X\cap\dot{m}_{\alpha}^{G_{\alpha+1}}\cap\mathcal{I}_{\alpha}^{g}$
is finite”. But $\dot{m}_{\alpha}^{G_{\alpha+1}}\cap\mathcal{I}_{\alpha}^{g}$
is a Boolean combination of $\mathcal{I}_{\kappa}$, contradicting the defining
property of $X$. ∎

Having established dense maximality we go on to consider the property of the
density filter being a $P$-filter.

###  3.2. ${\rm fil}(\mathcal{I}_{\kappa})$ is a $P$-Filter

We continue with our notation outlined above.

######  Lemma 3.3.

The density filter of the generic m.i.f. added by $\mathbb{P}_{\kappa}$ is a
P-filter.

###### Proof.

Let $\\{\dot{A}_{n}\;|\;n<\omega\\}$ name an $\omega$-sequence of elements of
${\rm fil}(\mathcal{I}_{\kappa})$. By the fact that $\kappa$ has uncountable
cofinality there is a $\gamma<\kappa$ so that $\dot{A}_{n}\in V[G_{\gamma}]$
and, moreover, by Lemma 2.2 we can find such a $\gamma$ so that
$\dot{A}_{n}\in{\rm fil}(\mathcal{I}_{\gamma})$ for all $n<\omega$. Work in
such a $V[G_{\gamma}]$ and let $A_{n}$ be the evaluation of $\dot{A}_{n}$ in
this model.

Since $A_{n}\in{\rm fil}(\mathcal{I}_{\gamma})$ for each $n<\omega$ we must
have that for each $n<\omega$ the set $A_{n}$ is in every diagonalization
filter we choose from stage $\gamma$ on, again by Lemma 2.2. Consequently for
all $\xi>\gamma$ we have that $m_{\xi}\subseteq^{*}A_{n}$ for all $n<\omega$.
In particular (working now in $V[G_{\gamma+\omega}]$) we have
$m_{\gamma+n}\subseteq^{*}A_{m}$ for all $n,m<\omega$. For each $k<\omega$ let
$l_{k}(n)$ be such that $m_{\gamma+n}\setminus l_{k}(n)\subseteq A_{k}$. Let
$f:\omega\to\omega$ dominate all of the $l_{k}$’s. Finally set

$B=\bigcup_{n<\omega}(m_{\gamma+n}\setminus f(n))$

We claim that $B\subseteq^{*}A_{n}$ for each $n<\omega$ and $B$ is forced to
be in the density filter for $\mathcal{I}_{\kappa}$, which completes the
proof. For the first part fix $k<\omega$ and let $m$ be such that for all
$n>m$ we have $f(n)>l_{k}(n)$. Now we have

$B=\bigcup_{n\leq m}(m_{\gamma+n}\setminus
f(n))\cup\bigcup_{n>m}(m_{\gamma+n}\setminus f(n))$

Observe that $\bigcup_{n\leq m}m_{\gamma+n}\subseteq^{*}A_{k}$ since it is a
finite union of almost subsets of $A_{k}$ and
$\bigcup_{n>m}m_{\gamma+n}\setminus f(n)\subseteq A_{k}$ (true inclusion - not
mod finite) since $f(n)>l_{k}(n)$ and by definition of $l_{k}$ we have that
$m_{\gamma+n}\setminus l_{k}(n)\subseteq A_{k}$. Putting these two
observations together proves the first part of our claim, namely that
$B\subseteq^{*}A_{k}$.

For the second part let $h\in\mathsf{FF}(\mathcal{I}_{\kappa})$. Since $h$ is
finite there is an $n<\omega$ so that $m_{\gamma+n}\notin{\rm dom}(h)$. Fix
such an $n<\omega$ and let $h^{\prime}=h\cup\langle m_{\gamma+n},0\rangle$.
Now $\mathcal{I}_{\kappa}^{h^{\prime}}=\mathcal{I}_{\kappa}^{h}\cap
m_{\gamma+n}\subseteq m_{\gamma+n}\subseteq^{*}B$ so $B$ is in the density
filter as needed. ∎

######  Remark 1.

By one of the results of [7] we know that forcing with
$\mathbb{M}(\mathcal{I})$ for $\mathcal{I}$ selective adds a dominating real.
It follows that, once we have proved Lemma 3.9 below and hence Theorem 3.1 in
Mathias iterations as we have been describing we get that
$\mathfrak{b}=\mathfrak{d}={\rm cof}(\kappa)$. The existence of such
dominating reals allows us to sup up the argument for 3.3 (since the only
place we used countability was to get a dominating function) so we will have
shown that in fact, assuming we choose the diagonalization filters correctly,
${\rm fil}(\mathcal{I}_{\kappa})$ is a $P_{{\rm cf}(\kappa)}$-filter i.e. any
${<}{\rm cof}(\kappa)$-many elements have a pseudointersection in the filter.

The proof of Lemma 3.3 actually shows that a basis for the density filter of
$\mathcal{I}_{\kappa}$ in $V[G_{\kappa}]$ is given by simply
$\bigcup_{n<\omega}(m_{\xi_{n}}\setminus f(n))$ for functions
$f:\omega\to\omega$ and elements $m_{\xi_{n}}\in\mathcal{I}_{\kappa}$ (with
infinitely many distinct). Extracting from this we get the following.

######  Lemma 3.4.

Let $A\in[\omega]^{\omega}\cap V[\mathcal{I}_{\kappa}]$. The following are
equivalent.

  1. (1)

There is a $\gamma<\kappa$ so that for all $\alpha\in(\gamma,\kappa)$ we have
$m_{\gamma}\subseteq^{*}A$.

  2. (2)

There are strictly increasing ordinals $\xi_{n}<\kappa$ for $n<\omega$ so that
for all $n<\omega$ we have $m_{\xi_{n}}\subseteq^{*}A$.

  3. (3)

$A\in{\rm fil}(\mathcal{I}_{\kappa})$.

###### Proof.

Fix $A$ as above and work in $V[\mathcal{I}_{\kappa}]$. Since (1) is an
obvious strengthening of (2) we have (1) implies (2) and (2) implies (3) is
exactly as in the proof of Lemma 3.3. Thus it suffices to show that (3)
implies (1). Observe that by the ccc there is a $\gamma<\kappa$ so that
$A\in[\omega]^{\omega}\cap V[\mathcal{I}_{\gamma}]$. Moreover since $A\in{\rm
fil}(\mathcal{I}_{\kappa})$ we can assume without loss of generality that
$A\in{\rm fil}(\mathcal{I}_{\gamma})$ (the $\gamma$ where $A$ first appears
might be before the one in which $A$ ends up in the density filter but we just
take the latter in this case). Now we get that $A\in\mathcal{F}_{\alpha}$ for
each $\alpha>\gamma$ hence $m_{\alpha}\subseteq^{*}A$ for every such $\alpha$
since $m_{\alpha}$ is a pseudointersection of $\mathcal{F}_{\alpha}$. ∎

###  3.3. ${\rm fil}(\mathcal{I}_{\kappa})$ is a $Q$-Filter

Finally we will show that ${\rm fil}(\mathcal{I}_{\kappa})$ is a $Q$-filter
when the diagonalization filters $\mathcal{F}_{\alpha}$ are chosen carefully
enough. As noted in the hypotheses of Theorem 3.1, we will eventually need
that $\kappa$ is a cardinal and $\kappa^{{<}\kappa}=\kappa$ but we will state
this explicitly when we need it. For now we proceed with the notation given
above. We will use the following characterization of $Q$-filters.

######  Fact 3.5 (See Lemma 3.7 of [6]).

Let $\mathcal{F}$ be a filter on $\omega$. The following are equivalent.

  1. (1)

$\mathcal{F}$ is a $Q$-filter.

  2. (2)

For every strictly increasing $f:\omega\to\omega$ there is a $A\in\mathcal{F}$
so that, letting $A=\\{k(n)\\}_{n<\omega}$ be an increasing enumeration of
$A$, $f(k(n))<k(n+1)$.

Moving forward, in the pursuit of brevity, if $f$ and $A$ have the property
described in (2) above we will say that $A$ $Q$-dominates $f$. We need one
more fact.

######  Lemma 3.6.

In $V[G_{\alpha}]$ there is a diagonalization filter
$\mathcal{F}^{\prime}\supseteq\mathcal{F}_{\alpha}$ for
$\mathcal{I}_{\alpha+1}$. Consequently we can always choose the
diagonalization filters for the iteration to be a $\subseteq$-strictly
increasing sequence.

###### Proof.

Work in $V[G_{\alpha}]$ and fix $X\in\mathcal{F}_{\alpha}$. It suffices to
show that, under the hypotheses we have that
$\Vdash_{\mathbb{M}(\mathcal{F}_{\alpha})}$ “$\check{X}$ has infinite
intersection with every $h\in\mathsf{FF}(\dot{\mathcal{I}}_{\alpha+1})$” as in
this case every $X\in\mathcal{F}_{\alpha}$ has infinite intersection with
every Boolean combination of $\mathcal{I}_{\alpha+1}$ (note that we are
assuming the maximal condition forces this) so we can extend
$\mathcal{F}_{\alpha}$ to some diagonalization filter for
$\mathcal{I}_{\alpha+1}$. Fix an arbitrary condition $(s,A)$ and an arbitrary
$h\in\mathsf{FF}(\mathcal{I}_{\alpha+1})$. If $m_{\alpha}\notin{\rm dom}(h)$
then by hypothesis we have $X\cap\mathcal{I}_{\alpha+1}^{h}$ is infinite so
assume $m_{\alpha}\in{\rm dom}(h)$ and let $h^{\prime}=h\setminus\\{\langle
m_{\alpha},h(m_{\alpha})\rangle\\}$. We need to show that for each $n<\omega$
and each $i<2$ we have that there is a $k>n$ with
$k\in\mathcal{I}_{\alpha}^{h^{\prime}}\cap X\cap m_{\alpha}^{i}$. Fix
$n<\omega$, and $i<2$. Without loss we can assume that ${\rm dom}(s)\supsetneq
n$ and $A\subseteq X$ as the set of conditions whose stem has domain
containing $n$ is dense and, since $X\in\mathcal{F}_{\alpha}$ we can always
replace $A$ by $A\cap X$ if we so choose. Note that again we have that
$A\cap\mathcal{I}^{h^{\prime}}_{\alpha}$ has infinite intersection, and
therefore there is in particular a $k\in
A\cap\mathcal{I}_{\alpha}^{h^{\prime}}$ and $k>n$ since $(s,A)$ is a condition
and therefore ${\rm min}(A)>n$. Let $s^{\prime}\supseteq s$ so that
$s^{\prime}(k)=i$. Then $(s^{\prime},A\setminus{\rm dom}(s^{\prime}))$ is a
condition extending $(s,A)$ which forces that
$k\in\mathcal{I}_{\alpha}^{h^{\prime}}\cap A\cap
m_{\alpha}^{i}\subseteq\mathcal{I}_{\alpha}^{h^{\prime}}\cap X\cap
m_{\alpha}^{i}$, so we are done. ∎

######  Lemma 3.7.

If $\gamma<\kappa$ and $f\in\omega^{\omega}\cap V[G_{\gamma}]$ is strictly
increasing, then there is a choice of diagonalization filters
$\dot{\mathcal{F}}_{\gamma+i}$ for $i\in\omega+\omega$ so that (using this
choice of filters for the Mathias forcing notions) we have that in
$V[G_{\gamma+\omega+\omega}]$ there is an $A\in{\rm
fil}(\mathcal{I}_{\gamma+\omega+\omega})$ which $Q$-dominates $f$.

###### Proof.

Fix $\gamma$ and $f$ as in the hypothesis of the lemma. Observe by the
finiteness of the support, a density argument ensures that for every
$k<\omega$ there is an $n<\omega$ so that ${\rm min}(m_{\gamma+n})>k$. Using
this, inductively define $A=\\{k(n)\\}_{n<\omega}$ so that $k(n+1)={\rm
min}(m_{\gamma+n_{n+1}})$ where $n_{n+1}$ is the least number $l$ so that
${\rm min}(m_{\gamma+l})>f(k(n))$. Clearly $A$, which is in
$V[G_{\gamma+\omega}]$, $Q$-dominates $f$ so it remains to show that the next
$\omega$-many diagonalization filters can be chosen so that $A$ is forced to
be in ${\rm fil}(\mathcal{I}_{\gamma+\omega+\omega})$.

Work in $V[G_{\gamma+\omega}]$.

######  Claim 3.8.

$A$ has infinite intersection with every Boolean combination in
$\mathcal{I}_{\gamma+\omega}$.

###### Proof of Claim 3.8.

This is a density argument. Suppose that $k<\omega$, and
$h\in\mathsf{FF}(\mathcal{I}_{\gamma+\omega})$. Let $n$ be large enough that
${\rm dom}(h)\subseteq\mathcal{I}_{\gamma+n}$ and let $m$ be such that the
first $m$-entries of $A$ are the minimums of elements from among
$m_{\gamma+l}$ for $l<n$ and denote these elements $\\{k(j)\\}_{j<m}$. Without
loss of generality we can assume that $m>k$. Work in $V[G_{\gamma+n}]$. We now
let $a>f(k(m-1))$ be in $\mathcal{I}_{\gamma+n}^{h}$. Since this set is
infinite such an $a<\omega$ exists. Finally let $s\in 2^{<\omega}$ be the
sequence of length $a+1$ so that for all $b<a$ we have $s(b)=0$ and $s(a)=1$.
Clearly, regardless of the choice of $\mathcal{F}_{\gamma+n}$ we have that
$(s,\omega)\in\mathbb{M}(\mathcal{F}_{\gamma+n})$ and forces that the $m^{\rm
th}$-element of $A$ is in $\mathcal{I}_{\gamma+n}^{h}\setminus k$. Since $k$,
$h$ and $n$ were arbitrary, the proof is complete. ∎

Given Claim 3.8, observe that we can put $A$ into $\mathcal{F}_{\xi}$ for
$\xi\in[\gamma+\omega,\gamma+\omega+\omega)$. The first step i.e. putting $A$
in $\mathcal{F}_{\gamma+\omega}$ follows from the claim since $A$ has infinite
intersection with every Boolean combination. The following steps follow from
Lemma 3.6. Therefore $A\in{\rm fil}(\mathcal{I}_{\gamma+\omega+\omega})$ and
hence $A\in{\rm fil}(\mathcal{I}_{\kappa})$ by Lemma 3.4, thus completing the
proof. ∎

Now we can prove the following lemma which implies Theorem 3.1.

######  Lemma 3.9.

If $\kappa^{{<}\kappa}=\kappa$ is a cardinal then there is a choice of
diagonalization filters so that $\mathbb{P}_{\kappa}$ forces that ${\rm
fil}(\dot{\mathcal{I}}_{\kappa})$ is a $Q$-filter.

###### Proof.

We want to show that we can choose the diagonalization filters so that every
strictly increasing $f\in\omega^{\omega}\cap V[G_{\kappa}]$ is $Q$-dominated
by some $A\in{\rm fil}(\mathcal{I}_{\kappa})$. By Lemma 3.7 we can ensure for
any fixed $f\in\omega^{\omega}\cap V[G_{\kappa}]$ this can be done but then
the cardinal arithmetic hypothesis, alongside the ccc of the forcing ensures
that there is enough space to handle every $f$ with some bookkeeping as there
are only $\kappa$-many nice names for reals. ∎

As stated before the combination of Lemmas 3.2, 3.3 and 3.9 prove Theorem 3.1
(and hence Theorem 1.2).

##  4\. Arbitrarily large selective independent families

Since Mathias forcing notions relativized to a filter are all
$\sigma$-centered, by [3, Theorem 7.12], we get the following, which
strengthens a theorem of Shelah from [12], who proved the same under the
stronger hypothesis of $\mathsf{CH}$ in place of
$\mathfrak{p}=2^{\aleph_{0}}$.

######  Theorem 4.1.

Assume $\mathfrak{p}=2^{\aleph_{0}}$. Every independent family
$\mathcal{I}_{0}$ of size ${<}2^{\aleph_{0}}$ can be extended to a selective
independent family.

###### Proof.

Fix $\mathcal{I}_{0}$, an independent family of some size
$\lambda<2^{\aleph_{0}}$. Enumerate the elements of $\mathcal{I}_{0}$ as
$\\{A_{\xi}\;|\;\xi<\lambda\\}$. For $\mathcal{I}_{0}$, and further
independent families we will build in this proof, we associate a finite
partial function $h:2^{\aleph_{0}}\to 2$ to a Boolean combination by mapping
e.g. $A_{\alpha}$ to $A_{\alpha}^{h(\alpha)}$. We will not comment on this
again and assume implicitly that some enumeration of our independent families
has been chosen to make sense of this. If there is a $\zeta\in{\rm dom}(h)$
which is greater than $\lambda$ then we consider the Boolean combination
undefined. Enumerate all pairs consisting of an element of Ramsey space and a
finite partial function $h:2^{\aleph_{0}}\to 2$ as
$\\{(X_{\alpha},h_{\alpha})\;|\;\alpha<2^{\aleph_{0}}\\}$, enumerate countable
subsets of Ramsey space
$\\{(A^{\alpha}_{n})\;|\;n<\omega,\,\alpha<2^{\aleph_{0}}\\}$ so that every
sequence appears unboundedly often and fix a scale
$\\{f_{\alpha}\;|\;\alpha<2^{\aleph_{0}}\\}\subseteq\omega^{\omega}$ (so
$\alpha<\beta$ implies $f_{\alpha}\leq^{*}f_{\beta}$ and this family is
dominating). Note that the assumption on $\mathfrak{p}$ guarantees such a
scale exists. We will inductively define a continuous, $\subseteq$-increasing
sequence of independent families
$\\{\mathcal{I}_{\alpha}\\}_{\alpha<2^{\aleph_{0}}}$ so that the union
$\bigcup_{\alpha<2^{\aleph_{0}}}\mathcal{I}_{\alpha}$ is selective. Indeed it
suffices to show that given $\mathcal{I}_{\alpha}$ independent we can find
$\mathcal{I}_{\alpha+1}\supseteq\mathcal{I}_{\alpha}$ so that the following
hold:

  1. (1)

If $X_{\alpha}$ has infinite intersection with every Boolean combination of
$\mathcal{I}_{\alpha}$ and $h_{\alpha}$ is defined on $\mathcal{I}_{\alpha}$
then there is an $h^{\prime}\supseteq h_{\alpha}$ so that
$\mathcal{I}_{\alpha}^{h^{\prime}}\setminus X_{\alpha}$ is finite.

  2. (2)

If $(A_{n}^{\alpha})\subseteq{\rm fil}(\mathcal{I}_{\alpha})$ then there is a
$B\in{\rm fil}(\mathcal{I}_{\alpha+1})$ so that for all $n<\omega$ we have
$B\subseteq^{*}A_{n}^{\alpha}$.

  3. (3)

There is a $C\in{\rm fil}(\mathcal{I}_{\alpha+1})$ which $Q$-dominates
$f_{\alpha}$.

The rest of the proof is standard bookkeeping argument. So fix
$\alpha<2^{\aleph_{0}}$. At each stage we will add at most countably many
reals so we can assume that $\mathcal{I}_{\alpha}$ has size
${<}2^{\aleph_{0}}$. We will deal with the three requirements in three steps.
In the first step, if $X_{\alpha}$ does not have infinite intersection with
every Boolean combination of $\mathcal{I}_{\alpha}$ or $h_{\alpha}$ is not
defined on $\mathcal{I}_{\alpha}$ then we do nothing and let
$\mathcal{I}_{\alpha}^{0}=\mathcal{I}_{\alpha}$. Otherwise we use the forcing
axiom characterization of $\mathfrak{p}=2^{\aleph_{0}}$ applied to
$\mathbb{M}(\mathcal{F}_{\alpha})$ where $\mathcal{F}_{\alpha}$ is a
diagonalization filter containing $X_{\alpha}$. By ${<}2^{\aleph_{0}}$-many
dense sets we can find a $Y$ which is independent over $\mathcal{I}_{\alpha}$
and $Y\subseteq^{*}X$ since there are ${<}2^{\aleph_{0}}$-many Boolean
combinations. Let $\mathcal{I}^{0}_{\alpha}=\mathcal{I}_{\alpha}\cup\\{Y\\}$
and note that by the same argument as in the proof of Lemma 3.2 this satisfies
criterion (1) above.

Next, if $(A_{n}^{\alpha})\nsubseteq{\rm fil}(\mathcal{I}_{\alpha})$, let
$\mathcal{I}^{1}_{\alpha}=\mathcal{I}^{0}_{\alpha}$. Otherwise, by
successively choosing diagonalization filters (which will all have all the
$A_{n}^{\alpha}$’s) we can find countably many sets $(Y_{n})_{n<\omega}$ so
that
$\mathcal{I}^{1}_{\alpha}:=\mathcal{I}^{0}_{\alpha}\cup\\{Y_{n}\;|\;n<\omega\\}$
is independent and each $Y_{n}$ is an almost subset of every $A^{\alpha}_{n}$.
As in the proof of Lemma 3.3, for each $k$ let $l_{k}(n)$ be such that
$Y_{n}\setminus l_{k}(n)\subseteq A^{\alpha}_{n}$ and let
$f\in\omega^{\omega}$ dominate all the $l_{k}$’s. The same proof as in Lemma
3.3 ensures then that $B=\bigcup_{n<\omega}(Y_{n}\setminus f(n))$ is in ${\rm
fil}(\mathcal{I}^{1}_{\alpha})$ and $B\subseteq^{*}A^{\alpha}_{n}$ for all
$n<\omega$ as needed for criterion (2).

Finally for criterion (3), we can again use the forcing axiom characterization
of $\mathfrak{p}=2^{\aleph_{0}}$ applied in this case to mimic the proof of
Lemma 3.7 to find a $Z$ which $Q$-dominates $f_{\alpha}$ and has infinite
intersection with every Boolean combination in $\mathcal{I}_{\alpha}^{1}$.
Finally similar to the proof of criterion (2) in the previous paragraph we can
find sets $\\{Z_{n}\;|\;n<\omega\\}$ so that
$\mathcal{I}_{\alpha+1}:=\mathcal{I}^{2}_{\alpha}=\mathcal{I}^{1}_{\alpha}\cup\\{Z_{n}\;|\;n<\omega\\}$
is independent and $Z_{n}\subseteq^{*}Z$ for all $n<\omega$. By the same proof
again as in Lemma 3.7, this ensures that $Z\in{\rm
fil}(\mathcal{I}_{\alpha+1})$, thus completing the construction and hence the
proof. ∎

We also get the following.

######  Theorem 4.2.

Let $\kappa<\lambda$ be cardinals both of uncountable cofinality. It is
consistent that $2^{\aleph_{0}}=\lambda$ and there is a selective independent
family of size $\kappa$. Moreover if $\kappa$ is regular we can have that
$\mathfrak{i}=\kappa$ i.e. the selective independent family is of minimal
size.

###### Proof.

By forcing if necessary assume that $2^{\aleph_{0}}=\lambda$. Let $\mu={\rm
cf}(\kappa)$ and let $\\{i_{\alpha}\;|\;\alpha<\mu\\}$ be a $\mu$-length
cofinal sequence. We will force that $\mathfrak{b}=\mathfrak{d}=\mu$ and there
is a selective independent family of size $\kappa$. Since
$\mathfrak{d}\leq\mathfrak{i}$ in $\mathsf{ZFC}$, see [3, Theorem 8.13], in
the case $\kappa$ is regular this will complete the proof of the “moreover”
part as well. Now, define a finite support iteration
$\langle\mathbb{P}_{\alpha},\dot{\mathbb{Q}}_{\alpha}\;|\;\alpha<\kappa\rangle$
so that if $\alpha\notin\\{i_{\xi}\;|\;\xi<\mu\\}$ then $\mathbb{P}_{\alpha}$
forces that $\dot{\mathbb{Q}}_{\alpha}$ is the Mathias forcing for some
inductively defined independent family as in the construction described in
Theorem 3.1. If $\alpha$ is some $i_{\xi}$ then let $\mathbb{P}_{\alpha}$
force that $\dot{\mathbb{Q}}_{\alpha}$ is Hechler forcing, followed by the
$\omega+\omega$ stage iteration described in Lemma 3.7 to make the Hechler
Generic $Q$-dominated by some element of the filter of the family we are
adding.

Let $\mathcal{I}_{\kappa}$ be the generic independent family added by this
iteration. By the arguments in the previous section, it is clear that this
family will be densely maximal and have a density filter which is a
$P$-filter. Moreover, the Hechler reals will form a scale of length $\mu$ (and
every set of reals of size ${<}\mu$ will be dominated by some Hechler real)
hence $\mathfrak{b}=\mathfrak{d}=\mu$. Also, each Hechler real will be
$Q$-dominated by some element of ${\rm fil}(\mathcal{I}_{\kappa})$. Since the
family of Hechler reals is dominating this is enough to ensure that ${\rm
fil}(\mathcal{I}_{\kappa})$ is a $Q$-filter thus completing the proof. ∎

##  5\. Conclusion and Open Questions

We conclude this paper with a list of questions for further research. The most
important of these, as mentioned in the introduction is the following.

######  Question 1.

Is there always a selective independent family? If there is one, is there
always one of size $\mathfrak{i}$?

Towards answering this question we note that very little is even known about
the existence of selective independent families in models where the ground
model selective independent families are not preserved. Indeed, until the
current paper we did not know if $\mathfrak{i}=2^{\aleph_{0}}>\aleph_{1}$ was
consistent with the existence of a selective independent family. In particular
we would like to know:

######  Question 2.

Are there selective independent families in the Cohen model?

Turning our attention to the results of this paper point out to the following
loose end from the proof of Theorem 3.1: Did we need to choose the
diagonalization filters to ensure the $Q$-filter property? More precisely of
interest is the following:

######  Question 3.

Can an iteration of Mathias forcing as described above produce an independent
family whose diagonalization filter is not a $Q$-filter?

## References

  * [1] Tomek Bartoszyński and Haim Judah.  Set Theory: On the Structure of the Real Line.  A.K. Peters, Wellsley, MA, 1995.
  * [2] Jeffrey Bergfalk, Vera Fischer and Corey Bacal Switzer.  Projective Well Orders and Coanalytic Witnesses,  Annals of Pure and Applied Logic, 173(8):103135, 2022.
  * [3] Andreas Blass.  Combinatorial cardinal characteristics of the continuum.  In Matthew Foreman and Akihiro Kanamori, editors, Handbook of Set Theory, pages 395–489. Springer, Dordrect, 2010.
  * [4] Jörg Brendle, Vera Fischer and Yuri Khomskii.  Definable Maximal Independent Families,  Proceedings of the American Mathematical Society, 147: 3547-3557, 2019.
  * [5] David Chodounský, Vera Fischer and Jan Grebík.  Free sequences in $\mathcal{P}(\omega)/{fin}$,  Archive for Mathematical Logic, 58(7-8): 1035-1051, 2019.
  * [6] Jorge A. Cruz-Chapital, Vera Fischer, Osvaldo Guzmán and Jaroslav Šupina.  Partition forcing and independent families,  Journal of Symbolic Logic, doi:10.1017/jsl.2002.68, 2022.
  * [7] Vera Fischer and Diana C. Montoya. Ideals of Independence, _Archive for Mathematical Logic_ 58(5-6), 767-785, 2019.
  * [8] Vera Fischer and Corey Bacal Switzer. Cohen Preservation and Independence To appear in Annals of Pure and Applied Logic, doi:10.1016/j.apal.2023.103291, 2023.
  * [9] Martin Goldstern and Saharon Shelah. Ramsey ultrafilters and the reaping number - Con ($\mathfrak{r}<\mathfrak{u}$), _Annals of Pure and Applied Logic_ 49(2), 121-142, 1994.
  * [10] Lorenz J. Halbeisen.  Combinatorial Set Theory with a Gentle Introduction to Forcing.  Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2017.
  * [11] Thomas Jech.  Set Theory.  Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003.
  * [12] Saharon Shelah.  CON($\mathfrak{u}>\mathfrak{i}$),  Arch. Math. Logic, 31(6): 433-443, 1992.
  * [13] C. Switzer  Selective independence and $h$-perfect tree forcing notions,  RIMS Kokyuroku Conference Proceedings: Set Theory of the Reals, 2213:63 - 74, 2022.


# Sparse Periodic Systolic Dataflow for Lowering Latency and Power Dissipation
of Convolutional Neural Network Accelerators

Jung Hwan Heo  University of Southern CaliforniaLos AngelesCaliforniaUSA
<EMAIL_ADDRESS>,  Arash Fayyazi  University of Southern CaliforniaLos
AngelesCaliforniaUSA<EMAIL_ADDRESS>,  Amirhossein Esmaili  University of
Southern CaliforniaLos AngelesCaliforniaUSA<EMAIL_ADDRESS>and  Massoud
Pedram  University of Southern CaliforniaLos AngelesCaliforniaUSA
<EMAIL_ADDRESS>
(2022)

###### Abstract.

This paper introduces the sparse periodic systolic (SPS) dataflow, which
advances the state-of-the-art hardware accelerator for supporting lightweight
neural networks. Specifically, the SPS dataflow enables a novel hardware
design approach unlocked by an emergent pruning scheme, periodic pattern-based
sparsity (PPS). By exploiting the regularity of PPS, our sparsity-aware
compiler optimally reorders the weights and uses a simple indexing unit in
hardware to create matches between the weights and activations. Through the
compiler-hardware codesign, SPS dataflow enjoys higher degrees of parallelism
while being free of the high indexing overhead and without model accuracy
loss. Evaluated on popular benchmarks such as VGG and ResNet, the SPS dataflow
and accompanying neural network compiler outperform prior work in
convolutional neural network (CNN) accelerator designs targeting FPGA devices.
Against other sparsity-supporting weight storage formats, SPS results in
4.49$\times$ energy efficiency gain while lowering storage requirements by
3.67$\times$ for total weight storage (non-pruned weights plus indexing) and
22,044$\times$ for indexing memory.

Deep Learning, Pattern-based Pruning, CNN Acceleration, FPGA

††journalyear: 2022††copyright: rightsretained††conference: ACM/IEEE
International Symposium on Low Power Electronics and Design; August 1–3, 2022;
Boston, MA, USA††booktitle: ACM/IEEE International Symposium on Low Power
Electronics and Design (ISLPED ’22), August 1–3, 2022, Boston, MA, USA††doi:
10.1145/3531437.3539715††isbn: 978-1-4503-9354-6/22/08††ccs: Computing
methodologies Machine learning††ccs: Hardware Power estimation and
optimization

##  1\. Introduction

Convolutional Neural Networks (CNNs) exhibit great performance in many
computer vision applications such as image classification, object recognition,
and scene labeling (Krizhevsky et al., 2012). However, the high performance of
deep CNNs is achieved at the cost of high computation. This makes it
challenging for networks to be deployed to resource-constrained edge devices
with strict storage and energy limits. Therefore, developing CNN architectures
with reduced computation and storage costs is of great importance. At the
algorithmic level, methods such as weight quantization (Nazemi et al., 2021),
weight pruning (Han et al., 2015; Ding et al., 2019), and knowledge
distillation (Hinton et al., 2015) have gained recent popularity.

In particular, weight pruning is a widely practiced approach for reducing the
memory footprint and computational cost of neural networks. By removing
redundant weights of a network that does not harm the model accuracy, the
model is compressed from a dense to a sparse computational graph. With the
progress in weight pruning methods, pattern-based pruning (Niu et al., 2020;
Kundu et al., 2020) has emerged as a promising avenue that seeks to find a
sweet spot between the two conventional pruning schemes: 1) structured pruning
(Wen et al., 2016) which has high regularity and is hardware-friendly, but
susceptible to accuracy degradation; 2) unstructured pruning which retains
high accuracy, but suffers from large hardware overhead to manage irregular
weight indices. Pattern-based pruning method compromises between these two
pruning schemes by enforcing a semi-structured level of regularity through
pre-defined patterns. This ameliorates the hardware overhead compared to
unstructured pruning, but it still necessitates a series of auxiliary buffers
to manage a unique set of indexing scenarios with the pattern-based approach.
At its core, hardware overhead caused by indexing sparse weights manifests a
fundamental design limitation for the accelerator to further optimize latency,
power, and memory requirements.

In this paper, we advance the state-of-the-art in sparse neural network
accelerator design by exploiting the concept of periodicity in pattern-based
pruning for the first time in hardware. Prior art (Kundu et al., 2020) mainly
explores the software stack of the periodic pattern-based pruning approach and
demonstrate that added periodicity has negligible accuracy loss. Here, we
observe periodicity as an opportunity in hardware to avoid indexing overhead
with its added regularity. We first present our compiler that reorders the
weights according to the periodicity, optimizing for maximum parallelism. Then
we present sparse periodic systolic (SPS) dataflow that computes convolutions
in a systolic array of processing elements, commonly seen in Field
Programmable Gate Arrays (FPGAs). Then, a dedicated indexing method is
introduced in hardware to fetch the pre-defined locations of nonzero weight
indices using significantly smaller memory requirements. The main
contributions of this paper are summarized as follows:

  * •

We present a novel SPS dataflow that exploits the _periodic pattern-based
sparsity_ in neural networks to achieve an FPGA-friendly architecture.

  * •

Using a compiler tailored to the SPS dataflow, we effectively solve the long-
standing indexing overhead problem for unstructured pruning. We co-design the
period-pattern-weight (PPW) compact storage format and the corresponding
architecture to efficiently fetch weights and activations.

  * •

We perform the next layer reordering (NLR) optimization method enabled by the
periodic pattern-based design to further reduce data movement cost in between
layers.

##  2\. Preliminaries and Background

This section includes background on deep neural network (DNN) processing and
details the _periodic pattern-based pruning_ method, which is the weight
reduction technique used for DNN compression in this paper.

###  2.1. DNN processing and Compilers

A convolutional layer receives input feature feature maps (IFMs) of size
$w_{\mathrm{in}}\times h_{\mathrm{in}}\times c_{\mathrm{in}}$ and convolves
them with $c_{\mathrm{out}}$ different filters, each filter of size
$w_{\mathrm{k}}\times h_{\mathrm{k}}\times c_{\mathrm{in}}$ to generate output
feature maps (OFMs) of size $w_{\mathrm{out}}\times h_{\mathrm{out}}\times
c_{\mathrm{out}}$. Here, $w_{\mathrm{x}}$, $h_{\mathrm{x}}$, $c_{\mathrm{x}}$
represent width, height, and depth of tensor $x$, which can represent the 3D
input/output feature map. The IFMs for the next convolutional layer are
equivalent of the current convolutional layer’s OFMs. Such computations can be
represented by a six-level nested loop (seven-level nested loops when
considering iteration over images in a mini-batch), i.e., loops over
$w_{\mathrm{out}},h_{\mathrm{out}},c_{\mathrm{out}},w_{\mathrm{k}},h_{\mathrm{k}},$
and $c_{\mathrm{in}}$. Also known as a computational block, these nested loops
characterize the computational flow for a convolutional layer in CNNs.

###  2.2. Periodic Pattern-based Sparsity (PPS)

Pattern-based sparsity will first be explained before the introduction of
periodicity. In pattern-based sparsity, a pattern is defined as a pre-defined
2D kernel that constrains the locations of nonzero entries, also referenced as
a kernel variant (KV). Thus, any given kernel of a 3D filter can be classified
as one of the KVs, since the locations of the weights are strictly assigned to
form a pattern while pruning. The number of nonzero entries (the kernel
support) in a $w_{\mathrm{k}}\times h_{\mathrm{k}}$ kernel is also referred to
kernel support size (KSS). KSS is fixed for all patterns to support high
regularity, which reduces workload imbalance between processing elements (PEs)
in the systolic array. Unlike unstructured pruning that prunes at the
granularity of individual weights, pattern-based pruning prunes at the
granularity of patterns, which adds regularity yet less flexibility. The
regularity helps with achieving higher hardware performance, but less
flexibility poses a relative challenge in retaining accuracy.

Figure 1. Illustration of PPS with params KSS=4 and P=2.

Periodic pattern-based sparsity is an extension of the pattern-based sparsity,
where the concept of periodicity constrains the sequence in which the patterns
occur in a given filter. Fig. 1 illustrates an example of PPS. Rotation of
patterns (or KVs) due to periodicity occurs in two directions, across the
kernels and across the filters. Each KV appears in a repeating sequence of
[KV1, KV2, KV1, …] for the first filter. Such sequence of filters with a
unique initial KV is denoted as a filter variant (FV). For the second FV, it
will begin with KV2 in a rotating sequence of [KV2, KV1, KV2, …]. Having
rotations across both channel and filter dimension adds flexibility to improve
network accuracy.

A key insight here is the simplicity at which the KVs can be indexed in an any
arbitrary filter. Thanks to the modulo rotation that occurs with an interval
of periodicity (P), the burden of storing the location of each KV (or pattern)
can be reduced to a single scalar value P, which is also the number of KVs.
This means the weights associated with each KV can be accessed by P with
minimal overhead. Thus, every KV of same type can be indexed by iterating
across the filter with offset P, which is much simpler than iterating over the
indices of each KV type and its respective location that irregularly occurs
across the filter.

Figure 2. Overall flow of the SPS Acceleration Framework.

##  3\. Overall Flow

Given the golden opportunity to design a hardware that does not suffer from
indexing overhead while preserving the network accuracy, we propose a novel
end-to-end FPGA-friendly DNN acceleration framework that can fully exploit the
new _periodic pattern-based_ dimension in its dataflow. Fig. 2 shows our
acceleration framework that consists of three stages. First is the model
pruning stage, where we employ pattern-based periodic pruning method developed
by (Kundu et al., 2020). Second is the sparsity-aware compiler optimization
(cf. Section 4) that performs a series of periodicity-driven weight reshaping
operations. The compiler provides a maximum degree of flexibility for model
compression parameters, such as pattern shapes, P, and KSS. Systolic padding
is also applied to maintain the parallelism that occurs across the two
dimensions of the systolic array. Last is the sparsity-aware architecture (cf.
Section 6), where the input matching Unit (IMU) is designed to facilitate the
SPS dataflow in an FPGA-friendly hardware architecture.

##  4\. Compiler Tailored to PPS

Once the model is trained using pattern-based periodic pruning, sparse weights
must be stored in an efficient format. Otherwise, the indexing overhead will
cause the expected benefits of pruning to be lost. As such, this section
introduces a compiler that shapes the initial weight tensor to a compact
format that we call period-pattern-weight (PPW) format. From the initial 4D
weight tensor that is periodically pattern-pruned with periodicity P and KSS
number of nonzero weights per KV, we apply a series of transformations to
arrive at the sparsity parameters described below in Table 1.

###  4.1. Sparsity-aware Optimizations

Key challenges of hardware acceleration for unstructured pruning can be
reduced to heavy control-flow instructions, as well as thread divergence and
load imbalance (Dave et al., 2021). These are largely solved by promoting
parallelism during the dataflow. Grouping filters with similar kernel
sequences achieves better _inter-thread_ parallelization, while grouping same
patterns within a filter improves _intra-thread_ parallelization (Niu et al.,
2020). Taken together, these provide a key insight as to how the patterns
should be rearranged by the compiler to maximize parallelism.

Figure 3. Overview of the PPW storage format.

Kernel and Filter Reordering:  Kernel and filter reorderings both group the
KVs according to P. A running example is illustrated in Fig. 2 where it shows
a grouping of three distinct KVs together. Periodicity of three results in a
first group KV1 that increments in multiples of three with the offset of one,
which is the KV number. Similarly, KV2 increments in P with offset of 2 and so
on. This results in 3 arrays of input channels (ICs) in the form of [1+P*0,
1+P*1, 1+P*2, …], [2+P*0, 2+P*1, …], and [3+P*0, 3+P*1, …] assuming 1-based
indexing. Each array has a size of $\lceil c_{in}/P\rceil$ denoted by
$IC_{p}$.

Once the same KVs are grouped together, the same _sequences of kernels_ are
grouped together as well. Each unique sequence produces a filter variant (FV),
where in our example equates to three groups of output channels (OC) being
produced with each group having a size of $\lceil c_{out}/P\rceil$, denoted by
$OC_{p}$ (see Fig. 3).

Table 1. Parameters used in the proposed compiler.

Symbol | Calculation | Description
---|---|---
$W_{NUM}$ | $P\times KSS$ | total # of predefined nonzero weights
$IC_{p}$ | $\lceil c_{\mathrm{in}}/P\rceil$ | # of input channels per group
$INC_{p}$ | $\lceil c_{\mathrm{cin}}/P/sys_{w}\rceil$ | # of input channels tiled iterations per group
$OC_{p}$ | $\lceil c_{\mathrm{out}}/P\rceil$ | # of output channels per group
$ONC_{p}$ | $\lceil c_{\mathrm{out}}/P/sys_{h}\rceil$ | # of output channels tiled iterations per group

Systolic Padding:  To support the SPS dataflow (Section 5) that concurrently
processes groups of input channels $IC_{p}$ and output channels $OC_{p}$
together, padding is applied when either of these groups doesn’t fully
populate the systolic array resources. It is worth noting that padding is
usually interpreted as a wasteful operation and should be avoided whenever
possible, for example by pipelining. However, in our experience, the number of
patterns required to achieve high performance is 6-8. This means that if the
dimension of the weight matrix ($IC_{p}$, $OC_{p}$) is divisible by
($sys_{w}$, $sys_{h}$), no padding will be necessary. Fortunately, most well-
known networks such as VGG and ResNets have weight dimensions in multiples of
8 with popular ones being 128, 256, and 512. Since the quotient values can be
used as reconfigurable systolic array dimensions, the cost incurred from
padding is minimal.

Input: $W^{oc,ic}_{kh,kw}$: Nonzero weights; $A^{ic}_{kh,kw}$: Input
activations;

$w_{\mathrm{k}}\times h_{\mathrm{k}}$: Kernel Size; PS[][]: Partial Sum
register in PE

$h_{\mathrm{out}}\times w_{\mathrm{out}}\times c_{\mathrm{out}}$: Output
Feature Map (OFM) Size;

Output: Result stored in OFM

1 for  _$oh=0;oh <h_{out};oh\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

2 for  _$ow=0;ow <w_{out};ow\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

// begin convolution

3 for  _$g=0;g <P;g\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

4 for  _$cc=0;cc <ONC_{p};cc\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

5 for  _$kv=0;kv <P;kv\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

6 for  _$w=0;w <KSS;w\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

// read Weight Index Buffer (kh, kw)

7 for  _$rr=0;rr <INC_{p};rr\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

8 for  _$i=0;i <w_{sys};i\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

9 #pragma unroll(i)

10 for  _$j=0;j <h_{sys};j\raisebox{0.4pt}{\scalebox{0.9}{++}}$_ do

11 #pragma unroll(j)

12 PS[j][i]+=$W^{j,i}_{kh,kw}*A^{i}_{kh,kw}$

13 end for

14

15 end for

16

17 end for

18

19 end for

20

21 end for

// Tree Adder to add Partial Sums across $w_{sys}$

// Accumulate partial OFM in Output Buffer

22 end for

// Store resulting OFM from the buffer to DRAM

23 end for

24

25 end for

26

27 end for

Algorithm 1 The Sparse Periodic Systolic Dataflow

##  5\. The Sparse Periodic Systolic Dataflow

The SPS Dataflow guides compact weights to be run in the FPGA-friendly
systolic architecture. It has two major functionalities: 1) matching the PPW
weight tensor with the corresponding activations and 2) tiling across the
$INC_{p}$ and $ONC_{p}$ by concurrently executing all MAC operations in the
systolic array.

First, the _temporal_ component of the SPS Dataflow may be understood by
looking at a single PE unit in the 2D systolic array of the hardware
accelerator. As Section 6 describes, weights are stored in the BRAMs in each
PE and the output of the associated MAC unit is stored in a partial sum
register inside the PE. Thus, the dataflow is a combination of weight
stationary and output stationary dataflow. This order maximizes the reuse of
weights as well as outputs, while paying some cost to stream the activations
to the computation units.

The _spatial_ component of the SPS Dataflow is mapped to match the dimensions
of the systolic array. The compiler has already grouped the input and output
channels according to weight patterns, and two additional inner loop nests (i
and j iterators in Algorithm 1) further blocks out the subgroup within
$IC_{p}$ by $sys_{w}$ and $OC_{p}$ by $sys_{h}$, resulting in $INC_{p}$ and
$ONC_{p}$, respectively.

The crux of the SPS dataflow lies in the simplicity of decoding the compressed
PPW format to fetch the corresponding input activations. Many state-of-the-art
sparsity-supported accelerators use storage formats such as the coordinate
list (COO), compressed sparse row (CSR), and compressed sparse column (CSC)
(Cheng et al., 2014), where the storage requirement for nonzero indexing
polynomially increases with the network size. However, the storage for PPW is
network architecture-agnostic, meaning it can stand on a constant storage
requirement only dependent on pruning parameters P and KSS, regardless of how
deep or wide the network is.

The method to facilitate the MAC operation indexing between activation and the
weight is as follows. We create two indexing buffers of size $W_{NUM}$, each
responsible for storing the two spatial dimensions of a kernel,
$h_{\mathrm{k}}$ and $w_{\mathrm{k}}$. Similar to the COO format, each weight
can be indexed by a single iterator that fetches the height and width of the
weight inside the kernel. Thanks to the highly regular occurrence of the
patterns, each weight in a given group, kernel number, and nonzero weight
number can be calculated by $((g+kv)*KSS+w)\%W_{NUM}$. The modulus operation
wraps the buffer so it continues the periodically occurring patterns.

###  5.1. Next Layer Reordering

After the convolution operation is completed, the results of the MAC
operations are stored. Due to compiler’s reordering, the unnatural ordering of
output channels produces results in increments of P. A naive solution is to
simply sort it to a natural order (increasing from channel 0 to
$c_{\mathrm{cout}}-1$. Yet, this causes a nontrivial amount of data movement
from scanning and reordering the entire output channel for _every layer
transition_ and also accessing the buffer that stores the the sorting indices.

Here, we observe that SPS dataflow produces the OFM with an increment of P.
Therein, the compiler can expect the channels to be grouped in certain strides
of P and _proactively_ reorder the channels for the next layer so that it
matches the channel ordering of incoming activations. As such, NLR can save
the total execution time and energy efficiency from reordering after each
convolutional layer, effectively imitating the dense dataflow where such
channel indexing problems do not occur.

Figure 4. Overview of systolic array accelerator design.

##  6\. Proposed Periodic Sparsity Architecture

In this section, we describe our FPGA-tailored architecture customized for the
proposed periodic pattern-based sparsity.

The accelerator contains (i) a 2D array of PEs (systolic array) which is
responsible for executing the MAC operations associated with the convolution
operation, (ii) a memory hierarchy feeding data to the said array, which
consists of register files, on-chip memory (Block RAMs on FPGA devices), and
external off-chip memory (DRAM), and (iii) an input matching unit (IMU) that
reads the nonzero weight indices from the Weight Index Buffer and matches with
the input feature maps. The systolic array is followed by a vector processing
unit, which includes multiple ALUs that conduct neural network operations such
as nonlinear activation functions and maximum pooling, as illustrated in Fig.
4.

The available hardware resources in an FPGA device, such as digital signal
processing units (DSPs), Configurable Logic Blocks (CLBs) that contain several
look-up tables (LUTs), and Block RAMs (BRAMs) are placed as resource groups in
a column-wise manner. Consequently, the all resources are uniformly
distributed on the FPGA chip, and one should place data that is used by a DSP
in a BRAM that is physically close to the DSP. Hence, A PE in our design
comprises one DSP and its adjacent BRAM. We also use some of the CLBs as
distributed memories to store indices of non-zero weights in KVs. Note that
these indices are low precision (e.g., 4 bits for a 2D kernel with size of
$3\times 3$ which is common in well-known computer vision models).

The IFMs are initially cached in an input buffer, then passed through the IMU
to skip pruned weights, and sequentially transmitted onto the first row of PEs
in the systolic array. In addition, input data is simply shifted into the PE
array and between nearby PEs on the same row of the systolic array. This
technique does away with the need for global interconnections between the
input buffers and all PEs and the costly multiplexers. We also bring the
indices associated with KVs in parallel with weight fetching. This is feasible
since input data, weights, and indices are stored in separate off-chip memory
banks in the target FPGA board and are thus simultaneously accessible.
Finally, the registered partial sum results that reside in the PEs of one row
are passed to the adder tree to conduct the required summation and generate
the final OFM value when all computations for one OFM are completed.

##  7\. Experimental Results

In this section, we assess the storage required by the proposed PPW format
compared to popular sparsity-supporting formats and present the hardware
utilization of our accelerator as well as its energy consumption comparison to
state-of-the-art accelerators.

###  7.1. Experimental Configuration

For the storage format experiments, 8 bit unsigned integers are used to
calculate the weight storage format. For a fair comparison, the connectivity
pruning that allows higher weight compression for FKW format is recognized
during calculation. Sparsity constants of KSS=2 and P=8 is used for all PPW
calculations, as we validate the model accuracy (91.2%) (Kundu et al., 2020)
that has less than 1% accuracy degradation compared to the non-pruned version.
For evaluating hardware performance, we targeted a Xilinx VU9P FPGA using the
AWS EC2 F1 instance. We implemented it on Xilinx Virtex UltraScale+ FPGA board
using Vivado HLS design suite 2019.1. We evaluate our SPS Dataflow on a VGG16
architecture on the CIFAR-10 dataset.

###  7.2. Storage Comparison

Figure 5. Total (Weight + Index) storage comparison.

Figure 6. Index storage comparison.

Fig. 5 shows that PPW compresses over 77.8% (4.5x), 72.8% (3.67x), 61.2%
(2.57x), 52.9% (2.12x), 10.5% (1.12x) of the total storage requirement
compared to dense, COO, CSR, CSC, and FKW, respectively over unique
convolutional layers in VGG16. Note that layers 8-10 and 11-13 in VGG16 has
the same weight matrix size and are represented by L7 and L8 in our figures.
Similar selection has been adopted for ResNet18. Dense model represents the
non-pruned baseline model.

Fig. 6 illustrates that PPW format requires 22044x less indexing storage even
compared to the FKW format, which is the most competitive. As seen on the
graph, PPW enjoys constant storage requirement of small amount of bits across
different convolutional layers in VGG, while others grow on the order of
MegaBytes. Similar effects are shown in selected convolutional layers of
ResNet18, where PPW consistently outperforms total storage while remaining
near zero-valued for indexing storage.

Figure 7. Percent Storage for unique layers.

For larger convolutional layers (the later layers) with many irregular
weights, more space is dedicated to store indexing buffers than the actual
weights (see Fig. 7). The halfway point (50%) of the total storage is marked
with a dotted line, and we can observe that most storage formats easily exceed
this threshold. This also shows that the marginal increase in indexing storage
is greater than that of weight storage. For example, COO steadily uses higher
proportions of storage for indexing with larger convolutional layers, from the
low point of 58% in the smallest layer to 73% in the largest layer.

Figure 8. Benchmarking effective sparsity threshold for VGG16.

To conduct a comparative analysis on a single storage format against others,
we benchmark the _effective sparsity threshold_ , which is defined as the
minimum sparsity rate that the weight format must achieve in order to realize
a lower total storage requirement. This attempts to answer the question: given
the pruning ratio and the total storage used for the benchmarked format, what
is the minimum sparsity that the other formats must achieve in order to save
more storage?

Our results from the left plot of Fig. 8 show that most traditional sparse
weight storage formats have a relatively harsh constraint on the sparsity
requirement, with COO requiring only 22.2% of weights to be unpruned. In other
words, it requires 77.8% of the weights to be pruned in order to begin saving
more storage than the baseline dense format.

We also benchmark PPW and observe as shown on the right of Fig. 8 that the
highly compact format of PPW enforces a strict effective sparsity threshold on
all other weight storage formats. The effective sparsity threshold for FKW,
the most competitive format, is 90%, which means that FKW requires the
compression ratio to be at least 10x to begin saving more storage than PPW.
Yet, reference (Niu et al., 2020) reports an 8x pruning rate, suggesting that
the PPW format saves more storage under similar network accuracy. FKW could
employ harsher pruning and achieve more than 10x pruning rate to realize lower
storage, but this would nontrivially sacrifice the network accuracy under 91%
which is more than the acceptable 1% degradation range.

###  7.3. Hardware Utilization and Energy Efficiency Comparisons

Table 2. Hardware Utilization for VGG16 on CIFAR-10.

Hardware resource | DSP48E | LUT | BRAM_18K | Frequency (MHz)
---|---|---|---|---
Usage in our architecture | 1038 (15%) | 115290 (10%) | 512 (12%) | 342
Baseline architecture∗ | 1038 (15%) | 115290 (10%) | 2942 (68%) | 342

∗the baseline architecture is used for handling the dense format.

In this section, we evaluate the aforementioned sparsity storage formats in
the FPGA platform. First, the hardware utilization of the proposed accelerator
tailored to SPS dataflow for running VGG16 on CIFAR-10 dataset is reported in
Table 2. The baseline architecture is similar to the architecture shown in
Fig. 4 while removing IMU and weight index buffer. As shown in the table, when
employing the accelerator design discussed in Section 7, periodic pattern-
based pruning that eliminates 77.8% of the weights stored in the BRAM
alongside with the PPW storage format that requires minimal indexing support
in hardware leads to efficient usage of hardware resources in the FPGA.

Next, we evaluate the energy efficiency of our proposed architecture and
dataflow compared to other formats. CSR and FKW are implemented as they are
the competitive formats that exist today. The relative energy savings is
reported in Fig. 9, normalized with the dense baseline architecture. Our PPW
format executed by the SPS dataflow achieves 4.49$\times$ energy savings over
the dense baseline, while CSR acehives 1.4$\times$ and FKW achieves
3.1$\times$. To understand the energy savings, we classify the resources of
energy cost in four ways: 1) bringing in weights 2) running MAC operations 3)
read/write from/to weight index buffers and 4) data reordering cost for
pattern-based dataflows such as the FKW. The first two costs are very similar
as they’re directly proportional to the the number of weights being moved
around the hardware (thus modeled by the weight density). However, the third
cost poses a nontrivial challenge to CSR, while FKW and PPW are relatively
immune to the indexing overhead that occurs while supporting the MAC
operation. This follows suit in Fig. 6. 4) is unique to pattern-based formats,
where FKW pays the cost of reordering the number of output channels that have
been mixed during the compiler optimization. Such indexing overhead occurs in
every layer, as the output feature map is the input feature map of the next
layer, and the dataflow expects it to be in the natural, unmixed order. On the
other hand, SPS dataflow’s next layer reordering allows outputs to be grouped
together without the need of data reordering, which eliminates the cost #4.

##  8\. Conclusion

The SPS dataflow offers a novel hardware design approach afforded by periodic
pattern-based sparsity, resulting in neural network weights with higher
degrees of regularity and thus parallelism. By avoiding excessive indexing
costs with the compiler-hardware co-design approach, the SPS dataflow
outperforms state-of-the-art sparisty formats in CNN accelerator designs
targeting FPGAs.

Acknowledgment: This research is supported by a grant from the Software and
Hardware Foundations program of the NSF.

Figure 9. Energy Savings over dense baseline for VGG16.

## References

  * (1)
  * Cheng et al. (2014) John Cheng, Max Grossman, and Ty McKercher. 2014.  _Professional CUDA c programming_.  John Wiley & Sons.
  * Dave et al. (2021) Dave et al. 2021\.  Hardware Acceleration of Sparse and Irregular Tensor Computations of ML Models: A Survey and Insights.  _Proc. IEEE_ 109, 10 (2021), 1706–1752.
  * Ding et al. (2019) Xiaohan Ding et al. 2019\.  Global Sparse Momentum SGD for Pruning Very Deep Neural Networks. In _Neurips_. 6379–6391.
  * Han et al. (2015) Song Han et al. 2015\.  Learning both Weights and Connections for Efficient Neural Networks.  _CoRR_ abs/1506.02626 (2015).  arXiv:1506.02626
  * Hinton et al. (2015) Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. 2015\.  Distilling the Knowledge in a Neural Network.  _CoRR_ abs/1503.02531 (2015).  arXiv:1503.02531
  * Krizhevsky et al. (2012) Alex Krizhevsky et al. 2012\.  ImageNet Classification with Deep Convolutional Neural Networks. In _Neurips_. 1106–1114.
  * Kundu et al. (2020) Souvik Kundu et al. 2020\.  Pre-Defined Sparsity for Low-Complexity Convolutional Neural Networks.  _IEEE Trans. Computers_ 69 (2020), 1045–1058.
  * Nazemi et al. (2021) Mahdi Nazemi et al. 2021\.  NullaNet Tiny: Ultra-low-latency DNN Inference Through Fixed-function Combinational Logic. In _29th IEEE FCCM_.
  * Niu et al. (2020) Wei Niu et al. 2020\.  PatDNN: Achieving Real-Time DNN Execution on Mobile Devices with Pattern-based Weight Pruning. In _ASPLOS ’20_. ACM, 907–922.
  * Wen et al. (2016) Wei Wen et al. 2016\.  Learning Structured Sparsity in Deep Neural Networks. In _Neurips 2016, December 5-10, 2016, Barcelona, Spain_ , Daniel D. Lee et al. (Eds.). 2074–2082.


#  COOLIO: A Language Support Extension for the
Classroom Object Oriented Language

Linhan Li  George Mason UniversityUSA and  ThanhVu Nguyen  George Mason
UniversityUSA

(2022)

###### Abstract.

COOL is an Object-Oriented programming language used to teach compiler design
in many undergraduate and graduate courses. Because most students are
unfamiliar with the language and code editors and IDEs often lack the support
for COOL, writing code and test programs in COOL are a burden to students,
causing them to not fully understand many important and advanced features of
the language and compiler. In this tool paper, we describe COOLIO, an
extension to support COOL in the popular VSCode IDE. COOLIO provides (i)
syntax highlighting supports for the COOL language through lexing and parsing,
(ii) semantics-aware autocompletion features that help students write less
code and reduce the burden of having to remember unfamiliar COOL grammar and
syntax, and (iii) relevant feedback from the underlying COOL
interpreter/compiler (e.g., error messages, typing information) to the
students through VSCode editor to aid debugging. We believe that COOLIO will
help students enjoy writing COOL programs and consequently learn and
appreciate more advanced compiler concepts.

COOL, Compilers, Language Support, Syntax Highlight, Autocompletion, User
Feedback, IDE’s

††copyright: acmcopyright††journalyear: 2022

##  1\. Introduction

COOL (Classroom Object Oriented Language) is a language often used in
undergraduate or graduate compiler classes. These include traditional courses
at Stanford, UC-Berkeley, University of Nebraska–Lincoln, University of
Virginia, University of Michigan, Vanderbilt,a nd online ones at Coursera,
EdX, and Stanford Online. The language is sufficiently small for students to
implement a complete interpreter or compiler for it within a semester, but is
still powerful enough to support major concepts in a modern programming
language including polymorphism, inheritance, dynamic dispatching, type
checking, and automatic garbage collection. As described by Alex Aiken, its
author, the COOL language is ”object-oriented, statically typed, and has
automatic memory management” (Aiken, 1996).

While being the chosen language for many Compilers and Programming Languages
courses, the syntax and semantics of COOL are unfamiliar to students. Thus,
students often just write simple COOL programs to test their Compiler
implementation. Such simple tests cause students to miss many important
features of language and therefore miss crucial designs of the compiler to
handle them (e.g., dynamic dispatching, inheritance, complex memory usage).
The reason is not that students are not willing to create more complicated and
thorough tests, but because they are not very excited to write long and
complex COOL programs without help from their favorite code editors.

#### Related Work

Currently, Extensions for editors and IDEs to support COOL, e.g., sublime-
cool-highlighter111https://github.com/princjef/sublime-cool-highlighter for
SublimeText, atom-language-cool222https://github.com/princjef/atom-language-
cool for Atom, and language-
cool333https://marketplace.visualstudio.com/items?itemName=maoguangming.cool
for VSCode, provide very basic syntax highlighting for COOL keywords.
Moreover, they miss many basic features of syntax highlighting, e.g., the
classes/variables defined by the user are not properly highlighted or
indented. Moreover, while syntax highlighting is useful, it is not sufficient
to engage users to use COOL. These extensions do not include important
features such as auto-completion and error-reporting, and thus students still
need to memorize all the syntax or repeatedly look at the manual or run the
provided reference compiler to check for syntax errors. In fact, because these
extensions are not well-maintained (e.g., language-cool has not been updated
since 2016) and do not properly cover even the basics of Cool, most students
instead just write COOL programs in plain text mode.

#### This Work

To help students learn COOL, we have developed COOLIO, a portable, feature-
rich extension for COOL to be used in major IDEs supporting the increasingly
popular Language Server Protocol (LSP) (Microsoft, 2022). While in this paper
we demonstrate COOLIO using the VSCode IDE, which is a favorite among students
and popular IDE (consistently ranked as one of the top IDE choices), COOLIO
works with any IDE supporting LSP such as Atom, Eclipse, Emacs, SublimeText,
Vim.

COOLIO supports syntax highlighting for the entire COOL language by using
regular expressions from the COOL lexer and parser to recognize COOL syntax.
COOLIO also has quick and useful autocompletion features that one would expect
from a modern IDE, e.g., code suggestion and auto structure completion, all of
which help the student write more correct code and reduce the burden of
memorizing COOL syntax and grammar. Finally, COOLIO exploits LSP client and
server design to send COOL’s type checking and evaluation information back to
the user through the VSCode editor (e.g., underline incorrect lines of code,
giving the reason why type checking fails in real-time), allowing the students
to quickly understand and debug COOL programs.

We believe that COOLIO can help students in Compiler or Programming Languages
courses that use COOL. This includes our Compiler class, which typically has
on average about 30 undergraduate and graduate students, and Compiler and PL
courses taught at other places and might have even more students (e.g., at
Stanford, UMich, or online courses such as Coursera). We have started using
COOLIO ourselves and have already let colleagues teaching courses involving
COOL know about COOLIO so that they can refer their students to try the tool.
We believe that the rich features provided by COOLIO will be useful to the
students, allowing them to learn more about COOL and design a better compiler
to support advanced features of the language.

COOLIO is open-source and available at https://github.com/dynaroars/COOL-
Language-Support. The users can easily search and install it directly from the
VSCode IDE or
Marketplace444https://marketplace.visualstudio.com/items?itemName=Linhan.cool-
language-support.

##  2\. COOL

Figure 1. Simple Cool program in VSCode with COOLIO

COOL is an Object-Oriented language and shares some design and syntax with
Java. Fig. 1 shows a small COOL program that prints HelloWorld (lines 1-3) and
a simple loop. The COOL manual, called CoolAid (Aiken, line), provides the
formal syntax and semantics of the language, which we summarize below.

#### Syntax

The syntax of COOL is designed to be simple. This allows students to write
regular expressions (regexes) for lexer and parser to recognize syntactically
correct COOL programs. The standard COOL specification does not have advanced
features such as list/array structures, threading/multi-processing supports,
or exception handling (supports for these are often used as homework or extra
credit assignments).

Table 1. Cool Syntax and Grammar program | ::= | $[class;]^{+}$
---|---|---
class | ::= |  class TYPE [inherits TYPE] $\\{$ [feature;]${}^{*}\\}$
feature | ::= |  ID([formal[,formal]∗]):TYPE $\\{$ expr $\\}$
| | |  ID:TYPE[¡- expr]
formal | ::= | ID:TYPE
expr | ::= |  ID ¡- expr
| | |<EMAIL_ADDRESS>([expr[ expr∗])
| | |  ID([expr [,expr]∗])
| | |  if expr then expr else expr fi
| | |  while expr loop expr pool
| | |  {[expr;]+}
| | |  let ID:TYPE [¡- expr] [,ID:TYPE [¡-expr]]∗ in expr
| | |  case expr of [ID:TYPE=¿ expr]+ esac
| | |  new TYPE | isvoid expr | ~expr | not expr
| | |  (expr) | expr [+—-—*—/] expr | expr [¡—¡=] expr
| | |  ID | constant(integer—string—true—false)

Tab. 1 displays the syntax and context-free grammar of COOL. A COOL program is
a set of COOL classes, and each class consists of features which are
attributes (variables) and methods. Each class defines a type and thus
programmer defines new types and associated data and methods by creating new
classes (similar to an OO language such as Java). COOL is an expression
language and thus most COOL constructs are expressions. Expressions take up a
large portion of the COOL syntax, but in general, are relatively
straightforward and similar to expressions in traditional languages. Note that
the let expression that declares a new variable is similar to the one used in
a functional language such as OCaml.

#### Type Checking and Semantics

COOL is a _type-safe_ language and thus its compiler type-checks the input
program to ensure no typing errors at run time. The typing rules for COOL,
defined in the CoolAid manual, provide deduction rules for COOL expressions
(e.g., if x is an integer and y is an integer then the expression x + y
results in an integer).

The evaluation of a COOL program is provided using operational semantics
rules. Similar to type checking rules that deduce the types of COOL
expressions, these operational semantic rules deduce values for COOL
expressions (e.g., if x is 3 and y is 7 then the expression x + y results in
10). These rules are also specified in the CoolAid manual. Fig. 2 shows the
type checking and operational semantics rules for applying binary operators
$*,+,-,/$ to expressions $e1$ and $e2$.

$\vdash e_{1}:Int$ $\vdash e_{2}:Int$ $op\in\\{*,+,-,/\\}$ $\vdash
e_{1}\;op\;e_{2}:Int$

$\vdash e_{1}:Int(i_{1})$ $\vdash e_{2}:Int(i_{2})$ $op\in\\{*,+,-,/\\}$
$v_{1}=Int(i_{1}\;op\;i_{2})\vdash e_{1}\;op\;e_{2}:v_{1}$

Figure 2. Type Checking and Operational Semantic Rules

#### Reference Compiler

Students taking compiler courses using COOL often implement a full COOL
compiler, which consists of main phases including lexing, parsing, type
checking, semantic evaluation, and ASM transforming. To help students debug
and make progress, the instructor often provides a complete “reference”
compiler, e.g., an executable binary compiled from a COOL compiler
implementation written in C or OCaml. Students then use the reference compiler
to check each step of their implementation in both output results and error
messages. COOLIO relies on the reference compiler to return error messages to
the user.

##  3\. COOLIO

Figure 3. Overview of COOLIO

The COOL Language Server Extension (COOLIO) can be found through the VSCode’s
extension window or its Github repository given in §1. It is automatically
activated when the user opens a COOL file with a .cl extension and adds
language support to the COOL program opened in the editor. COOLIO is composed
of four components shown in Fig. 3.

  * ①

The editor provides a GUI interface to the user, and is the host of many
editing features such as the syntax highlight and autocomplete. It also
interfaces with the language client (②) through its API to display information
such as error messages from the COOL compiler.

  * ②

The language client interacts with the editor and the language server by
sending and receiving information, e.g., getting the content of an opened
file, cursor position, or display error messages. Whenever the client is
activated, it creates a language server and sends data to the server.

  * ③

The language server is a proxy to our COOL compiler. When a request from the
client is received, the server retrieves the source code and sends it to the
COOL compiler for analysis. The analysis results are composed into the LSP
response format and returned to the client for display.

  * ④

The COOL reference compiler performs standard compilation phases such as
parsing, type checking, and communicating results (e.g., warning and error
messages) to the language server).

###  3.1. Syntax Highlight

Syntax highlight in COOLIO is handled by the VSCode editor. The editor
tokenizes the source code using the regex rules specified in a TextMate
configuration file. After that, the editor assigns colors to the tokens
displayed in the IDE based on their defined roles and the colors specified in
IDEs current theme (e.g., comments are blue in some themes while red in
others).

⬇

1 "scopeName": "source.cool",

2 "name": "COOL",

3 "fileTypes": ["cl"]

4 "patterns":[

5 "line_comment": {

6 "begin": "\--", "end": "$\\\n?",

7 "name": "comment.line.double-dash.cool"

8 }

9 "class": {

10 "match": "[A-Z][a-z]*",

11 "name": "entity.name.type.class.cool"

12 }]

Figure 4. Syntax Highlight Configuration in COOLIO

For COOLIO, we create a TextMate(MacroMates, 2021) JSON file consisting of
regular expressions (regexes) for all of COOL’s keywords, tokens, etc. Fig. 4
shows a snippet of a TextMate configuration having regexes for line comments
and class identifiers. Tab. 2 shows syntax highlighting regexes for several
main components in COOL.

When the user opens a COOL (.cl) file, the COOLIO extension is activated and
uses these rules for syntax highlighting. While regexes can be complicated,
the COOL reference compiler already contains similar regexes for lexing and
parsing. Thus, we adapt and reuse these regexes.

#### Example

Fig. 1 demonstrates syntax highlight in COOLIO. In this default _VSCode Light_
theme, keywords are black, control flow structures are purple, class names are
cyan, integer constants are green, and so on.

Table 2. Syntax Highlight Rules COOL Constructs | Regex Descriptions
---|---
integer | non negative integer with no leading zero
ID(Class) | alphanumeric string start with a uppercase letter
ID(other) | alphanumeric string start with a lowercase letter
special ID | self, SELF_TYPE
string | alphanumeric string enclosed by double quote
comment | line start with ”–” and block enclosed by ”(*”, ”*)”
keywords | class, else, false, fi, if, in, inherits, isvoid, let, loop,
| pool, then, while, case, esac, new, of, not, true

###  3.2. Auto Completion

COOLIO supports standard autocompletion (also called ”Intellisense” in
VSCode(Microsoft, 2021)). This allows the user to type a few keywords and the
IDE can suggest and autocomplete common code structures. For example, when
COOLIO detects that the user is typing the keyword if, it will ask if the user
wants to replace that with the COOL snippet if condition then expression else
expression fi. This autocompletion is straightforward yet useful in code
development in an IDE as they help accomplish the goal of reducing typing
effort and syntax errors from the developer.

To offer syntactically and structurally correct snippets, COOLIO’s
autocompletion has knowledge about the syntax and grammar of COOL. Similar to
syntax highlighting (§3.1), this is achieved at the editor level using a user-
supplied TextMate configuration file. This TextMate file consists of rules
mapping prefix strings (e.g., let) with code snippets (e.g., let var ... in
..). The code snippets can have multiple placeholders for any sub-expressions,
and the user can switch between them using the “Tab” key. Once the
configuration file is loaded with the extension, the editor will automatically
try to match the prefix with the string the user entered. If the input matched
(can be fully or partially) the prefix of any snippets, the name and
description of the snippet will be listed in a drop-down manual for the user
to select.

⬇

1"COOL_class_inherits": {

2 "prefix": "class",

3 "body": [

4 "class ${1:Name} inherits ${2:Object}{",

5 "\t${0:body}",

6 "};"],

7 "description": "COOL: class inherits"}

Figure 5. TextMate Autocompletion Configuration

Fig. 5 shows an example of COOLIO’s TextMate configuration. Here, ”body”
defines the code snippet line by line, and the "${...}" marks the
placeholders. This snippet defines the snippet for a class definition in COOL
(i.e., when the user types class, the COOLIO can fill in the skeleton for
defining a class in COOL).

Figure 6. Autocompletion in COOLIO

#### Example

Fig. 6 shows an example when COOLIO senses that the user wants to declare a
new variable through the let keyword and generates the snippet for new
variable declaration with appropriate placeholders for specifying the type and
initial value.

###  3.3. Communication with the User

COOLIO uses LSP for feedback communication, i.e., displaying information from
the backend COOL compiler such as errors and warnings to the frontend editor.
The design of the LSP allows the analysis to be done in separate processes,
and communicate the results with the editor through inter-process
communication (thus analysis done in the server does not affect the user’s
interaction with the editor).

COOLIO includes a pair of language client and server. The language sever is
used as a proxy to communicate with the COOL reference compiler. When the user
saves their code changes, the server invokes the COOL compiler on the code and
sends outputs to the client. The language client acts as a middle layer
between the editor and the language server. It receives data such as error
messages from the server and invokes the editor’s API to display them to the
user.

For COOLIO, reporting data such as error messages from the COOL compiler to
the client is achieved by format and translating the error message into a
representation that the editor can understand and display. More specifically,
when the compiler reports an error or warning is found in the program, the
editor displays the line number, the stage of compilation, and the detailed
error message. These errors and warnings can come from any compilation phase,
e.g., failing to parse certain expressions or having incorrect type
associations.

Note that the COOL compiler used line numbers to record the error location,
whereas the LSP requires an error location represented in character position.
This issue was handled by the languages server, in which we replaced the line
number with the position of corresponding new line characters.

Figure 7. Display an Error Message

#### Example

Fig. 7 shows how COOLIO communicates error messages to the user via the
editor. In line 2, the user assigns a string constant to variable ”num” of
type Int, which is not allowed (since the types do not conform and COOL does
not support type casting). This error is caught by the backend compiler and
reported to the user. The red wavy line indicates the location of the error,
and if the user hoover over the line, a detailed error message will appear.

##  4\. Conclusion

We presented COOLIO, a Language Server Protocol (LSP) that extends existing
IDEs and editors to support the COOL programming language. Similar to LSPs for
other languages such as C++ and Python, COOLIO aims to make writing code in
COOL easier through features such as complete syntax highlighting,
intellisense code autocompletion, and rich error and communication mechanism
between the backend compiler and frontend editor.

An indirect goal of COOLIO is to show researchers an easy way to make their
research more visible and usable for users who are familiar with IDEs, but not
with research tools, which are often written as command-line tools.
Researchers can make their research tools (e.g., static or dynamic analysis
tools) part of the LSP and interact with the user the same way COOLIO
interacts with the COOL compiler. For example, in addition to creating a
command line fault localization or program repair tool, the developers can
also create an LSP connecting the tool with the IDE, allowing the users to
interact with the tool to repair code directly through any code editor
supporting LSP. Given the popularity of IDEs such as VSCode and their powerful
extension ecosystem, we believe this will make research tools more attractive
to users, who are often excited about trying new extensions that are easy to
install and use as in the case of in VSCode.

## References

  * (1)
  * Aiken (1996) Alexander Aiken. 1996\.  Cool: A Portable Project for Teaching Compiler Construction.  _SIGPLAN Not._ 31, 7 (jul 1996), 19–24.
  * Aiken (line) Alexander Aiken. 1996 [Online].  COOL.  http://theory.stanford.edu/~aiken/software/cool/cool.html, accessed on .
  * MacroMates (2021) MacroMates. 2021\.  TextMate: Text editor for macOS.  https://macromates.com/, accessed on .
  * Microsoft (2021) Microsoft. 2021\.  IntelliSense in Visual Studio Code.  https://code.visualstudio.com/docs/editor/intellisense, accessed on .
  * Microsoft (2022) Microsoft. 2022\.  Official page for Language Server Protocol.  ttps://microsoft.github.io/language-server-protocol, accessed on .