Sortle

Sortle is an esoteric programming language created by Scott Feeney in 2005 based on the concept of insertion sort. Programs consist of lists of named expressions, which are sorted and evaluated from top to bottom. Expressions have no side effects; the result of an expression becomes the new name of the expression, and the list's order is adjusted accordingly.
An expression that renames itself to "" (the null string) is deleted. An expression that renames itself to the name of another expression replaces that expression. When only one expression remains, its name is printed out to the user and the program halts. This is both the only way to end the program and the only form of output.
An expression can use (very limited) regular expressions to match names of other expressions. This is the only way of storing data in Sortle.
==Control flow==
Program code takes the form of a list mapping names to expressions, in the form:
 name := expression
The name/expression pairs are sorted in ASCII order, and the first one is evaluated, producing a string. This string becomes the new name of the expression, and the expression is re-inserted into the sorted list at the appropriate position. Then flow proceeds to the next expression, wrapping around if necessary.
When an expression would rename itself to the null string, it is deleted and said to have committed suicide. If an expression renames itself to the same name as another expression, it clobbers the second one, which is removed and replaced by the first.
Execution terminates when only one expression remains; its name is printed as output. Here is a hello program in this language:
 hello := ""
Since there is only one expression, its content is not significant because it is never evaluated. The program immediately halts, printing "hello". A "hello, world" program is slightly harder, but not much:
 quit := ""
 hello := "hello, world"
Since "hello" compares less than "quit", "hello" is evaluated first and renames itself to the string "hello, world". Then control passes to "quit", which deletes itself by renaming itself to the empty string. Only one expression is left, so its name, "hello, world", is printed, and the program halts.
==Expressions and values==
Expression evaluation is stack-based and runs left to right. Expressions contain literal strings and integers, which are pushed onto the stack, and operators. Each operator takes two values off the stack, does something with them, and pushes a single result. When evaluation is finished, there must be exactly one value on the stack. If numeric, it is converted to a string containing the number's value as rendered in decimal, with no more digits than necessary. Sortle is serious about not wasting digits: the number 0 converts not to "0" but to the null string, "".
Operators are as follows. Here op1 is the first value popped, while op2 is the second, from deeper down in the stack.
Operator	Operands (2)	Result 	Description
Numbers 	Number 	Adds op1 and op2	
* 	Numbers 	Number 	Multiplies op1 and op2
/ 	Numbers 	Number 	Divides op1 into op2 and returns a truncated result
% 	Numbers 	Number 	Divides op1 into op2 and returns the remainder
^ 	Strings 	String 	Provides whichever compares greater out of op1 and op2
~ 	Strings 	String 	Concatenates op1 onto the end of op2
? 	Strings 	String 	Does regex matching; see below
$ 	Strings 	String 	Returns "" if both strings are "", the string that comes later out of op1 and op2 if neither string is "", or the string that is not "", if one of them is ""
Literal strings appear in the source code within double quote marks. They can contain escapes in the form of \xx where xx is any hex code from 01 to ff; for example:
 "This is a \22string\22.\0a"
==Regexes==
To be written. Until then, see the spec under External resources.
==Computational class==
Sortle is Turing-complete because the Turing-complete language Bitwise Cyclic Tag has been implemented in it.
==Examples==
===Digital root calculator===
Replace the number 234567 on the first line with any positive integer to calculate its digital root.
 a := "+bca 234567" \
 "+bc" "(b).!" "" ? ~ \
 "b(c)0.!" "" ? "bc0(.)!" "" ? ~ \
 "b(c).0.!" "" ? "bc(.)0.!" "" ? ~ "bc.0(.)!" "" ? ~ \
 "(b)c...!" "" ? 9 "bc(.)..!" "" ? "bc.(.).!" "" ? + 8 + % 1 + ~ \
 "bc..(.)!" "" ? ~ \
 "(b)c.." "" ? 9 "bc(.)." "" ? "bc.(.)" "" ? + 8 + % 1 + ~ \
 ^ ^ ^ ~ \
 "bc(.)" "" ? ^ ^
 b := "+(bc)...!" "" ? "+bc..(.)!" "" ? ~
