Ksplang/instructions

This is a full list of instructions of ksplang.

Reference table

Stack manipulation

ID	Zápis	Popis
0	praise	Adds "Mám rád KSP" N times (Czech for “I like KSP”).
1	pop	Removes the top value.
2	pop2	Removes the second value from the top.
3	max	Removes the smaller of the top two values.
4	L-swap	Swaps the first and last value on the stack.
5	lroll	Rolls the top N values on the stack K positions to the right.
6	-ff	If the top of the stack is 2, then 4, do nothing; otherwise empty the stack and fill it with -2^63.
7	swap	Pop an index n, then swap new top value with n-th value from the bottom (zero-indexed).
8	kPi	Gets decimal digits of π (see full description for details).

Arithmetic

ID	Zápis	Popis
9	++	Increments the top number by 1.
10	u	Universal arithmetic; first pops operation id, then does addition/absolute difference/multiplication/division or remainder/factorial/sign.
11	REM	Truncated division modulo (like a % b in C).
12	%	Euclidean modulo (like a % abs(b) in Python).
13	tetr	Tetration.
14	^^	Tetration (reverse parameter order compared to tetr).
15	m	Median of top k numbers, k is top value on the stack (not removed).
16	CS	Digit sum of top number (not removed).
17	lensum	Sum “decimal lengths” of top two numbers on the stack.
18	bitshift	Left bitshift.
19	And	Bitwise AND of top two numbers.
20	sum	Sum the entire stack.
21	gcd	GCD of two numbers.
22	d	GCD of n numbers.
23	qeq	Finds integer solutions of quadratic equations.
24	funkcia	Factorizes 2 numbers and multiplies the factorization except for common primes, modulo 1000000007.
25	bulkxor	Pops N and then applies XOR to N pairs of values interpreted as x > 0 and creates N zeros/ones.

Control flow

IP is the current instruction pointer.

ID	Zápis	Popis
26	BRZ	Sets IP to second top value if the top is zero (conditional absolute jump).
27	call	Adds IP+1 to the stack and sets top of the stack as IP (absolute jump with return IP).
28	GOTO	Sets IP to top value (absolute jump).
29	j	Adds top value + 1 to IP (relative jump).
30	rev	Jumps forward, rotates the stack and executes code backwards until itself (see full description for details)

Other

ID	Zápis	Popis
31	SPANEK	During task evaluation, gives double the points and goes to sleep… (results in a timeout error)
32	deez	Reads n values, translates them to instructions by their ids, evaluates the subprogram and appends the resulting stack as instructions to the end of the program.

Detailed instructions

In examples, we will be writing the stack as a sequence of numbers, with the topmost number on the right, and the stack bottom on the left. If integer overflow (signed 64-bit) occurs at any point, the program execution ends with an error. The reference implementation may be also useful for reference.

praise - I like KSP

Replaces the top number n on the stack with the Unicode characters “Mám rád KSP” repeated n times. For negative n, program execution ends with an error.

Example: 1 🡒 77 225 109 32 114 225 100 32 75 83 80

TL note: The phrase “Mám rád KSP” means “I like KSP” in Czech.

pop

Removes the top value from the stack. If the stack is empty, program execution ends with an error.

Example: 1 2 3 🡒 1 2

pop2 - pop second

Removes the second value from the top of the stack. If the stack has less than two values, program execution ends with an error.

Example: 1 2 3 4 🡒 1 2 4

L-swap - swap first and last

Swaps the first and last value on the stack. If the stack is empty, nothing happens.

Example: 1 2 3 4 🡒 4 2 3 1

lroll - roll the stack top

Pops two numbers from the stack, n and x. Then takes the next n values, shifts them x positions towards the top of the stack, and the first x values are shifted to positions n .. n - x.

If there are not at least n values on the stack, program execution ends with an error. For negative n, program execution ends with an error. For n = 0 or x = 0, no shift occurs.

For negative x, the operation rotates the elements in the other direction. For x greater than n or less than -n, the rotation occurs multiple times (i.e., it rotates by x mod n).

Examples:

For 1 2 3 4 1 4, it rolls the top 4 values by 1, resulting in 4 1 2 3. For 1 2 3 4 -1 4, it rolls the top 4 values by 1 in the other direction, resulting in 2 3 4 1. For 0 1 2 3 4 2 4, it rolls the top 4 values by 2, resulting in 0 3 4 1 2.

-ff

If the top of the stack is not 2, then 4, it empties the stack and fills it with -2^63 (the smallest int64). Requires at least two values on the stack, otherwise program execution ends with an error.

swap - addressed swap

