Category Iterators

Home › All Categories › Iterators

Iterators

Why It Exists

OPERATOR FOR / OPERATOR NEXT / OPERATOR STEP form an iteration protocol of their own, which serves

for i as T = a to b

That is a RANGE protocol. It does not solve the collection problem, for three reasons:

1. Seven declarations and seven definitions to iterate one type -- two

constructors and an OPERATOR LET on top of the three iteration operators,
because the loop variable is copy-constructed and assigned.

2. The loop variable IS the iterator, not the element. The body says

'i.cur'. Every use site has to know the iterator's representation.

3. FOR is 'start TO limit', and the limit is structural to the statement.

Iterating a linked list means inventing a sentinel object meaning
"exhausted". The collection is never named in the loop at all.

This protocol is the collection half. A collection hands out an iterator; the iterator hands out elements until it runs out.

The Contract

A type is ITERABLE if it has

declare function GetIterator( ) as I

taking no parameters, where I is an ITERATOR TYPE. GetIterator may be CONST.

A type is an ITERATOR TYPE if it has all three of

declare function IsValid( ) as boolean      '' still on an element?
declare function Value( ) [byref] as E      '' the current element
declare sub      MoveNext( )                '' advance

all taking no parameters. E -- whatever Value returns -- is the ELEMENT TYPE. IsValid and Value may be CONST; MoveNext may not.

That is the whole thing:

type IntListIterator
    as IntNode ptr node
    declare function IsValid( ) as boolean
    declare function Value( ) byref as int32
    declare sub      MoveNext( )
end type

function IntListIterator.IsValid( ) as boolean
    return this.node <> 0
end function

function IntListIterator.Value( ) byref as int32
    return this.node->value
end function

sub IntListIterator.MoveNext( )
    this.node = this.node->nxt
end sub

type IntList
    as IntNode ptr head
    declare function GetIterator( ) as IntListIterator
end type

function IntList.GetIterator( ) as IntListIterator
    dim it as IntListIterator
    it.node = this.head
    return it
end function

Structural, NOT Nominal

There is no Iterable interface to implement and nothing to inherit. A type is iterable because name lookup finds the members.

This is deliberate. tiko has no interface feature independent of inheritance, so a nominal protocol would consume the type's single inheritance slot, add a vtable and a virtual call per element to types that are otherwise plain data, and force every existing collection to be modified. Structural matching costs one name lookup at compile time and produces a direct, inlinable call.

The cost is that a type can conform by accident, and that a near-miss ('MoveNxt') reads as "not iterable" rather than "you misspelled it".

What An Implementer Promises

None of this is checkable by the compiler.

• IsValid is pure and repeatable. Calling it twice without an intervening

MoveNext gives the same answer.

• Value may be called only while IsValid is true, and may be called more than

once for the same element.

• MoveNext may be called only while IsValid is true. After the last element it

leaves the iterator with IsValid false.

• A freshly returned iterator is ALREADY ON the first element, or has IsValid

false for an empty collection. THERE IS NO "BEFORE THE FIRST ELEMENT" STATE
-- MoveNext is not called before the first Value. This differs from C#'s
IEnumerator, and it is what lets a linked-list iterator be one pointer and
an array iterator be a pointer and an index, with the empty case falling
out for free.

• Mutating the collection's STRUCTURE during iteration invalidates the

iterator. Mutating an element's VALUE through a byref Value does not.

Byref OR By Value

The element type is whatever Value returns. Declare it BYREF and elements can be modified in place:

function ArrayIterator( of T ).Value( ) byref as T
    return this.first[ this.idx ]
end function

Declare it by value and the caller gets a copy. Both are legal; the choice is the implementer's.

Generic Collections

With generics the iterator is written once:

type ArrayIterator( of T )
    as T ptr first
    as int32 idx, count
    declare function IsValid( ) as boolean
    declare function Value( ) byref as T
    declare sub      MoveNext( )
end type

type Buf( of T )
    as T e( 0 to 7 )
    as int32 n
    declare function GetIterator( ) as ArrayIterator( of T )
end type

Note that Buf's GetIterator returns an instantiation of a DIFFERENT generic. That works, and it is the shape the standard containers use.

Iterators Are Ordinary Values

An iterator has ordinary tiko lifetime. If it holds a resource, give it a destructor and the destructor runs when it goes out of scope -- including on EXIT FOR, on GOTO out of a loop, and while an error unwinds the scope. The protocol adds no lifetime rule of its own; it relies on the one the language already has.

This is why GetIterator returns BY VALUE rather than allocating. A typical iterator is a pointer and two integers and costs nothing.

Coexistence

OPERATOR FOR / NEXT / STEP is a fully supported protocol in its own right. A type may implement both protocols and they do not interfere: they are looked up separately and neither falls back to the other.

A collection is even allowed to BE its own iterator (GetIterator returning itself by value). Convenient for one-shot generators, and an easy way to make an aliasing mistake -- two "independent" iterations would share one cursor.

Known Limits

• CONST OVERLOADING IS NOT AVAILABLE. tiko does not distinguish

overloads by constness alone:

    declare function f( ) as int32
    declare const function f( ) as int32
    error 4: Duplicated definition

So a type cannot supply a const and a non-const GetIterator pair. Declare
the single GetIterator CONST -- it then serves const and non-const
collections alike, which is what a container wants anyway.

• SINGLE PASS ONLY. There is no Reset, no MovePrev, no random access and no

way to ask a collection for its length. That is enough to walk a
collection and not enough for a generic algorithms library.

• The names GetIterator, IsValid, Value and MoveNext are NOT reserved words

and are not in the keyword table. A type that has them compiles and
behaves as it would without the protocol; the only consequence is that it
may also be walkable.

Conformance Suite

tests/generics/iterator-protocol.bas exercises every shape above: the hand-written linked-list iterator, the generic one, byref and by-value Value, a const GetIterator reached from const and non-const collections, an empty collection, two independent iterators over one collection, element types that are UDTs and generic instantiations, an iterator with a destructor (asserting constructed == destroyed), and one type carrying both protocols at once.

---

---

Home · Keyword Index