MSM programming language reference implementation
Overview
MSM ( Mutating Stack Machine ) is a minimalist self-modifying, stack-based esoteric programming language. It was designed to create the smallest usable stack machine implementation ever possible in JavaScript.
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:
- Shift (read and remove) the value from the stack bottom (effectively treating it as a queue on this step).
- 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.
- 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:
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'.'/.;;;.;.;...:
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.