Glon Version of @rgchris's Iterator Framework


Chris's iterator framework inspired another Glon experiment.

We've now implemented a general-purpose, closure-based iterator vocabulary in Glon, without introducing a native ITERATOR! datatype, new binding semantics, looping constructs or changes to the frozen S1 substrate.

The vocabulary provides it/bytes, it/peek, it/peek2, it/next, it/pos, it/skip, it/take and explicit end-of-stream detection.

A lexer built on these iterators produces the same token representation as our earlier native Glon Pratt parser.

Results on the 65,536-cell Glon reference machine:

  • 77/77 iterator tests passed.

  • 28/28 lexer tests passed.

  • 1,200 differential token sequences comprising 11,307 tokens matched the original Pratt lexer exactly.

  • Byte advancement requires no managed-heap allocation.

  • Iterator state survives repeated garbage collections.

  • Traversal across 201 fragments works without linear growth in return-stack depth.

There are trade-offs. The iterator lexer is about twice as slow as the original position-based lexer in our unoptimised native benchmark, although repeated peeking is considerably cheaper. WASM-specific iterator parity remains to be tested.

The interesting result is architectural: Glon's existing closures and contexts were sufficient to implement resumable iteration as a loadable vocabulary. We didn't need any new evaluator machinery.

The implementation and tests are available here:

Our next experiment is to use this iterator-based lexer in the native Glon Pratt parser and see whether the abstraction remains worthwhile in a complete parser.

Thanks, Chris, for providing such an interesting challenge! :grinning_face_with_smiling_eyes:

1 Like

An update on Chris RG's iterator framework, which we've been experimenting with in Glon.

We started with byte and token iterators, then implemented DOM traversal using it/peek, it/next, it/pos and it/close (to skip a subtree).

Here's some actual Glon code from our tested DOM link extractor:

lk/steps: func [w n] [
    either lk/done [ none ] [
        either = n 1 [ lk/event it/next w ] [
            lk/steps w / n 2
            lk/steps w - n / n 2
        ]
    ]
]

lk/run: func [w n] [
    lk/steps w n
    either lk/done [ none ] [ lk/run w * n 2 ]
]

The balanced recursion lets us consume long event streams without exhausting the return stack.

We then connected the iterator to real HTML, with libcurl fetching pages and libxml2 parsing them. Glon performs the traversal and hyperlink extraction.

For example:

build/glon-web links.glon https://en.wikipedia.org/wiki/Rebol

Result: 449 hyperlinks from 5,946 DOM events, verified byte-for-byte against libxml2.

A 10,048-node document required only about 1,424 additional Glon heap cells above baseline. The full DOM remains in host memory.

We've also demonstrated two independent extractors processing separate documents with interleaved execution, sharing the same vocabulary definitions but keeping their state in separate closures. All five tests passed, including repeated garbage collection.

The DOM iterator handles 150 levels of nesting with constant return-stack usage per advancement.

No native ITERATOR! datatype, no new evaluator primitives, and no changes to Glon's frozen seven-primitive substrate.

Chris's iterator abstraction has turned out to be rather useful!

1 Like