IBSA

IBSA (short for Interacting Binary Substitution Automata) is an esolang made by User:Simple9371. Its main idea is the method call syntax <object>.<method>(<inputs>) in Object-oriented languages.

Documentation

IBSA has no stdin and stdout. An IBSA code has three parts: 1) objects initialization, 2) flow definition, and 3) first execution. Whitespaces (line breaks, spaces, tabs, etc.) and comments are like in C-style languages.

Objects initialization

Objects are always finite binary strings (i.e. $\in \{0,1\}^{*}$); the empty string is written as !. Objects are assigned via either:

• <objectName>/<binaryString>; (explicit assignment of binary string), or
• <objectName>/<anotherObjectName>; (which copies the value of the previously defined object).

Overall, here is what objects initialization would look like:

x0/100;
x1/x0;   // also becomes 100
x2/1010101;
// the objects below will be mutable
obj0/x0;   // also becomes 100 initially
obj1/00011101;

Allowed names for objects are similar to many conventional languages: name must satisfy the regex ^[a-zA-Z_][a-zA-Z_0-9]*.

Flow definition

Flow definitions are written "next to" initialized objects to make them mutable.

We will write <objOrBin> in place of either an object or a raw binary string.

From the introduction above, the main idea for this language is the "call". Here is its syntax:

<call> ::= <objName>.<objOrBin0>(<objOrBin1>)|#!|#

The first expression means that the object <objName> with the "method" <objOrBin0> is called with the input <objOrBin1>, in which the roles will be explained in a short while. On the other hand, #! means halting the program with indication of "success", and # means halting the program with indication of "error".

Now the flow of the whole program is defined through "statements". Here is its syntax:

<statement> ::= <objOrBin>? <call0>: <call1>;

Statements are put "next to" an initialized object like this:

<objInit> {
    <statement0>
    <statement1>
    ...
};

A statement will "activate" if the initialized object (i.e. the <objectName> in <objInit>) with method <objOrBin> is called from a call. Upon activation, a check is performed if the <objOrBin1> of the call that triggered the activation is a prefix of the current value of initialized object. If true, then the prefix <objOrBin1> in the current value of initialized object is completely replaced by the current value of <objOrBin>, and then call <call0>. Else, no bit string replacement will occur, and then call <call1> instead. Here are some examples of prefix checking:

• It is true that <objOrBin1>='001' is a prefix of the initialized object with current value of '001011'.
• It is true that <objOrBin1>='001011' is a prefix of the initialized object with current value of '001011'.
• It is true that <objOrBin1>=! is a prefix of any bit string (including itself). In this case, string replacement becomes prefix insertion.
• It is false that <objOrBin1>='1' is a prefix of the initialized object with current value of '001011'.

Overall, here is what flow definition would look like by modifying parts of the above objects initialization code:

// the objects below will be mutable
obj0/x0 {   // also becomes 100 initially
    x1? obj1.obj0(!): obj0.01(10);
    01? obj1.obj0(x0): #;
};
obj1/00011101 {
    obj0? #: obj0.x1(obj1);
};

First execution

This last part is simply a <call>; to start the flow of the program. Here is what first execution would look like.

obj0.01(x2);

A complete code

Here is what a complete code looks like. Note that objects initialization and flow definition must be written before the first execution.

x0/100;
x1/x0;   // also becomes 100
x2/1010101;
// the objects below will be mutable
obj0/x0 {   // also becomes 100 initially
    x1? obj1.obj0(!): obj0.01(10);
    01? obj1.obj0(x0): #!;
};
obj1/00011101 {
    obj0? #!: obj0.x1(obj1);
};
// run now!
obj0.01(x2);

The overall "output" of an IBSA program is the final values of objects after the halt.

Computational class

IBSA is Turing-complete. Every Cyclic tag system can be converted to an IBSA program, as demonstrated by the IBSA program below.

/*
An IBSA program implementing the example in the Cyclic tag system article (as of 11/04/2023):
Productions: (011, 10, 101), Initial data-string: 1.
*/
prod0/011;
prod1/10;
prod2/101;

data_str/1 {
   !? check_init_bit.0(1): check_init_bit.1(0);
   new_str? curr_prod_idx.01(00): #;
}

// this is used to check initial bit of data_str
// NOTE: halt is a success iff data_str == !.
check_init_bit/0 {
    1? data_str.!(check_init_bit): #!;
    0? new_str.data_str(!): curr_prod_idx.01(00);
}

// this replaces the data_str
new_str/prod0 {
    data_str? data_str.new_str(data_str): #;
    prod0? data_str.!(1): #;
    prod1? data_str.!(1): #;
    prod2? data_str.!(1): #;
}

// this tracks the current production
// NOTE: the length of values of curr_prod_idx SHOULD be equal to the number of bits of
// binary representation of (number of productions - 1). this is so that prefix checking
// becomes equality checking (e.g. curr_prod_idx == 01?).
// in our case, number of productions = 3. since 3 - 1 = 2 is 10 (base 2) and '10' has 2 bits,
// thus the values of curr_prod_idx should be 2 bit (e.g. 00, 01, ...).
curr_prod_idx/00 {
    00? new_str.prod0(new_str): #;
    01? new_str.prod1(new_str): curr_prod_idx.10(01);
    10? new_str.prod2(new_str): curr_prod_idx.00(10);
}

data_str.!(check_init_bit);