Atomless set computation

I want to make it clear that this is a language and it has nothing to do with any hypothetical practical use of this term.

Atomless set computation, with that exact capitalization and spacing, is an esolang based on computation over an atomless Boolean algebra. A value is therefore interpreted as a "region" rather than as an atomic object or even a set.

The algebra `Algebra` contains two distinguished values, `0` and `1`, where 0 ≠ 1.

• `0`, the empty or impossible region
• `1`, the universal region

It supports the standard Boolean-algebra operations of meet, join, and complement. For values `A` and `B`:

• `A & B` represents their meet, or intersection
• `A | B` represents their join, or union
• `~A` represents the complement of `A`
• `A <= B` means that `A` is contained within `B`

The defining property of the language is atomlessness. For every nonzero value `X`, there exists another value `Y` such that:

0 < Y < X

Therefore, no nonempty runtime value is indivisible. Every nonzero region contains a smaller nonzero region.

Operations

All predicates within the language return 1 for true and 0 for false.

Command	Description	Arguments
`zero X -> R`	Tests whether `X` is equal to `0`.	X: the region to test. R receives 1 if the predicate holds and 0 otherwise
`nonzero X -> R`	Tests whether `X` is not equal to `0`.	X: the region to test. R receives 1 if the predicate holds and 0 otherwise
`subset A B -> R`	Tests whether `A <= B`, meaning that `A` is contained within `B` in the Boolean-algebra ordering.	A: the possible subregion. B: the possible containing region. R receives 1 if the predicate holds and 0 otherwise
`meet A B -> C`	Computes the meet of `A` and `B`.	A: the first region. B: the second region. C: receives `A & B`.
`join A B -> C`	Computes the join of `A` and `B`.	A: the first region. B: the second region. C: receives `A | B`.
`complement A -> B`	Computes the complement of `A` relative to the universal region `1`.	A: the region to complement. B: receives `~A`.
`difference A B -> C`	Computes the portion of `A` lying outside `B`.	A: the source region. B: the region to exclude. C: receives `A & ~B`.
`xor A B -> C`	Computes the symmetric difference of `A` and `B`.	A: the first region. B: the second region. C: receives the region belonging to exactly one of `A` or `B`.
`split A -> B C`	Nondeterministically partitions a nonzero region `A` into two disjoint nonzero proper subregions whose join is `A`.	A: the region to partition. B: receives the first subregion. C: receives the second subregion.
`refine A -> B`	Nondeterministically selects a nonzero proper subregion of `A`.	A: the region to refine. B: receives a region satisfying `0 < B < A`.
`when X { ... }`	Executes a block if `X` is nonzero.	X: the region used as the condition. ...: the block to execute.
`otherwise { ... }`	Executes a block if the region tested by the immediately preceding `when` was `0`.	...: the block to execute.
`equal A B -> R`	Tests whether `A` and `B` denote the same element of `Algebra`.	A: the first region. B: the second region. R receives 1 if the predicate holds and 0 otherwise
`disjoint A B -> R`	Tests whether `A` and `B` have meet `0`.	A: the first region. B: the second region. R receives 1 if the predicate holds and 0 otherwise
`emit X`	Produces `X` as an observable result of the current computation.	X: the region to emit.

Variables start with a single capital letter and are followed by any number of alphanumeric symbols (capital letters, lowercase letters, numerals 0-9).

Programming

Runtime Values

All runtime values are elements of the same atomless Boolean algebra `Algebra`.

For example:

meet A B -> C

does not compute the intersection of two conventional container objects. It computes the Boolean-algebra meet:

C = A & B

Likewise:

join A B -> C

computes:

C = A | B

and:

complement A -> B

computes:

B = ~A

Control Flow

Atomless set computation does not require a primitive Boolean type. Instead, control flow is based on whether a region is zero.

A `when` block executes if its controlling region is nonzero:

when X {
emit Y
}

This executes precisely when:

X != 0

The zero region therefore behaves like false, while any nonzero region behaves like true for control-flow purposes.

A two-way conditional may be written as:

when X {
emit A
}
otherwise {
emit B
}

If `X != 0`, the first branch runs. If `X = 0`, the second branch runs.

A `when` pairs with an `otherwise` only if the `otherwise` is the next statement in the same block.

Splitting

The primitive operation:

split X -> A B

nondeterministically partitions `X` into two disjoint nonzero regions.

split X -> A B is basically the same as refine X -> A followed by difference X A -> B.

The result satisfies:

A & B = 0
A | B = X

with both `A` and `B` strictly below `X`.

Since both resulting regions are nonzero, either can immediately be split again.

split X -> A B
split A -> C D
split B -> E F

producing progressively finer partitions of the original region.

No sequence of splits can reach an indivisible nonzero atom, because no such atom exists.

Splitting 0 is a runtime error and halts the program. Which piece is B and which is C is unspecified.

Refinement

`refine` expresses nondeterministic restriction.

For:

refine X -> Y

the result must satisfy:

0 < Y < X

but the language does not require one unique choice of `Y`.

A computation involving repeated refinement may therefore proceed through a descending sequence:

X0 > X1 > X2 > X3 > ...

where each value is a nonzero proper subregion of the preceding value.

For example:

refine 1 -> A
refine A -> B
refine B -> C
emit C

produces some region satisfying:

0 < C < B < A < 1

The result of computation is therefore often a progressively constrained region rather than a conventional scalar value.

