STXTRM

From Esolang
Jump to: navigation, search

STXTRM (pronounced as "StackStream") is a minimalist self-modifying, stack-based esoteric programming language. It was designed as a direct successor to MSM and created by User:Plugnburn on August 9, 2013 along with its reference implementation.

Language structure

STXTRM consists of one stack (common for program and data) and seven instructions.

The following 5 instructions are essentially the same as in MSM:

  • ; - duplicate the top value on the stack;
  • : - split the top value on the stack (pop the initial value, split it into characters and push them individually onto the stack);
  • , - drop the top value from the stack;
  • / - swap two top values in the stack;
  • . - concatenation: pop the two top values, concatenate the second top value to the end of top value and push the result back onto the stack;

Additionally, most important changes were made with the following two instructions:

  • | - revert the entire stack (the top value becomes the bottom value and vice versa, the second top value becomes the second bottom and vice versa, and so on);
  • [string] - push everything between the [ and the matching ] onto the stack. You can also use any number of nested square brackets, as long as the count of opening square brackets is equal to the count of the closing ones.

Unlike MSM, anything not in the above list is simply ignored, so comments in this language are trivial.

The only data type STXTRM operates on is strings.

Program flow

On start, the interpreter initializes the stack with the source code, character by character. So before the main loop begins, the stack is already filled with characters of the source code. Then the main loop begins. On each iteration, the interpreter performs the following steps:

  1. Shift (read and remove) the value from the stack bottom (effectively treating it as a queue on this step).
  2. If the value is not present in the instruction list, ignore it and continue to the next iteration.
  3. If the value is [ character, read the string up to matching ] character and push it as the value onto the stack, else perform the perform the action on the current stack according to the instruction definition.

The main loop is repeated until only one value remains in the stack or no recognizable instructions remain in the code. The top value is then returned as the machine output.

Examples

Hello world

[Hello, world!]

Quine

Due to the way the interpreter works, any 1-character program is trivially a quine.

Q

Other examples are coming soon. ;)

Implementation

The reference implementation of STXTRM in JavaScript is exactly 300 bytes long:

function(s,i,x){for(s=s.split("");(i=s.shift())&&s[0];)with(s)eval({";":"s=concat(slice(-1))",":":"s=concat(pop().split(''))",".":"pop()","/":"push(pop(),pop())",".":"push(pop()+pop())","|":"reverse()","[":"for(i=-(x=1);x&&s[++i];)x+={'[':1,']':-1}[s[i]]||0;push(splice(0,i).join(''))"}[i]);return i}

Turing completeness question

At the moment, STXTRM is not strictly proven to be Turing-complete. However, some of its constructs can be translated to Underload ones:

  • / (swap) is identical to Underload's ~;
  • ; (dup) is identical to Underload's :;
  • , (drop) is identical to Underload's !;
  • [] (literal separator) is identical to Underload's ();
  • : (split/eval) is technically equal to Underload's ^ (eval), except STXTRM uses the single area for code and data;
  • . (concat) is almost identical to Underload's *, but STXTRM uses the same argument order as MSM, so one must write /. to exactly simulate Underload's behaviour.

That means a necessary minimal Turing-complete subset of Underload can be implemented in STXTRM. In addition to that, | instruction gives the ability to quickly affect the program flow by reverting the (constantly changing) stack and thus another unusual form of flow control.

See also

  • MSM, a less practical predecessor of STXTRM
  • Underload is a language that heavily influenced the creation of STXTRM