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.