Changeset 1f922f4

Timestamp:

Jul 23, 2024, 3:23:04 PM (4 months ago)

Author:

Andrew Beach <ajbeach@…>

Branches:

master

Children:

35c792f

Parents:

719fdbc

Message:

Updated iterator proposal. It was supposed to just go into a bit more detail about ranges, but ended up being a complete rewrite.

File:

• doc/proposals/iterators.md (modified) (2 diffs)

doc/proposals/iterators.md

@@ -10 +10 @@
 There are two groups of types that interact with this proposal.
 
+Iterable
+
+An iterable is a container of some type that has a default iterator that goes
+over its own contents. It may be a logical container, like a mathematical range,
+that does not store elements in memory, but it should have logical elements.
+A trait is defined to standardize how to get that iterator.
+
+        forall(C, I)
+        trait is_iterable {
+                I get_iterator(C&);
+        }
+
+This is not particularly useful on its own, but is used as standardized glue
+between some other features below.
+
 Iterator
 
-An iterator has a very simple interface with a single operation.
-The operation is "get the next value in the sequence", but this actually has
-several parts, in that it has to check if there are move values, return the
-next one if there is one, and update any internal information in the iterator.
-For example: `Maybe(Item) next(Iter &);`.
-
-Now, iterators can have other operations. Notably, they are often also
-iterables that return themselves. They can also have a verity of iterator
-transformers built in.
-
-Iterable
-
-Anything that you can get an iterator from is called an iterable. There
-is an operation to get an iterator from an iterable.
-
-Range For Loop
---------------
-One part of the language that could be reworked to make good use of this is
-for loops. In short, remove most of the special rules that can be done inside
-the identifier and make it a generic range for loop:
-
-    ```
-    for ( IDENTIFIER ; EXPRESSION ) STATEMENT
-    ```
-
-The common way to implement this is that expression produces an iterable.
-The for loop gets an iterator from the iterable (which is why iterators are
-often iterables, so they can be passed in with the same interface) and stores
-it. Then, for each value in the iterator, the loop binds the value to the
-identifier and then executes the statement. The loop exits after every value
-has been used and the iterator is exhausted.
-
-For the chained for loop (`for (i; _: j; _)`) can still have its existing
-behaviour, advancing through each range in parallel and stopping as soon
-as the first one is exhausted.
+An iterator is an object that can be advanced through a sequence of values.
+An iterator can be checked to see if it is at the end of the sequence, if not
+the next value can be retrieved from it and the iterator advanced. This can
+be done in as little as a single operation:
+
+        forall(Iter, Elem)
+        trait is_iterator {
+                maybe(Elem) next(Iter&);
+
+                // is_iterable(I, I&)
+                Iter& get_iterator(Iter&);
+        }
+
+This interface is not fixed, the function could change or be split into
+multiple functions (ex: `bool next(Elem&, Iter&)`). It should be natural,
+but also efficient to implement. This version will be used for examples in
+the proposal.
+
+When next is called, if there are elements left in the iterators, the next
+element is returned in a maybe and the iterator is advanced. If the iterator
+is exhausted nothing is changed and an empty maybe is returned.
+
+Iterators are also iterables. They must return themselves, this allows
+iterators to be used directly where iterables are expected.
+
+For-Each Loop
+-------------
+The main part of this proposal which is part of the language definition,
+the rest is part of the standard library. And this is the new for-each loop:
+
+        for ( IDENTIFIER ; EXPRESSION ) STATEMENT
+
+While this uses similar syntax to the existing special for loops, but takes
+a standard expression. This expression is evaluated, and then the iterator is
+retrieved from it (this should be the identity function iterators). Each
+iteration of the loop then checks the iterator to see if it is exhausted, if
+not it uses the value to execute the statement. If the iterator is exhausted,
+the loop is completed, and control continues after the loop (or the else
+clause if provided).
+
+The loop should show the same behaviour as the following code:
+(`typeof(?)` should be decided by the resolver.)
+
+        {
+                typeof(?) __iterable = EXPRESSION;
+                typeof(?) __iterator = get_iterator(__iterable);
+                typeof(?) __next = next(__iterator);
+                while (has_value(&__next)) {
+                        typeof(?) IDENTIFIER = get(&__next)
+                        STATEMENT
+                        __next = next(__iterator);
+                }
+        }
+
+This new loop can (but may not need to) also support the existing variants,
+where the name is omitted or multiple iterators are advanced in lock-step:
+
+        for ( EXPRESSION ) STATEMENT
+        for ( IDENTIFIER0 ; EXPRESSION0 : IDENTIFIER1 ; EXPRESSION1 ) STATEMENT
+
+These may not be needed. The unnamed variant is a nice short hand.
+The multiple iterator method could be replaced with an iterator transformer
+that has the same behaviour:
+
+        for (i, j, k; zip(iter, range, container)) { ... }
+
+This would require some further extensions, but would also allow single
+iterators to iterate over sets of related values. It also shows how library
+features can be used to extend the for-each loop.
+
+Containers as Iterables
+-----------------------
+The primary iterator application is going over the contents of various
+collections. Most of the collections should support the iterable interface.
+Each of these iterators should go over each element in the container.
+
+They could support multiple iterator interfaces. For example, a map could go
+over key-value-pairs, or just keys or just values.
+
+There isn't a lot to say here, except that as the implementation progresses,
+various rules about iterator invalidation should be hammered out.
 
 Ranges
 ------
