APGsembly

From LifeWiki
Jump to navigation Jump to search

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).

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 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:

  1. Clock.
  2. Program code.
  3. Computational unit array.
  4. 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.

  1. 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.
  2. If the program is written according the usual rules (i.e. a single return signal per line), it will run indefinitely.
  3. 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.

  1. 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.
  2. 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.
  3. NextStateID Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
  4. 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. The above sample program could be written more compactly as 

INITIAL; ZZ; A2; NOP
A1; *; A2; INC T0
A2; *; A1; READ T0, SET T0

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.

  1. NOP - The NOP action sends a Z output directly, and takes no other action.
  2. R - sliding block register (holds a single integer value, stored in unary)
  3. T - binary string register (holds an arbitrary-length string of binary digits)
  4. ADD - adder
  5. SUB - subtractor
  6. 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.
  7. SQ - a two-dimensional (square) array of data.

The calculator can have an arbitrary number of R, T, ADD, SUB, and MUL units, one SQ 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 SQ units.

R: Sliding block

  • Sliding block registers in APGsembly code are denoted by keywords starting with the letter R, short for "register" -- 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 Actions:

  • 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", but SET and RESET are the terms used in existing APGsembly.

T Actions

  • 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 current binary bit to 1. Must be after READ action which removes the previous state. No return signal.
  • RESET Tx sets the state of the current binary bit to 0. Must be after READ action which removes the previous state. No return signal.

ADD: adder

One should think about the adder as having two bits, A and B. Each of them can be either 0 or 1, and each of these options is an input to the adder. 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.
  • A1 is a valid input
  • B0, B1 should come after A is initialized.
  • The adder returns (Ax + By + Memory) % 2
  • The adder stores Memory = (Ax + By + Prev Memory >= 2)
  • The "carry" memory bit is stored in the unit until the next use of the adder.
  • If you are not sure about the state of the adder, just send B0 and you can be sure the memory is cleared.

ADD Actions

  • ADD A1
  • ADD B0
  • ADD B1

SUB: subtractor

The subtractor works exactly the same as the adder, except for subtracting two numbers bit by bit, keeping in internal memory a 0 or 1 "carry" value.

SUB Actions

  • SUB A1
  • SUB B0
  • SUB B1

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

SQ: 2d binary register

  • SQ is two-dimensional binary register and is unbounded in positive X and Y directions.
  • SQ can be used as memory array as well as 2d plotter.
  • SQ register commands contain the string "SQ" in APGsembly code -- e.g., INC SQ, DEC SQ, READ SQ, etc.
  • The SQ has two arms X and Y. Each arm can be moved with INC and DEC -- e.g., INC SQX, DEC SQY.
  • A program can retrieve a bit located at (X, Y) via the READ SQ command. Unlike T where you must follow with SET or RESET, READ SQ will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET SQ command, so only SET SQ is implemented.
  • 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 Actions

  • 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.

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

Retrieved from "https://conwaylife.com/w/index.php?title=APGsembly&oldid=138432"