Sonata

Sonata is a string-rewriting language by User:Afarnen.

Language overview

All program data is represented as a single string. This string is repeatedly manipulated in a deterministic fashion according to rewriting rules of the form

lhs->rhs

A single step of computation rewrites the string according to the first applicable rule. If no rule can be applied to the string, the program halts.

Note that the left-hand side of a rule must match the entire string, not just a substring. For example, the rule

apple->orange

transforms "apple" into "orange", but not "1apple2" into "1orange2".

There are two types of variables that can appear in a rule, s-vars and m-vars. An s-var stands for any single character and is written by prepending a "^" to any character, while an m-var stands for any substring of zero or more characters and is written by prepending a "_" to any character. For example, the rule

^A_B->^A^A_B

duplicates the first character in a string. Here "^A" represents the first character, and "_B" represents the rest of the string.

M-vars are bound to substrings left-to-right, and always match the shortest possible substring so that the left-hand side matches the entire string. For example, the rule

_Aa_Bb->_A,_B

transforms "aabb" into ",ab" and not "a,b".

A Sonata program is simply zero or more rules written on separate lines. Rules are searched from top to bottom. A program's input is the initial value of the string to be rewritten, and its output is the final value of the string if the program halts.

Turing completeness

Sonata can trivially emulate any m-tag system. Since the set of all m-tag systems (for any m>1) is Turing-complete, Sonata must also be Turing-complete. For example, the program

a^X_Y->_Ybc
b^X_Y->_Ya
c^X_Y->_Yaaa

emulates the 2-tag system

a -> bc
b -> a
c -> aaa

which computes the Collatz sequence for some number n, written in unary using a's.