--- title: "Writing Custom Iterators" output: rmarkdown::html_vignette author: - Steve Weston (originally for package `iterators`) - Peter Meilstrup (adapted for package `iterors`) vignette: > %\VignetteEngine{knitr::rmarkdown} %\VignetteIndexEntry{Writing Custom Iterators} %\VignetteEncoding{UTF-8} --- ```{R echo=FALSE, results="hide"} library(iterors) ``` An _iterator_ is a special type of object that supplies data on demand, one element [^one] at a time. This is a nice abstraction that can help simplify many programs. Iterators are particularly useful in parallel computing, since they facilitate splitting a problem into smaller pieces that can then be executed in parallel. [^one]: An ``element'' in this case can be basically any object. I don't mean to suggest that the data is necessarily returned as scalar values, for example. Iterators can also be used to reduce the total memory that is needed at any one time. For example, if you want to process the lines of text in a file, it is common to write a loop that reads the file one line at a time, rather than reading the entire file in order to avoid running out of memory on huge files. That's the basic idea of iterators. Iterators provide a standard method for getting the next element, which allows us to write functions that take an iterator as an argument to provide a source of data. The function doesn't need to know what kind of iterator it is. It just needs to know how to get another piece of data. The data could be coming from a file, a database, a vector, or it could be dynamically generated. There are a number of iterators that come in the `iterors` package. The `iteror.array` method allows you to iterate over arrays, in much the same way as the standard `apply` function. `apply` has fixed rules on how the results are returned, which may require you to reshape the results, which can be inefficient, as well as inconvenient. But since `i_apply` doesn't process any data or combine the results, it is more flexible. You can use `i_apply` with the `foreach` package to perform a parallel `apply` operation, and combine the results any way you want via the `.combine` argument to `foreach`. Another iterator that comes in the `iterors` package is the `isplit` function, which works much like the standard `split` function. `split` returns a list containing all of the data divided into groups. `isplit` only generates one group at a time, as they are needed, which can reduce the amount memory that is needed. But of course, there will be times when you need an iterator that isn't provided by the `iterors` package. That is when you need to write your own custom iterator. Fortunately, that is fairly easy to do. ## What methods are needed for an iteror? Basically, an `iteror` is an S3 object whose base class is `"iteror"`, which has defined methods called `nextOr` and `iteror`. The function `iteror` is a generic method. The purpose of the `iteror` method is to construct an iterator for the specified object. For example, this makes an iteror `it` out of a list: ```{R iterable1} it <- iteror(list(1:2, 3:4)) ``` When `iteror` is called on a list (or any object without a class) it finds the method `iteror.default`, which constructs an iterator which returns one element at a time from the given vector. If `x` is already of class `"iteror"` then `iteror(x)` simply returns `x`, which seems odd at first. But the `iteror` method can be defined for other objects that don't define a `nextOr` method. We call those objects _iterables_, meaning that you can iterate over them. The `iterators` package defines `iteror` methods for vectors, lists, matrices, and data frames, making those objects iterables. By defining an `iteror` method for data types, you can pass those types directly to any function that expects an iterable. If you want to create an iterator for some existing class, you can do that by writing an `iteror` method that constructs an appropriate iterator. The alternative is to write your own function that takes arbitrary arguments, and returns an iterator. You can choose whichever method is most natural. The most important method required for iterators is `nextOr(obj, or)`. Given an iteror `obj`, this simply returns the next value, or forces and returns its second argument `or.` Returning the value of `or=` indicates that there are no more values available in the iterator. There is (by design) no default value for `or`; you need to specify one. Above we created an iterator from a list; we can now call `nextOr` on that iterator to get the values from the list: ```{R iterable2} nextOr(it, NULL) nextOr(it, NULL) nextOr(it, NULL) ``` This shows how `nextOr` behaves at the stop of iteration, returning whatever value was given to argument `or`. Here we specified NULL, but we will later see other ways to use the second argument. ## Handling the end of iteration In many situations, you will be dealing with effectively finite data, but data for which you don't necessarily know the length. So if you extract values one at a time from an iterator, you need to handle the case where there isn't a next value. This is where the `iterors` package improves on `iterators` by giving you a few options for how to respond to the end of iteration. ### Breaking out of a loop at end of iteration If you are consuming an iterator in a loop, the easiest (and often fastest) way to respond to the end of iteration so to break out of the loop. You just put a break directly in the second argument of `nextOr`. ```{R consuming_iter_break} x <- icount(10) repeat { print(nextOr(x, break)) } ``` Because the `or` argument is lazily evaluated, the `break` does not execute until `nextOr` evaluates its second argument. You can put any code into the `or` argument, which will come in useful below. ### Detecting end of iteration with a sentinel value Sometimes a break or return isn't the right action to take. As we saw above, `nextOr` will return its second argument (whatever that is) to signal end of iteration, when the iterator contains no more data. So you can check whether the returned value is the same as the one you provided, and interpret that as the end of iteration. ```{R consuming_iter} x <- icount(10) while (!is.null(val <- nextOr(x, NULL))) { print(val) } ``` Here, if `nextOr` returns `NULL`, the `while` loop will exit. A special value used like `NULL` is used above, is often called a _sentinel value_. #### Unsafe sentinel values It's popular to use `NULL` as a sentinel, but it's worth considering what would happen if there were an iterator that legitimately returns `NULL` as a value. For instance, this list contains some tricky values: ```{R bad_iter} bad_values <- list( quote(.StopIteration), NA, NULL, list(), simpleError("StopIteration"), try(stop("StopIteration", call.=FALSE), silent=TRUE), "", numeric(0)) ``` Suppose you iterate over this list using NULL as your end-of-iteration sentinel, like this: ```{R enum} it <- iteror(bad_values) while (!is.null(val <- nextOr(it, NULL))) { print(val) } ``` The enumeration stops early because it mistakes `NULL`, a legitimate value in the list that we are iterating over, for `NULL` the sentinel value. This is a general problem with the sentinel value scheme in dynamically-typed languages; any value you could use to signal a stop, could also be a legitimate value for an iterator to emit. #### Safe sentinel values A way to escape this problem is to construct a one-shot, _unique_ sentinel value to use locally, just with this iteror, and then throw away, not keeping it in your code. One easy way to do this by using `new.env()`. Consuming an iterator using a local sentinel value looks like this: ```{R consuming_sentinel} end_sentinel <- new.env() it <- iteror(bad_values) repeat { val <- nextOr(it, end_sentinel) if (identical(val, end_sentinel)) break print(val) } ``` Because environments compare by reference, a newly constructed environment is guaranteed not to be `identical()` to any other object in the R session, and the check for identity is very fast (just a pointer comparison.) By using a locally generated, unique sentinel value you avoid mistaking a legitimate value in your data for the end of iteration. ## A simple iterator It's time to show the implementation of a very simple iterator. Although I've made it sound like you have to write your own `nextOr` methods, you can use a standard one. In fact, that's what all of the following examples do. The method `iteror.function` takes a function you specify and wraps it in an object with class `iteror`, which has a `nextOr` method defined. Now here's a function that creates a very simple iterator, one that returns the same value `x` indefinitely.: ```{R iter1} iforever <- function(x) { nextOr_ <- function(or) x iteror(nextOr_) } ``` Note that I called the internal function `nextOr_` with an underscore, rather than `nextOr`. I do that by convention to avoid masking the standard `nextOr` generic function. That would cause problems when you want your iterator to call the `nextOr` method of another iterator, which can be quite useful, as we'll see in a later example. We create an instance of this iterator by calling the `iforever` function, and then use it by calling the `nextOr` method on the resulting object: ```{R runiter1} it <- iforever(42) nextOr(it, NULL) nextOr(it, NULL) ``` You can also get values from an iterator using `as.numeric`. But since this is an infinite iterator, you need to also give an argument `n` argument to avoid getting stuck in an infinite loop until you run out of memory: ```{R runiter1.part2} as.numeric(it, n=6) ``` Notice that it doesn't make sense to implement this iterator by defining a new `iteror` method, since there is no natural iterable to dispatch on; the argument 42 is just a vector of length 1 and `iterator.default` already handles that case. So instead, we implement this iterator by defining a normal function that returns the iterator. This iterator is quite simple to implement, and possibly even useful. [^3] The iterator returned by `iforever` is actually just the same function you provided, with the class `iteror` added. This means you get `nextOr` method already defined, whlch just delegates to your given function. Additionally since the returned object has class `iteror`, it inherits an `iteror` method that will return itself. [^3]: Be careful how you use this iterator! If you pass it to `foreach`, it will result in an infinite loop unless you pair it with a non-infinite iterator. Also, _never_ pass this to the `as.list` function without the `n` argument. Of course, the reason this iterator is so simple is because it doesn't contain any state. Most iterators need to contain some state, or it will be difficult to make it return different values and eventually stop. Managing the state is usually the real trick to writing iterators. ## A stateful iterator that stops Let's modify the previous iterator `iforever` to stop after it returns a certain number of values. I'll call the new function `irep`, and give it another argument called `times`: ```{R iter2} irep <- function(x, times) { nextOr_ <- function(or) { if (times > 0) { times <<- times - 1 x } else { or } } iteror(nextOr_) } ``` Now let's try it out: ```{R runiter2} it <- irep(7, 6) unlist(as.list(it)) ``` The differences between `iforever` and `irep` are in the inner function `nextOr_`. This inner function not only accesses the values of the variables `x` and `times`, but it also modifies the value of `times`. This is accomplished by means of the "`<<-=`"[^1] operator, and the rules of lexical scoping. [^1]: It's commonly believed that `<<-` is only used to set variables in the global environment, but that isn't true. I think of it as an _inheriting_ assignment operator.} After enough calls, the inner function will find `times <= 0`, and will return its argument `or`. As the author of an iterator this is how you signal end of iteration. When implementing an iterator you never need to do anything with `or` other than return it when appropriate; otherwise leave it alone, allowing R to be lazy in treating that argument. Technically, this kind of function that refers to enclosing variables is called a _closure_, and is a fundamental feature of `R`. The important thing to remember is that `nextOr_` is able to get the value of variables that were passed as arguments to `irep`, and it can modify those values using the `<<-` operator. These are _not_ global variables: they are defined in the enclosing environment of the `nextOr_` function. You can create as many iterators as you want using the `irep` function, and they will all work as expected without conflicts. Note that this iterator only uses the arguments to `irep` to store its state. If any other state variables are needed, they can be defined anywhere inside the `irep` function. ## Using an iterator inside an iterator The previous section described a general way of writing custom iterators. Almost any iterator can be written using those basic techniques. At times, it may be simpler to make use of an existing iterator to implement a new iterator. Let's say that you need an iterator that splits a vector into subvectors. That can allow you to process the vector in parallel, but still use vector operations, which is essential to getting good sequential performance in R. The following function returns just such an iterator: ```{R iter3} ivector <- function(x, ...) { i <- 1 it <- idiv(length(x), ...) nextOr_ <- function(or) { n <- nextOr(it, return(or)) ix <- seq(i, length=n) i <<- i + n x[ix] } iteror(nextOr_) } ``` `ivector` uses `...` to pass options on to `idiv`. `idiv` supports the `chunks` argument to split its argument into a specified number of pieces, and the `chunkSize` argument to split it into pieces of a specified maximum size. Let's create an `ivector` iterator to split a vector into three pieces using the `chunks` argument: ```{R runiter3} it <- ivector(1:25, chunks=3) as.list(it) ``` Note how our `nextOr_` function handles the end of iteration. If the underlying `idiv` iterator reaches the end, it will force its `or` argument, which we have specified as `return(or)`, Although it is forced by the underlying iterator, R correctly evaluates a `return` call in a lazy argument according to the scope that call was written in. So when `it` of the internal `idiv` reaches the end, and forces its `or` argument, our `nextOr_` passes that signal along by returning _its_ `or` argument. The `nextOr` method uses a lazy evaluated argument expressly for this purpose, so that you can respond to end of iteration by using a control flow operator like `return`, `break`, `next` or `stop`. It should be clear that only minor modification need to be made to this function to create an iterator over the blocks of rows or columns of a matrix or data frame. But I'll leave that as an exercise for the reader. ## A recycling iterator You can start to compose simple iterators together to do more complex things by writing functions that take in one iterator and construct a new one. In this example, we'll return an iterator that recycles the values of the wrapped iterator: [^2] [^2]: Actually, many of the standard `iteror` methods support a `recycle` argument. But this is a nice example, and a more general solution, since it works on any iterator. ```{R recyle} i_recycle <- function(it) { values <- as.list(iteror(it)) i <- length(values) nextOr_ <- function(or) { i <<- i + 1 if (i > length(values)) i <<- 1 values[[i]] } iteror(nextOr_) } ``` This is fairly nice, but note that this is another one of those infinite iterators that we need to be careful about. Also, make sure that you don't pass an infinite iterator to `i_recycle`. That would be pointless of course, since there's no reason to recycle an iterator that never ends. It would be possible to write this to avoid that problem by not grabbing all of the values right up front, but you would still end up saving values that will never be recycled, so I've opted to keep this simple. Let's try it out: ```{R recyleexample} it <- i_recycle(icount(3)) unlist(as.list(it, n=9)) ``` ## Limiting infinite iterators I was tempted to add an argument to the `i_recycle` function to limit the number of values that it returns, because sometimes you want to recycle for awhile, but not forever. I didn't do that, because rather than make `i_recycle` more complicated, I decided to write another function that takes an iterator and returns a modified iterator. Functions like this are _composable_; the limiting function can be applied to any underlying iterator instead of just `i_recycle`. ```{R i_limit} i_limit <- function(it, times) { it <- iteror(it) nextOr_ <- function(or) { if (times > 0) { times <<- times - 1 nextOr(it, or) } else return(or) } iteror(nextOr_) } ``` By convention, the `iterors` package uses the prefix `i_` for this kind of composing iterator function, and a bare `i` for functions that build an iterator based on basic data. Note that this looks an awful lot like the `irep` function that we implemented previously. In fact, using `i_limit`, we can implement `irep` using `iforever` much more simply, and without duplication of code: ```{R irep2} irep2 <- function(x, times) i_limit(iforever(x), times) ``` To demonstrate `irep2`: ```{R testirep2} it <- irep2('foo', 3) repeat { print(nextOr(it, break)) } ``` Here's one last example. Let's recycle a vector three times using `i_limit`, and convert it back into a vector using `as.numeric`: ```{R testi_recycle} iterable <- 1:3 n <- 3 it <- i_limit(i_recycle(iterable), n * length(iterable)) as.numeric(it) ``` Sort of a complicated version of: ```{R rep} rep(iterable, n) ``` Aren't iterators fun? ## Conclusion Writing your own iterators can be quite simple, and yet is very useful and powerful. It provides a very effective way to extend the capabilities of other packages that use iterators, such as the `foreach` package. By writing iterators that wrap other iterators, it is possible to put together a powerful and flexible set of tools that work well together, and that can solve many of the complex problems that come up in parallel computing.