IBSA

From Esolang
Jump to navigation Jump to search

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. ); 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. Note that for object methods, its current value is not involved in what statement activates. For example, for an object

x/... {
    01? ...
    y? ...
};

When x.y(...) is called somewhere, even if the current value of y is '01', still only the y statement in x will activate and the '01' statement will not.

Now 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.

A Simple Extension

A simple extension is to allow statements to be delegated when an object is initialized using another object. This can be done by inserting pub before the statement. For example, in the code

obj0/x0 {
    x1? obj1.obj0(!): obj0.01(10);
    pub 01? obj1.obj0(x0): #!;
};

obj2/obj0;

since the second statement of obj0 has pub and obj2 is initialized using obj0, thus the second statement also applies to obj2.

This extension will make the esolang fully Prototype-based.

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);