The Official GRIP (GRId Programming) Language GRIP '92 ============================================= Contents: * Introduction * State of a GRIP Process * Initial state of a GRIP Process * Execution order of GRIP Processes * GRIP Reserved Symbols * GRIP Instruction Set Introduction ------------ This file contains the specification for GRIP 92, the version of the GRIP language that will be used in the AI Olympics GridWars event. This spec is guaranteed not to change before the event, although if ambiguities in the language are found, they may be clarified. The State of a GRIP process consists of: ---------------------------------------- H(0),H(1),... An infinite list of husks. A husk is a triple of location-direction coordinates. It can be thought of as a 2-D Turing machine tape head. The first husk, H(0), is the processor's PC (program counter) husk. c A natural-number index specifying which husk in the above list is the "current" husk. R( ),R(!),R("),...,R(|),R(}),R(~) 95 registers (one for each printable ASCII character) each of which may be either be empty or contain a location-direction pair. These are used for subroutine definition and temporary storage of husk locations. S(0),S(1),... An unlimited-length stack of location-direction pairs. These are used to save return addresses when subroutine-calling. s Index of next unused position on stack. Plus a small amount of internal state used for executing multi-symbol instructions. The initial state of a GRIP process is: --------------------------------------- * All husks (including PC) at the same initial location + direction. H(0)=H(1)=... * Current husk is the PC. c=0. * All registers are empty. R( )=R(!)=...= empty * Stack is empty: s=0, and contents of all S(i) are undefined. Execution order of GRIP processes ---------------------------------- A PROGRAM consists of a set of PROCESSES running concurrently. A GROUP consists of a set of programs running concurrently. Groups of GRIP programs run in a series of TIME-STEPS. During each time-step, each program in the group does one PROGRAM-STEP, in order of the programs' creation. During each program-step, one of the program's processes (see Fork below) performs one EXECUTION CYCLE. An execution cycle consists of three stages: fetch: The processor fetches the instruction symbol at the current location of the PC. This may be only part of a multi-symbol instruction. execute: The processor executes the instruction, possibly causing a husk to move, turn, read, or write. If the instruction consists of several symbols (e.g., get), the instruction will generally not be carried out until all the symbols have been read. Branch instructions behave specially; see their descriptions. move: The PC moves forward one square, unless the process has done of of the following commands already during this execution cycle: 1. A subroutine call 2. A 'j' (Jump) instruction 3. A 'G','L','R','A', or 'm' instruction when the current husk was the PC (c=0). If moving forward would take the PC out of the grid, then it does not move. GRIP Reserved Symbols --------------------- The following symbols are defined GRIP instructions, and may not be used as names of user-defined subroutines. Symbol Name ------ ---- ^ North V South > East < West P Port. S Starboard. / Slash-Mirror. \ Backslash-Mirror. # Bumper. $ Skip. G Go L Left R Right A Around l Turn-Left r Turn-Right a Turn-Around C Case ? If-Reading N If-Not-Reading ~ If-Random W If-Wall g Get p Put [ Next ] Previous { At-PC ( At-Cur s Store m Move j Jump D Define E End " " (Space) No-Op Y Fork Q Quit @ Suicide GRIP Instruction Set ------------------------ ---------------------------------------------------------------------- PC Absolute Directionals ^ PC turn north V PC turn south > PC turn east < PC turn west These instructions change the direction of the PC's motion to the indicated direction. ---------------------------------------------------------------------- PC Relative Directionals P Port - PC turn left S Starboard - PC turn right / Slash-Mirror - PC turn (north<->east,south<->west) \ Backslash-Mirror - PC turn (north<->west,south<->east) # Bumper - PC turn (north<->south,east<->west) These instructions change the direction of the PC's motion to a direction that depends on its current direction, as indicated. These instructions can be useful for making programs more compact. ---------------------------------------------------------------------- Skip $x Skip the instruction x. (Ignore it, do not execute it.) The '$' (Skip) instruction changes the internal state of the process so that during the next execution cycle it will do a No-Op, thus ignoring the symbol just after the '$'. The process will return to normal the following cycle. Thus the net effect of the instruction is to skip over the next symbol. This can be useful for writing a new path of instructions that crosses laterally over an existing path. Skip can be thought of as an Branch-Never conditional. ---------------------------------------------------------------------- Husk Motion: Go, Left, Right, and Around G Current husk move forward L Current husk turn left and move forward R Current husk turn right and move forward A Current husk turn around and move forward These instructions all move the current husk, after turning it in the indicated direction. ---------------------------------------------------------------------- Husk Direction: Turn-Left, Turn-Right, Turn-Around l Current husk turn left r Current husk turn right a Current husk turn around These instructions turn the current husk without moving it. ---------------------------------------------------------------------- Conditionals: If-Reading, If-Not-Reading, If-Random, If-Wall ?yx If symbol at current husk is equal to y, do x, else skip over x. Nyx If symbol at current husk if not equal to y, do x, else skip over x. Wx If the wall is just ahead, do x, else skip over x. ~x With probability 0.5, do x, else skip over x. These multi-symbol instructions allow conditional branching of execution paths. They change the internal state of the process so that it will Skip over the symbol x, or not skip over x, as appropriate. (See Skip above.) The symbol x is usually a PC directional (e.g., '>', '<', 'V', or '^'), so that control-flow will be directed down a new path if the test succeeds. Or, x might be symbol for a 1-symbol instruction or a subroutine call. The '?' (If-Reading) and 'N' (If-Not-Reading) instructions determine, after reading the symbol y, whether the current husk is currently reading (positioned over) an symbol equal to y. Note that two separate execution cycles are required to read the '?' (or 'N') instruction and its argument y. '?' will do x if the symbols are equal, 'N' if the symbols are unequal. Otherwise, x will be skipped, as in '$' (Skip). The 'W' instruction will do x if the current husk is at a wall and cannot move forward; otherwise x will be skipped. The '~' instruction will randomly, with probability 0.5, decide whether to do x or skip over it. ---------------------------------------------------------------------- Case CxXyY...zZEC If x, do X, if y, do Y, ..., if z, do Z, else nothing When the processor executes 'C' (case) it goes into case-mode. In case mode, symbols are examined two at a time. When the first symbol in the pair matches the symbol under the current husk, the processor leaves case mode, and will execute the second symbol in the pair. Otherwise, the processor skips over the second symbol in the pair on the next cycle, and remains in case mode. Case mode is only terminated upon reading a pair in which the second symbol is a 'C'. The first symbol in such a pair should be an 'E' to indicate the mnemonic 'End Case'; however, this is not required. Note that the processor in case mode moves over the case statement at the rate of one square per execution cycle, just as if it were in normal mode. ---------------------------------------------------------------------- Get, Put gx get (read) symbol at current husk, put in into location of x px put (write) symbol x at current husk The 'g' (Get) instruction places the processor into a state such that on the next execution cycle, the symbol under the processor's current husk will be copied to the PC's current location, replacing the symbol x that was previously there. The 'p' (Put) instruction does the opposite; it places the processor in a state where on the next cycle, the symbol x at the PC will be copied to the location of the current husk. ---------------------------------------------------------------------- Store, Move, Jump sx store current husk location in the regiser R(x) mx move current husk to location stored in the register R(x) jx PC jump to location in register x. H(0):=R(x). These instructions access the registers, R(' ') through R('~'). 's' (Store) puts the process into a state where on the next cycle, it will store the current husk's location (& direction) into the register named by the symbol x at the PC. 'm' (Move) will, after reading x on the next cycle, move the current husk to the location (& direction) stored in the register named by the symbol x at the PC. If R(x) is empty, 'm' is a No-Op (and x is skipped). 'j' (Jump) causes the PC to move to the location (& direction) stored in the register named by the next symbol x. The PC will not move again this execution cycle. Jump is not a subroutine call; for that see Subroutine Call below. If R(x) is empty, the 'j' is a No-Op (x is skipped). ---------------------------------------------------------------------- Define & End Dxy Define - put location of y in the register R(x). E End (return from) subroutine. 'D' is used to define subroutines. After the processor reads 'D' (Define) and the next symbol x and moves to the location of y, the current PC location & direction are stored into the register R(x), and y is skipped. y is typically a PC directional ('>', 'V', etc.) that leads to a subroutine, off to the side. See Subroutine Call below for how to call subroutines. Note that 'D' uses the same registers as 's' (Store). Subroutines are terminated with the 'E' (End) instruction, which pops the PC stack if not already empty. (If s>0, s is decremented, and H(0):=S(s).) If the stack is empty, E is a No-Op. ---------------------------------------------------------------------- Next, Previous, At-PC, At-Cur [ Increment c. ] Decrement c, if not already 0. { Increment c, and then set H(c) to location-direction of PC (H(0)). ( Increment c, and then set H(c) to H(c-1) These instructions all change which husk is the CURRENT HUSK of the process. Each process has an unbounded number of husks it may control. '[' (Next) changes to the next husk in the sequence. If the husk has not been visited before, it will still be at the process's initial location. ']' (Prev) changes to the previous husk in the sequence. If we're already at the first husk, this is a No-Op. '{' (At-PC) changes to the next husk, and moves that husk to the current PC location. This is approximately equivalent to the instruction sequence "Dx [mx", except that it takes less space and the contents of R(x) are not overwritten. '(' (At-Cur) changes to the next husk and moves it to the location of the previous husk. This is approximately equivalent to the instruction sequence "sx[mx", except that it takes less space and the contents of R(x) are not overwritten. ---------------------------------------------------------------------- No-Op " " (Space) Official No-Op. Space is the official No-Op instruction. Any symbol that is not a reserved symbol also behaves as a No-Op, if there is no subroutine defined for it. However, those symbols may have meanings in future revisions of the language. Space is guaranteed to remain a No-Op even if the language is extended. ---------------------------------------------------------------------- Fork Yx Fork Creates a copy of the current process, except that the current process skips over x (see '$') and the new process executes it. The new process is said to be in the same "program" as the parent process. Processes in a program are run in round-robin fashion, in order of creation. A processor's time-slice ends after one execution cycle (which ends just after its PC moves). ---------------------------------------------------------------------- Quit Q Quit process. The process will be destroyed and will no longer consume any of the family's execution time. If this is the last process, Q is a No-op. ---------------------------------------------------------------------- Suicide @ Suicide. Like Q, but if the process was the family's last process, the family dies. This is the recommended weapon for destroying and enemy program. ---------------------------------------------------------------------- Subroutine Call x (Any symbol that is not a reserved symbol.) Non-reserved symbols constitute subroutine calls. Subroutines are typically defined using 'D' (Define, see above). If the register R(x) is non-empty, the PC is moved to the location-direction stored in R(x), and its previous location is pushed onto the stack. (S(s):=H(0); s:=s+1; H(0):=R(x).) This replaces the PC's normal forward motion for this cycle. If R(x) is empty, the symbol is a No-Op. ----------------------------------------------------------------------