# Jungle

**Jungle** is an esoteric programming language created by User:Madk in May 2019.

## Syntax

A Jungle program is made up of statements and nodes. The nodes are arranged in a binary tree. A node is a parenthesized list of zero or more statements, except for the root node, which is not enclosed within parentheses.

A statement begins with an instruction, which is followed by zero or more arguments, and is terminated by a semicolon.

Nodes are syntactically similar to statements. A left node is declared with the "left" keyword and a right node is declared with the "right" keyword. A node is not required to have a left child or right child. However, a node may not have more than one of each, and may not have more than two children in total.

### Syntax example

write_char "Hello from the root node!"; goto left; left ( write_char "Hello from the root's left child node!"; goto sibling; ) right ( write_char "Hello from the root's right child node!"; goto left; left ( write_char "Hello from the left child of the root's right child!"; exit; ) )

## Nodes

Every node has its own program counter, accumulator (**acc**), stack, stack pointer, carry flag (**carry**), overflow buffer (**overflow**), division by zero flag (**divz**), stack wrapping flag (**wrapped**), and error code (**error**). Nodes can share information by reading and manipulating each other's accumulator and stack. The accumulator and every value on the stack are represented as 32-bit two's complement signed integers.

The program terminates upon any node's program counter exceeding its final instruction, i.e. reaching the end of a node's code without having gone somewhere else. Note that the **goto**, **transfer**, and **again** instructions can be used to implement loops and conditionals. The program will also terminate upon using an instruction such as **return** or **goto origin** if there is no such origin node, i.e. no other node ever jumped to the node evaluating the instruction.

Each node's stack is of an implementation-defined size. Operations which would inspect the stack or set the stack pointer at a location that is outside the range [0, **stack_size**) causes the operation to wrap to the other end of the stack. When this happens, stack-related instructions like **push** and **pop** will set the **wrapped** flag to 1 on the node which executed the instruction.

## Condition arguments

Some instructions accept a condition argument. Here is what each condition means for the action implied by an instruction:

**always**: Do it unconditionally.**if_zero**: Do it if the accumulator is zero.**if_nonzero**: Do it if the accumulator is not zero.**if_positive**: Do it if the accumulator is greater than zero.**if_not_positive**: Do it if the accumulator is not greater than zero.**if_negative**: Do it if the accumulator is less than zero.**if_not_negative**: Do it if the accumulator is not less than zero.**if_carry**: Do it if the carry flag is not zero.**if_not_carry**: Do it if the carry flag is zero.**if_divz**: Do it if the division by zero flag is not zero.**if_not_divz**: Do it if the division by zero flag is zero.**if_wrapped**: Do it if the stack pointer wrapped flag is not zero.**if_not_wrapped**: Do it if the stack pointer wrapped flag is zero.**if_error**: Do it if the error code is not zero.**if_no_error**: Do it if the error code is zero.

## Node arguments

Some instructions accept a node argument. Here is what each recognized node argument refers to:

**self**: This self-same node, i.e. the node executing the instruction in question.**root**: The program's first, or root node.**parent**: The node's immediate parent.**left**: The node's left child.**right**: The node's right child.**sibling**: The opposite child of the node's parent.**leftmost**: Beginning with this node, traverse left children until the first node without a left child.**rightmost**: Beginning with this node, traverse right children until the first node without a right child.**next**: The node after this one in an in-order left-to-right traversal.**prev**: The node before this one in an in-order left-to-right traversal.**origin**: The last node to have resumed execution at this one via**goto**or**transfer**.

## Value arguments

Many instructions accept a value argument. The **push** and **write_char** instructions can accept multiple value arguments. A value argument can be literal constant, or it can be one of these special keywords:

