source: doc/proposals/iterators.md @ 8baa40aa

ADTast-experimentalpthread-emulation
Last change on this file since 8baa40aa was 8baa40aa, checked in by Andrew Beach <ajbeach@…>, 2 years ago

First draft of new iterator proposal.

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