bitch

From Esolang
Jump to: navigation, search
bitch
Paradigm(s) imperative, structured
Designed by User:Helen
Appeared in 2019
Computational class Turing complete
Reference implementation See Java implementation
Major implementations The Java implementation below
Influenced by BITCHWISE
File extension(s) Unknown


bitch (non-capitalised) is a minimalistic language created by User:Helen inspired by Arphimigon's BITCHWISE[1].
It has a total of 15 instructions[2] (one of which is no-op[3]) and a (technically) infinite number of instruction characters, as all unrecognised characters are no-ops[3].

Storage

bitch has a single place to store values, the accumulator.
The value of the accumulator is accessible by every function, but certain functions don't use them.
Some instructions in bitch allow a constant integer to be input as a second (or sometimes only) parameter.

Instruction Set

There are 3 types of instructions, which I will call flow, I/O[4] and bitwise instructions[5].

Flow Instructions


There are 5 flow instructions, 2 of which are conditional instructions[6].
Basic flow instructions do not use the accumulator value, however, the conditional flow instructions do.

Basic Flow Instructions

> - marks the beginning of a code block
< - jumps to the nearest >
. - ends the program

>code< is a loop that will run the code code indefinitely.

Conditional Flow Instructions

: - only executes the next instruction if the value in the accumulator is equal to 0
; - only executes the next instruction if the value in the accumulator is NOT equal to 0

This makes clever usage of conditionals essential for short code, as a conditional block is completely impossible.
Each instruction would have to be preceded by a conditional symbol, doubling the length of the conditional code.

I/O Instructions


There are only two actual I/O instructions, since bitch is a relatively restricted language.
However, there is a number literal form which is also included here.
It is impossible to have non-integer input or output.

\ - stores one integer of input in the accumulator
/ - outputs the accumulator value
#number - stores the specified constant in the accumulator

Bitwise Instructions


There are 6 bitwise instructions, less than the normal set of bitwise instructions.
This is because most other instructions can be formed from a combination of these.

&number - AND bitwise instruction, equivalent to accumulator AND number
|number - OR bitwise instruction, equivalent to accumulator OR number
~ - NOT bitwise instruction, equivalent to finding the 1's complement of a number
^number - XOR bitwise instruction, equivalent to accumulator XOR number
[number - left shift instruction, equivalent to accumulator left shift by number
]number - right shift instruction, equivalent to accumulator right shift by number

