Guide: Iterators

(Work in progress...)

One of Alice's more powerful concepts is that of iterators, inspired by Befunge 98's k, which repeats the next command n times. This concept has been slightly generalised with an iterator queue and two different kinds of iterators in Alice. The relevant command is &:

• In Cardinal mode, it pops an integer n which is used as a repetition iterator. It's similar to Befunge's k in that it repeats a command n times.
• In Ordinal mode, it pops a string s which is used as a folding iterator. This one repeats a command once for each character in s, but before doing so it pushes that character to the stack. This folds the command over the string s from the left. (Some languages use the term "reduce" instead of "fold".)

The iterator queue comes into play when multiple iterators are added before one can be used (this can in fact only happen when iterators are themselves applied to &). Whenever & is used, the iterator gets added to the end of the iterator queue (which is usually empty). Whenever a command needs to be executed, an iterator gets dequeued and is used to determine how that command should be repeated (if the queue is empty, it's treated as if it contained a single 1 iterator, so the command is executed once).

There is one other way to modify the iterator queue and that is with the skipping commands, # and $. These put a 0 iterator at the front of the queue (unconditionally and conditionally, respectively), so they will skip a command before looking at any further iterators.

It's important that we're talking about commands in the above paragraphs, because a few cells are not considered commands, in particular /\_|. Since the first two change Alice's mode, this means that both repetition and folding can be used in either mode on any command. That leads to a lot of non-trivial interaction between iterators and the various available commands. This guide is meant to act as a reference for all the possible effects of iterators.

Repetition: Basics

Whether a repetition iterator is applied to a Cardinal or Ordinal command doesn't make a big difference, since these iterators don't add any data that might need to be converted.

Note that negative repetition iterators are treated as zeros. So really, an iterator n means that the affected command is executed max(0, n) times.

Since 0 iterators skip a command, & can also be used to execute commands conditionally. If you know that the argument of & is either 0 (or negative) or 1, this can be used to execute the command only if the value is 1. That makes it similar to $, but there are a few crucial differences:

• $ will execute the next command if its argument is negative, whereas & won't.
• $ will execute the next command only once even if its argument is greater than 1.
• & enqueues the iterator while $ puts it at the front of the queue. This only makes a difference if the queue isn't empty to begin with, which is a fairly rare situation, but when one does work with iterator chains, this should be kept in mind.

Otherwise, & is generally used for its intended purpose of repeating a single command a set number of times.

Two important classes of operators here are unary and binary operators.

On unary operators with one output, the top of the stack is simply transformed n times.

On binary operators with one output, repetition essentially implements a folding operation form the right. The top n+1 stack elements are folded into one, going from the top to the bottom.

Folding: Basics

For folding, it does make a difference whether the iterator is used in Cardinal or Ordinal mode, because Cardinal mode will attempt to convert the current character before applying each iteration of the current command.

But before we get to that, note that folding operators can also be used to skip commands by using the empty string, "", as an iterator. This will lead to the relevant command being skipped in either mode. But note that using a non-empty string will not be equivalent to any form of $ because it will push at least one character to the stack before executing a command.

For further basic usage notes of folding, we need to look at the mode it's used in.

Folding in Ordinal mode

This is the more straight-forward case, since we're using a string-based iterator in the string-based mode. Alice will simply go through the iterator character by character, push that character, and then execute the command.

If the command is binary (i.e. it uses two operands from the stack), we get the usual left-folding (or reducing) behaviour the iterators get their name from. But for other kinds of commands, we actually get different kinds of useful iterator behaviour.

If the command is unary, we essentially map the command over the string by applying it to each character individually. But note that the string is split up into its individual characters in the process. If we remember the string length up front, we can join them again at the end. To be fair, there aren't a lot of useful unary commands that don't operate on each character anyway, but as an example we can use g to use each character as a label on the grid and replace it with the diagonal after it:

/
 i           \?t&/
  .         g     *
   !       &       o
    /[e)q!\         @

Try it online! (The digits are merely there to show the diagonals being returned.)

If the command is nullary (it pops no arguments, e.g. the constants a and e, the escape command ', leaving string mode with " or pushing the current date and time with T), this interleaves the characters of the string with the output of the nullary command.

For other commands (e.g. ternary or variadic commands), details will be discussed for each command individually below.

Folding in Cardinal mode

Folding in Cardinal mode is a bit trickier. Most Cardinal commands pop one or more values from the stack first, which causes Alice to convert strings on top of the stack implicitly to integers. In particular, if the strings on top of the stack don't contain any digits, they're simply discarded. So the characters of a folding iterator might be discarded completely by such commands.

We can distinguish three important cases for these kinds of commands:

• If the string contains no digits whatsoever, none of the characters will survive. In this case, the iterator is effectively equivalent to a repetition iterator of the length of the string. E.g. folding h over "abc" will add 3 to the top of the stack.
• If the string contains only digits, each digit will be converted to its numerical value, and we get the usual folding operation, but over these small integers instead of characters. E.g. folding + over "123" will add 6 to the top of the stack.
• If the string contains both digits and non-digits, we get a weird mixture of these two behaviours: whenever there's a digit, this digit will be pushed and the command will run on it. But then the command will be repeatedly applied again for each non-digit to the current state of the stack. E.g. folding h over xx1xxx3xx will add 2 to the top of the stack and then push 5 (= 1+4) and 6 (= 3+3).

Apart from this, the above considerations for unary and binary commands apply in Cardinal mode as well when folding over strings of digits.

Iterating Iterators

The most complex behaviour you can obtain from iterators is to run & itself when an iterator is already in the queue, as this is the only way to get multiple iterators into the queue at once. There are four cases to distinguish:

• Repeating Repeat: If we have && in Cardinal mode, the second & will be repeated according to the first. This means that the first & determines how many repetitions we want to enqueue, and the second one enqueues those. If our stack is (..., 2, 0, 5, 3) from bottom to top, and we run &&abc, this will execute a five times, skip b and execute c twice.
• Repeating Fold: This is basically the same as the previous case, only that multiple strings will be popped to enqueue several folding iterators.
• Folding Repeat: Folding Cardinal & over a string containing digits, is similar to using && in Cardinal mode. We simply end up enqueuing each digit as a separate iterator. The main difference is where we get those individual iterators from and that we don't need to explicitly determine the number of iterators we want to enqueue. Folding it over a string that contains a mix of non-digits and digits, will enqueue a mix of digits from the string and integers from the stack.
• Folding Fold: Using && in Ordinal mode enqueues each character of the string as a separate iterator. For example if the stack holds the string "XYZ" and we execute &&abc, we will push "X" before running a, "Y" before running b and then "Z" before running c. The usefulness of this is likely limited to very specific situations but it can help simplify some stack manipulation, since we can abuse the iterator queue as temporary storage of the individual characters.

Of course, it's also possible to chain more than two &, but the situations where this is useful will be very rare and figuring them out is left as an exercise to the reader.

When we're talking about combining iterators, we should also mention # and $ again. Repeating # skips the next n commands (even if there are further iterators enqueued). Repeating $ will pop n values and skip one command for each falsy value among them. Folding over these is also possible but probably less useful (in particular, folding over $ in Ordinal mode does nothing at all, except consume the iterator).

Idempotent Commands

Some commands are idempotent, which means that the effect of executing them repeatedly is the same as executing them once. The canonical example of an idempotent operation is probably taking the absolute value of a number.

These are clearly special when talking about repetition, but it also means there's less to talk about. Using repetition on them doesn't lead to any new behaviour, but it makes repetition even more useful for conditional execution. In these cases, the command gets executed for a positive argument and doesn't for a non-positive one.

• Idempotent Cardinal commands: @<>^vKHluDbs. c is idempotent unless its argument is 1.
• Idempotent Ordinal commands: @<>^vKHmluDcfUbrs.

Involutions

Another important class of operations are involutions, or self-inverse functions. These are functions which undo themselves. In other words, when the operation is executed twice, the effect is the same as not executing it at all. A basic example is to multiply a number by -1.

In the context of repetition, these are special because every other iteration simply cancels the effect. So using repetition on such an operation will only execute it if the iteration is odd and positive.

• Involutions in Cardinal mode: ~RN. n becomes an involution after the first application.
• Involutions in Ordinal mode: ~QRN. n becomes an involution after the first application.

Repeated data

Some of the simplest commands are those that take no input and push some value to the stack. Primarily, those include the digits 0 to 9 in Cardinal mode, the constants a and e (10, "\n", and -1, "", respectively), escaped cells 'x and string mode "...". Using these with a repetition operator does the obvious thing, which can be quite useful: it pushes that many copies of this value.

There are a few other commands which work like this though. ? retrieves the current cell or string from the tape and repeating it pushes the value that many times. q retrieves the current tape position or the entire tape joined into a single string. M in Cardinal mode pushes the number of remaining command-line arguments. The duplication operator . sort of falls into this category as well, since repeating it will push the same value once for each iteration (just that the value itself is read from the stack).

Finally, there are a few commands which also push a value without popping one, but which can or will push different values if repeated:

• T in Ordinal mode will repeatedly push the current time. If you repeat it often enough this process will take enough time that the actual string can change in the process. There's probably no reasonable use case for this though.
• M in Ordinal mode pushes and consumes a command-line argument. That means repeating M will push consecutive arguments.
• d in Cardinal mode pushes the stack depth. If you repeat it, this takes into account the value you just pushed, so the values will actually increment. That means if the stack initially contains m values and you iterate d n times, you'll get an integer range from m to m+n-1. This can be potentially useful if you can manipulate the stack depth to your needs.
• d in Ordinal mode pushes the concatenation of the entire stack. Again, repeating this will take into account what the previous iteration pushed. That means, on each iteration, the string is doubled. If the stack originally contains "ab", 12, "!", the first d gives "ab12!", the second one gives "ab12!ab12!", the third one "ab12!ab12!ab12!ab12!" and so on.

Of course, all of these commands can also be used with folding iterators. In the case of the first class of commands above, these simply interleave copies of the pushed value with the characters of the string that's being folded over. The most notable case is probably Cardinal d whose values will now increase by 2 on every iteration (again, interspersed with the characters from the string). Either way, I expect the usefulness of these folding operations to be very limited.

Repetition and the return address stack: simple loops

The return commands kKwW can be used quite effectively with repetition to build simple loops for a given number of iterations.

Using &w pushes the address of the w to the return address stack n times. If you later use k it will pop one of those copies from the return address stack and return to the w (without executing it again). That means if we have &w...k, the ... will be executed n+1 times before the return addresses are depleted. If the return address stack was initially empty, then the k will simply become a no-op at the end. If you were already using the return address stack, because you're inside a subroutine, you should wrap the loop in its own subroutine, so that the final k simply exits that inner subroutine without consuming a return address you wanted to use elsewhere.

Inside the loop, we can also make use of &k, K, &W or W to modify the number of iterations dynamically during the loop. Want to skip one iteration? Discard a return address from the stack with W or 2&k. Want to extend the loop by an iteration? Move to the next iteration with K instead of k.

Remember that the return address stack stores no information about the direction of the IP, so make sure that the IP points in the same direction at the beginning and end of a loop iteration. However, if you make deliberate use of a changing direction, you can actually implement a loop that cycles between two (or three) different loop bodies on each iteration:

...number of iterations...&w...even iteration...v
                           .                    k
                           >...odd iteration...k>...end of loop...

Extending this to three loop bodies is left an exercise to the reader.