**acc**: The current value of the accumulator.**top**: The value of the top item in the stack. (Won't set**wrapped**flag.)**carry**: The carry flag, either 0 or 1.**overflow**: Overflow, e.g. from multiplication.**divz**: Division by zero flag, either 0 or 1.**wrapped**: Stack pointer overflow/underflow flag, either 0 or 1.**error**: Error number, set by instructions that can fail. Cleared by**clear_error**.

There are also names for referencing some important constants:

**min**: The lowest negative representable value, 0x80000000.**max**: The greatest positive representable value, 0x7FFFFFFF.**stack_size**: The number of items that can be pushed to the stack before wrapping.**no_error**: Value to which**error**is set at start, or after**clear_error**.**read_char_error**: Value to which**error**is set if**read_char**fails.**read_int_error**: Value to which**error**is set if**read_int**fails.

## Reference implementation

These are characteristics of the Jungle interpreter written by User:Madk in May 2019, but are not inherent language features:

A comment begins with two forward slashes "//" and ends at the next newline. Text in comments is ignored by the parser and is not considered as Jungle code.

The special string **///BEGIN///** indicates the start of source code. Content before the first **///BEGIN///** in a file will not be parsed as source code.

The special string **///END///** indicates an end of source code. Content after the first **///END///** in a file will not be parsed as source code. Instances of **///END///** preceding the first **///BEGIN///** are ignored.

The stack size is 256 items. This means that the **stack_size** named constant is equal to 256, and that the stack pointer will wrap back to the beginning of the stack memory if it exceeds this size.

When the instruction **push** has more than one value argument, the statement is unwrapped into one **push** for every argument. The arguments are pushed in reverse-order, i.e. the last argument is pushed first and the first argument is pushed last. In other words, the first argument will end up on the top of the stack and the final argument will end up below all the other items on the stack.

When the **write_char** instruction has more than one value argument, the statement is unwrapped into one **write_char** for every argument. The arguments are written in the same order that they are given.

Literal constants can be either number literals e.g. 1234, 0x100, or they can be string literals e.g. "Hello world!". A string constant is functionally the same as writing each of its unicode code points in order as a list of number literals.

Escape sequences starting with a backslash are supported in string literals. \0 aliases the null character (0x00), \a aliases the bell or alert character (0x07), \b aliases the backspace character (0x08), \e references the escape character or "ESC" (0x1B), \f references the form feed character (0x0C), \n references the line feed character (0x0A), \r references the carriage return character (0x0D), \t references the horizontal tab character (0x09), and \v references the vertical tab character (0x0B). Escape sequences of the form \x00 are also supported, where "00" are two hexadecimal digits representing one UTF-8 code unit.

## Example programs

### Hello, world!

write_char "Hello world!";

### Cat

read_char; write_char acc; xor "\n"; again if_nonzero;

### Fibonacci sequence

write_char "First 20 numbers of the Fibonacci sequence:\n0"; push right 0 1; transfer 20 left; write_char "\n"; left ( dec; goto sibling if_nonzero; return if_zero; again; ) right ( swap; pop; add top; push acc; write_char ", "; write_int acc; return; )

## Instruction list

**exit**: Terminate program.**void**: No operation.**goto**: Jump to node.**transfer**: Jump to node and set its**acc**.**again**: Jump back to start of the same node.**return**: Resume execution in the last node to jump to this one.**return_with**: Resume execution and set target node's**acc**.**swap**: Swap top two stack values.**push**: Push values to the stack.**pop**: Pop a value and set**acc**.**discard**: Discard the top stack value.**peek**: Set**acc**to the top stack value.**assign**: Assign**acc**to a value.**inc**: Increment value in**acc**.**dec**: Decrement value in**acc**.**shl**: Logical shift left**acc**by a given number of bits.**shr**: Logical shift right**acc**by a given number of bits.**sar**: Arithmetic shift right**acc**by a given number of bits.**negate**: Negate the value of**acc**.**abs**: Negate**acc**if**acc**is negative.**not**: Flip the bits of**acc**.**add**: Add a value to**acc**.**sub**: Subtract a value from**acc**.**mul**: Multiply**acc**by a value.**div**: Divide**acc**by a value.**mod**: Set**acc**to the modulo of**acc**over the given value.**rem**: Set**acc**to the remainder of**acc**over the given value.**and**: Set**acc**to the output of bitwise AND with the given value.**or**: Set**acc**to the output of bitwise OR with the given value.**xor**: Set**acc**to the output of bitwise XOR with the given value.**clear_error**: Set**error**flag to**no_error**, i.e. zero.**write_char**: Write unicode code points to stdout.**write_int**: Write value as a decimal integer to stdout.**read_char**: Read one unicode code point from stdin and set**acc**.**read_int**: Read line from stdin, parse it as an integer, and set**acc**.

## Instruction reference

In the following argument lists, [node] means that the instruction accepts a node relation argument. When the node argument is omitted, **self** is used as a default.
[cond] means that the instruction accepts a condition argument. When the condition argument is omitted, **always** is used as a default.
[val] means that the instruction accepts and requires exactly one value argument, i.e. **acc**, **top**, **carry**, **overflow**, **divz**, **error**, or a constant.
[val...] means that the instruction accepts and requires one or more value or value arguments.
Note that the order of arguments does not matter, except for the order of value arguments for the instructions which accept more than one.

### void

No operation; do nothing.

void;

### exit

Immediately terminate the program.

exit;

### goto

Resume execution at the first instruction of the given node.

Sets the origin node and program counter in the destination node to this node and the instruction after the **goto**, respectively.

goto [node] [cond]; goto right; // Jump to right child unconditionally goto parent if_zero; // Jump to parent if the accumulator is zero

### transfer

Assign the accumulator of the given node to the specified value, then resume execution at the first instruction of that node.

Sets the origin node and program counter in the destination node to this node and the instruction after the **transfer**, respectively.

transfer [val] [node] [cond]; transfer acc left if_positive; // Jump to left child with acc if acc is positive

### again

Resume execution at the first instruction in this node.

again [cond]; again; // Repeat unconditionally again if_no_error; // Repeat only if error is zero

### return

Resume execution in the origin node (i.e. the last node to **goto** or **transfer** with this node as the destination) immediately after the instruction which caused control to transfer to this node.

return [cond]; return; // Return unconditionally return if_nonzero; // Return only if acc is not zero

### return_with

Resume execution in the origin node (i.e. the last node to **goto** or **transfer** with this node as the destination) immediately after the instruction which caused control to transfer to this node.

Additionally set the accumulator of the destination node to the specified value, before resuming execution there.

return_with [val] [cond]; return_with 0xFF; // Return unconditionally and set acc to 255 return_with top if_not_negative; // Return and set acc to top of stack if acc >= 0

### swap

Swap the two values on top of the given node's stack.

Set **wrapped** to 1 when the stack pointer was 0 or 1, and to 1 otherwise.

swap [node]; swap; // Swap own stack swap parent; // Swap top values of parent node's stack

### push

Push one or more values onto the given node's stack.

Set **wrapped** to 1 when the stack pointer was at its maximum value and wrapped to the start of the stack, and to 0 otherwise.

push [node] [val...]; push 1234; // Push 1234 to the top of this node's own stack push "Hello world!"; // Push unicode code points of the string "Hello world!" push leftmost -1; // Push -1 to leftmost child's stack

### pop

Pop one value from the given node's stack, and store that value in this node's accumulator.

Set **wrapped** to 1 when the stack pointer was at its minimum value and wrapped to the end of the stack, and to 0 otherwise.

pop [node]; pop; // Pop own stack and set accumulator to the popped value pop sibling; // Pop sibling node's stack and set own accumulator

### discard

Pop one value from the given node's stack, but don't store the discarded value anywhere.

Set **wrapped** to 1 when the stack pointer was at its minimum value and wrapped to the end of the stack, and to 0 otherwise.

discard [node]; discard; // Discard top of own stack discard right; // Discard top of right child node's stack

### peek

Copy the given node's top stack value into this node's accumulator.

Set **wrapped** to 1 when the stack pointer was at its minimum value (normally meaning the stack was empty), and to 0 otherwise.

peek [node]; peek; // Set acc to top of own stack peek root; // Set own acc to top of root node's stack

### assign

Set the given node's accumulator to the specified value.

assign [node] [val]; assign 16; // Set own accumulator to 16 assign parent 100; // Set parent node's accumulator to 100

### inc

Increment the accumulator.

Set **carry** to 1 when the accumulator overflowed and 0 when it didn't.

inc;

### dec

Decrement the accumulator.

Set **carry** to 1 when the accumulator underflowed and 0 when it didn't.

dec;

### shl

Shift the accumulator left by a number of bits, filling the new least significant bits with zeros. The shift value is masked and only the lowest 5 bits are considered, i.e. the shift value is wrapped to be an unsigned value from 0 to 31.

Set **overflow** to the sign-extended high bits that were shifted out of the accumulator. Set **carry** to 1 when information about the value was lost, i.e. a successive shift arithmetic right (**sar**) by the same number of bits would not reproduce the original accumulator value. In other words, if all shifted bits and the new highest bit were not all the same value. Set **carry** to 0 otherwise.

shl [val]; shl 2; // Shift logical left by two bits

### shr

Shift the accumulator right by a number of bits, filling the new most significant bits with zeros. The shift value is masked and only the lowest five bits are considered, i.e. the shift value is wrapped to be an unsigned value from 0 to 31.

Set **overflow** to the low-order bits that were shifted out of the accumulator. Set **carry** to 1 when any of the shifted-out bits were nonzero and to 0 when those bits were all zero.

shr [val]; shr 3; // Shift logical right by three bits

### sar

Shift the accumulator right by a number of bits, filling the new most significant bits with the original value's most significant bit, i.e. its sign bit. The shift value is masked and only the lowest five bits are considered, i.e. the shift value is wrapped to be an unsigned value from 0 to 31.

Set **overflow** to the low-order bits that were shifted out of the accumulator. Set **carry** to 1 when any of the shifted-out bits were nonzero and to 0 when those bits were all zero.

sar [val]; shr 1; // Shift arithemtic right by one bit

### negate

Negate the accumulator.

Set **carry** to 1 when the accumulator was the largest possible negative value and 0 when it wasn't.

negate;

### abs

Negate the accumulator if its value is less than zero.

Set **carry** to 1 when the accumulator was the largest possible negative value and 0 when it wasn't.

abs;

### not

Flip each bit of the accumulator.

not;

### add

Add a value to the accumulator.

Set **carry** to 1 when the sum overflowed and 0 when it didn't.

add [val]; add 100; // Add 100 to the accumulator

### sub

Subtract a value from the accumulator.

Set **carry** to 1 when the difference overflowed and 0 when it didn't.

sub [val]; sub stack_size; // Subtract stack size (e.g. 256) from the accumulator

### mul

Multiply the accumulator by the given value.

Set **carry** to 1 when the product overflowed and 0 when it didn't. The accumulator receives the lower 32 bits of the product and **overflow** is set to the higher 32 bits, i.e. the overflow.

mul [val]; mul 5; // Multiply the accumulator by 5

### div

Divide the accumulator by the given value.

Set **divz** to 1 when the divisor value was zero and 0 otherwise.

div [val]; div 4; // Divide the accumulator by 4

### mod

Set the accumulator to the modulo from dividing the accumulator by the given value. The modulo has the same sign as the divisor, meaning in this case the input value.

Set **divz** to 1 when the divisor value was zero and 0 otherwise.

mod [val]; mod 4; // Set accumulator to the outcome of accumulator mod 4

### rem

Set the accumulator to the remainder from dividing the accumulator by the given value. The remainder has the same sign as the dividend, meaning in this case the accumulator.

Set **divz** to 1 when the divisor value was zero and 0 otherwise.

rem [val]; rem 10; // Set acc to the remainder after dividing acc by 10

### and

Assign the accumulator to the result of a bitwise AND with the given value.

and [val]; and 0xFFFF0000; // Set acc to acc & 0xFFFF0000

### or

Assign the accumulator to the result of a bitwise OR with the given value.

or [val]; or 0x0000FFFF; // Set acc to acc | 0x0000FFFF

### xor

Assign the accumulator to the result of a bitwise XOR with the given value.

xor [val]; xor 0x00FFFF00; // Set acc to acc ^ 0x00FFFF00

### clear_error

Set the **error** status for this node to 0, meaning no error.

clear_error;

### write_char

Write one or more values to stdout, each as a unicode code point.

write_char [val...]; write_char 65; // Write "A" to stdout write_char "Hello world!\n"; // Write "Hello world!" to stdout, then a newline

### write_int

Write a value to stdout as a decimal integer number.

write_int [val]; write_int acc; // Write value of the accumulator to stdout as a decimal integer

### read_char

Wait for and read a single unicode code point from stdin. Store the code point in the accumulator.

Set **error** to **read_char_error** when there was a problem reading from the input, such as due to EOF or invalid unicode The accumulator is set to zero when there was an error.

read_char;

### read_int

Wait for and read characters from stdin up until the next newline \n, then parse the result as a number. Store the resulting number in the accumulator.

The instruction is required to parse decimal integers with and without a preceding sign e.g. 1234, +456, -789. The specification allows for but does not require other forms of input to be accepted.

Set **error** to **read_int_error** when there was a problem reading from the input or parsing a number given the input. The accumulator is set to zero when there was an error.

read_int;