SMETANA To Infinity!

From Esolang
Jump to: navigation, search

SMETANA To Infinity! is an esoteric programming language inspired by SMETANA. It was created by Tanner Swett in 2016.

Syntax

Program    ::= {Step "."}
Step       ::= "Step" Expression "." (GoTo | Swap | Output | "Stop")
GoTo       ::= "Go" "to" "step" Expression
Swap       ::= "Swap" "step" Expression "with" "step" Expression
Output     ::= "Output" "character" Expression
Expression ::= Number | [Number] "n" ["+" Number]

"Number" means a token consisting of one or more decimal digits, interpreted as a decimal number. It is illegal to use a number token whose value is 0, except in an "output" statement. Letters within tokens can have any capitalization. Whitespace is allowed before and after tokens, but not within tokens. If the first non-whitespace character on a line is "#", that line is ignored.

Execution

The memory of a program consists of an infinite array of memory cells ("steps"), indexed by the positive integers, each one containing one instruction. Initially, every memory cell contains the instruction "Stop".

Execution consists of two phases: memory initialization and main execution. Conceptually, memory initialization may involve modifying infinitely many memory cells. An implementation of SMETANA To Infinity! must somehow simulate this process using a finite amount of time.

To perform memory initialization, repeat the following process for each statement in the program, in order:

  • Check whether the step number of the statement is an integer or an "n" expression.
  • If the step number is an integer:
    • Every expression in the statement must be an integer. If one of the statements is an "n" expression, then the program is illegal.
    • Load the body of the statement into memory at the index specified by the step number.
  • If the step number is an "n" expression:
    • For each positive integer "n":
      • Consider the statement formed by replacing each "n" expression with its value.
      • Load the body of this new statement into memory at the index specified by its step number.

Example of memory initialization

Consider this program:

Step n. Go to step 3n + 1.
Step 2n. Go to step n.
Step 1. Go to step 7.
Step 4. Stop.

After memory initialization, the memory will contain:

 1: Go to step 7.
 2: Go to step 1.
 3: Go to step 10.
 4: Stop.
 5: Go to step 16.
 6: Go to step 3.
 7: Go to step 22.
 8: Go to step 4.
 9: Go to step 28.
10: Go to step 5.
11: Go to step 34.
12: Go to step 6.
(...)

Main execution

To perform main execution, execute the instructions in memory in sequence, starting with step 1. After a "go to" instruction is executed, continue executing at the specified location, instead of at the location following the "go to" instruction. After a "stop" instruction is executed, stop executing instructions.

The interpretation of the numbers which are output is unspecified. They could be interpreted as bytes, as Unicode scalar values, or just as numbers.

Computational class

SMETANA To Infinity! seems to be Turing-complete. A Turing machine (with tape infinite in only one direction) could be implemented by representing each space on the tape as a sequence of contiguous memory cells. The state of a cell could be represented by swapping around some of the instructions in the cell. Motion of the head could be implemented by jumping between regions of memory, and the state of the head could be represented by jumping to a specific location within each region.

An alternative proof of Turing-completeness is to note that you can pretty much directly write the Collatz function encoding of a Fractran program, using only the `Go to` and `Stop` commands. The Collatz function rule

f(mx+i) = aix + bi

becomes

Step m n + i. Go to step ai n + bi.

Also, see SMETANA To Infinity!/brainfuck for methods of translating from (1-bit) brainfuck.