Stacky

About Stacky

Stacky is an esoteric programming language involving stacks and only stacks. Everything in this language is a stack and stacks can transfer elements to another stack. Some special stacks are added in this language to execute special tasks.

Stacky Specification

Memory System

Stacks store everything as element. Each element of the stack is an signed 32-bit number. Theoretically, stacks can hold an infinite number of elements, and the number of different stacks is also infinite, but due to implementation constraints, the actual capacity can be limited. The interpreter maintains a pointer of a stack. The pointer points to the current source stack.

Operations

You can perform two types of operations in Stacky.

• Move operation (denoted by >) is used to move an element from source stack to target stack.
• Copy operation (denoted by +) is used to copy an element from source stack to target stack.

Both operations are binary operations, so the syntax was designed to resolve source stack and target stack from code.

Loops Blocks

• Zero Check Block (denoted by [ ]). If the top element of the source stack is non-zero at the start of this block [ , then the statement inside this block will execute. If the top element inside the source stack(can be a different stack) is still non-zero at the end ] , then it loops from the start again.
• Empty Check Block(denoted by { }), Same as Zero Check Block, but the condition is changed. The statements inside the block will execute if the source stack is non-empty. Same condition for looping.

Stack and Number Stack

• Any combination of alphabets a-z and A-Z represents a stack of that name.
• Any combination of numbers 0-9 represents a number stack of that value(Decimal). Elements are 32-bit in size.

Rules

• Stacks, which follow an operator, represent target stack for that operator and source stack for the next operator.
• Stacks, which do not follow an operator, represent change in source stack pointer.
  Example-
  The code C>A+B implies
  1. C - Set the source stack pointer to C,
  2. >A - Perform move(>) operation with target A and set the source stack pointer to A,
  3. +B - Perform copy(+) operation with target B and set the source stack pointer to B,
• Starting token of the code should always be a stack or a number stack.
  Example-
  {A>B} is wrong, however A{A>B} is correct.
• Number stack can be only treated as source but never as target.
  Example-
  45>A is correct but A>45 is wrong.
• Code inside { } and [ ] will loop until the respective condition is met.

Operator Chaining

The move(>) and copy(+) operators can be chained together to form bigger operators like >>>+>.
Chained operators are first performed on the source stack while treating an intermediate queue as target stack, and then the queue is transferred to the actual target stack.
Using an intermediate queue grants us perk to use the same stack as source and target. Example-

• A+A will duplicate the top element of A and set the source stack to A.
• A>>>A will reverse the top three elements of A and set the source stack to A.
• A>>>+A will reverse the top three elements of A, add a copy of 4th element on top of them and set the source stack to A.

Number Stack

Number stack is a special stack which is always empty. Both operations will create an element holding the value of this stack.
Example-

• 45>A will put an element valued 45 to stack A and set the source stack to A.

Loops

Loops will execute the statements inside them until the required conditions are met.
Example-
A{>B A} will transfer all elements of A to B in reverse order.
A at the start will set the source stack to A.
The following { will execute code inside the block (assuming that A is non-empty at this point).
>B will transfer the top element of source stack (A in this case) to B and set the source stack to B.
The next A will set the source stack to A so the following } will check again for source stack to be non-empty.
Same goes for the [] block.

Loops as if block

Loops can be used as if conditional by setting the source stack to any empty stack at the end of inner block. Example

• 45>>>>A{A>B 0} will transfer 45 from A to B once because at the end( } ) the source stack is set to number stack 0 and number stacks are always empty.

Special Stacks

Some special stacks are added to extend functionality.

• io stack. io as a source provides interface to read the console input buffer. io as a target provides interface to write console output. Example-

  • 66>io will print B and
  • io>A will transfer the first character of input to A.

  > will transfer one charcter from input buffer to target stack.
  + will copy one character from input buffer to target stack.
  The distinction can be made by io>>>io and io+++io, first code will take 3 character inputs and prints them while the second code will take 1 character input and prints it 3 times.
  The + operator only copies the character from input buffer. io becomes empty when the input stream becomes empty.

• add stack. If there are more than 1 element in add then they become one element whose value is sum of all elements of add
  Example
  33>add33>add>io will print B (ASCII value 66 = 33+33)

• and stack. It performs same as add but the operation it performs is bitwise AND(&).

• or stack. It performs same as add but the operation it performs is bitwise OR(|).

• rsft stack. Any element pushed to rsft will get right shifted by one place.
  Example-
  132>rsft>io will print B (ascii code 66 which is 132 >> 1)

• lsft stack. It is same as rsft however the operation it performs is left shift by one place.

• inv stack. It is same as rsft however the operation it performs is bitwise INVERT(~).

• int stack. It performs the same operation as number stack, but as a target it prints the pushed element as unsigned integer.

• bin stack. It is an always empty stack used to destroy elements. Push elements to bin to destroy them.

Examples

Hello World

72>io
101>io  
108>>io  
111>io  
32>io  
87>io  
111>io  
114>io  
108>io  
100>io

Cat Program

io
{
    io>io
}

Fibonacci Numbers

1>a+b+int10>io
20>c
[
    a>add
    b>a+add>b
    a+int
    10>io
    c>add
    0>inv>add>c
]

Subtraction

50>>a
20>>b
b>inv>add
1>add
a>add
add>c

a>int
45>io
b>int
61>io
c>int

Implementation

The cpp directory contains a c++ implementation of the language. Execute makefile
$ make -C ./cpp/
which result in the creation of executable cpp/program. Execute it by
$ ./cpp/program "source_file_name"
to start the interpreter.

Brainfuck2Stacky

The file converter/converter.py is a python3 program which converts valid brainfuck code to stacky code. It takes brainfuck code as console input and prints stacky code as console output. Execute
$ python3 ./converter/converter.py < "input_bf_code_file" > "output_stacky_code_file"
Since stacky can simulate brainfuck, therefore it is turing complete.