bitch

**bitch**
Paradigm(s)	imperative, structured
Designed by	User:Helen
Appeared in	2019
Memory system	accumulator-based
Dimensions	one-dimensional
Computational class	Turing complete
Reference implementation	bitch v4.12
Major implementations	bitch v4.12 https://github.com/int-e/bits
Influenced by	BITCHWISE
File extension(s)	Unspecified

bitch (alternatively bit**) is a minimalistic language created by User:Helen inspired by User: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].

Etymology

BITCHWISE's name is a portmanteau between "bitch" and "bitwise". It originates from the word "bitwise", as to mean "bitwise operations" - the only mathematical operations available in both languages.
The usage of the expletive "bitch" in "BITCHWISE" is to convey anger in a brusque and uncouth manner.
These combine to help convey the combination of difficulty and esoteric design in the language.

bitch's name, in turn, originates from a shortening of BITCHWISE, its influencer.
However, the "bitwise" is deleted from the name, implying that bitch doesn't contain any interesting esotericism but rather only agonising language design.
This is quite reflective of the language, which keeps the same core concepts of BITCHWISE whilst significantly pushing the limits of what is necessary.

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

> - marks the beginning of a loop block
< - jumps to the latest marked > (this causes undefined behaviour if there is no beginning >)
. - 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^[4] instructions, since bitch is a relatively restricted language.
In addition, there is a number literal form which is also included here.

\ - 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

Certain implementations will implement other I/O^[4] operations, such as character I/O.
For example, Helen's GitHub interpreter implements a flag to turn on character I/O.

However, only integer I/O is specified as part of the language.
Any other I/O is implementation specific and will need to be researched for that specific implementation.

Bitwise Instructions

There are 6 bitwise instructions, less than the normal set of bitwise instructions.

This is because 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^[4] 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 of 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 hijk, the accumulator is set to abcdefghij and the storage is set to k.
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

bitch is Turing-complete (see A Turing machine ).

In particular, bitch can simulate any finite-state automaton.
The storage can easily be used as a stack (using ] for push and [ for pop), so bitch is also capable of implementing push-down automata.
For practical programming, using the bounded random-access memory is more convenient than the Turing machine construction.

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.