-Ranges, which may be a data type or a trait, are containers that contain
-a sequence of values. Unlike an array or vector, these values are stored
-logically instead of by copy.
-
-The purpose of this container is to bridge the new iterator interfaces with
-the existing range syntax. The range syntax would become an operator that
-returns a range object, which can be used as any other type.
-
-It might not cover every single case with the same syntax (the `@` syntax may
-not translate to operators very well), but should be able to maintain every
-option with some library range.
-
-Library Enhancements
---------------------
-There are various other tools in the library that should be improved.
-The simplest is to make sure most containers are iterables.
-
-Also, new utilities for manipulating iterators should be created. The exact
-list would have to wait but here are some examples.
-
-Transformers take in an iterator and produce another iterator.
-Examples include map, which modifies each element in turn, and filter,
-which checks each element and removes the ones that fail.
-
-Producers create new iterators from other information.
-Most practical iterators tend to be iterable containers, which produce all
-the elements in the container, this includes ranges. Others include infinite
-series of one element.
-
-Consumers take an iterator and convert it into something else.
-They might be converted into a container or used in a for loop. Dedicated
-consumers will be some form of folding function.
+The existing range syntax is incompatible with the for-each loop. But this
+can be recovered by making at least some of the range syntax into operators.
+These operators create and return new range types.
+
+The ranges are types that map a random numeric range. For iteration, a range
+is also considered an iterator over the numbers in the range.
+
+The there could be up to 6 new operators to create ranges. These are:
+    `~` `+~` `~=` `+~=` `-~` `-~=`
+
+Parsing issues might rule some of these out. Others may be rendered
+irrelevant by iterator transformers. For example, adding a transformer that
+reverses the iterator could replace having downwards range operators.
+
+The one range that does not involve the operator is the lone number. This is
+a shorthand for a half-open/exclusive range from zero to the given number.
+That is the same behaviour as one (or two ~ and +~) of the existing range
+operators. So it only saves 2-3 characters.
+
+But if we want to save those characters, there may be a special form that
+could be used (for example, in the unnamed case) or you could treat integers
+as iterables that create iterators that count from zero up to the limit.
+
+        forall(N) struct Upto { N current; N limit; };
+        Upto(int) get_iterator(const int&);
+
+Enumerations as Iterators
+-------------------------
+To convert enumerations to the new form, a new syntax will have to be created
+to treat an enumeration type as an expression returning a range.
+
+Using the unmodified type name seems problematic, it could be done if we
+convert the type expression to some type object that can be passed to the
+get_iterator function. But there are other alternatives.
+
+An operator could be created to convert the type into an iterable expression.
+
+        range_over(EnumType)
+
+It is also possible to create a library type that iterates over the range.
+Then we use a compound literal of a nullary type as a flag to get it.
+
+        (ERange(EnumType)){}
+
+Both of these are placed in the EXPRESSION part of the for-each loop.
+
+Iterator Transformers
+---------------------
+New library features could be created to work with iterators. One of the
+biggest groups are transformers, which allow for more complicated compound
+operations on iterators.
+
+For a few examples:
+
+        // Create a new iterator that transforms elements from a source iterator.
+        forall(I, T, U | is_iterator(I, T))
+        /* Iterator over U */ map(U (*func)(T), I iter);
+
+        // Create an iterator that keeps only elements that satisfy a predicate.
+        forall(I, T | is_iterator(I, T))
+        /* Iterator over T */ filter(bool (*pred)(const T&), I iter);
+
+        forall(Is..., Ts... | is_iterator(Is, Ts)...)
+        /* Iterator over [Ts] */ zip(Is iters);
+
+        forall(Index, I, T | is_serial(Index) | is_iterator(I, T))
+        /* Iterator over [Index, T]) */ enumerate(Index, I);
+
+The return type is omitted in each case, because usually these functions end
+up being thin wrappers around a constructor for a specialized type that is
+the iterator, in each case, this is the return type.
+
+Also, these should be over iterables (with the conversion from iterable to
+iterator part of the thin wrapper), not just iterators. But the examples are
+easier to write out this way.
+
+Here is one example expanded to cover those details:
+
+        forall(Iter, Elem)
+        struct Filter {
+                bool (*pred)(const Elem&);
+                Iter iterator;
+        }
+
+        forall(Iter, Elem | is_iterator(Iter, Elem))
+        maybe(Elem) next(Filter(Iter, Elem) & this) {
+                maybe(Elem) ret;
+                do {
+                        ret = next(this.iterator);
+                } while (has_value(ret) && this.pred(get(&ret)));
+                return ret;
+        }
+
+        forall(T, Iter, Elem | is_iterable(T, Iter) | is_iterator(Iter, Elem))
+        Filter(Iter, Elem) filter(bool (*pred)(const Elem&), T& iterable) {
+                return (Filter(Iter, Elem)){ pred, get_iterator(iterable) };
+        }
+
+Iterator Consumers
+------------------
+Eventually we will have to turn the iterators into something else. Iterator
+consumers take an iterator and turn it into something else. The biggest of
+these is the for-each loop, as described above. In addition various library
+functions can be added.
+
+One group of functions are container constructors which take everything from
+the iterable and build a new container out of it. There would be various
+instances of this because you will need one for each container type.
+
+Higher order folding functions (for example, the functional
+`foldr : (a -> b -> b) -> b -> [a]`) are a bit less useful since Cforall does
+not work with anonymous functions quite as well. However, some of the
+specialized versions may still be useful. For example, getting the sum of an
+iterable's elements.
+
+        forall(T, I, N | is_iterable(T, I) | is_iterator(I, N) |
+                        { void ?{}(N&, zero_t); N ?+=?(N&, N); })
+        N sum(T & iterable) {
+                N acc = 0;
+                for ( i ; iterable ) acc += i;
+                return acc;
+        }
+
+Iterator Producers
+------------------
+Another group of library features are iterator producers, that take some
+data and create an iterator out of it. Many of already discussed cases are
+actually examples of this (containers, ranges and enumerations).
+
+There are a few more cases that might be useful. Such as "repeat", which
+takes a single element and iterates over it infinitely. This is usually
+combined with other iterators and not used directly.
+
+Other Improvements to Cforall
+----------------------------
+All code snippets should be considered pseudo-code because they require some
+features that do not currently exist. There are also some that just run into
+current bugs. For instance, my proof of concept for ERange encountered a few
+warnings even after I got it working.
+
+This proposal might also benefit from associated types. Both is_iterable and
+is_iterator may not need to be generic over all their type parameters.
+
+Tuple enhancements might also help with iterators that want to return more
+than one value.
 
 Related Work
 ------------
