Myth programming language reference implementation

README.md

Myth programming language reference implementation

Myth is a minimalist Turing-complete non-deterministic esoteric programming language based on the string-rewriting paradigm.

Language structure

The interpreter is non-interactive. It takes the Myth code in JSON format as the input and returns the final state as the output.

Myth code consists of key-value string replacement rules.

The string "_" (single underscore) is used as the key to specify the initial state, so it's the only string in Myth that cannot be used as a rewriting rule.

Myth computational model is similar to those in Thue, PROLAN/M and REBEL. The interpreter takes the initial state, repeatedly loops through the rules and applies the first matching substitution, then repeats the outer loop until no rules match the current state, and returns the final state to the environment.

As the Myth code can be transparently translated to Thue and vice versa (moreover, Myth code can be considered a JSON-serialized version of Thue code), Myth is also Turing-complete.

Examples

Hello world:

{"_":"Hello world!"}

Or more complicated version that also shows the rewriting concept:

{"a":"Hello","b":"world","_":"a b!"}

Binary number increment (a port from Thue page):

{"1_":"1++","0_":"1","01++":"10","11++":"1++0","_0":"_","_1++":"10","_":"_11111111111_"}

Myth reference implementation for ES5-compatible languages is only 137 bytes long.

annotated.js

function(m,y,t,h){
	m=JSON.parse(m); //parse the code into JS object
	for(y=m._;h=1;) { //read the initial state, set the inner loop flag
		for(t in m) //iterate through the rules
			if(t!="_"&&~y.indexOf(t)) { //check if the rule isn't "_" and is present in current state
				y=y.replace(t,m[t]); //perform the replacement
				h=0; //set the flag to continue outer loop
				break //break the inner loop
			}
			if(h)break //break the outer loop if no rules matched current state
	} return y //return final state
}

index.js

function(m,y,t,h){m=JSON.parse(m);for(y=m._;h=1;){for(t in m)if(t!="_"&&~y.indexOf(t)){y=y.replace(t,m[t]);h=0;break}if(h)break}return y}

LICENSE.txt

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2013 plugnburn

 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO.

package.json

{
  "name": "mythInterpreter",

  "description": "Myth programming language reference implementation",

  "keywords": [
    "myth",
    "programming",
    "language",
    "string",
    "rewriting"
  ]
}