Bubbles

From Esolang
Jump to navigation Jump to search

Bubbles (not to be confused with Bubble) has only one datatype: the unordered collection, which is called a bubble. However, it does not have a choice function, i.e. it is impossible to operate on a specific bubble that is inside another, only operate on all of them. There is no way to perform an operation on 'a random bubble inside that bubble' or 'the first bubble that's inside that bubble' because bubbles are opaque - indistinguishable from the outside.

Design

An executing program consists of an instruction pointer and some memory, the latter being a nested hierarchy of bubbles, one or more of which is selected as the 'current bubble'. Most commands operate only on whatever bubbles are inside the current bubble. Conditionals depend entirely on how many bubbles are contained within it, for example. In order to send data up the hierarchy, you must pop the current bubble, which expels it's internal bubbles up to the level above. It isn't possible to choose some arbitrary bubble that's inside the current bubble. You have to choose all of them at once - that's why you can have multiple current bubbles. For example, if you want to pop a bubble which you know contains four bubbles, you must iterate through all the bubbles in the current bubble, popping them if they contain four bubbles.

Commands

The format of conditions is yet to be settled. For now, you can imagine them as " 0 <= n < 30 or n == 42 " or similar. Conditionals depend only on the cardinality (i.e. number of bubbles inside) of the current bubble (using a shallow check rather than recursive).

[...]

while the amount of bubbles ...

The notation begins with a condition, then runs the contained commands until the condition evaluates falsey.

(...)

if the amount of bubbles ...

Like [], but the code is only run once, even if the condition continues to be truthy.

{...}

for each bubble ...

Sets the current bubble to each bubble inside the current current bubble, if that makes sense (one by one or concurrently depending on the implementation) then runs the code inside the squiggly brackets. After the end of the brackets is reached, the current bubble is reset to refer to what it was before.

@

envelop all bubbles

Replace the current bubble with a bubble that contains the current bubble. In other words, blow a bubble so big that all the other bubbles in the current bubble go inside it. A mnemonic is the way an @ symbol resembles a bubble put inside a bubble.

v

pop a bubble

Delete the current bubble, transferring all the orphaned bubbles that were previously inside it to whatever bubble contained the current bubble. This symbol was chosen because the letter looks pointy.

o

blow a bubble

Put an extra empty bubble into the current one, alongside whichever bubbles are already there. The round shape of the letter o calls to mind the bubble it creates.

Simulation of Minsky Machine

Bubbles can be proven Turing complete by simulating a two-counter Minsky machine. Here is an semiformal description. One can represent a non-negative integer using set theoretic ordinals, i.e. 0 is an empty bubble, and for any n, n+1 is the result of wrapping a bubble around n. So, 6 is represented by seven layers of nested bubbles. (Von Neumann ordinals are also suitable, with slightly different incrementation and decrementation procedures.)

A program can increment a number represented like that, simply by using the @ to envelop the number with another bubble. The other necessary command for a Minsky machine is "decrement or branch if 0". Checking if a number is zero can be accomplished using an [...] if block, with the condition representing x = 0 where x is the cardinality of the current bubble. Decrementation is simply mapping a pop to the number using a for loop, {v}.

From there, what remains is the capability to differentiate between different stored numbers using the aforementioned commands. Let a and b each be a bubble containing a number. The top level of the data structure, a bubble, will contain two bubbles, which are of course identical from the outside. In the first of these, a can be placed alongside one other bubble. In the second, b with two other bubbles. One can find a using a for loop in the outermost bubble, comprising an if statement that only runs the code if the bubble contains two bubbles (a and the one other bubble). To select b, the if statement should run if it finds three bubbles (b and the two bubbles placed with it). Hence you can decide what to apply to a and what to apply to b. If one feels especially daring, one can even use the same code on both simultaneously, although that shouldn't be necessary for this Minsky machine. (In practice, one can use other numbers than just one and two, taking care that those specifier cardinalities do not become ambiguous if a signal is added to the bubble.)

Left as an exercise for reader (or editor): proof that one can create the necessary state transitions using the control flow tools available, noting that a signal can be passed from a bubble to its container by first enveloping, then blowing some amount of bubbles, then popping the current bubble, and noting that the signal can subsequently be read by the conditional expressions.

Applications

While the data encapsulation present in Bubbles lends itself to concurrency and multi-core processing, there are currently no I/O capacities, and it is also a Turing tarpit.