-Python has a robust iterator tool set. It also has a `range` built-in which
-does many of the same things as the special for loops (the finite and
-half-open ranges).
+Python has a robust iterator tool set. It uses the same iterator / iterable
+divide as described above and has the interfaces (note, Python uses duck
+typing instead of defined interfaces, so these are "imaginary"):
+
+        class Iterable:
+
+                def __iter__(self):
+                        # Return an iterator over the iterable's contents.
+
+        class Iterator(Iterable):
+
+                def __iter__(self):
+                        # Iterators are iterable over themselves.
+                        return self
+
+                def __next__(self):
+                        # Return next value if present and advance internal state.
+                        # Otherwise raise StopIteration exception.
+
+It uses this in for loops, the for loop takes an iterable gets the iterable,
+and iterates until the iterable is exhausted. Iterators are iterables so they
+can be passed in directly as well.
+
+It also has a `range` built-in which handles integer loops, although only
+increasing half-open ranges.
 
 In addition, it has many dedicated iterator constructors and transformers,
 and many containers can both produce and be constructed from iterators.
-
+For example, the chain function goes though a series of iterators in sequence
+an can be used by:
+
+        import itertools
+        itertools.chain(iter_a, iter_b)
+
+Python enumerations are implemented in the standard library and are iterables
+over all their possible values. There is no special construct for this, in
+Python types are object, and the type of an enum type object is EnumType
+which supports the iterable interface.
+
+        for elem in SomeEnum:
+                print(elem)
+
+Python References
 +   https://docs.python.org/3/reference/datamodel.html#object.__iter__
 +   https://docs.python.org/3/library/functions.html#func-range
