Interpret the Shue Language

Question

Overview

Shue (Simplified Thue) is a language that was designed by AnttiP for this challenge. A Shue program consists of the possible outputs and a list of string replacements. For example, the following program prints "yes" if an unary string is even:

yes
no
11=2
12=1
22=2
1=no
2=yes

Try it online!

The possible outputs here are listed as "yes" and "no". Then comes the list of replacements. Here, "11" is replaced with "2", "22" with "2", "12" with "1", "1" with "no", and "2" with "yes". All replacements are done non-deterministically. Once the program reaches a state where one of the replacements is the output, it terminates and prints the output.

Exact definition of Shue

Copied from the original post

The source code is interpreted as a list of bytes. The only characters with special meaning are the newline, the equals sign and the backslash. \n corresponds to a literal newline, \= to a literal equals sign and \\ to a literal backslash. Any other use of \ is an error. Every line must contain 0 or 1 unescaped equals signs.

Or in other words, to be syntactically valid, the program has to match the following regex: /([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?(\n([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?)*/

Here is the mathematical definition of a Shue program:

A Shue program is a set of terminator strings \$T_e\$, and a set of transformation rules \$T_r\$, which are pairs of strings.

The execution of a Shue program on a input string \$i\$ is defined as follows. Let \$U\$ be the minimal set, so that \$i\in U\$ and \$\forall a,x,y,b: axb \in U \land (x,y) \in T_r \rightarrow ayb \in U\$. Let \$S=U\cap T_e\$.

If \$S=\{x\}\$, then the program will terminate, and \$x\$ will be printed to stdout.

If \$S=\emptyset\$ and \$|U|=\aleph_0\$, then the program will enter an infinite loop.

In all other cases, the behavior is undefined (yes, Shue isn't memory safe).

However, since most esolangs cannot process byte arrays, you may take a string or a list of lines as input. See the linked original challenge for a better definition and more examples.

Reference Implementation

Here is the Python reference implementation:

import re, sys
re1 = re.compile(rb"(([^=]|\\=)*)(=([^=]|\\=)*)?")

def unescape(i):
    ret = b""
    esc = 0
    for c in i:
        if esc and c == b"\\":
            ret+= b"\\"
            esc = 0
        elif esc and c == b"=":
            ret+= b"="
            esc = 0
        elif esc and c == b"n":
            ret+= b"\n"
            esc = 0
        elif esc:
            raise ValueError(f"Parser error: got character {c} after \\")
        elif c == b"\\":
            esc = 1
        else:
            ret+= bytes([c])
    if esc:
        raise ValueError(f"Parser error: got EOL/EOF after \\")
    return ret


def parse(i):
    terminators = set()
    rules = set()
    lines = i.split(b"\n")
    for l in lines:
        m = re1.match(l)
        if m.group(3):
            rules|= {(unescape(m.group(1)), unescape(m.group(3)[1:]))}
        else:
            terminators|= {unescape(m.group(1))}
    return terminators, rules

def execute(c, i):
    terms, rules = parse(c)
    universe = {i}
    mod = True
    while mod:
        mod = False
        new_universe = set()
        for s in universe:
            if s in terms:return s
        for s in universe:
            for a,b in rules:
                for o in range(len(s)+1):
                    if s[o:o+len(a)] == a:
                        new_universe|= {s[:o]+b+s[o+len(a):]}
                        mod = True
        universe = new_universe
    raise ValueError(f"Program error: no replacements are possible (undefined behaviour)")


code = input().encode()
inp = sys.stdin.read().encode()

res = execute(code, inp)
print(res.decode())

Rules

• Standard loopholes are forbidden
• You may take input either as a byte list, a single string, or a list of lines.
• As this is code-golf, shortest program in bytes wins.

Answer 1

Python3, 264 bytes:

lambda x,y:next(M(x,p(y)))
def M(s,g):
 if s in g[0]:yield s
 for a,b in g[1]:
  for i in range(len(s)):
   if a==s[i:i+len(a)]:yield from M(s[:i]+b+s[i+len(a):],g)
def p(s):
 d={}
 for i in s.split('\n'):d[c]=d.get((c:='='in i),[])+[[i,i.split('=')][c]]
 return d

Try it online!

Answer 2

JavaScript (Node.js), 198 bytes

c=>g=(a,...b)=>c.every(s=>([_,p,q,r]=s.match(/^((?:\\?.)*?)(=(.*))?$/).map(t=>t&&eval(`"${t.split`"`.join`\\"`}"`)),q?[...a].map((_,i)=>b.push(a.slice(0,i)+a.slice(i).replace(p,r))):a!=p))?g(...b):a

Try it online!

Fixed and optimized tsh's (deleted) answer