ksplang

From Esolang
Jump to navigation Jump to search
ksplang
Designed by 33 high school students
Appeared in 2023
Memory system Stack-based
Computational class Turing complete
Major implementations ksplang,
File extension(s) .ksplang

Ksplang is a stack-based programming language with 33 instructions, independently designed by 33 people. It is a surprisingly good puzzle to find out how to write some basic programs in this language, and yet it is powerful enough to do anything with reasonable performance.

History

The famous Czech children’s story Jak si pejsek s kočičkou dělali k svátku dort (English translation) by Josef Čapek teaches that you can bake the best cake by adding all the good things you can think of into it. Yes, that is definitely the correct interpretation. We have decided to prove this experimentally, with a programming language.

We have done this within KSP, a Czech programming competition for high-school students. Within the first series of tasks of the 36th year, we have asked each competitor for a single original instruction for a stack-based language. Within the second and third series we have assigned tasks to solve in ksplang.

Learning the language

These tasks are good first steps to learn how to use the language. All of them assume a non-empty stack.

  • task 1: Add 0 to the stack (leaving all the other elements intact)
  • task 2: Turn x into -x (except for -2^63)
  • task 3: Duplicate a number
  • task 4: Turn positive k into a sequence k k-1 ... 0
  • task 5: Sort the stack (given its length)
  • task 6: Calculate the stack length

There are detailed write-ups here (1-3) and here (4-6) on how to solve the tasks available in Czech, but it is really recommended to at least figure out the first 3 tasks.

The stack

We have one stack of 64-bit signed values (-2^63 to 2^63-1). The initial stack is the input, the resulting stack is the output. Overflows are generally an error, so is indexing out of bounds. The list of instructions is indexed from zero. Instructions have ids (0 to 32). Programs are sequences of case insensitive instructions, separated by whitespace. The program ends when the program naturally reaches past the end or the start when executing backwards.

The max stack size is configurable, but in general, we assume it is large enough to fit anything we need.

Overview of instructions

See ksplang/instructions for a full list with all details. Alternatively, you can check out the reference Rust interpreter.

In the description, we usually talk about the stack growing right or upwards.

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.

Computational class

Assuming a sufficiently big max stack size, the language is Turing-complete (a brainfuck -> ksplang translation exists and has been implemented).

Empty or non-empty stack

There are two different classes of programs depending on whether the initial stack is empty or not.

There is only one instruction which can be used with an empty stack: sum, which results in the creation of a zero on the stack. Additionally, there is only one instruction which can be safely used with an arbitrary stack without destroying some of its values: CS.

Because of this, it is not possible to write a program which handles both empty and non-empty initial stack, as programs for the two different cases must start with a different instruction.

Open questions

  • What is the smallest maximum stack size required to calculate anything regardless of the max stack size bounds? The deez instruction allows to store data in the program rather on the stack. But you still need some memory for deez invocations. What is the smallest max stack size which does not prevent from calculating like we have infinite max stack size?

External resources

Implementations

  • ksp/ksplang is the reference Rust interpreter
  • web interpreter is an interactive interpreter with a stepping debugger (unfortunately in Czech, but it's only a few words, so a translator will deal with it easily)
  • ksplang programs has a Kotlin translation of the Rust interpreter


Programs implemented in ksplang

Before looking at this, you should really try to solve those first tasks

Retrieved from "https://esolangs.org/w/index.php?title=Ksplang&oldid=169130"