APGsembly
- Original article on LifeWiki: APGsembly
The general purpose calculator (GPC) is a way to implement computational tasks inside Conway's Game of Life. It is Turing complete and programmed by a special-purpose programming language called APGsembly. The first computational Life patterns using this technology were constructed by Adam P. Goucher in 2009 and 2010. The Spartan universal computer-constructor, pi calculator and phi calculator patterns, and a related pattern programmed to grow at O(sqrt(log(t))), had all the same basic general-purpose components that make up the GPC.
Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by Dave Greene to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by Michael Simkin and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from Conway's Game of Life: Mathematics and Construction textbook.[1]
The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.
Overview
The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see B2D below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output lanes, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.
Thus the GPC has four major physical components:
- Clock.
- Program code.
- Computational unit array.
- Printer and B2D.
The computational cycle
Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a universal regulator mechanism.
- The return signal is always a one-bit output value, either Z or NZ.
- Each cycle is expected to return exactly one such output.
Program code
APGsembly code consists of a list of actions to be performed for each state ID, for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
- The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
- Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.
Each line of code consists of 4 parts, separated by semicolons and optional whitespace:
StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.
- StateID. Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
- Z/NZ. Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
- NextStateID. Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
- Action. Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.
Example:
INITIAL; Z; A2; NOP INITIAL; NZ; A2; NOP A1; Z; A2; INC B0, NOP A1; NZ; A2; INC B0, NOP A2; Z; A1; SET B0, NOP A2; NZ; A1; SET B0, NOP
This loads the B0 register with an increasing number of '1' bits. Notice that each state ID INITIAL, A1, and A2 appears twice in the program, once for each possible Z return and once for each NZ return.
A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as
INITIAL; ZZ; A2; NOP A1; *; A2; INC B0, NOP A2; *; A1; SET B0, NOP
Computational units
There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.
- NOP - The NOP action sends a Z output directly, and takes no other action.
- HALT - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
- U - sliding block register (holds a single integer value, stored in unary)
- B - binary string register (holds an arbitrary-length string of binary digits)
- ADD - adder
- SUB - subtractor
- MUL - multiplier
- B2D - a two-dimensional binary register.
The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.
Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.[2]
U: Sliding block register
- Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
- A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).
U Actions:
- INC Ux will increase the register by 1. No return signal.
- TDEC Ux will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.
B: Binary string register
- Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
- A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
- A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.
B Actions
- INC Bx increases the position of reading head. No return signal.
- TDEC Bx decreases the position of reading head. Returns NZ unless at 0.
- READ Bx returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
- SET Bx sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.
ADD: adder
One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.
- A0 is not implemented as an input, because there is nothing to change.
ADD Actions
- ADD A1 increments the number (modulo 4). No return signal.
| Current | Next |
|---|---|
| 00 | 01 |
| 01 | 10 |
| 10 | 11 |
| 11 | 00 |
- ADD B0 right-shifts the number. Returns Z if the value before the action is even and NZ if odd.
| Current | Next | Output |
|---|---|---|
| 00 | 00 | Z |
| 01 | 00 | NZ |
| 10 | 01 | Z |
| 11 | 01 | NZ |
- ADD B1 increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.
| Current | Next | Output |
|---|---|---|
| 00 | 00 | NZ |
| 01 | 01 | Z |
| 10 | 01 | NZ |
| 11 | 00 | Z |
SUB: subtractor
The subtractor works same as the adder, but using 2-bit two's complement arithmetic.
SUB Actions
- SUB A1 increments the number (modulo 4). No return signal.
| Current | Next |
|---|---|
| 00 | 01 |
| 01 | 10 |
| 10 | 11 |
| 11 | 00 |
- SUB B0 right-shifts the number. Returns Z if the value before the action is even and NZ if odd.
| Current | Next | Output |
|---|---|---|
| 00 | 00 | Z |
| 01 | 00 | NZ |
| 10 | 11 | Z |
| 11 | 11 | NZ |
- SUB B1 decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.
| Current | Next | Output |
|---|---|---|
| 00 | 11 | NZ |
| 01 | 00 | Z |
| 10 | 00 | NZ |
| 11 | 11 | Z |
MUL
MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and then divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the pi and phi calculator programs.
MUL Actions
- MUL 0
- MUL 1
B2D: 2d binary register
- B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
- B2D can be used as memory array as well as 2d plotter.
- B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
- The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
- A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.
- This B2D unit's internal circuitry operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.
B2D Actions
- INC B2DX increases the position of the X arm. No return signal.
- INC B2DY increases the position of the Y arm. No return signal.
- TDEC B2DX decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
- TDEC B2DY decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
- READ B2D returns the state of the binary value located at (X, Y). Returns Z if the current state is 0 (empty), otherwise NZ.
- SET B2D sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.
Digit printer
The digit printer can print "." and digits 0-9. No return signal.
Digit printer actions
- OUTPUT x, for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.
Further details
- For further discussion and examples, or to ask questions, see this conwaylife.com forum thread.
- Conway's Game of Life: Mathematics and Construction Chapter 9. Universal Computation
- A compiler and emulator written in Lua for use in Golly.
- A compiler and debugger for use in Golly. This is an old (1.0) version.
- An emulator that works in a web browser.