Pops the top value i from the stack, then swaps the new top value with the i-th value from the bottom (zero-indexed). If i is negative, the program ends with an error. If i is greater than or equal to the stack size, the program ends with an error.

Example: 1 2 3 4 5 6 7 8 3 🡒 1 2 3 8 5 6 7 4

kPi

Searches the stack from the top, and the first value k that is also at index k is replaced with the k-th digit of π. The stack is indexed from the bottom, starting at zero, and π is also indexed from zero, with the zeroth digit being 3, the first being 1, the second being 4, etc. If no matching k is found on the stack, the entire stack is replaced with the digits of π.

Examples:

• 1 2 3 4 5 🡒 3 1 4 1 5 (no k found)
• 2 2 2 2 2 🡒 2 2 4 2 2 (k = 2, there is a 2 on stack index 2, so it is replaced with the 2nd digit of π, which is 4)
• 0 1 2 3 4 🡒 0 1 2 3 5 (k = 4 found; all values would match, but the search is done from the top of the stack and only the first incidence is replaced)

++ - increment

Replaces the top value on the stack with its incremented value (top + 1). If there is no value on the stack, program execution ends with an error.

Example: 1 2 3 🡒 1 2 4

max

Removes the smaller of the top two values from the stack, leaving the larger one on the stack. If there are not at least two values on the stack, program execution ends with an error.

Example: 4 2 🡒 4

u - the universal arithmetic instruction

Pops the top value from the stack, this is the operation id.

If operation id is: - 0, replaces next two top values with their sum. - 1, replaces next two top values with their absolute difference. - 2, replaces next two top values with their product. - 3, divides the top value by the second top value, - if the result is an integer, replaces the two values with the quotient - if the result is not an integer, replaces the two values with the remainder (like a % b in C) - 4, replaces the top value with its factorial of its absolute value - 5, replaces the top value with its sign (1 for positive, -1 for negative, 0 for zero) - otherwise, program execution ends with an error.

If there are not enough values on the stack, program execution ends with an error.

REM - truncated division modulo

Replaces top 2 values by the remainder of division of the top value by the second top value.

For (not only) negative values, this behaves as the % operator in C - it maintains the negative sign, but otherwise behaves the same as for positive values.

Examples:

• 3 1 🡒 1
• -3 1 🡒 1
• 3 -1 🡒 -1
• -3 -1 🡒 -1

% - Euclidean modulo

Replaces top 2 values by the modulus of the top value divided by the second top value.

For negative values, behaves as Python a % abs(b) - it always returns a non-negative value.

Note: we recommend reading the Wikipedia article for the comparison of various implementation of modulo in programming languages.

Examples:

• 3 1 🡒 1
• -3 1 🡒 1
• 3 -1 🡒 2
• -3 -1 🡒 2

tetr - tetration

Replaces the top two numbers on the stack with their tetration. The top number is the base, the second is the number of iterations.

If the number of iterations is 0, the result is 1. If the number of iterations is negative, program execution ends with an error.

Examples:

• 2 3 🡒 27
• 3 3 🡒 7625597484987

- tetration

Replaces the top two numbers on the stack with their tetration. The top number is the number of iterations, the second is the base.

If the number of iterations is 0, the result is 1. If the number of iterations is negative, program execution ends with an error.

Examples:

• 3 2 🡒 27
• 3 3 🡒 7625597484987

m - median

Adds the median of the top k numbers on the stack, where k is the top value on the stack (not removed). The median naturally includes k as well. If k is even, the median is defined as the average of the two middle values, rounded towards zero.

If k is not positive, the program ends with an error.

Examples:

• 30 10 5 4 🡒 2 10 1 4 7
• 10 1 3 🡒 10 1 3 3

CS - digit sum

Adds the digit sum of the top value on the stack (not removed). For negative numbers, the sign does not matter (the result is the same as it would be for its absolute value).

Examples:

• 18 🡒 18 9
• -456 🡒 -456 15
• 0 🡒 0 0

TL Note: the name CS comes from the Czech term “ciferný součet”, meaning “digit sum”.

lensum - length sum

Replaces the top 2 values by the sum of their lengths.

The length is defined as the amount of integer divisions by 10 needed to reach zero. Equivalently, it is the number of digits in the decimal representation of the absolute value of the number, with the exception of zero, which has length 0.

Examples:

• 0 0 🡒 0
• 3 2 🡒 2
• -3 2 🡒 2
• -22 22 🡒 4

bitshift - left bitshift

Replaces the top 2 values by the result of shifting the second top value left by the number of bits given by the top value. Negative numbers are represented in two’s complement, so if you push a 1 to the MSB, you get a negative number.

This is the only instruction which does not error on overflow. If the top value (bit count) is negative, program execution ends with an error.