Equality

Equality in Atomless set computation refers to equality inside the Boolean algebra.

For:

equal A B -> R

R = 1 precisely when:

A = B

as elements of `Algebra`.

There is no distinction between structural equality and semantic equality at the core language level. Runtime values are algebra elements, so two variables referring to the same algebra element are equal regardless of how that value was computed.

For example:

meet A B -> C
meet B A -> D

guarantees:

C = D

because meet is commutative.

Similarly:

join A 0 -> B

guarantees:

A = B

Disjointness

Two regions are disjoint when their meet is `0`.

Thus:

disjoint A B -> R

causes R to be 1 precisely when:

A & B = 0

This relation is particularly important when constructing partitions.

For example, after:

split X -> A B

the language guarantees that after:

disjoint A B -> R

then R = 1.

Representing Conventional Data

Atomless set computation has no primitive integers, strings, or characters.

If a program wishes to represent conventional information, it must do so through patterns of regions and relations between those regions.

For example, a finite number may be represented indirectly by a finite partition.

Three could be encoded by three nonzero pairwise disjoint regions:

A
B
C

satisfying:

A & B = 0
A & C = 0
B & C = 0
A | B | C = X

The number is represented by the structure of the partition, not by the cardinality of the regions themselves.

Each individual region remains nonzero and can still be divided indefinitely.

Therefore, the three regions do not represent three atomic elements. They represent a partition with three cells.

Computation as Restriction

Many Atomless set computation programs can be understood as progressively restricting the computational universe.

A program may begin with:

X = 1

and then repeatedly derive smaller regions:

1 >= X0 >= X1 >= X2 >= ...

A result is then a region satisfying the constraints accumulated during execution.

This gives Atomless set computation a constraint-oriented interpretation: computation eliminates incompatible portions of the universal region until only an acceptable region remains.

The language does not necessarily identify one individual point as the final answer. In a genuinely atomless model, such points are not runtime values at all.

Procedures

Functions, hereafter referred to as "procedures", are indicated using proc.

A call is a statement: name(X, Y). Arguments are evaluated first and passed by value (regions are immutable values).

Parameters and all variables assigned inside a procedure are local to that call. There are no global variables.

Procedures may call themselves or each other. Declaration order does not matter, and calling with the wrong number of arguments is a runtime error.

A procedure has no return value. `emit X` appends X to the program's single output stream, in execution order, including from nested calls.

Bisecting a Region

The following procedure divides a nonzero region into two pieces:

proc bisect(X) {
when X {
split X -> A B

emit A
emit B
}
}

If `X != 0`, `split` guarantees:

A != 0
B != 0
A & B = 0
A | B = X

As before, both `A` and `B` remain nonzero and can therefore be subdivided further.

Testing for Overlap

The following procedure determines whether two regions overlap:

proc overlaps(A, B) {
meet A B -> C

when C {
emit C
}
}

If `A` and `B` overlap, their meet is nonzero, and the overlapping region is emitted.

If they are disjoint:

A & B = 0

so the `when` body does not execute.

Testing Whether Two Regions Differ

The symmetric difference of two regions is zero exactly when the regions are equal.

proc distinguish(A, B) {
xor A B -> D

when D {
emit D
}
otherwise {
emit 0
}
}

If:

A = B

then:

D = 0

Otherwise, `D` represents the portion in which the two regions differ.

Refining the Universal Region

The following program progressively narrows the universal region:

proc narrow() {
refine 1 -> A
refine A -> B
refine B -> C

emit C
}

The result satisfies:

0 < C < B < A < 1

No concrete point is selected. The program only produces a progressively smaller nonzero region.

Partitioning a Region into Four Parts

Repeated splitting can construct a finite partition.

proc quarter(X) {
split X -> A B
split A -> A1 A2
split B -> B1 B2

emit A1
emit A2
emit B1
emit B2
}

The four emitted regions are pairwise disjoint and satisfy:

A1 | A2 | B1 | B2 = X

Removing a Region

The following program removes `B` from `A`:

proc remove(A, B) {
difference A B -> C
emit C
}

The resulting region is:

C = A & ~B

If `B` completely contains `A`, then:

C = 0

If `A` and `B` are disjoint, then:

C = A

Infinite Fragmentation

The following program repeatedly splits every region it receives:

proc fragment(X) {
when X {
split X -> A B

emit A
emit B

fragment(A)
fragment(B)
}
}

Because every nonzero element below `B` contains a smaller nonzero element, neither `A` nor `B` can ever be an atom.

Therefore, this program has no natural nonzero base case and continues fragmenting indefinitely.

Implementations

An implementation should represent each region as a finite union of half-open intervals [a, b) with rational endpoints, 0 <= a < b <= 1, stored in canonical form (sorted, pairwise disjoint, non-adjacent).

• 0 is the empty union and 1 is [0, 1).
• meet, join, and complement are ordinary interval arithmetic.
• Every nonzero region contains a smaller one: [a, b) contains [a, (a+b)/2), so the algebra is atomless.

split halves the first interval at its midpoint, and refine returns any nonempty proper sub-union.

The endpoints must come from a dense order (the rationals, not the integers) and the intervals must be half-open and nonempty. Otherwise single-point regions would be atoms.

Up to isomorphism, this is the unique countable atomless Boolean algebra, so any countable atomless implementation is equivalent to it.