% cat README
,-'~~~'-,
.~ `. ~.
/ 8 | \
: ,' :
| .--~ |
! ; !
\ | 8 /
`. ', .'
`-.___.-`
B A L A N C E
User's Manual
I. Introduction
Night and day. Beauty and truth. Oxygen and phlogiston. Everywhere we
look there are perfect opposites. Balance is a programming language
based on the concept of harmoniously coexisting duals. In this
language, every operation has an equal and opposite reaction. This
ensures that the machine state does not stray from equilibrium.
Because it performs two operations for each instruction, the language
is also twice as fast as single-operation languages.
Balance programs are run inside an 8-bit machine with the following
features:
* CODE: an arbitrarily long immutable stream of bytes
* M[0..255]: 256 8-bit bytes of memory
* IP: the instruction pointer (an arbitrary non-negative value)
* IS: the instruction speed (ranging from -16 to +15)
* sR[0..3]: four 8-bit source registers
* dR[0..1]: two 8-bit destination registers
* four instructions
Each instruction is specified by a single 8-bit byte. The bits
are numbered from most to least meaningful as follows:
lmb
.--------.
|76543210|
`--------'
mmb
* The bits 7,6,5 specify the opcode
and depending on the instruction:
* bits 4,3,2,1,0 specify an immediate value IMM
or
* bit 4 denotes a destination register D
* bits 3,2 denote the first source register S1
* bits 1,0 denote the second source register S2
Every problem in computer science can be solved by an additional layer
of indirection. Balance thus provides this facility automatically:
Each of the source and destination registers is an indirect register.
For instance, most instructions do not work on the contents of
registers S1 and S2 directly, but use the contents of S1 and S2 as
indices into the memory M. The result is not stored in D, but rather
stored in the memory location indicated by the current contents of D.
The machine begins with IP = 0 and IS = 1. At each step of the
machine, an instruction is fetched from CODE[IP] (where CODE[0] is the
first instruction, CODE[1] the second, etc.). The instruction is
executed, and then IP is increased (or decreased) by the value of IS,
modulo the length of CODE.
II. Instruction Reference
The four instructions of Balance are MATH, LOGIC, SCIENCE, and
PHYSICS. The following is their specification; some examples are
given in a separate section below.
Opcode (bits) Description
MATH 001
MATH performs addition and its dual, subtraction.
These act on different registers so that the math is
not undone. All operations are modular with respect
to the number of relevant bits. Source registers are
represented with two bits, so if S1 is 3, then
sR[S1+1] is sR[0]. Similarly, dR[1+1] is dR[0].
Quantities in memory are eight bits, so 250 + 20 is
14.
M[ dR[D+1] ] <- M[ sR[S1+1] ] - M[ sR[S2+1] ]
M[ dR[D] ] <- M[ sR[S1] ] + M[ sR[S2] ]
LOGIC 010
LOGIC performs bitwise 'and' as well as its perfect
dual, bitwise 'exclusive or.'
M[ dR[D+1] ] <- M[ sR[S1+1] ] XOR M[ sR[S2+1] ]
M[ dR[D] ] <- M[ sR[S1] ] AND M[ sR[S2] ]
SCIENCE 000
SCIENCE tests a hypothesis and determines the speed
at which the program progresses. When executed, it
sets the instruction speed IS to immediate value IMM,
as long as the memory cell indicated by sR[0] does
not contain 0. Because this instruction behaves
specially when the memory cell contains 0, it also
behaves specially if IS is set to zero: the machine
then halts. The value IMM is treated as a signed
five-bit number in two's complement form, so it can
take on values from -16 to +15.
if M[ sR[0] ] = 0 then (nothing)
otherwise IS <- IMM
if IS = 0 then HALT
else (nothing)
PHYSICS 011
PHYSICS changes what the registers reference, in both
a linear and angular way. The immediate value IMM,
treated as a signed five-bit number, is added to the
register sR[0] so that it may reference a different
memory cell. The instruction also rotates the values
between some subset of the registers, according to a
bitmask derived from IMM. The source register sR[0]
is always part of the rotated set, so the bitmask
used is a 6 bit number where the lowest 5 bits are
the same as IMM and the sixth bit is always 1.
sR[0] <- sR[0] + (IMM as signed 5-bit number)
let L=L0,...,L4 be the registers
dR[1], dR[0], sR[3], sR[2], sR[1]
then let C be the list of n elements Li
such that bit i is set in IMM
(bit 0 is the least significant,
bit 4 is the most significant)
then let Cs be the list (sR[0], C0, ..., C(n-1))
and let Cd be the list (C0, ..., C(n-1), sR[0])
then, simultaneously
Cd0 <- Cs0
...
Cdn <- Csn
Any other opcode stands for the instruction BAIL, which will cause the
machine to terminate in failure. Programmers sometimes insert such
bugs deliberately in order to quickly halt the interpreter during
testing.
III. Examples
If M[sR[0]] = 0, IP = 3, IS = 6, length(CODE) = 100,
and CODE[IP] = SCIENCE 12,
then in the next cycle IP = 9 and IS = 6.
If M[sR[0]] = 9, IP = 3, IS = 6, length(CODE) = 100,
and CODE[IP] = SCIENCE 12,
then in the next cycle IP = 15 and IS = 12.
If sR = {0, 1, 2, 3}, dR = {4, 5}, M = {2, 3, 5, 7, 11, 13, 17, ...},
and CODE[IP] = MATH (0, 3, 1)
then in the next cycle M = {2, 3, 5, 7, 10, 253, 17, ...}.
If sR = {0, 1, 2, 3}, dR = {4, 5}, M = {2, 3, 5, 7, 11, 13, 17, ...},
and CODE[IP] = LOGIC (0, 3, 1)
then in the next cycle M = {2, 3, 5, 7, 7, 32, 17, ...}.
If sR = {0, 1, 2, 3}, dR = {4, 5}
and CODE[IP] = PHYSICS -1
then sR[0] is updated with sR[0] + -1 = 255
and in the next cycle sR = {1, 2, 3, 4}, dR = {5, 255}.
If sR = {0, 1, 2, 3}, dR = {4, 5}
and CODE[IP] = PHYSICS 16
then sR[0] is updated with sR[0] + 16 = 16.
The bitmask for rotation is 1 1 0 0 0 0
for the register set {16, 1, 2, 3} {4, 5},
so in the next cycle sR = {1, 16, 2, 3}, dR = {4, 5}.
If sR = {0, 1, 2, 3}, dR = {4, 5}
and CODE[IP] = PHYSICS 15
then sR[0] is updated with sR[0] + 15 = 15.
The bitmask for rotation is 1 0 1 1 1 1
for the register set {15, 1, 2, 3} {4, 5}
so in the next cycle sR = {2, 1, 3, 4}, dR = {5, 15}.
IV. Syntax
The Balance language concrete syntax is simply a single line of bytes,
each written as two hexadecimal digits, with no whitespace or other
characters.
V. Balance Certified Professional Program (BCPP)
As a professional programmer, you are invited to join one of the
industry's leading programmer certification programs. BCPP
certification can be obtained automatically by solving a series of
challenge problems and verifying the results using the supplied
program "certify".
Please see the file PUZZLES for the list of challenge problems. To
certify a solution, stored in a file called "solve.bal", to the
problem called "prop", run the command
certify prop solve.bal
Because a professional programmer knows that shorter code is better
code, your certified skill level depends on the length of the program
that you submit to the certifier.
A challenge problem consists of a description of the initial register
and memory values and the desired final configuration. A program
solves the challenge if it achieves the final configuration and halts
gracefully (SCIENCE 0 with M[sR[0]] <> 0).
Accepted applicants will receive an engraved sandstone diploma and
will be added to the 19101 electronic edition of "Who's Who in
Computerology." Please allow 4-6 weeks for delivery.
% cat PUZZLES
Balance Certified Professional Program Puzzles
This file contains a list of puzzles. Solutions to these puzzles may count
towards your BCPP certification. Use the certify program to submit
your solutions. (Note: Not all maximum scores have been attained by the
BCPP organization.)
Puzzle: stop
Initial memory: M[0-5] = [0, 1, 0, 0, 0, 0]
Remainder of memory initialized from /etc/passwd
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: Any
Final registers: Any
Certification point value: 5 - 10
Puzzle: stop1
Initial memory: M[0-5] = [0, 1, 0, 0, 0, 0].
Remainder of memory initialized from /etc/passwd
Initial registers: {0, 0, 0, 0} {0, 0}
Final memory: Any
Final registers: Any
Certification point value: 5 - 10
Puzzle: stop127
Initial memory: All zeroes except for M[127] = 127
Initial registers: {0, 0, 0, 0} {0, 0}
Final memory: Any
Final registers: Any
Certification point value: 5 - 20
Puzzle: stop128
Initial memory: All zeroes except for M[128] = 128
Initial registers: {0, 0, 0, 0} {0, 0}
Final memory: Any
Final registers: Any
Certification point value: 5 - 15
Puzzle: copymem
Initial memory: M[0] = a, where a <> 0. M[1] = 1.
All other memory locations initialized to 0
Initial registers: {0, 0, 0, 0} {0, 0}
Final memory: Any
Final registers: At least one register should contain a
Certification point value: 60 - 200
Puzzle: copyreg
Initial memory: M[0-7] = [1, 2, 4, 8, 16, 32, 64, 128].
All other memory locations initialized to 0.
Initial registers: {a, 0, 1, 2} {3, 4} where a <> 0
Final memory: At least one memory location should contain a
Final registers: Any
Certification point value: 60 - 200
Puzzle: swapmem
Initial memory: M[0-7] = [1, 2, 4, 8, 16, 32, 64, 128].
All other memory locations initialized to 0.
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: There exist i and j such that 0 <= i < j <= 7 and
M[i] contains the original value of M[j] and M[j]
contains the original value of M[i]
Final registers: Any
Certification point value: 10 - 40
Puzzle: swapreg
Initial memory: All memory locations initialized to 1
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: Any
Final registers: Swap any two distinct registers. The value of the
other registers may be anything
Certification point value: 5 - 50
Puzzle: swapreg2
Initial memory: All memory locations initialized to 1
Initial registers: {a, b, c, d} {x, y} where a, b, c, d, x, y <> 0
Final memory: Any
Final registers: Swap any two distinct registers. The value of the
other registers may be anything
Certification point value: 10 - 50
Puzzle: addmem
Initial memory: M[0] = a, M[1] = b, where a, b <> 0
All other memory locations initialized to 0
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: M[2] = a + b
Final registers: Any
Certification point value: 5 - 40
Puzzle: addmem2
Initial memory: M[0] = a, M[1] = b, where a, b <> 0
All other memory locations initialized to 0
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: M[0] = a, M[1] = b, M[2] = a + b.
All other memory locations must be 0
Final registers: Any
Certification point value: 10 - 50
Puzzle: multmem
Initial memory: M[0] = a, M[1] = b, where a, b <> 0
All other memory locations initialized to 0
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: M[2] = a * b
Final registers: Any
Certification point value: 60 - 200
Puzzle: fillmem
Initial memory: M[0-2] = [a, i, j], where a <> 0, 8 <= i < j <= 255
All other memory locations are initialized to 0
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: Memory locations from 8 to (i-1) must contain 0
Memory locations from i to (j-1) must contain a
Memory locations from j to 255 must contain 0
(all ranges are inclusive)
Final registers: Any
Certification point value: 60 - 200
Puzzle: clearreg
Initial memory: For each i from 0 to 255, M[i] = i
Initial registers: {0, 1, 2, 3} {4, 5}
Final memory: Any
Final registers: All registers must be set to 0
Certification point value: 20 - 100
%