For operands of known size, it is possible to avoid the use of > and < by unrolling the inner loop, which allows some simplifications. For example, 8-bit subtraction can be implemented by

 SUB(8) =
   ]8|[7
   [8^]15]8&[15
   [7^]14]7&[14
   [6^]13]6&[13
   [5^]12]5&[12
   [4^]11]4&[11
   [3^]10]3&[10
   [2^]9 ]2&[9
   [1^]8 ]1
   &0[8

More Bitwise Operations

There are 16 different bitwise operations on two operands.
We can derive the 8 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
op	b=0	1	0	1	code	comment	op	b=0	1	0	1	code	comment
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 but without modifying the storage.
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.
However, it does not modify the storage, as i is working on a copy of the current state and ^ doesn't affect the storage directly either.

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/

Bounded storage

bitch can implement bounded storage in the form of random-access memory with fixed address and word size.

To this end, the storage is filled alternatingly with data words and the corresponding address.
Adresses are given in bits, and must be aligned to two times the word size.

We will call the word size B, and assume it's a power of 2.
Furthermore, we define M = 2^B and m = M-1.

There are two key operations, PEEK and POKE.

The operation PEEK takes an address in the accumulator and replaces it by the value at that address:

 # comment format:      # accumulator | reverse storage
 PEEK =                 #           A | ... A W ...
   ^^[^B                #   A ... A W | ... A W ...
   ]B&0[B               #           W | ... A W ...

The operation POKE takes two words in the accumulator, with the address in the lower word, and the value to be written in the upper word:

 # comment format:      # accumulator | reverse storage
 POKE =                 #         X A | ... A W (A+2B) ...
   [&m                  #         X A ... A | W (A+2B) ...
   [B                   #         X A ... A W | (A+2B) ...
   &-M                  #         X A ... A 0 | (A+2B) ...
   ^^[B                 #  X A ... A 0 (A+2B) | (A+2B) ...
   ^]&m                 #  X A ... A X   ??   | (A+2B) ...
   ^^]B                 #         X A ... A X | (A+2B) ...
   ]B                   #         X A ... A | X (A+2B) ...
   ]&m                  #         X A | ... A X (A+2B) ...

Note that POKE relies on the stored (A+2B) value in order to find the original accumulator.

Memory can be initialized as follows,

  INIT = >DEC&-(2B)](2B)|[(2B);<[(2B)

where DEC is a loop-free B-bit decrement operation.

A Turing machine

Any Turing machine is characterized by a transition function that takes a state and a tape value, and produces a new tape value, a new state, and whether to move the read head left, right, or not at all before the next step.
If we encode states as binary strings, the transition function can be computed by a Boolean circuit^[7].

Data layout

We store the left part of the tape and the current state in the accumulator, and the right part of the tape in the storage.

In order to implement the Boolean circuit, we use only every third bit of the accumulator/store data, encoding the bit b as 0 b 0.
Let us write <b> for the encoding of a bit, that is, 0 b 0.
For lists of bits, <x₀...x_n-1> expands to <x₀>...<x_n-1>.

In addition to storing bits as triplets, we use the lowest bit of the accumulator as a one-bit accumulator A.

Circuit building blocks

In order to implement arbitrary Boolean circuits, we define the following basic operations.

Set, clear, or negate A.

 STA      := |1
 CLA      := &-2
 NOTA     := ^1

Set, clear, or negate b_n.

 SET(n)   := |{1<<3*n+1}
 CLR(n)   := &{~(1<<3*n+1)}
 NOT(n)   := ^{1<<3*n+1}

Store A into b_n. Note that ^[{3*n+1} copies bits in the left tape part of the accumulator to unused 0 bits; these copies are cleaned up again by &]{3*n+1}.

 STORE(n) := SET(n) ^[{3*n+1} NOT(n) &]{3*n+1}

Or A with b_n. This is a slight variation of LOAD. This follows the same basic principle as STORE, but we need to add some scratch space first because otherwise the cleanup &[{3*n+1} would destroy 3n precious bits.

 OR(n)    := ^^[{3*n+1} |]{3*n+1} |1 &[{3*n+1} ^^]{3*n+1}

Load A from b_n.

 LOAD(n)  := CLA OR(n)

These operations are sufficient for encoding arbitrary Boolean circuits (we have negation, binary or, and arbitrary fan-out).

Implementing the Turing machine

Using the basic building blocks from the previous section, we can program a circuit that takes as input a Turing machine configuration encoded in the form

 ... <k> <l> <ss> <0> <0> <0> <0> <r> | <q> ...

where ...:k:l is the left part of the tape, r:q:... is the right part of the tape, and ss is the current state as a string of bits, possibly padded to make room for scratch bits. The circuit produces as output

 ... <k> <l'> <ss'> <0> <0> <0> <0> <r> | <q> ...     # if standing still
 ... <k> <l'> <r> <ss'> <1> <0> <0> <0> | <q> ...     # if moving left
 ... <k> <ss'> <0> <0> <0> <1> <l'> <r> | <q> ...     # if moving right

where ss' and l' are the new state and tape symbol, respectively.

The actual move of the tape head can then be performed by:

 ADJUST   := ]9 LOAD(0) [&3 [3 LOAD(0) ]&3 [6 &{~((3<<3)|(3<<12))}

The whole Turing machine can then be implemented as a loop of the following shape, where s is the initial state, circuit implements the transition function circuit, and the tape starts out empty:

 MAIN     := #s [15 > circuit ADJUST <

Finishing touches

Termination:

One can implement a halting state that stops the machine when the tape contents to the left is empty:

 ]15 ^h :. ^h [15

where h is the integer encoding the halting state.

Alternatively, one can replace the main program as follows (this variant allows later code to be executed):

 MAIN     := #(s XOR h) > ^h [15 circuit ADJUST ]15 ^h ;<

All-at-once input and output:

We can easily prepend a loop that reads all input and stores it to the right (in reverse order), and append a loop that outputs the remaining data on the tape after the Turing machine halts.

Interactive input and output:

Because \ and / operate on the whole accumulator, and the accumulator contains the tape contents to the left of the head, interactive I/O will only work when the tape to the left is empty.
Even then it is tricky, but a proof of concept is implemented in the bounded storage Brainfuck interpreter.

Implementation

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

TODO

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.

Alternate implementations are available at Try It Online or in the GitHub for bitch.

More implementations (in Haskell and in C++, both with bignum state) can be found at https://github.com/int-e/bits.

References

↑ No available webpage for BITCHWISE as of 05/01/2019.
↑ Link to Wikipedia's article on instructions and instruction set architecture.
↑ ^3.0 ^3.1 Link to Wikipedia's article on no-ops.
↑ ^4.0 ^4.1 ^4.2 ^4.3 Link to Wikipedia's article on I/O.
↑ Link to Wikipedia's article on bitwise instructions.
↑ Link to Wikipedia's article on conditional instructions.
↑ Link to Wikipedia's article on Boolean circuits.