Mutating Stack Machine

MSM (Mutating Stack Machine) is a minimalist self-modifying, stack-based esoteric programming language. It was designed with the goal to create the smallest usable stack machine implementation ever possible in JavaScript. The working MSM implementation was created by User:Plugnburn on August 4, 2013.

Language structure

Mutating Stack Machine consists of one stack (common for program and data) and seven instructions:

• ; - 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;
• ? - skip the next instruction if two top values on the stack are equal;
• ' (single quote) - set the mutagen (escaping) flag to treat the next character as a regular character even if it is an instruction.

Anything not in this list is treated as a regular character and pushed onto the stack (see "Program flow" section).

The only data type MSM 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 mutagen flag is set, push the value onto the stack as it is, unset the mutagen flag and continue to next loop iteration, else go to step 3.
3. If the value is present in the instruction list, perform the action on the current stack according to the instruction definition, else push the value onto the stack as it is.

The main loop is repeated until only one value remains in the stack. This value is then returned as the machine output.

Examples

Hello world

Trivial version:

dlrow olleh..........

A longer but more obvious version:

hello world/./././././././././.   

A version using the mutagen flag that shows the ability to pass code as data:

'.;;;;;;;;;dlrow olleh

Another obvious version using split (:) instruction that shows the ability to build code at runtime:

hello world'.'/.;;;.;.;...:

Quines

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

Q

A non-trivial quine.

',;;;'/':''';...':';''','';;':''',;;;...........'/':'''/...':';'.;'';;';'';........''':'';''';'/'.'''/;'''/'..........;';./'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;''./'//'./;'/./'//'./;''./'//'./;''./'//'./;''./'//'./;';./'//'./;'/./'//'./;''./'//'./;''./'//'./;''./'//'./;'../'//'./;''./'//'./;'/./'//'./;''./'//'./;';./'//'./;''./'//'./;''./'//'./;''./'//'./;';./'//'./;''./'//'./;''./'//'./;':./'//'./;''./'//'./;''./'//'./;''./'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;';./'//'./;''./'//'./;''./'//'./;';./'//'./;''./'//'./;';./'//'./;';./'//'./;''./'//'./;''./'//'./;';./'//'./;'../'//'./;''./'//'./;';./'//'./;''./'//'./;':./'//'./;''./'//'./;'../'//'./;'../'//'./;'../'//'./;'/./'//'./;''./'//'./;''./'//'./;''./'//'./;':./'//'./;''./'//'./;'/./'//'./;''./'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;'../'//'./;';./'//'./;';./'//'./;';./'//'./;',./'//'./;''./'//'./;''./'//'./;''./'//'./;':./'//'./;''./'//'./;';./'//'./;';./'//'./;''./'//'./;''./'//'./;',./'//'./;''./'//'./;''./'//'./;''./'//'./;';./'//'./;''./'//'./;':./'//'./;''./'//'./;'../'//'./;'../'//'./;'../'//'./;';./'//'./;''./'//'./;''./'//'./;''./'//'./;':./'//'./;''./'//'./;'/./'//'./;''./'//'./;';./'//'./;';./'//'./;';./'//'./;',./'//'./;''./'//'./;'

Other examples are coming soon. ;)

Implementations

As MSM code is hard to debug due to its mutating nature, two reference implementations in JS are offered. The following is a production version with no debugging features (274 bytes):

function(s,t,a,c,k,y){for(s=s.split("");(t=s.shift())&&s[0];)with(s)y?y=0:k?(push(t),k=0):(a=s[c=length-1],","==t?pop():"/"==t?(s[c]=s[--c],s[c]=a):"."==t?push(pop()+pop()):"'"==t?k=1:":"==t?(push.apply(s,pop().split(""))):"?"==t?(y=s[c]==s[c-1]):push(";"==t?a:t));return t}

The following is a developer's version that dumps the stack state to browser (or nodeJS, or whatever) debug console after each instruction (290 bytes and much slower):

function(s,t,a,c,k,y){for(s=s.split("");(t=s.shift())&&s[0];console.log(t,s))with(s)y?y=0:k?(push(t),k=0):(a=s[c=length-1],","==t?pop():"/"==t?(s[c]=s[--c],s[c]=a):"."==t?push(pop()+pop()):"'"==t?k=1:":"==t?(push.apply(s,pop().split(""))):"?"==t?(y=s[c]==s[c-1]):push(";"==t?a:t));return t}

Both implementations accept MSM code as a single parameter and return the machine output. They also show that it's very easy to change the default MSM syntax to your own (provided that all instructions will be 1 character long).

Turing completeness question

At the moment, it's unclear whether MSM is Turing-complete.

See also

• Underload is a language that heavily influenced the creation of MSM
• STXTRM, a more usable direct successor to MSM

External resources

• Docs and reference implementation on GitHub
• Golfed Ruby implementation (without ? instruction yet)