===Quine===
The definition of the fifth (and last) expression, q, has been wrapped for readability, but should be saved with the extra line breaks removed (or download quine.sort).
 z := "0" "qat(z).!" "" ? "qatz(.)!" "" ? ~ ^
 t := "s(t)..!" "" ? "st.(.)!" "" ? ~
 s := "z.!" "" ? "st" "t.!" "" ? "(q)z.!" "" ? "qz(.)!" "" ? ~ ^ ~ ^
 r := "z.!" "" ? "qz" "qa.(.)!" "" ? ~ ^
 q := "z.!" "" ? "qa" "q(z).!" 6 1 + ".!" ~ ~ "" ? "qz(.)!" 6 1 + ".!" ~ ~
 "" ? "\5c" "qz.!" 6 1 + "(.)!" ~ ~ "" ? ~ ~ ~ "q(z).!" 6 2 + ".!" ~ ~ ""
 ? "qz(.)!" 6 2 + ".!" ~ ~ "" ? "\22" "qz.!" 6 2 + "(.)!" ~ ~ "" ? ~ ~ ~
 "q(z).!" 6 3 + ".!" ~ ~ "" ? "qz(.)!" 6 3 + ".!" ~ ~ "" ? "\0a" "qz.!" 6
 3 + "(.)!" ~ ~ "" ? ~ ~ ~ "(t).!" "" ? "q(z).!" "" ? ~ "qz(.)!" "" ? ~
 "t(.)!" "" ? ~ "\22 ^ ^ ^ ^ ~ ^" ~ "a := 808 8qat(z).!8 88 ? 8qatz(.)!8
 88 ? ~ ^9t := 8s(t)..!8 88 ? 8st.(.)!8 88 ? ~9s := 8z.!8 88 ? 8st8 8t.!8
 88 ? 8(q)z.!8 88 ? 8qz(.)!8 88 ? ~ ^ ~ ^9r := 8z.!8 88 ? 8qz8 8qa.(.)!8
 88 ? ~ ^9q := 8z.!8 88 ? 8qa8 8q(z).!8 6 1 + 8.!8 ~ ~ 88 ? 8qz(.)!8 6 1
 + 8.!8 ~ ~ 88 ? 875c8 8qz.!8 6 1 + 8(.)!8 ~ ~ 88 ? ~ ~ ~ 8q(z).!8 6 2 +
 8.!8 ~ ~ 88 ? 8qz(.)!8 6 2 + 8.!8 ~ ~ 88 ? 87228 8qz.!8 6 2 + 8(.)!8 ~ ~
 88 ? ~ ~ ~ 8q(z).!8 6 3 + 8.!8 ~ ~ 88 ? 8qz(.)!8 6 3 + 8.!8 ~ ~ 88 ?
 870a8 8qz.!8 6 3 + 8(.)!8 ~ ~ 88 ? ~ ~ ~ 8(t).!8 88 ? 8q(z).!8 88 ? ~
 8qz(.)!8 88 ? ~ 8t(.)!8 88 ? ~ 8722 ^ ^ ^ ^ ~ ^8 ~ 8a" ^ ^ ^ ^ ~ ^
The core of this quine is the long string with all the 8s in it. This string consists of the letter "a" followed by all the code from the second character in the file, to the open quote and the "a" that begin this string, with the digits 7, 8 and 9 used to escape special characters. Expressions "s" and "t"/"st" hold this string unchanged with 7s, 8s and 9s intact, while expressions "q"/"qa" and "r"/"qz" loop through and replace all occurrences of these digits one by one (which is why the quine takes so long to run). Control flow can be understood via the following pseudocode:
 q/qa. line - if z(...) exists, clobber it - END
 else if qz(...)7(...) exists, rename yourself qaz(...)\(...) - MIDDLE
 else if qz(...)8(...) exists, rename yourself qaz(...)"(...) - MIDDLE
 else if qz(...)9(...) exists, rename yourself qaz(...)[newline](...) - MIDDLE
 else if qz(...) and t(...) exist, rename yourself qa(t)z(qz's ...)(t's ...)[tail] - PRE-END
 else init yourself to qaa plus a string with all code before the string, 789-escaped - INIT
 r/qz line - if z(...) exists, clobber it - END
 else, qa.(...) exists and you rename yourself qz(...) - INIT,MIDDLE
 s/st. line - if z(...) exists, clobber it - END
 else if t(...) exists rename yourself stt(...) - MIDDLE
 else if qz(...) exists rename yourself stq(...) - INIT
 t line - given st.(...) rename yourself to t(...), or suicide - END
 z/0 line - rename yourself "0", unless qatz(...) exists, then rename yourself z(...) - END
INIT actions occur first and prepare expression names for use in computation. MIDDLE actions perform the computation (replacing 7s, 8s, 9s). When the computation is done (i.e. there is an expression whose name holds the full program source code), END actions cause every expression to either clobber that result or commit suicide so that only the result is left.
These INIT, MIDDLE and END stages appear to be common to most Sortle programs.
==Deviations from spec==
According to a 2019 message posted on User:Graue's talk page by User:Qpliu, the Perl implementation deviates from the specification in the following ways, which might or might not be intentional:
The spec says that the initial names can only consist of letters. The implementation also allows numbers.
The spec says that numerical calculations are done modulo 4294967296. The implementation uses larger ints and accepts negative numbers. The fib.sort example calculates a number larger than 4294967296.
The spec says that matching "(f.n)!d" with "finfund" results in "fin". The implementation results in "finfun". Many of the examples, using (.)! rather than (.!), depend on this behavior.
==See also==
* Forte
* Muriel
==External resources==
* Interpreter with step-through debugger
* Sortle implementation in Perl
* Sortle standard document
* More examples in the Esoteric Files Archive
Category:Output only
Category:High-level
Category:Turing complete
Category:Implemented
Category:Languages
Category:String-rewriting paradigm
Category:2005