# 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 as n a's.