ponderosa/SPEC.md

Overview

A forest is a 16-bit virtual computing platform inspired by stack machines and cellular automata with some unique characteristics:

• Every program (forest) is broken into limited-sized, parallel, looping units of execution (trees)
• Trees act on two stacks (the root and trunk) and cells relative to its position (base) in an N-dimensional array (land)

Forests are ideological machines. They have a highly opinionated design to encourage developers to think about memory as something to be conserved and shared. Lots of forestry jargon ahead.

Forests

A forest is the entire universe of operation

Every forest grows on land. Internally, land is a matrix. It can be any number of dimensions, though using more than two or three would rapidly become difficult to visualize. It's also limited in size. Both the size and dimensionality of a forest's land is predetermined when the virtual machine starts

If an access is made to a cell outside of the "boundaries" of a forest, then it loops around to the other side. For example, in a one dimensional forest read left-to-right, if a cell one cell beyond the rightmost boundary is accessed, that should be treated as an access to the cell at the leftmost bounary.

Preconfigured details of a forest are specified in a configuration file ROM. This ROM specifies:

• Initial state of the land as a sparse matrix
• Start of execution

Trees

A tree is a single, spatially rooted context of execution in a forest. It's analagous to a process or a thread on most operating systems, but different in a few key ways.

Like processes, trees run in parallel. Unlike modern processes, trees don't get time slices, they get slices of execution. All trees in the forest get to execute a limited number of instructions each cycle. The capped number of instructions run per cycle is called the tree's "rule," and a "generation" is the time it takes to execute every tree's rule once. The terms "rule" and "generation" are borrowed from cellular automata.

Rules, like in celullar automata, are looped every generation.

Trees use their rules to operate on two stacks: the root and the trunk. By convention, we imagine the tree pulling values from it's root, operating on them, and then pushing them to the trunk. In other words, the trunk is used for results, and the roots are used for operands. However, trees may push to the root and pull from the trunk if applicable.

Every tree has a base, that is, a particular spot on the land, or a cell in the matrix. Land-access is made relative to the position of the base cell, and with respect to the tree, the base cell has coordinates of the zero vector of the forest (i.e. [0] for a 1-dimensional forest, [0, 0] for two dimensions, and so on).

In a given direction, trees can access cells -4 through 3 (mapping to the possible integers in four-bit two's compliment representation).

Planting trees

Planting a tree means scheduling its rule and building its dynamic execution context.

At least one rule is specified in the forest ROM. Each rule is assigned a unique, incrementing integer starting from zero that can be used elsewhere for identification.

Later trees can be planted by other trees, referenced by numeric ID.

How a tree's dynamic execution context is organized is implementation-dependent, but it must include the:

• coordinates of the base
• root stack
• trunk stack
• rule

Rules

Rules may be defined in the forest ROM. During execution, rules should be stored in a data structure such that they can be referenced by numeric ID. By using particular instructions, trees can load new rules into this structure.

Instructions

Stack code

A stack code is at least three bits. A 0 bit represents the root, and a 1 bit represents the trunk.

A unary operation needs only a one bit stack code. If the operation has a stack code with a bit-width of two, the second bit is used and the first is ignored.

A binary operation needs at least two stack bits, the first being for the "left" side and the second being for the "right" side. If both bits are the same, then the arguments are the results of calling "pop" on the stack twice (as opposed two the same value twice).

A third stack bit signifies where any relevant result is stored.

Arithmetic

| op code | stack | signed? | unused | shift amount |

| 00000 | 000 | 0 | 000 | 0000 |

00110 001 1 000 0000 0011 0001 1000 0000 3180 - add two from root and put them in trunk, signed

• and; 0000 1
• nand
• or
• nor
• xor
• not
• add
• multiply
• divide
• slt - "set if less than"
• left - left shift by n bits
• right - right shift by n bits

Stack

Stack management

| op code | stack code | signed? | immediate |

| 00000 | 0 | 0 | 0 0000 0000 |

• push

Stack operations

| op code | stack | unused |

| 00000 | 00 | 0 0000 0000 |

• pull
• swap
• rotate
• flip - Move from one stack to the other
• clear

Control

| op code | stack code | immediate |

| 00000 | 00 | 0 0000 0000 |

You can only jump forward. You "jump back" by letting the rule repeat

• skip - Skip "immediate" instructions
• skim - Skip the number of instructions given in the first stack

Forestry

| op code | stack | relative x | relative y |

| 00000 | 0 | 00000 | 00000 |

The coordinates specified here are signed, two's compliment integers and are computed relative to the base of the tree. Therefore, a tree can sow and reap within the 32x32 cube surrounding it

• sow - store value in cell
• reap - retrieve value from cell
• plant- plants tree. The first value signifies the rule ID, and the second the stack size (must be equal to or less than the current rule's stack size)
• replant - Move tree to specified location
• yeild - (prematurely) end execution of the rule
• compost - (prematurely) end execution of rule, remove the tree from the scheduler, and deallocate the tree's stacks
• define- Creates a new rule based on values from the first stack. The first popped value defines the number of instructions, and subsequently that many more values are popped from the stack for inclusion in the rule. The ID of the rule is stored in the second stack.
• wait - execute wait on a cell's semaphore
• signal - execute signal on a cell's semaphore

| literally just a zero word |

| 0000 0000 0000 0000 |

Deliniates between different rules, parts of the rom, etc. Every rule must terminate with a null word. As such, rules stored across separate roms may be combined by cating the files together, lead by some base rom describing the world.