++   https://docs.python.org/3/library/enum.html
 
 C++ has many iterator tools at well, except for the fact it's "iterators" are
@@ -104 +315 @@
 They do appear to be a wrapper around the "pointer" iterators.
 
+        template< class T >
+        concept range = requires( T& t ) {
+                ranges::begin(t);
+                ranges::end(t);
+        };
+
+C++ also has "structured bindings" which can be used to unpack an object and
+bind its components to different names. This can be used to iterate over
+multiple values simultaneously. In this example from the Cforall compiler
+using a custom utility function written without special support.
+
+        for ( auto const & [index, handler] : enumerate( terminate_handlers ) ) {
+                ...
+        }
+
+C++ References
 +   https://en.cppreference.com/w/cpp/ranges
++   https://en.cppreference.com/w/cpp/language/structured_binding
 
 Rust also has a imperative implementation of a functional style of iterators,
+with iterator tools implemented as "Provided Methods". Provided methods
 including a great number of standard transformers. Otherwise, it is very
 similar to Python.
 
-+   https://doc.rust-lang.org/std/iter/index.html
+        pub trait Iterator {
+                type Item;
+
+                fn next(&mut self) -> Option<Self::Item>;
+
+                // Many provided methods ...
+        }
+
+Not that Rust has many of its iterator transformers stored as methods on the
+iterator. These methods are "provided" so you only have to define next, but
+you can redefine the other methods to provide optimizations.
+
+Rust also has range expressions. Based around `start .. end` and
+`start ..= end`, with the sub-expressions giving the start and end of the
+range being optional, except for end after `..=`. If start is omitted, the
+range has no lower bound, otherwise the range uses start as its inclusive
+lower bound. It is the same case for end and the upper bound, except that the
+`..=` will have an inclusive upper bound instead of an exclusive one.
+
+Rust achieves ordering and step control by iterator transformers. `.rev()`
+allows you to reverse a range and `.step_by(step)` provides a positive step
+value.
+
+Rust Reference
++   https://doc.rust-lang.org/std/iter/trait.Iterator.html
++   https://doc.rust-lang.org/reference/expressions/range-expr.html
++   https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.rev