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 toaccumulatorANDnumber|number- OR bitwise instruction, equivalent toaccumulatorORnumber~- NOT bitwise instruction, equivalent to finding the 1's complement of a number^number- XOR bitwise instruction, equivalent toaccumulatorXORnumber[number- left shift instruction, equivalent toaccumulatorleft shift bynumber]number- right shift instruction, equivalent toaccumulatorright shift bynumber
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
abcdefgby3places, you storeefgand the accumulator is set toabcd. - When you left shift a binary number
abcdefgby3places and the storage is empty, the accumulator is set toabcdefg000and nothing is stored. - When you left shift a binary number
abcdefgby3places and the storage is set tohijk, the accumulator is set toabcdefghijand the storage is set tok. - When you use either
#numberor\, the storage is emptied. - When you use
xnumberwherexis 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 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 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:
^^nsets the accumulator to n without clearing the storage^^[8shifts the accumulator to the left, copying the lower 8 bits of storage into the lower 8 bit of the accumulator in reverse order^^]8shifts 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 = 2B 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, <x0...xn-1> expands to <x0>...<xn-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 bn.
SET(n) := |{1<<3*n+1}
CLR(n) := &{~(1<<3*n+1)}
NOT(n) := ^{1<<3*n+1}
- Store A into bn. Note that
^[{3*n+1}copies bits in the left tape part of the accumulator to unused0bits; 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 bn. This is a slight variation of
LOAD. This follows the same basic principle asSTORE, 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 bn.
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.
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 in powers of 2 minus 1.
The counter here is log2(accumulator + 1) - 1, it goes from 1 to the size of the accumulator (assuming an unsigned accumulator):
#1>/|[1<
Binary to unary conversion
This is definitely "cheating", as it does not use replaces and is only binary to unary by a technicality.
The maximum input size is 7 bits and input must be in decimal form - bitch stores numbers in binary but takes in input in decimal.
\>]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.
This doesn't show anything about the language as its output is constant.
#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 \ stores the Unicode value of the next character (-1 on EOF) and / outputs 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/<
Another version using a lookup table (cf. rot13-lut.pp):
>\]8;.|[11|256^9495516882517365034402269903000168120394070347137372457794342656^^]&2040&31^[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 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.
See also
- Talk:bitch (Although it is a mess, it still provides useful information.)