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 as opposed to sets (the name is a misnomer). 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`, the empty or impossible region
• `1`, the universal region

and 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`.	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`	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 `B`.	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).

The operations primarily affect regions based on how far their dimensions stretch. Therefore, if A is a 10-dimensional region, the two regions B and C created by `split A -> B C` are more likely to be 10 dimensional regions than 5-dimensional regions.

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.

Splitting

The primitive operation:

split X -> A B

partitions `X` into two disjoint nonzero regions.

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.

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.

Bisecting a Region

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

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

However, they aren't necessarily equal in size, and they are definitionally not equal by any form of equality which can be tested through the language itself.

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 of `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

If I were to implement this language in Python, I would have the regions be objects which may have the following attributes:

• a dictionary dimensions with a random number of dimensions in which the region stretches, with a list of minimum and maximum dimensions within each dimension space that are represented by strings that represent base-1114112 decimals, as well as indicators of whether it includes that actual value or not within the range
  • dimensions would be a dictionary with strings as keys and lists of strings as values
• a boolean complement which indicates whether it is defined by the lack of some dimensions or by the dimensions themselves

Whatever machine can implement the commands which aren't emit is free to implement emit in the most convenient way possible, whether as a percentage or a black hole.