bitch

From Esolang
Jump to: navigation, search
bitch
Paradigm(s) imperative, structured
Designed by User:Helen
Appeared in 2019
Memory system Accumulator-based
Dimensions one-dimensional
Computational class Unknown
Reference implementation bitch v4.12
Major implementations bitch v4.12 https://github.com/int-e/bitch
Influenced by BITCHWISE
File extension(s) Unspecified


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]. Many of the major implementations implement the rest of the commands as syntax errors, and the program will exit immediately. However, this was ignored in the documentation, and is therefore not portable.

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

  • > - remember the beginning of a code block
  • < - jumps to the latest remembered > (if a loop start instruction is skipped it will not be jumped to)
  • . - ends the program

So >code<, where code contains no < nor >, 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.

In addition, there is a number literal form which is also included here.

It is impossible to have non-integer input or output. (The GitHub version of the interpreter implements character I/O as a variant.)

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

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

In the above (including the section on I/O instructions), number can be either a number literal (without a #) or any valid bitch instruction.

In case that number is an instruction, the given instruction is evaluated on a copy of the accumulator and storage and the resulting accumulator value is used as the argument for the instruction. In particular this means that any effect that instruction has on the storage and accumulator will be discarded. Non-I/O effects, i.e., termination (by .) or remembering or jumping to a code block (by > or <), are discarded as well.

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.

Computational class

Attempts to prove Turing-completeness have been ongoing in this article's talk page.

It has been shown that bitch can simulate any Finite-state automaton. Furthermore, with the Cell-based tape structure memory structure, RAM machine sketch, and the bounded brainfuck interpreter implementation it is clear that that bitch can simulate any arbitrary sized Bounded-storage machine with unbounded input. This puts it in a computational class similar to languages such as Malbolge, but whereas Malbolge is bounded by its specification, bitch is only bounded in a particular implementation of any algorithm. Additionally, bitch can implement some (albiet trivial) unbounded algorithms, which conventional BSMs are unable to implement. Therefore it is slightly more computationally powerful than a conventional BSM, although still potentially less than Turing complete. If bitch does prove to be Turing complete, it will either be due to this class of simulating-arbitrary-sized BSMs being Turing equivalent, or some other feature of bitch enabling it. Exploring mechanisms to dynamically expand the bounded memory limits as needed would be the obvious path to explore to extend this class to Turing complete.

bitch is also capable of implementing Push-down automata, using the storage as the stack.

Common Algorithms

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

Addition

\]32|\>[32^]32]32&^[32^^[1&-2]32&0[32;<[32/

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                        # a is stored in the lower 32 bits of the storage
b <- input                        # b is stored in the accumulator

while (b != 0) {
    a <- a XOR b
    b <- (b AND (b XOR a)) LS 1   # (b XOR a) is the original value of a!
}

Subtraction

\]32|\>[32^]32]32&[32^^[1&-2]32&0[32;<[32/

The logic is the same as for addition, except that the carry is (b AND (a XOR b)) LS 1.

More Bitwise Operations

There are 16 different bitwise operations on two operands. We can derive the operations that map 0,0 to 0 per the following table, where a is an accumulator bit and b is the corresponding bit in the other operand B.

op a=0 0 1 1 code comment op a=0 0 1 1 code comment
b=0 1 0 1 b=0 1 0 1
0 0 0 0 0 &0, ^|&B the variant may be useful if B does I/O a AND b 0 0 0 1 &B built in
a AND (NOT b) 0 0 1 0 &^B a 0 0 1 1 , |&B the variant may be useful if B does I/O
(NOT a) AND b 0 1 0 0 ^|B b 0 1 0 1 ^^B see below
a XOR b 0 1 1 0 ^B built in a OR b 0 1 1 1 |B built in

The remaining 8 bitwise operations can be obtained by first computing the complement of the result and then executing ~. The constant 1 function and NOT a can also be computed in a single instruction, using |-1 and ~, respectively.

The ^^ Trick

The ^^ case is surprisingly useful. The effect of ^^i on the accumulator is that of i (to wit, if the old accumulator value is A, and the new accumulator value after i is B, then the resulting accumulator after ^^i is A^(A^B) = B), but the storage is not modified, because i is working on a copy of the state (accumulator and storage), and ^ does not affect the storage. Examples:

  • ^^n sets the accumulator to n without clearing the storage
  • ^^[8 shifts the accumulator to the left, copying the lower 8 bits of storage into the lower 8 bit of the accumulator in reverse order
  • ^^]8 shifts the accumulator to the right, destroying 8 bits

Swapping two values

\[32\^]32^[32^]32/

Equivalent to the C alternative x^=y^=x^=y. This is limited to 32 bits, but it can be extended. It outputs both of the values as 1 value. Here is an alternate version:

\[32\^]32^[32^]32]32/&0[32/

Popular Problem solutions in bitch

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

Possible

Truth-machine

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

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

Infinite loop

This is pretty straightforward:

><

Looping counter

This counts from 99 to 1:

#99>/]7^1[7^]7]7&[7[6^]6]6&[6[5^]5]5&[5[4^]4]4&[4[3^]3]3&[3[2^]2]2&[2[1^]1]1&[1&0[7;<

Counting to infinity is trivial but possible. Here is a clever way count. This program repeatedly copies the 1 bit inside the accumulator to the uninitialized memory:

#1>/|[1<

Binary to unary conversion

This is definitely "cheating", as it does not use replaces. The maximum input is 7 bits. Input in the decimal form. (The form of input does not matter, since the internal storage of bitch is in binary.)

\>]7^^0/^1[7^]7]7&[7[6^]6]6&[6[5^]5]5&[5[4^]4]4&[4[3^]3]3&[3[2^]2]2&[2[1^]1]1&[1&0[7;<

Fibonacci sequence

Prints out the first few Fibonacci numbers.

#0/#1/#1/#2/#3/#5/#8/#13/#21/#34/#55/#89/#144/#233/#377/#610/#987/#1597/#2584/#4181/

Possible with adjustments

The most common adjustment is to do character-based I/O, where \ returns the Unicode value of the next character (-1 on EOF) and / writes a character with the given Unicode value. A byte-oriented version is possible as well.

Cat program

We use character-based I/O.

>\/<

This is a variation that halts on EOF:

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

A simplified program that is equivalent to the program above:

>\~:.~/<

Reverse cat(reverses input per line):

\~>]32&\~;<>&0[32:.]32~[32~/<

Hello, world!

We use character-based I/O.

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

In Chinese:

#20320/#22909/#65292/#19990/#30028/

Quine

See List of Quines for a quine using character-based I/O.

ROT13

We use character-based I/O. The following is a naive ROT13 implementation that replaces A by N, B by O, and so on, testing for each case individually. This should make for an interesting golfing exercise.

>\~:.~^65:^271^3:^269^1:^275^7:^277^1:^279^3:^277^1:^275^15:^285^1:^287^3:^285^1:^275^7:^277^1:^279^3:^15^1:^13^31:^19^1:^21^3:^23^1:^21^7:^19^1:^29^3:^31^1:^29^15:^19^1:^21^3:^23^59:^271^3:^269^1:^275^7:^277^1:^279^3:^277^1:^275^15:^285^1:^287^3:^285^1:^275^7:^277^1:^279^3:^15^1:^13^31:^19^1:^21^3:^23^1:^21^7:^19^1:^29^3:^31^1:^29^15:^19^1:^21^3:^23^122]8&0[8/<

Similar, but handling lower and upper case in one go (cf. rot13.pp for some comments):

>\~:.~]8|[8|32^97:^47^3:^45^1:^51^7:^53^1:^55^3:^53^1:^51^15:^61^1:^63^3:^61^1:^51^7:^53^1:^55^3:^15^1:^13^31:^19^1:^21^3:^23^1:^21^7:^19^1:^29^3:^31^1:^29^15:^19^1:^21^3:^23^90[8&-8416^]8&255/<

99 bottles of beer

Try it Online. This cheats and does not use loops.

Mandelbrot set

See Try it Online for code which reproduces the ASCII output of a Mandlebrot set plot without calculation.

Bounded-storage machine: brainfuck interpreter

This bounded brainfuck interpreter by User:int-e uses 16 bit cells and is limited to a maximum nested loop depth of 63, and combined data area and program size of ~1900 cells.

Implementation

A nice 128-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 = new Long(scanner.findInLine("[^\\s]+")); }
                       catch(NullPointerException|NumberFormatException 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, storage, 0, 0);
        while(p.nextIteration());

        return p.currentValue;
    }
    
    private void rightShift(long n) {
        for(int x = 0; x < n; x++) {
            this.storage = (this.storage << 1) | (this.currentValue & 1);
            this.currentValue >>>= 1;
        }
    }

    private void leftShift(long n) {
        for(int x = 0; x < n; x++) {
            this.currentValue = (this.currentValue << 1) | (this.storage & 1);
            this.storage >>>= 1;
        }
    }

    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.

Another implementation (in Haskell, with bignum state) can be found at https://github.com/int-e/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.