Examples:

• 2 1 🡒 4
• 3 1 🡒 6

And - bitwise AND

Replaces the top 2 values by their bitwise AND. Negative numbers are represented in two’s complement.

Examples:

• 5 3 🡒 1
• -5 -3 🡒 -7

sum - sum the entire stack

Replaces the entire stack with a single value, which is the sum of all values on the stack. For an empty stack, the result is 0.

The stack must fit into a 64-bit signed integer, otherwise program execution ends with an error. Intermediate results do not have to fit.

Examples:

• 1 2 3 🡒 6
• -1 -2 -3 🡒 -6
• (empty stack) 🡒 0

gcd - greatest common divisor of 2 numbers

Replaces the top 2 values by their greatest common divisor (GCD).

The result is always non-negative. If the result does not fit into a 64-bit signed integer, program execution ends with an error.

Examples:

• 12 15 🡒 3
• -12 15 🡒 3
• 4 0 🡒 4
• 0 0 🡒 0
• 0 -2^63 🡒 error
• -2^63 -2^63 🡒 error

d - greatest common divisor of n numbers

Pops the top value n from the stack, then replaces the next n values by their greatest common divisor (GCD).

If n is not positive, program execution ends with an error.

The result is always non-negative. If the result does not fit into a 64-bit signed integer, program execution ends with an error.

Examples:

• 12 15 9 3 4 🡒 3

funkcia

Pops 2 values from the stack. Factorize both values into their prime factors. Then remove all common prime factors (regardless of exponent) from both factorizations. The result is the multiplication of the remaining prime factors modulo 1,000,000,007. If the set of prime factors is empty, the result is 0. Negative are defined to have no prime factors.

For example for numbers 100 = 2^2 * 5^2 and 54 = 3^3 * 2, the common prime factor is 2, so we remove it from both factorizations, resulting in 5^2 and 3^3. The final result is 25 * 27 = 675. Modulo 1,000,000,007 doesn’t change anything for a number this small.

Examples:

• 100 54 🡒 675
• 0 0 🡒 0
• 1 0 🡒 0
• -88 -40 🡒 0

TL note: “funkcia” is the Slovak word for “function”. Please also imagine this description is written in Slovak while all the other descriptions are in Czech.

bulkxor - bulk XOR

Pops the top value n from the stack. Then pops 2n values from the stack, interpreting them as 1 if the value is positive, and 0 if zero or negative. Then it applies XOR to each pair of values, resulting in n values.

Example: 1 -1 3 3 2 🡒 1 0

BRZ - branch if zero

Reads (does not pop) the top value c from the stack. If c is zero, reads (again, does not pop) one more number i, and jumps to instruction i. If c is not zero, continues with the next instruction. Instructions are indexed from zero.

All control flow instructions result in an error if the target instruction is out of bounds. The minimum is 0, the maximum is program length - 1.

If the program is running backwards, nothing changes.

Example: With stack 0 0, program brz is an infinite loop. With stack 0 1, program brz ends normally and does not change the stack.

call - save IP + jump

Reads (does not pop) the top value i from the stack and pushes the index of the next instruction (IP + 1) onto the stack. Then jumps to instruction i.

All control flow instructions result in an error if the target instruction is out of bounds. The minimum is 0, the maximum is program length - 1.

If the program is running backwards, IP - 1 is saved instead.

GOTO - absolute jump

Reads (does not pop) the top value i from the stack and jumps to instruction i.

All control flow instructions result in an error if the target instruction is out of bounds. The minimum is 0, the maximum is program length - 1.

If the program is running backwards, nothing changes.

j - relative jump

Reads (does not pop) top value offset from the stack and jumps that many instruction in the direction of the program execution. If the number is negative, jumps in the opposite direction of program execution. Zero is the next instruction, -1 is back to this instruction, 1 skips one instruction, and so on.

All control flow instructions result in an error if the target instruction is out of bounds. The minimum is 0, the maximum is program length - 1.

rev

TODO: describe this fully.

It calculates how far to jump by finding roots of a quadratic function, then jumps forwards, reverts the stack, reverts program execution, until it reaches the original rev instruction.

You can check out the Czech version in the meantime, there is a picture!

SPANEK

Results in a timeout error during program evaluation.

TL note: “spánek” is the Czech word for “sleep”.

deez

Pops the top value n from the stack. Then pops n values, translates them to instructions by their ids (ordered from the top of the stack) to a standalone program.

This subprogram is then evaluated with an empty stack, and when it finishes, the resulting stack is appended as instructions (translated by their ids again) to the end of the program.

If any value is not a valid instruction id, program execution ends with an error.