Snowflake

Snowflake is a reversible, self-modifying, data-parallel esoteric programming language created by User:ais523 in 2013. Its most notable unusual feature is that unlike most self-modifying languages, both the program and interpreter modify themselves during execution, and the changes to both the program and interpreter overwrite the original files, permanently changing what will happen the next time that the program runs. As such, a program and interpreter grow together over the course of many executions, becoming more and more specialised to each other; the ultimate goal of a Snowflake programmer is to produce a program that will eventually (given enough time and luck) optimise itself down to a single command, that has the same effect that the original program did.

Snowflake was inspired by a large number of languages, although Burro is quite notable as an inspiration (and TMMLPTEALPAITAFNFAL and Java2K should be mentioned too, because the author was disappointed with those languages' execution of their ideas and felt that it was possible to do better), and also has quite a few peculiarities of its own, even beyond the almost literal interpretation of being a self-modifying language. The name comes from the common belief that no two snowflakes are the same.

Syntax and data model

In Snowflake, there are two data types. A list can be empty, or contain any number of polarized lists. In a program, a list is written by enclosing its contents in square brackets: [] is an empty list, for instance. (No delimiter is required between the elements, because there is never ambiguity; however, whitespace can be used between list elements for clarity.) A polarized list is a list with a polarity attached, either positive or negative; this is notated via writing + or - before the list. So for instance, +[+[]-[]] is a valid polarized list (a positive list, whose elements are an empty positive list, and an empty negative list).

As an abbreviation, a list consisting entirely of +[] elements can alternatively be written simply by writing the number of elements in the list, in decimal. So for instance, +3 means +[+[]+[]+[]], and -2 could also be written as -[+0+0]. This is purely an abbreviation and has no effect on semantics, although interpreters are expected to optimize such lists internally, via storing only the length rather than the entire list.

A Snowflake program is simply a list, written using the normal syntax for lists (except that the [] surrounding the list can be omitted if desired); it should be stored in files encoded in ASCII (more complex encodings are unnecessary due to the highly limited character set). There is no facility for entering comments, due for the tendency for documentation to get out of date quickly. (The program must be stored in a disk file or similar permanent storage, or it is not a valid Snowflake program. Likewise, an interpreter must also be stored in a disk file or similar permanent storage; and it is impossible to write a Snowflake compiler, due to the possibility that the compiler would be deleted before the program was run (thus leaving the program with no implementation to modify). This is not a major problem, because even if there were not a requirement to write the modifications back to disk, it's hard to see how to write a compiler that does not simply bundle an interpreter anyway.)

During execution, a Snowflake program has a number of threads. There is only one instruction pointer, and it is shared by all threads; however, each thread has its own storage, a single list called its stack; the front of the list (left on the page when written down) is called the top of the stack, and the back of the list is the bottom. (The stack is normally used like a traditional stack, pushing elements onto the top and popping them from the top; however, there are exceptions.) Each thread can be shiny, tarnished, shabby or decrepit, and typically has a parent, which is also a thread. (Threads effectively always have a parent: whenever a thread has no parent and its parent would become relevant, a new parentless tarnished thread with stack [+[+[]]] (i.e. [+1]) is created as its parent. As such, there is an effective column of tarnished thread stretching off into infinity.) Additionally, if threads share a parent, they have an order; it makes sense to refer to a thread's "first child", "second child", and so on.

Execution model

Snowflake execution proceeds in a number of cycles. On each cycle, each element of the program in sequence (from front to back) is interpreted as a command, and executed. There are no control flow operations within a cycle; each command always runs exactly once, in order. Each command that is not specifically for the purpose of manipulating threads runs on each shiny thread (and has no effect on the other types of thread); for instance, +1 pops -0 from the stack of each shiny thread that has -0 on top of the stack, and pushes +0 onto the stack of each other shiny thread. When interpreting a list element as a command, in most cases the contents of the list are irrelevant; all that matters are its polarity and length. For a given length, the command with that length and a positive polarity has the opposite effect of the command with that length and a negative polarity; in all cases, +n-n and -n+n each have no effect.

At the start of program execution, there is one shiny thread, with no parent, and one stack element: the program that is being executed.

At the end of each cycle, a random shiny thread is chosen, and the others are discarded (leaving the randomly chosen thread with no parents). (This is the only way to break reversibility in the language; all commands have an inverse, but the transition from one cycle to the next can be irreversible.) If there are no shiny threads, the program exits. Additionally, other things may happen based on the contents of the stack:

• If the stack has at least one element, the program is replaced (on disk, as well as in memory) with the top element of the stack (ignoring its polarity). (That element is not popped; it remains on the stack for the next cycle.)
• If the stack has at least two elements, and the second element (i.e. the element below the top element) is not +0, then I/O is performed:
  • If the second stack element has negative polarity, then one character in the system's encoding (as determined from command-line options, the system's environment LANG and LC_ALL variables, or via other system-specific means, and defaulting to Latin-1 with 0x0A as newline if no encoding can be determined) is read from standard input, and a positively polarized list is added to the end of the second stack element with a number of elements equal to the Unicode codepoint of that character, each of which is +0 (no element is added upon EOF or error);
  • If the second stack element has positive polarity and is nonempty (i.e. is not +0), then its first element is removed, and the character whose Unicode codepoint is the length of that list is output on standard output, using the system's encoding. (The element is not removed if there was an error trying to write it. Not that anyone is likely to check that error condition from within a Snowflake program, ever.)
• There is another effect that can occur if the stack has at least two elements (and which can be obtained without the need to do I/O via using +0 as the second stack element): the modification of the language that the Snowflake interpreter interprets. (The resulting language is still Snowflake, because it's interpreted by a spec-compliant Snowflake interpreter; just a different, and typically more useful, dialect than is implemented via a new interpreter.) The modifications are as follows:
  • An "abbreviated program" is constructed from the programs that ran on previous cycles (all the programs that ran since the last time the set of commands changed, or ever if the interpreter is still on the original set of commands): the programs are concatenated, then all no-op commands, such as +0, and any commands that have not been assigned a meaning yet, are deleted from the concatenation; and repeatedly, any two adjacent commands that have the same length but opposite polarity are deleted (unless they came from different cycles), until any adjacent pair of commands has either different lengths or else the same polarity. Thus, at the end of the first cycle, if the program is e.g. +3+4+0-2-100+[+0-0]-4-6+6+5, the abbreviated program would become +3+4-2+[+0-0]-4-6+6+5 (+0 and -100 are no-ops), then +3+4-4+5 (deleting the -2+[+0-0] and -6+6 pairs), then +3+5 (deleting the +4-4 pair).
  • Out of all the pairs of consecutive commands that exist in the abbreviated program (before replacement via the top stack element), the interpreter picks a random pair of adjacent commands, weighted towards pairs that appear more often. The probabilities are proportional to the square of the number of times each pair appears in the program; for instance, if the abbreviated program is +2+3+2+3, then there would be an 80% chance of picking +2+3 and a 20% chance of picking +3+2; +2+3 appears twice as often as +3+2, and thus should have 2² = 4 times the probability of being chosen. As an exception to this rule, a pair has no chance of being chosen if both commands in it have the same length.
  • A random element of this pair is chosen to be the new deprecated command. (It remains deprecated until a new deprecated command is selected via this mechanism.) If there was previously a deprecated command, it becomes the old deprecated command (and the previous old deprecated command ceases to be deprecated). Normally, both elements have equal probability of being selected as the deprecated command; as an exception, if one of the elements has length 1, it cannot be selected as the deprecated command, and the other element must be selected instead.
  • A length is chosen for a newly added command. If there is no old deprecated command, or if the old deprecated command is contained in the chosen pair, the length chosen is the lowest positive integer that is not currently being used for a command. There is a probability of (a³+b³)/(a+b+1)³, where a is the number of occurrences of the old deprecated command in the abbreviated program, and b is the number of occurrences of the most recently added command in the old program, that this length will be chosen even in other circumstances. Otherwise, the new command replaces the old deprecated command, removing the old deprecated command from the language entirely (except to the extent that other commands were defined based on its behaviour). (The idea behind the formula is as follows: if the program failed to adopt the most recently added command, it will likely be forced to adapt via the deletion of the deprecated command; if it abandoned the old deprecated command entirely, it clearly doesn't need it; but if it used a mix of the newly added command and the old, the interpreter should tend to avoid disrupting the situation.)
  • A new pair of commands (that are inverses of each other) is added to the language, represented by lists of the chosen length. One of the two new commands (i.e. negative or positive polarity with the chosen length), with polarity chosen randomly, has the same effect as the chosen pair had on the previous cycle; the other new command, with the opposite polarity, has the inverse effect (so, e.g., if the chosen pair was +2+3, then one of the new commands will have the effect that +2+3 had on the previous cycle, and the other new command will have the effect that -3-2 had, with polarities selected at random).
  • Finally, a new element is added to the bottom of the stack, indicating what changes were made: it has the same polarity as the top stack element and five elements, which are the old deprecated command, new deprecated command, first element of the chosen pair, second element of the chosen pair, and newly added command with the same semantics as the chosen pair, in that order. (Commands are expressed as a list of +0s with the appropriate length and polarity.) Additionally, the interpreter itself is changed so that it will forevermore interpret commands with the new meaning.

Here's a example, to make things clearer. Suppose the program that just executed is +2+3+2+0+3+4, and there is only one shiny thread, with stack [+[+2+3+2+0+4]+[+65]]; and that the most recently added command was +40 on the previous cycle (which is also the highest numbered command, because it happened to not replace a different command when added) and the old deprecated command is +2. The program is changed to +2+3+2+0+4; the abbreviated program, based on the program before the change, is +2+3+2+3+4, which gives a 1 in 6 chance of +3+4 being the chosen pair. If this pair is chosen, then the new deprecated command has a 50/50 chance of being +3 and a 50/50 chance of being +4. The program contained two uses of +2 and none of +40, giving an 8 in 9 chance that the new command will replace the old deprecated command +2; in that case, on the next cycle (and all future cycles until +2 gets replaced again), one of +2 and -2 (as well as all other lists with the same length and polarity) will have the same meaning as +3+4 had on the previous cycle (and still has this cycle), and the other will have the same meaning as -4-3 had. If the 1 in 9 chance of no replacement happens, then the new commands will be +41 and -41 instead, and +2 will continue to have its previous meaning for now (and quite possibly for a while, seeing as it is no longer deprecated). A capital A will be output to standard output; and if the newly added command with the semantics of +3+4 is -2, the new stack could be [+[+2+3+2+0+4]+0+[+2+3+3+4-2]].

Commands

Apart from length 1, all commands of the same length and polarity have the same effect (both the commands that exist with a freshly written Snowflake interpreter or a backup copy of one, and commands that are added over the course of program execution). Any lists that are sufficiently long that they are currently not defined as a command are no-ops as a command (but unlike +0 and -0, which are always no-ops, such long lists can end up gaining a meaning over the course of successive cycles of execution – at least, those which attempt to do I/O, in addition to those which just feel like helping their personal interpreter evolve).

New Snowflake interpreters understand the following commands (each of which has a name by which it can be referred to in conversation):

NOP (Length 0)

Does nothing, regardless of polarity. This command cannot be redefined (because it never appears in the abbreviated program). (+0 and -0 don't have different names as commands, because they both do the same thing, and neither does anything useful.)

LITERAL (Length 1, positive) / ILLITERAL (Length 1, negative)

This is the only command whose effect depends on the elements of the list that represents it, as well as the length. If the top element of the stack is equal to the (only) element of the command itself, except with the opposite polarity (for LITERAL) or including with the same polarity (for ILLITERAL), it is popped. Otherwise, the element of the command is pushed onto the stack (with its polarity reversed, in the case of ILLITERAL). (As with all commands that do not explicitly manipulate threads, these operations are carried out individually on each shiny thread.)

FUSE (Length 2, positive) / DEFUSE (Length 2, negative).

Nothing happens if the stack is empty. Otherwise, the top stack element is viewed as one long single list of the elements of its elements, with separators added to show the transition between one list and the next and which polarity those lists have (i.e. +[+[+1+2]+[-3+4-5]+[]-[+6]] is interpreted as +[(+)+1+2(+)-3+4-5(+)(-)+6]). For FUSE, each subsequence of the form +x(+)-y (for any lists x and y, whether or not they are composed entirely of +0) is replaced with +x-y; +x-y is replaced with +x(-)-y, and +x(-)-y is replaced with +x(+)-y. Then all the elements of its elements change polarity. Thus, FUSing +[+[+1+2]+[-3+4-5]+[]-[+6]] gives the list viewed as +[(+)-1-2+3-4(-)+5(+)(-)-6], which is +[+[-1-2+3-4]-[+5]+[]-[-6]]. DEFUSE works the same way with all the polarities reversed (i.e. it's the boundary between negative and positive elements of elements that matters, and (-) changes to no separator changes to (+); the DEFUSion of +[+[+1+2]+[-3+4-5]+[]-[+6]] is thus +[+[-1-2]+[+3]+[-4+5]+[]-[-6]].

SUMMON (Length 3, positive) / BANISH (Length 3, negative)

BANISH moves the top stack element down to the third position in the stack, letting the second and third elements move up nearer to the top. SUMMON moves the third stack element up to the top of the stack, pushing the first and second elements down. Neither has any effect unless the stack has at least three elements.

FORK (Length 4, positive) / SPOON (Length 4, negative)

These are Snowflake's thread manipulation commands: the only commands that don't affect all shiny threads equally, and the only commands that affect non-shiny threads. FORK behaves as follows:

• Each shabby thread becomes decrepit, and is given a shabby child thread with an empty stack (shabby and decrepit threads actually always have empty stacks);
• Each shiny thread becomes tarnished, and creates one or more child threads:
  • If the formerly shiny thread has an empty stack, or if its top stack element has no elements, it creates a single shabby child thread with an empty stack;
  • Otherwise, it creates one shiny child thread for each element of its top stack element (in the same order). These threads use those elements (minus polarities) as their stacks.

SPOON does the opposite:

• Each shabby thread is destroyed, causing its parent to become shabby if decrepit or shiny if tarnished;
• Each shiny thread is destroyed, causing its parent to become shiny. Its final stack is used to replace the matching element of the stack element of its parent, preserving polarity (e.g. when the shiny second child of a tarnished parent is destroyed, if the child's stack was [+2] and the parent's stack was [+[+1-3+4]+5], the parent's stack will become [+[+1-[+2]+4]+5]).

FORK…SPOON can be observed to have many similarities to the commonly used "map" primitive in functional programming. They can also be used as flow control to some extent (conditionally causing threads to become shabby, causing most commands to ignore them, effectively skips over sections of the program).

HOKEY (Length 5, positive) / COKEY (Length 5, negative)

Each of these performs two operations on the top stack element: segmented transposition, and ignorant reversal. The difference is that HOKEY does the transposition first, whereas COKEY does the reversal first. (Nothing happens if the stack is empty.)

Segmented transposition

The top stack element is interpreted as a sequence of segments of adjacent lists that have the same length and polarity. (For instance, +[+2+[+1-1]+2-4+4+4] would be interpreted as three segments, +[+2+[+1-1]+2 -4 +4+4].) Each segment is transposed; instead of x lists of y elements, it becomes y lists of x elements (and the same polarity), with the first new list being formed of the first element of each old list, and so on. The segmented transposition of +[+2+[+1-1]+2-4+4+4] is thus +[+[+0+1+0]+[+0-1+0]-1-1-1-1+2+2+2+2]. As a special case, if two adjacent segments have the same polarity, and either the same number of lists or the same number of elements per list, segmented transposition does nothing at all to any of the segments. (Segmented transposition can be seen to be self-inverse; the restrictions on when segmented transposition does anything mean that segments retain their identity as segments, and transposition is a self-inverse operation.)

Ignorant reversal

The top stack element is considered as a set of second-level elements fitting into a template that shows how they are arranged; e.g. +[+[+1+2]-[+3]+[]+[+4]] is seen as the elements +1 +2 +3 +4 and the structure +[+[??]-[?]+[]+[?]]. The elements themselves are reversed, ignoring the structure (which stays the same); then they are placed back into the structure in their new reverse order, giving (in this example) +[+[+4+3]-[+2]+[]+[+1]]. (Ignorant reversal can also clearly be seen to be self-inverse.)

HOKEY and COKEY are opposites, as is required for Snowflake commands. Their main use is in list manipulation; despite being very complex, they can typically be used to construct much simpler manipulations, such as duplicating or flattening lists, so long as such lists can be given an appropriate internal structure (e.g. by means of FORK). In fact, the complexity is something of an advantage; pretty much every aspect of HOKEY/COKEY behaviour can be exploited for some useful end or another.

KITTEN (Length 6, positive) / ANTIKITTEN (Length 6, negative)

KITTEN and ANTIKITTEN are sort-of Snowflake's "cons"/"uncons" commands; they often (but not always) serve the purpose of attaching elements to, or detaching elements from, the start of a list. The exact behaviour depends on the size of the stack and the size and polarity of the top stack element:

• If the stack is empty, KITTEN and ANTIKITTEN do nothing.
• If the stack has exactly one element, and the top stack element is negative for ANTIKITTEN or positive for KITTEN, the top stack element reverses polarity.
• If the top stack element is empty, and negative for KITTEN or positive for ANTIKITTEN, it reverses polarity.
• If the stack has more than one element, and the top stack element is negative for ANTIKITTEN or positive for KITTEN, then the second stack element is added to the start of the first stack element (removing it from the stack); e.g. KITTEN on a stack of [+[+1]+[+2]] makes the new stack [+[+[+2]+1]].
• If the top stack element is nonempty, and negative for KITTEN or positive for ANTIKITTEN, then its first element is removed and placed immediately below it on the stack.

Programming in Snowflake

There are two basic issues in writing a Snowflake program: one is to try to manipulate data in a desired way using its somewhat eclectic set of original primitives, and the other is to get the program to self-modify alongside the interpreter, such that it keeps working even after the changes. (A Snowflake program can be considered to be of a better quality if it attempts to shorten itself through changes, rather than taking the easy way out and continuously lengthening.) It should be noted that if an idiom is frequently used throughout Snowflake code, it will tend to become shorter over time as new commands are defined containing parts of it, and eventually may even reach status as a new command of the language itself. (This is intentional in the design of Snowflake.) Thus, a Snowflake interpreter that has already been used somewhat will be more useful than the original for writing new programs, in addition to simply running the program it grew up with, and will even have moulded somewhat to the personality of the programmer who uses it. However, as a result, old Snowflake programs will typically suffer from bitrot. This is another reason to attempt to write high-quality programs, besides style points; they will not only increase the chance of new commands being added (rather than replacing old ones), but be shorter and easier to update to the new version of the language. (A particularly devious program may even attempt to undo accidental "damage" to the language, by aiming to manipulate the probabilities cause particular commands to be deprecated and particular replacements to occur for them; note that this process must be automated, because attempting to produce output to let the user know which changes may be made will make it too late for the user to act on that information.) The ideal end goal, where each program is only one command long, will lead to no further changes to the language occurring, because they are unnecessary; the language will have perfected itself.

Snowflake is carefully designed such that random command drift will never make it impossible to implement something that could have been implemented in a previous version of the language. If a command gets replaced, its semantics still live on in some other command; they're combined with a different command, but that command can be reversed. So, for instance, if a new command +8 has the semantics of +2+3 and then +2 and -2 get deleted, it will still be possible to FUSE via +8-3, which before +2 was deleted would have been +2+3-3. This is the main design reason for making Snowflake reversible: so that just as data is never lost in a reversible language, commands are never lost if you can reverse the extra behaviour they gained. This further explains why Snowflake has no loop constructs apart from cycle boundaries (an infinite loop is not reversible), and no "eval" except for program modification at a cycle boundary (it's too easy to construct an infinite loop with one, Underload- or Muriel-style). There's another reason to avoid "eval"; if a new command is formed out of LITERAL+"eval", then it can change semantics if commands inside that literal change semantics, meaning that more than one command can change at a time, and previously useful commands can suddenly become useless without warning or replacement ­– far from perfect for a language that's attempting to reach perfection! Instead of potentially abusable looping constructs, FORK/SPOON are available as an interesting command that still allows commands to operate on all elements of a list, a very loop-like construct that nonetheless cannot go infinite. The command set in general is constructed to make it reasonably easy (but not too easy!) to write a Snowflake program to repair itself as the interpreter changes (in particular, it aims to make it possible to write a self-repair that runs in one cycle, which is why a FORK-like looping construct was required; FUSE/DEFUSE are also required for this purpose, because otherwise the program can't lengthen itself quickly enough to keep up).

There are various problems merely trying to use the primitives, too. Probably the biggest is that it is quite easy to construct operations which will work on most data, but fail on a small subset. For instance, trying to swap the top two stack elements using only SUMMON/BANISH simply doesn't work. It's easy if you add in LITERAL/ILLITERAL too (to create temporaries that can later be removed again), except if there's a specific value within the top two stack elements; then, you end up popping it by mistake, messing up which elements get manipulated. The obvious solution is to designate certain values that should never appear on the stack, and use those as the temporaries (-0 is a reasonably obvious choice, given that it's not useful in a program and won't ever be added to the stack during a cycle transition, although it is probably also a suboptimal choice due to its inverse +0 appearing pretty much everywhere); the problem is that such values may nonetheless end up appearing as the program attempts to self-manipulate to adapt to changes in the commands, because they tend to have to appear in the program in order to do their jobs. One solution that may be very effective is to attempt to get commands that push and pop them into the Snowflake vocabulary very early, without making them overwrite another command to do so; that way, there will be no need to mention them in order to be able to use them. That one change to the language seems to be a very high-priority change to aim for, because it makes things like a reliable swap idiom possible. The reason that there isn't a swap command in the language is actually precisely to discourage continuously working from a backup of a new interpreter, rather than aiming to produce an interpreter/program pair for a particular program. (Writing programs for new Snowflake interpreters is still interesting, though, especially when attempting to determine its computational class.)

However, there are still many tasks that can be undertaken simply using the original primitives:

Swap

If you know a specific value that isn't within the top two elements of the stack, you can swap them via adding extra elements as temporaries. Adding one element allows you to SUMMON the second stack element to the top; then adding another lets you SUMMON it below the two added elements (but still above the original top element), at which point you can just remove the elements again. Here's a swap that works if neither of the top two elements is -0:

+1+3+1+3-1-1

Escaping and reversing lists

It's very useful to be able to encase lists in extra +[] wrappers, because so many primitives operate on the list's elements, or even the list's element's elements, and because this gives certainty about the polarity of the top of the stack. By far the simplest way is to KITTEN the list into an empty list (again, this requires that we know that the top of the stack isn't -0):

+1+6

It's also useful to be able to escape the elements of a list individually. The basic way to do this is to escape the list as a whole, then HOKEY or COKEY (doesn't matter) the escaping onto the individual elements. One problem is that this reverses the order of the list, but you can simply do it twice, then unescape:

+1+6+5+1+6+5-6-1

Operating on stacks as lists (or vice versa)

Snowflake is technically a concatenative language. It doesn't really work much like, say, Underload, because it has no "eval" instruction; but the general concatenative principle of treating stacks and lists interchangeably still exists (say, to be able to reverse the stack via treating it as a list so that you can escape-HOKEY/COKEY it). FORK/SPOON might appear to be obviously intended to have the FORK come first, but for treating the stack as a list, using SPOON first is more useful:

-4+1+6+5+4

Now, the stack has been captured into a single list. This doesn't need any knowledge of the thread whose stack you presumably wanted to escape to work correctly. However, it does require there to be no shabby threads whose parents have nonempty stacks, it reverses the numbering of the threads (no real issue, just do it twice), and it moves some information about polarity into the wrong thread (some polarities from the parent threads will become positive, with the polarities from the parent threads ending up capturing the stack; this can also mostly be worked around simply via reversing the sequence later). The first problem is the largest one, but it should be easy to keep track of which threads you're using, especially because you're reset to one thread at the start of every cycle.

To go the other way, treating a list as a stack (e.g. so you can SUMMON it), just add an extra wrapper around the list (again, you need to know what the top element isn't), then FORK:

+1+6+4

You're in a different thread, but you have a 1-to-1 correspondence between threads after and threads before, so it doesn't really matter, and you have the entire stack of the new thread to mess around in without fear of disturbing the other stack elements of the thread you were previously in. (It's probably a good idea to undo the sequence once you're done.)

Duplicating lists

Snowflake doesn't actually have any primitives that can look arbitrarily deeply into a data structure, apart from LITERAL/ILLITERAL for comparing with literals (which is still not arbitrarily deep because it's limited by the literal itself), so it's impossible to duplicate arbitrarily nested lists within a single cycle. If you know a limit to how deeply your data structure can be nested, though, and don't care about preserving polarities on one of the copies, it's possible. The algorithm is built up recursively: the base case is that if you know a list has length 0, it's trivial to duplicate. So just "loop" over your list using FORK to duplicate each element, then HOKEY/COKEY your list of copies into a copy of lists (and reverse back into order, if necessary). This requires several layers of escaping/unescaping, but it's not that difficult. (Of course, this technique can be run in reverse to unduplicate lists, taking two identical lists back into one. This isn't particularly useful, though, and causes absolute chaos if the lists weren't actually equal.)

Flattening lists

Flattening lists is not a reversible operation, but that doesn't make it impossible to implement (at least, for flattening one level at a time). The basic idea is to create a list with the same length as the flattened list; then KITTEN it onto the list you want to flatten, and use HOKEY/COKEY to transfer all the elements from the non-flat list onto the new flat list via ignorant reversal. (You also need to stop the segmented transposition taking effect, or it will mess this up, but that can be accomplished via adding a few extra lists in between, e.g. +2+1+2+1.) Then, you just dispose of the original list somehow (most likely, via leaving it in a tarnished thread to get discarded at the end of a cycle). To create the new flat list, the basic technique is to do something similar to duplication, but to make a copy where all the elements are -0, rather than copies of the original elements; then you can change the first element of each list to +0 via using FORK/SPOON like a map operator, and FUSE all the small lists together into one big, flat list. This breaks down if any of the small lists have a length shorter than 2, because then they no longer have a +0(+)-0 boundary to fuse together. One possible solution here is simply to form an overlong flat list, then use -0 to pad out the extra elements and ensure (via wrapping with +0) that the elements that will end up in the flattened list are entirely made of positive lists. Then you can use FUSE or DEFUSE to carefully separate the useful elements from the padding.

Substitution

One very important task to be able to perform is to search a list for specific elements, replacing them with other specific elements, basically because doing that to the program is the easiest way to adapt it to changes in the commands. The simplest way is if you have literals for the search value and replacement; escape each element of the list, "loop" over the list with FORK, placing the replacement beneath the elements, ILLITERALing the value to replace above, then BANISHing once; this produces a list where the first element of each element forms the list that you want. The first list can then be separated from the rest of the list via extra escaping and ANTIKITTEN, allowing HOKEY/COKEY to group all the heads and all the tails together, providing the substituted list.

If you don't have literals to compare with, things get more complex. Probably the most fruitful approach is to compare polarity and length using HOKEY/COKEY; it's possible to produce contexts where the segmented transposition will fail if the polarity and/or length is different, such that the second element of the list will end up different depending on whether it succeeded or not.

Arithmetic

Snowflake appears to be capable of at least addition and subtraction, and multiplication and division by constants. Addition is basically just list flattening; for subtraction, you fill one list with +0, the other list with -0, do an ignorant reversal, then FUSE/DEFUSE to separate out the overlap from the non-overlapping bit (the difference between the numbers). Zero is a special case here, but one that's not particularly hard to handle. Multiplication by a constant can be implemented either with repeated addition, or more efficiently via map+FUSE; for division, you multiply the list by the number you want to divide by, then cut the product down to the size of the original list, and then undo the multiplication. (You even get a useful remainder this way!) Multiplying the lengths of two lists, where neither is a constant, is clearly impossible in a single cycle (because no command, and thus no string of commands, can increase the total number of list wrappers in existence by more than a constant factor, but no matter how large the factor is, there's some multiplication that would exceed it).

Computational class

There are basically two interesting computational-class-like questions to do with Snowflake. The most obvious, "is it Turing complete", misses the point to some extent; because Turing-completeness does not require I/O, it likewise can be done without the interpreter changing. (It's possible to do output of constant strings without the interpreter changing, too; the only command that's ever necessary in a Hello world program is LITERAL, and programs made entirely out of a single command cannot trigger changes to the language. However, doing this will cause the program to delete itself, and a program that does not run correctly the second time does not really count.) Still, Snowflake's primitives are bizarre enough that it's a non-obvious question; the most obvious method to show Turing-completeness if you're not taking advantage of cycle boundaries for anything other than loops is to try to implement a Minsky machine, but there may well be crazier alternatives involving something like a tag system instead.

Probably more interesting is the question "is it possible to write a program for a new interpreter to perform any Turing-computable calculation, with input and output, with probability X?" (where requiring a 100% probability, and just a nonzero probability, are both interesting; the nonzero probability corresponds to the case where there's an active attempt to force the interpreter down a certain path for the evolution of the language). In order to write such a program, it has to automatically adapt itself to the way the language evolves, using the top stack element to ensure that the program on disk always changes to match the interpreter. There are various harder versions of this problem, too (such as triggering an interpreter change every cycle even when there was nothing to input or output, and for really hardcore programs, disregarding the bottom stack element and attempting to deduce the changes to the language via experiment). A fun variation would be for the Snowflake interpreter to be able to feed not just the currently executing program, but all the other programs it had ever executed, to the currently running program, and allow it to update them to the new language standards as the language changed; this would probably require extreme measures (if it's even possible in general at all), due to the difficulty of determining whether any particular literal is being used as code or data or both.

Minimization is another common problem for esoteric programming languages. If, as seems likely, Snowflake is Turing-complete, the question arises of what commands could be omitted while still leaving the language Turing-complete. (Snowflake was not really designed as a Turing tarpit, but nonetheless has a remarkably small number of command-pairs.) SUMMON/BANISH seem like the most likely possibilities; and LITERAL/ILLITERAL is potentially possible (although it'd lead to a severe shortage of new list wrappers, you could still obtain them via transposition or in emergencies via SPOON or language changes). FUSE is necessary if you want to be able to get much done in a single cycle, because it's the only way to get a list that's longer than the longest currently existing list except via laboriously KITTENing one together (which only gives you a finite lengthening), and thus without it, there's a hard limit on how much increase in data structure complexity you can get per cycle. However, with infinite cycles, this may well not be a problem. KITTEN/ANTIKITTEN are the only sensible way to change the number of levels of escaping in a list, meaning that without them, FORK (which cannot distinguish the order of elements) would be the only way to get at the deeper levels of elements. That might not be a problem either, although it would probably require crazy wizardry with FUSE to get anywhere without them. The remaining commands are FORK/SPOON, which seem necessary to get much done within a single cycle (but again, there are infinitely many cycles, so…), and HOKEY/COKEY, which fulfil so many purposes that Snowflake programming would seem very different without them (or improved, evolved versions).