[8baa40aa] | 1 | Iterators |
---|
| 2 | ========= |
---|
| 3 | This is the proposal for adding iterators to Cforall and the standard |
---|
| 4 | libary. Iterators provide a common interface for sequences of values in |
---|
| 5 | the language. Many inputs and outputs can be described in terms of sequences, |
---|
| 6 | creating a common interface that can be used in many places. |
---|
| 7 | |
---|
| 8 | Related Traits |
---|
| 9 | -------------- |
---|
| 10 | There are two groups of types that interact with this proposal. |
---|
| 11 | |
---|
| 12 | Iterator |
---|
| 13 | |
---|
| 14 | An iterator has a very simple interface with a single operation. |
---|
| 15 | The operation is "get the next value in the sequence", but this actually has |
---|
| 16 | several parts, in that it has to check if there are move values, return the |
---|
| 17 | next one if there is, and update any internal information in the iterator. |
---|
| 18 | For example: `Maybe(Item) next(Iter &);`. |
---|
| 19 | |
---|
| 20 | Now, iterators can have other operations. Notably, they are often also |
---|
| 21 | iterables that return themselves. They can also have a veriaty of iterator |
---|
| 22 | transformers built in. |
---|
| 23 | |
---|
| 24 | Iterable |
---|
| 25 | |
---|
| 26 | Anything that you can get an iterator from is called an iterable. There |
---|
| 27 | is an operation to get an iterator from an iterator. |
---|
| 28 | |
---|
| 29 | Range For Loop |
---|
| 30 | -------------- |
---|
| 31 | One part of the language that could be reworked to make good use of this is |
---|
| 32 | for loops. In short, remove most of the special rules that can be done inside |
---|
| 33 | the identifer and make it a generic range for loop: |
---|
| 34 | |
---|
| 35 | ``` |
---|
| 36 | for ( IDENTIFIER ; EXPRESSION ) STATEMENT |
---|
| 37 | ``` |
---|
| 38 | |
---|
| 39 | The common way to implement this is that expression produces an iterable. |
---|
| 40 | The for loop gets an iterator from the iterable (which is why iterators are |
---|
| 41 | often iterables, so they can be passed in with the same iterface) and stores |
---|
| 42 | it. Then, for each value in the iterator, the loop binds the value to the |
---|
| 43 | identifier and then executes the statement. The loop exits after every value |
---|
| 44 | has been used and the iterator is exausted. |
---|
| 45 | |
---|
| 46 | For the chained for loop (`for (i; _: j; _)`) can still have its existing |
---|
| 47 | behaviour, advancing through each range in parallel and stopping as soon |
---|
| 48 | as the first one is exausted. |
---|
| 49 | |
---|
| 50 | Ranges |
---|
| 51 | ------ |
---|
| 52 | Ranges, which may be a data type or a trait, are containers that contain |
---|
| 53 | a sequence of values. Unlike an array or vector, these values are stored |
---|
| 54 | logically instead of by copy. |
---|
| 55 | |
---|
| 56 | The purpose of this container is to bridge the new iterator iterfaces with |
---|
| 57 | the existing range syntax. The range syntax would become an operator that |
---|
| 58 | returns a range object, which can be used as any other type. |
---|
| 59 | |
---|
| 60 | Library Enhancements |
---|
| 61 | -------------------- |
---|
| 62 | There are various other tools in the library that should be improved. |
---|
| 63 | The simplest is to make sure most containers are iterables. |
---|
| 64 | |
---|
| 65 | Also, new utilities for manipulating iterators should be created. The exact |
---|
| 66 | list would have to wait but here are some examples. |
---|
| 67 | |
---|
| 68 | Transformers take in an iterator and produce another iterator. |
---|
| 69 | Examples include map, which modifies each element in turn, and filter, |
---|
| 70 | which checks each element and removes the ones that fail. |
---|
| 71 | |
---|
| 72 | Producers create new iterators from other information. |
---|
| 73 | Most practical iterators tend to be iterable containers, which produce all |
---|
| 74 | the elements in the container, this includes ranges. Others include infinite |
---|
| 75 | series of one element. |
---|
| 76 | |
---|
| 77 | Consumers take an iterator and convert it into something else. |
---|
| 78 | They might be converted into a container or used in a for loop. Dedicated |
---|
| 79 | consumers will be some form of folding function. |
---|
| 80 | |
---|
| 81 | Related Work |
---|
| 82 | ------------ |
---|
| 83 | Python has a robust iterator tool set. It also has a `range` built-in which |
---|
| 84 | does many of the same things as the special for loops. |
---|
| 85 | |
---|
| 86 | + https://docs.python.org/3/reference/datamodel.html#object.__iter__ |
---|
| 87 | + https://docs.python.org/3/library/functions.html#func-range |
---|
| 88 | |
---|
| 89 | C++ has many iterator tools at well, except for the fact it's `iterators` are |
---|
| 90 | not what are usually called iterators (as above) but rather an abstraction of |
---|
| 91 | pointers. |
---|
| 92 | |
---|
| 93 | Rust also has a imparative implementation of a functional style of iterators, |
---|
| 94 | including a great number of standard transformers. Otherwise, it is very |
---|
| 95 | similar to Python. |
---|
| 96 | |
---|
| 97 | + https://doc.rust-lang.org/std/iter/index.html |
---|