Count how often your code asks: is this one of those?

if (c == RED || c == YELLOW || c == ORANGE) ...
if (tok == IF || tok == WHILE || tok == NUMBER || ...) ...

Chains like these are membership tests written out longhand, and they rot in a particular way: the list appears three times in three functions, someone adds a case to two of them, and the third is a bug no compiler sees. The fix is as old as Pascal — make the set a value, name it once, and ask with one operator — and Mica keeps it, with the machine cost you would hope for: one word, one bit test.

The example is examples/Sets. Build and run it:

make -C examples/Sets run

A set over a named domain

type
    Color  = (Red, Green, Blue, Yellow);
    Colors = set of Color;
warm := [Red, Yellow];
cool := [Blue, Green];

if Blue in cool then
    WriteLn("  Blue is cool");

Colors can hold any combination of exactly those four members. The constructor [Red, Yellow] builds one; in asks the question. The compiler sizes the value to the domain — four possible members is four bits in one machine word — and in compiles to a bit test, however the set was built.

The domain is part of the type, and that has teeth. A set of colors and a set of months cannot meet in one expression:

analyzer error 5112: incompatible data types in arithmetic operation
'addition': Colors and Months

An int bitmask would have merged them silently and meant nothing. That refusal is the difference between a set type and a bag of bits.

The algebra composes answers

both := warm + cool;
overlap := warm * cool;
  every color is in warm+cool: 1 1 1 1
  warm and cool share nothing: 1
  warm differs from cool:      1
  warm is a subset of both:    1

Union is +, difference -, intersection *. Equality is = and inequality is # — whole-value comparisons, like every Mica value’s. (If # looks unfamiliar: it is Wirth’s spelling, and Mica keeps his lineage where the symbol earns it.)

There is no subset operator, and the example shows the idiom that replaces it:

Ord(warm - both = [])

Nothing of warm lies outside both — the algebra says it in five tokens, readably, and [] is the empty set adopting whatever domain the expression needs.

The worked use: a parser’s recovery set

Here is the section this type exists for, and it is not a toy — it is the load-bearing idiom of every recursive-descent parser, including the PL/0 compiler this site takes apart chapter by chapter.

A parser that hits an error cannot just stop; it must skip input until it reaches something that could legally begin a statement, then resume. “Something that could legally begin a statement” is a set the grammar defines once:

statementBegin := [TokIf, TokWhile, TokNumber];
stop := statementBegin + [TokEnd];

while not (input[cursor] in stop) do
begin
    WriteLn("  skipping token %lld", Ord(input[cursor]));
    cursor := cursor + 1;
end;
  skipping token 1
  skipping token 2
  skipping token 3
  recovered at token 5, a legal statement start

Read the loop condition aloud: while the current token is not in the stop set, skip. That is the algorithm, stated as itself. The real PL/0 parser composes its recovery sets exactly this way — DeclarationBegin, StatementBegin, FactorBegin, unioned per call site with what the caller can accept — and set of Symbol is why a fifty-year-old error-recovery technique reads like prose in it.

When the same recognizer is written with comparison chains, the “set” exists only as a habit spread over the file. Here it is a value: passable to a procedure, unionable at a call site, checked against its domain.

bitset[N]: positions without a domain

Sometimes there is no enumeration — the bits are hardware flags, protocol bits, a bloom filter’s slots. bitset[N] is the same machinery over raw positions 0 to N-1:

type
    Flags = bitset[16];
f := [1..3, 10];
  f[2] 1, f[4] 0, Count 4
  bit 1 is set
  bit 2 is set
  bit 3 is set
  bit 10 is set

The constructor takes single positions and ranges alike. Indexing reads one bit back. Count — imported from the bits unit, like everything, via imp Count : bits; — answers the cardinality. And the for-in visits exactly the set positions, in ascending order: the loop you would otherwise write over all sixteen positions with a test inside, provided by the type. (The control variable is a uint64, because what it holds are positions.)

Choose by whether the positions mean something: named meanings take set of over an enumeration and get domain checking; raw positions take bitset[N] and get width checking. Both cost the same machine word.

What this does not do

No hash sets. set of needs an ordinal domain — an enumeration or a subrange — and sizes storage to it at compile time. A set of strings or of records is a different data structure with different costs, and Mica does not blur them under one name.

No subset/superset operators. <= on sets is refused (sets are not ordered); the a - b = [] idiom is the spelling, shown above.

Membership is over the domain, only. 13 in months for a set of 1..12 is refused at compile time — the question itself is malformed, and the compiler says so rather than answering false:

analyzer error 5115: incompatible data types in comparison operation 'in':
int32 and Months

A bitset index past N-1 traps. Same named-line trap as an array’s; the width is the bound.

What the compiler proved

The color that was in cool was not in warm, by one bit test each. Two domains could not meet in one union. The recovery loop skipped exactly the three tokens outside its stop set and stopped on the first one inside it. And sixteen raw positions round-tripped through a range constructor, an index, a count and an ascending walk — in one machine word, with no allocation anywhere on this page.

Next

Memory classes — the memory section opens: the same program compiled hosted and fixed-arena, what the embedded deployment promises, and what it refuses. (In preparation; its example is next in the repository.)