number in this case, can be either a number literal (without a #) or any 1 valid bitch instruction.
In the case that number is an instruction, the given instruction is evaluated on the accumulator and the value is used as the argument for the instruction.

When bitshifting, there is no such thing as sign extension or no sign extension since integers in bitch are supposed to be (hypothetically) infinite precision.
Therefore, there are no empty spaces to fill since there are an infinite number of digits leftwards and there is always a digit that can replace another.

Shift Storage

When bit-shifting, a bit storage is used.

Right shifting (]) moves bits from the end of the binary number into the top of the storage.
Left shifting ([) moves bits from the top of the storage into the end of the binary number.

Number literals and input reset this storage.
However, when used as an argument to bitwise operators, they do not.

This simply means that:

  • When you right shift a binary number abcdefg by 3 places, you store efg and the accumulator is set to abcd.
  • When you left shift a binary number abcdefg by 3 places and the storage is empty, the accumulator is set to abcdefg000 and nothing is stored.
  • When you left shift a binary number abcdefg by 3 places and the storage is set to hij, the accumulator is set to abcdefghij and the storage is emptied.
  • When you use either #number or \, the storage is emptied.
  • When you use xnumber where x is a bitwise operator (but not a bitshift), the storage remains unchanged.

Turing-completeness

bitch is most likely not Turing-complete[7].
However, this has not been proven and therefore it is possible that it could be. (23:14, 5 January 2019 revision)

Attempt by User:A (Basic compilation)

This programming language looks like Konrad Zuse's Z3, which was already proven to be Turing-complete by Raúl Rojas here.

First of all, Z3 is capable of executing an infinite loop. This is achieved in bitch as the > < block.

Also, Z3 has math operation evaluation capabilities.

Z3 can implement 5 operations. (Addition, subtraction, multiplication, division, and square-rooting) Even though some arithmetic operations can not be implemented, only the operations zeroing a value and incrementing a value will be necessary for Turing-completeness, as mentioned here. Raúl Rojas shows that an instruction set with load, store, increment, zero and unconditional branching is Turing-complete. (By the way, Load and Store has to be indirect. They should be nested for at least 2 indexes.)

Also, infinite memory (a requirement for Turing-completeness) can be implemented in the Z3.

I am developing a way to index infinite memory using an accumulator. I had problems implementing them, though.

Finally, Z3 has a way to stop the program by using an invalid operation. That is . in bitch.

Continuation on the above by User:Helen (Implementing arithematic operations)

The conditional snippet below is easy to replicate in bitch:

if (z = i) then 0 else 1

We simply use XOR to check if a number is equal to some constant like this:

#z^i;#1

If they are equal, the result of XORing them is automatically 0.
If they are not, the result is some non-zero number which we can detect and then set the accumulator to 1.

Mathematical operations are a bit harder to pull off.
I have managed to get an algorithm for addition.
Subtraction can be imitated through addition with negatives (due to algorithm overflowing and actually giving the correct number). It can't.
User:A: can a-b be implemented by adding a by the complement of b(bitwise NOT plus 1, ignoring overflow)?
I haven't managed to get an algorithm for multiplication or division yet.


Addition:
Binary addition is very simple.

Ignoring carry overs, each digit behaves like this:

a b a+b
0 0 0
0 1 1
1 0 1
1 1 0

This is equivalent to XOR.

In order to get full addition behaviour though (rather than just "fairly close but not really" addition behaviour), we have to consider carry overs.
This is how carry overs behave:

a b a+b's carry
0 0 0
0 1 0
1 0 0
1 1 1

This is equivalent to AND.
The carry overs are put onto the next digit though.
Therefore, we left shift each carry once.

This gives us our full (recursive) algorithm.
In pseudocode:

a <- input
b <- input

oldA <- a+1
while (a != oldA) {
    withoutCarries <- a XOR b
    carries <- (a AND b) LS 1

    oldA <- a
    a <- withoutCarries
    b <- carries
}

This is perfectly doable in v4.7* bitch (takes 2 inputs):

\[16|\]32>|[32&4294967295#|0^[16|-281474976710656&]32]15&131070|[31&281470681743360|]16&4294901760|[16#|0&4294967295|[32&281474976710655]32;<|[16/

Continuation on the above by User:A (Implementing a tape)

Maybe this way can be used to store an array of bitwise values in the accumulator. (This might be what you used in your addition program.)

When something is added to the accumulator, shift-store the value for the accumulator. To index, shift a specific value. Though, this does not ensure that the cells are unbounded. (That might be a problem for cells to be bitwise.) Also, the other bits might be deleted.

This tries to present the use of shift storage:

#1/[1|3/]1/

|3 is the increment operation, for simplicity of the program.

It saves 1 inside the accumulator. Then it left shifts for storing another bit. After that, it deletes the leftmost bit to set the accumulator as the rightmost bit's value. (If you don't mind, I am using the interpreter at Try It Online.)


bitch can simulate an (inaccurate) tape by right-shifting and left-shifting, which corresponds setting the current index as the previous and next index. (Though, the tape indexes both the value and every value before the value altogether.)

This program simulates a tape:

#1/[1|3/]1/[1/

The procedure:

  • Set the accumulator as 1. (This results in 1(in binary)).
  • Left shifts the value. (Results in 10)
  • ORs the value by 3. i.e. increment the value. (Results in 11)
  • Right shifts the accumulator by 1. (This prints out the decimal "1")
  • Left shifts the accumulator by 1, just to ensure that bitch actually can simulate a tape. (This prints out the decimal "3").

An additional example for a tape:

#1/[1|3/[1|7/]1/]1/[1/[1/

To remove the other bits from the result of an index: A procedure "tail" would be nested in the original cell index.

Tail procedure

This procedure returns the rightmost element of a list of cells.

This is a weird way, since there will be more code than what will be expected.

#5/^4/

First, it loads 5(binary 101) into the memory. Then, it XORs it by 4(Binary 100) to clear the backmost cell. So, only the lowest digit (1 in binary) is kept.

Standard output:

5
1

Bit comparison

As long as a bit can be indexed, the comparison code snippet can be used.

Bit modifying

That would also be quite easy.

Compare the bits and do a corresponding operation that can set another bit into another value, for example ^4.

Common Algorithms

This section is simply for the purpose of documenting useful algorithms in bitch.

Addition

\[16|\]32>|[32&4294967295#|0^[16|-281474976710656&]32]15&131070|[31&281470681743360|]16&4294901760|[16#|0&4294967295|[32&281474976710655]32;<|[16/

The logic behind this is fairly simple:
Given a and b, the carry overs are a AND b, which would become a AND b LS 1 when carried over.
The bits that stay in place are a XOR b.
a becomes a XOR b and b becomes a AND b LS 1.
Given that the new value of b is non-zero, we repeat this.
The value of a after the end of repetitions is the correct value of the sum.
Or in pseudocode:

a <- input
b <- input

oldA <- a+1
while (a != oldA) {
    withoutCarries <- a XOR b
    carries <- (a AND b) LS 1

    oldA <- a
    a <- withoutCarries
    b <- carries
}

Popular Problem solutions in bitch

These are solutions (written in bitch) to problems on the Popular Problems page.

Possible

Cat program (limited to integers)

>\/<

This is a variation that halts when nothing is inputted(the program above prints -1 indefinitely using the online implementation):

>\^-1:.^-1/<

Truth-machine

Will print nothing if input doesn't equal 0 or 1 (behaviour here not defined by the article).

\:/:.&-2;.#1>/<

Possible with adjustments

Hello, world!

This becomes trivial as long as we allow output to be integer values representing the actual output string.

#72/#101/#108/#108/#111/#44/#32/#119/#111/#114/#108/#100/#33/

Impossible

There are a lot of trivially impossible programs, as a lot of them involve printing characters or taking in characters as input.
These include: Hello, world!, 99 bottles of beer, Quine (unfortunately), Mandelbrot set, ROT13 encoder/decoder, FizzBuzz.
However, all of these, except for ROT13 encoder/decoder, can (probably) be made possible if we allow for usage of ASCII character values, and convert output into text manually.

ROT13 encoder/decoder is probably doable considering it can be done character by character.
By taking in one character of input, then applying ROT13 then outputting and zeroing everything repeatedly, we can apply ROT13 to a whole string.

It is impossible to do a true Bootstrap since bitch has specific characters for each operation and therefore text would have to be involved, which is impossible in bitch.
With adjustments it's probably possible to interpret a proto-bitch, with certain limitations:

  • Integer literals are simply represented by their ASCII character (e.g.: 171 is ½)
  • Only constant arguments to instructions are allowed.

A simple language with such limitations could definitely be interpreted in v4.10 bitch.

A pi calculator might be impossible due to its involvement with decimals.
However it might be possible to emulate decimals by multiplying by 10 every time a digit is calculated, allowing us to deal with integers rather than reals.
This would involve outputting each digit at a time, which would definitely work.

Unproven

Possible? Fibonacci sequence, Factorials, Prime numbers, Disan Count, Digital root calculator, Pi calculator.
Possible with adjustments? 99 bottles of beer, Quine, Mandelbrot set, ROT13 encoder/decoder, FizzBuzz, Bootstrap.
Impossible?

Implementation

A nice 124-line implementation of the latest spec of bitch is possible in Java:

import java.util.NoSuchElementException;
import java.util.Scanner;

public class bitch {
    public static void main(String[] args) {
        @SuppressWarnings("resource") Scanner s = new Scanner(System.in);

        while(true) {
            new Program(s.nextLine().toCharArray()).conclude();
            System.out.println("----------------------------");
        }
    }
}

class Program {
    public char[] program;
    public int opCounter;

    public long currentValue;
    public long storage;
    
    public int startPoint;

    public Program(char[] program) { this(program, 0, 0, 0, 0); }
    public Program(char[] program, long currentValue, long storage, int opCounter, int startPoint) {
        this.program = new char[program.length];
        for(int x = 0; x < this.program.length; x++) { this.program[x] = program[x]; }

        this.currentValue = currentValue;
        this.storage = storage;

        this.opCounter = opCounter;
        this.startPoint = startPoint;
    }

    public static final char[] fsChars = { '\\', '/', '>', '<', '.', ':', ';', '~' };
    public static final char[] conjChars = { '#', '|', '^', '&', ']', '[' };
    public static final char[] numberChars = { '-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    public final Scanner scanner = new Scanner(System.in);
    public void conclude() { while(this.nextIteration()); }
    public boolean nextIteration() {
        char[] op = new char[] { '.' };
        
        {
            String nextOp = "";
            boolean nFlag = false;
            for(int x = opCounter; x < this.program.length; x++) {
                if(!nFlag && contains(conjChars, program[x])) { nextOp += program[x]; }
                else if(!nFlag && contains(fsChars, program[x])) { nextOp += program[x]; break; }
                else if(contains(numberChars, program[x])) { nFlag = true; nextOp += program[x]; }
                else { break; }
            }

            op = nextOp.toCharArray();
        }
        if(op.length == 0) return false;

        switch(op[0]) {
            case '\\': try { this.currentValue = scanner.nextLong(); }
                       catch(NoSuchElementException e) { this.currentValue = -1; } this.storage = 0; break;
            case '/': System.out.println(this.currentValue); break;
            case '#': this.currentValue = evaluate(substring(op, 1), this.currentValue, this.storage); this.storage = 0; break;
            
            case '>': this.startPoint = this.opCounter; break;
            case '<': this.opCounter = this.startPoint; return true;
            case '.': return false;

            case ':': if(this.currentValue == 0) opCounter -= op.length - 1; break;
            case ';': if(this.currentValue != 0) opCounter -= op.length - 1; break;
            
            case '|': this.currentValue |= evaluate(substring(op, 1), this.currentValue, this.storage); break;
            case '^': this.currentValue ^= evaluate(substring(op, 1), this.currentValue, this.storage); break;
            case '&': this.currentValue &= evaluate(substring(op, 1), this.currentValue, this.storage); break;
            case '~': this.currentValue = ~this.currentValue; break;
            case ']': this.rightShift(evaluate(substring(op, 1), this.currentValue, this.storage)); break;
            case '[': this.leftShift(evaluate(substring(op, 1), this.currentValue, this.storage)); break;
        }

        this.opCounter += op.length;

        return true;
    }

    public static long evaluate(char[] program) { return evaluate(program, 0, 0); }
    public static long evaluate(char[] program, long startValue, long storage) {
        if(contains(numberChars, program[0])) return new Long(new String(program));

        Program p = new Program(program, startValue, 0, 0, 0);
        while(p.nextIteration());

        return p.currentValue;
    }
    
    private void rightShift(long n) {
        this.storage = (this.storage<<n) | (this.currentValue & ((2<<n)-1));
        this.currentValue >>>= n;
    }

    private void leftShift(long n) {
        this.currentValue = (this.currentValue<<n) | (this.storage & ((2<<n)-1));
        this.storage >>>= n;
    }

    private static boolean contains(char[] charset, char... chars) {
        boolean contains = true;
        
        outer:
        for(char c : chars) {
            for(char d : charset) { if(c == d) continue outer; }
            contains = false;
        }
        
        return contains;
    }

    private static char[] substring(char[] array, int start) { return substring(array, start, array.length); }
    private static char[] substring(char[] array, int start, int end) {
        char[] output = new char[end-start];

        for(int x = start; x < end; x++) output[x-start] = array[x];

        return output;
    }
}

A .jar might be available here.
If so, you can use it like this:

java -jar bitch.jar

This implementation has an infinite loop of getting the next line (on which a bitch program would be written) and then running the bitch program.
All bitch instructions are compatible with this implementation.

An alternate implementation is available at Try It Online or in the GitHub for bitch.

References

  1. No available webpage for BITCHWISE as of 05/01/2019.
  2. Link to Wikipedia's article on instructions and instruction set architecture.
  3. 3.0 3.1 Link to Wikipedia's article on no-ops.
  4. Link to Wikipedia's article on I/O.
  5. Link to Wikipedia's article on bitwise instructions.
  6. Link to Wikipedia's article on conditional instructions.
  7. Link to Esolang's article and Wikipedia's article on Turing-completeness.