# Iterators

Iterators are generic and convenient ways to iterate over arbitrary elements in
a loop syntax. Iterator words are compiler words that use RS as a storage
mechanism, with "i" and "j" as convenience wrappers around RS+0 and RS+4. "i"
and "j" obey "to" semantics.

Another feature of iterators is that they're "guarded" against zero-iteration
overflow. That is, if you call an iterator with parameters that should result in
no iteration taking place, then no iteration takes place (with the naive
implementation, there's always at least one iteration).

Here's an example:

  : foo 5 for i . next ;

This translates naively to:

  : foo 5 >r begin i . to1- i i not until rdrop ;

The actual result is not this because there's zero guards and the whole thing
is compiled in efficient HAL [doc/hal] but the basic idea is there.

## Using iterators

Before diving into the gory details of creating new iterators (because that's
what's great about them: it's easy to create new ones), let's see how to use the
two iterators that are built-in: "for" and "for2".

"for" takes a single argument and counts down to 0 from that argument. In the
loop body, you can refer to the value-like word "i":

  : foo 5 for i . spc> next ;
  foo --> prints "5 4 3 2 1 "

The "next" word closes all iterators, not just "for".

"for2" takes 2 arguments, a "high" number and then a "low" number and counts
from "low" up to "high". "i" gives the counter, "j" gives the upper limit.

  : foo 12 18 for2 i . spc> next ;
  foo --> prints "12 13 14 15 16 17 "

## Breaking

It's a common pattern to break from an iterator early. To exit the loop early,
you can use the "break" word (again, an immediate). This words de-allocates any
RS space used by the iterator and jumps outside of it. Example:

  : foo 5 for i . i 3 = if break then next ; foo --> prints "543"

Because break jump are "out of band" with other structured jumps (that is, they
don't obey "clean nesting" rules), they can't use PS directly, so they use
a global variable. This means that:

1. There can only be one "break" per "next" loop.
2. A break cannot appear before a nested "next" loop, otherwise it's the nested
   loop that's going to process the "break" and it won't have the expected
   results.
3. These limitations are compile time ones, which means that "break" works fine
   when the loop calls a word that has a "next" loop inside it.
4. Break only works in "next" loop, not other loops.

It's also useful to know, once we're outside the loop, whether the loop has
exited through breaking or through exhausting its iteration source. For this,
there's "broke?", which yields 1 if the previously executed next loop exited
through "break", 0 otherwise.

## Creating iterators

An iterator is an immediate word that has no compile time parameters and
arbitrary runtime parameters. This word has multiple roles:

1. Compile RS allocation and initialization.
2. Yield a target address for "next"'s backward jump.
3. Compile iteration code which contains an "exit jump".
4. Yield a word to execute that compiles RS cleanup.

The immediate signature of such word is ( -- tgt exit-jmp [clean,] ).
Let's use "for"'s implementation as an example:

  : for ( -- tgt exit-jmp [clean], ) ( Runtime: n -- )
    1 i) +, [compile] >r here
    -1 RSP) +n, 0 Z) branchC, ['] rdrop ; immediate

As you notice, most of the words here are compiler words, that's because it's
what we do: we *compile* a loop, not implement one.

The first thing we do is add 1 to "n" and then send it to RS. That's
initialization.

Then, with "here", we yield "tgt", which is where "next" will jump back.

Then, we compile a decrease of 1 for RS+0 along with a conditional branch for
when RS+0 reaches 0. That jump will lead to after the backward "next" jump,
right before the compiled cleanup.

Lastly, we yield a pointer to a "cleanup" word that the "next" immediate will
compile right after our exit jump.

So that's it, that's how you create a new iterator!

## Zero-guard

You might find it peculiar that iterator conditional jumping is done in a
forward fashion. That's so that we can guard against the "zero iteration" case.

If the conditional jump went backwards, there would always be at least one
iteration.

This means that the initialization phase of your iterator needs to mangle with
its argument to add a "ghost" step to be ran before the first iteration is done.

This is why, in "for", we add 1 to the input argument.

## i and j

"i" and "j" are value-like words (obey "to" semantics) that live on RS. They
work a lot like local variables, but their offset is calculated from RS top
rather than from [rcnt]. "i" lives at RS+0 and "j" lives at RS+4.

We use RS for those variables for multiple reasons:

1. Yielding on PS makes PS management awkward for the iterator consumer. It's
   unclear what is PS status when the iterator ends.
2. Having individual iterators define their own global values could work, but if
   one wants to support nesting, the iterator has to preserve values through RS.

The easiest and simplest way to be directly on RS through i and j.
