Difference between revisions of "APGsembly"
m (bolded) |
m (mention * and ZZ syntactic shortcuts.) |
||
Line 1: | Line 1: | ||
The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It's 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 2010. These [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC. | The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It's 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 2010. These [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|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 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). | 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). | ||
The base GPC pattern includes just the logic and memory circuitry; an additional | 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 == | == 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 '''SQ''' below). These guns emit a glider each time an operation has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as 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. | 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 '''SQ''' below). These guns emit a glider each time an operation has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, 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: | Thus the GPC has four major physical components: | ||
# Clock. | # Clock. | ||
# | # Program code. | ||
# Computational unit array. | # Computational unit array. | ||
# Printer and SQ | # Printer and SQ | ||
Line 22: | Line 22: | ||
* Each cycle is expected to return exactly one such output. | * 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. | 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 reaches a state where none of the actions return a Z/NZ response. | #The program must start with INITIAL, and will halt if it ever reaches a state where none of the actions return a Z/NZ response. | ||
#If the program is written according the usual rules (i.e. single return per line), it will run indefinitely. | #If the program is written according the usual rules (i.e. a single return signal per line), it will run indefinitely. | ||
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely | #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: | Each line of code consists of 4 parts, separated by semicolons and optional whitespace: | ||
Line 36: | Line 36: | ||
#'''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. | #'''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. | #'''NextStateID''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed. | ||
#'''Op.''' Each line's fourth element defines a list of operations to be executed. | #'''Op.''' Each line's fourth element defines a comma-separated list of operations, or "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:''' | '''Example:''' | ||
INITIAL; Z; A2; NOP | INITIAL; Z; A2; NOP | ||
INITIAL; NZ; A2; NOP | |||
A1; Z; A2; INC T0 | A1; Z; A2; INC T0 | ||
A1; NZ; A2; INC T0 | A1; NZ; A2; INC T0 | ||
A2; Z; A1; READ T0, SET T0 | A2; Z; A1; READ T0, SET T0 | ||
A2; NZ; A1; READ T0, SET T0 | A2; NZ; A1; READ T0, SET T0 | ||
This loads the T0 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. | |||
== Computational units == | == Computational units == | ||
Line 50: | Line 55: | ||
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. | 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 | # ''NOP'' - The NOP action sends a Z output directly, and takes no other action. | ||
# ''R'' - sliding block register (holds a single integer value, stored in unary) | # ''R'' - sliding block register (holds a single integer value, stored in unary) | ||
# ''T'' - binary string register (holds an arbitrary-length string of binary digits) | # ''T'' - binary string register (holds an arbitrary-length string of binary digits) |
Revision as of 14:15, 2 December 2019
The general purpose calculator (GPC) is a way to implement computational tasks inside Conway's Game of Life. It's 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 2010. These 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).
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 SQ below). These guns emit a glider each time an operation 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 SQ
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 reaches a state where none of the actions return a Z/NZ response.
- If the program is written according the usual rules (i.e. a single return signal per line), it will run indefinitely.
- 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; Op1, Op2, Op3, 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.
- Op. Each line's fourth element defines a comma-separated list of operations, or "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 T0 A1; NZ; A2; INC T0 A2; Z; A1; READ T0, SET T0 A2; NZ; A1; READ T0, SET T0
This loads the T0 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.
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.
- R - sliding block register (holds a single integer value, stored in unary)
- T - binary string register (holds an arbitrary-length string of binary digits)
- ADD - adder
- SUB - subtractor
- MUL - ... we're not sure how to use this, but it shows up in the pi and phi calculator code, apparently as a binary-to-decimal converter.
- SQ - a two-dimensional (square) array of data.
The calculator can have an arbitrary number of R, T, ADD, SUB, and MUL units, a single SQ unit, and a single digit or character printer.
R: Sliding block
- Sliding block registers in APGsembly code are denoted by keywords starting with the letter R -- for example, R0, R1, R2, 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).
R: Operations:
- INC Rx will increase the register by 1. No return signal.
- TDEC Rx will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.
T: Binary string register
- Binary string registers in APGsembly code are denoted by keywords starting with T, short for "tape" -- for example, T0, T1, T2, etc.
- A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and DEC, 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, followed by SET or RESET actions. SET and RESET might be more clearly named "WRITE 1" and "WRITE 0".
T: Operations
- INC Tx increases the position of reading head. Returns Z unless the space is empty then it returns NZ.
- DEC Tx decreases the position of reading head. Returns NZ unless at 0.
- READ Tx return the state of the binary string value located at reading head. Returns Z if the value is 0 and NZ if 1.
- SET Tx sets the state of the binary string to 1. Must be after READ operation which deletes the state. No return signal.
- RESET Tx setse state of the binary string to 0. Must be after READ operation which deletes the state. No return signal.
ADD: adder
One should think about the adder as having two bits A and B. Each of them has 0 or 1 option, and each of the options is an input to the adder. A input is just changing the state of the Adder unit, and B input returns the result.
- A0 is ignored case because there is nothing to change.
- A1 is a valid input
- B0, B1 should come after A was initialized.
- The adder returns (Ax + By + Memory) % 2
- The adder stores Memory = (Ax + By + Prev Memory >= 2)
- The memory bit is always stored in the unit when existent.
- If you not sure about the state of the adder just send B0 and you can be sure the Memory is cleaned.
ADD Actions
- ADD A1
- ADD B0
- ADD B1
SUB: subtractor
The subtractor works exactly as adder, just for subtracting two numbers bit by bit keeping in memory 0 or 1.
SUB Actions
- SUB A1
- SUB B0
- SUB B1
MUL
MUL keeps inside a register a number between 0 and 10. MUL 0 divides the number by 2, and MUL 1 divides it by 2 and adds 5. As mentioned we're not yet sure how exactly it is used, but it's involved with binary-to-decimal conversion in the pi and phi calculator programs.
MUL Actions
- MUL 0
- MUL 1
SQ: a two dimensional array
- The SQ register is starting with SQ. For example INC SQ, DEC SQ, READ SQ etc. in APGsembly.
- The SQ has two arms X and Y. Each arm can be moved with INC and DEC. For example INC SQX, DEC SQY.
- A program can retrieve a bit located at (X, Y) by READ command. Unlike T where you must follow with SET, RESET the SQ will erase the (X, Y) bit only if it was existing. It also has only SET SQ command.
- This SQ unit's internal circuitrly operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.
SQ Operations
- INC SQX increases the position of the X arm. No return signal.
- INC SQY increases the position of the Y arm. No return signal.
- DEC SQX decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
- DEC SQY 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 SQ returns the state of the binary value located at (X, Y). Returns Z if the current state is 0 (empty), otherwise NZ.
- SET SQ sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.
Printer
The printer can print "." and digits 0-9. No return signal.
The command is
OUTPUT x
Further details
For further discussion and examples, or to ask questions, see this conwaylife.com forum thread.
Here you can download the compiler and debugger.