Skip to content

Instantly share code, notes, and snippets.

@plugnburn
Forked from 140bytes/LICENSE.txt
Last active December 20, 2015 09:49
Show Gist options
  • Save plugnburn/6111062 to your computer and use it in GitHub Desktop.
Save plugnburn/6111062 to your computer and use it in GitHub Desktop.
Myth programming language reference implementation

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.

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
}
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}
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.
{
"name": "mythInterpreter",
"description": "Myth programming language reference implementation",
"keywords": [
"myth",
"programming",
"language",
"string",
"rewriting"
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment