Ételp moc gniruttéy gnitir wérgnirts

Ételp moc gniruttéy gnitir wérgnirts(Official pronounciation: eɪtʰɛlpʰ mɔkʰ ɦniɾutʰeɪj ɦnitʰiɾ ʋeɪɾɦniɾt͡sʰ) is designed by PSTF. If you remove the diacritical marks and read it backwards, you get 'String rewriting yet Turing-complete,' which is what category this programming language belongs to. But this language has nothing to do with cirt e mys or noit o' mnain worb and is an individual serie of language.

Overview

Program Format

Each program consists of the following parts: the first is the initial string, and the others are rules.

Rule format is shown as this:

pattern -> replacement [condition]

Where:

• Pattern: String to match
• Replacement: String to replace with
• Condition (optional): Contextual constraint

Reserved Symbols

Question mark reads a character for input.

Exclamation mark prints the following character.

Double exclamation mark prints the current string.

Vertical bar divides the rule.

Semicolon starts a single line comment.

Asterisk matches any substring.

Hashtag followed with a decimal number means the reference of captured group.

!HALT simply halts the program.

This is the program structure.

INIT: initial_string
RULES:
rule1
rule2
...

Examples

Hello, world!

INIT: "start"
RULES:
start -> !H!e!l!l!o! !W!o!r!l!d!! !HALT

Binary increment

INIT: ">1011"
RULES:
; State q0: scan right to find least significant bit
>0 -> 0> |
>1 -> 1> |
>*$ -> <#1 |
; State q1: found end, now moving left to increment
<0 -> 1S |
<1 -> 0< |
<* -> 1S |
; State S: success, copy rest
S0 -> 0S |
S1 -> 1S |
S* -> !#1!! !HALT

Formal Definition of Language

Program ::= "INIT:" String "RULES:" RuleList
RuleList ::= Rule ("|" Rule)*
Rule ::= Pattern "->" Replacement ("[" Condition "]")?
Pattern ::= String (with * wildcards)
Replacement ::= String (with #n group refs)
Condition ::= "IF" Test
Test ::= GroupRef "=" String

Semantics

1. Start with initial string S
2. Repeatedly apply rules:
   • Find first rule where pattern matches current string
   • Replace matched portion with replacement
   • Execute embedded I/O operations left-to-right
3. Halt when !HALT encountered or no rule applies

Computational Class

Ételp moc gniruttéy gnitir wérgnirts is Turing-complete since it can simulate a Turing-machine like this:

1. Tape represented as string: [left]q[tape symbol][right]
2. States as symbols in string
3. Transition rules as rewrite rules:

   qX -> Yp  ; δ(q, X) = (p, Y, R) | ZqX -> pZY ; δ(q, X) = (p, Y, L)

A universal Turing machine:

INIT: "U>encodedTM>input"
RULES:
; Decode and execute TM transitions
U>*qX*y* -> U*#1Yp#3* [IF lookup(q,X)=(p,Y,R)] |
U>*ZqX* -> U*#1pZY#3* [IF lookup(q,X)=(p,Y,L)] |
U>*q* -> !HALT!  ; Accept state

Interpreter

Python

import re

class ReWriteInterpreter:
    def __init__(self, program):
        self.program = program
        self.string = ""
        self.rules = []
        self.input_buffer = []
        self.output = ""
        self.parse_program()
    
    def parse_program(self):
        lines = self.program.split('\n')
        in_rules = False
        
        for line in lines:
            line = line.split(';')[0].strip()  # Remove comments
            if not line:
                continue
            
            if line.startswith("INIT:"):
                self.string = line[5:].strip().strip('"')
            elif line.startswith("RULES:"):
                in_rules = True
            elif in_rules and "->" in line:
                pattern, replacement = line.split("->", 1)
                pattern = pattern.strip()
                replacement = replacement.strip()
                self.rules.append((pattern, replacement))
    
    def apply_rules(self, max_steps=10000):
        step = 0
        while step < max_steps:
            step += 1
            applied = False
            
            for pattern, replacement in self.rules:
                # Convert wildcards to regex
                regex_pattern = re.escape(pattern)
                regex_pattern = regex_pattern.replace(r'\*', '(.*?)')
                
                match = re.match(regex_pattern, self.string)
                if match:
                    # Build replacement string
                    repl = replacement
                    for i in range(len(match.groups())):
                        repl = repl.replace(f'#{i+1}', match.group(i+1) or '')
                    
                    # Process I/O ops
                    final_repl = ""
                    i = 0
                    while i < len(repl):
                        if repl[i:i+2] == "!!":
                            print(self.string)
                            self.output += self.string + "\n"
                            i += 2
                        elif repl[i] == "!" and i+1 < len(repl):
                            print(repl[i+1], end='')
                            self.output += repl[i+1]
                            i += 2
                        elif repl[i] == "?":
                            if self.input_buffer:
                                final_repl += self.input_buffer.pop(0)
                            else:
                                final_repl += input("Input: ")[0]
                            i += 1
                        elif repl[i:i+5] == "!HALT":
                            return
                        else:
                            final_repl += repl[i]
                            i += 1
                    
                    # Apply replacement
                    self.string = self.string[:match.start()] + final_repl + self.string[match.end():]
                    applied = True
                    break
            
            if not applied:
                break
        
        print(f"\nFinished in {step} steps")

# Example usage
program = """
INIT: "start"
RULES:
start -> !H!e!l!l!o! !W!o!r!l!d!! !HALT
"""

interpreter = ReWriteInterpreter(program)
interpreter.apply_rules()

More Interpreters

Welcome everyone to add more interpreters!