Bitxtreme Programming Language


Introduction

Bitxtreme is a language which has be inspired by the BIT programming language and the One Instruction Set Computing (OISC) concept.

Just as in BIT, the basic data type is the bit. However, unlike BIT, there's no such thing as an address-of-a-bit concept.

Just as in OISC, there is one single instruction: subtract and branch if negative. As with OISC, every instruction has two operands, and the instruction itself has no representation in the virtual machine's memory space.

This specification attempts to be as complete as possible, trying to avoid any ambiguity or indefinition. There have been previous cases where this has been a problem; for example the HQ9+ language specification does not specify the initial value for the accumulator, so implementors are left at their own (they usually initialize it to the value zero but some interpreters can use a different value, so usage of the instruction + by HQ9+ coders in their programs is discouraged for portability reasons).

Virtual machine description

Bitxtreme takes the concept of "everything is a bit" to the extreme. It is designed to be run under a virtual machine. This machine has just two registers, the current Program Counter (PC) which is itself a bit, and the Accumulator (A) which is also a bit.

At start, the virtual machine starts with PC=0 and A=0. Operands are read in pairs starting from the memory address pointed to by the current PC; then PC is increased by two, modulo 2. The first bit of each pair is a pointer to the memory position which holds the value to subtract from the accumulator. The result is stored in that same memory position pointed to by the operand. If the result is negative (the bits are in two's complement representation) then the second bit of the pair will be added to the current PC, modulo 2.

Input/Output

Memory positions 0 and 1 are special. When an instruction affects position 0, the value written is output to a buffer as well as being written into memory. When 8 bits are output, the resulting byte (LSB first) is written to standard output. During read operations the initial value is assumed to be 0 unless overwritten by program code.

Memory position 1 is used for input operations. When read, the value read is a bit coming from standard input (serialized, LSB first). The value written is discarded. EOF is signaled by an ASCII EOT char (ASCII code 4).

Note that there are a few cases in which PC can be at memory position 1. The read of memory position 1 for interpretation of the instruction does not count as an input. In an actual chip this can be accomplished by means of a FETCH pin which is active when the instruction is fetched. (Note for hardware implementors: I'm in the process of patenting this revolutionary VM design so don't use it or we'll meet in court!)

Language description

The program source uses the ISO-8859-15 encoding. The binary representation of each character's code (LSB first) is directly loaded into the VM's memory. Unused bit positions within a byte must be zero-padded. No comments are allowed. To avoid confusion with other kinds of files the standard source file extension is .txt (for Bitxtreme), which is rarely used.

Tips and tricks

You can force a jump's destination address to be in the middle of two operands. This is a dirty trick but for some programs it may be convenient to do so.

Sample programs

Here are four sample programs to demonstrate the power of Bitxtreme:

  <NUL> (bit representation in memory: 0,0)

This program is a quine! It subtracts 0 from 0 and stores the result into position 0 which is standard output. Since the PC wraps around when reaching its maximum value, the program starts again and more zeros are written to stdout. The program source being output is repeated indefinitely.

  <STX> (bit representation in memory: 0,1)

This program is similar to the previous example with the exception that its output is not its own source. Since the branch to bit position 1 never occurs, the program repeatedly outputs all zeros as the previous one.

  <SOH> (bit representation in memory: 1,0)

This is an amazing piece of code! It exercises several advanced techniques such as self-modification, read and write from/to standard input/output, and the jump in the middle of an instruction as described in the Tips and Tricks section. It acts as a state machine. I still have to find out what it can be useful for. Unfortunately all it can write to standard output is ones.

  <ETX> (bit representation in memory: 1,1)

This one behaves very similar to <SOH> above except that it starts in a different state.

Contributions

I'll be glad to publish here any other Bitxtreme programs sent by the readers. In particular, classic examples such as 99 bottles of beer or a port of the Linux O.S. are welcome.

Turing-completeness

OISC is Turing-complete. The fact that integers are limited to 1 bit doesn't affect that result. Thus, Bitxtreme must also be Turing-complete itself, I'm sure. The amount of memory supported by the virtual machine is unbounded, thus complying with the requisite for Turing-completeness; actual implementations will however impose an upper bound. Some people object that the limitation of PC to 1 bit imposes severe restrictions for Turing completeness but I'm sure that the examples above will be enough to show that that argument is bogus.

Interpreter

Here's an interpreter of Bitxtreme in Python that you can use to try the examples above and any other program you can come up with. It's in the public domain. It has the memory limited to 2 bits for space reasons, but in case you have a high-end machine with plenty of RAM you can modify it to support greater amounts of memory.

Source code for the examples


Use this address to send me E-mail: parigalo@formauri.es.
NOTE: THIS ADDRESS IS NOT PERMANENT. Always verify this page to send me E-mail because it's likely to change often for spam reasons.

Any kind of suggestions are welcome.

Back


© Copyright 1998,1999,2000,2002,2003,2004,2005 Pedro Gimeno Fortea. All rights reserved.
This is valid XHTML 1.0.