Nanyx
PlaygroundPackages

Lazy sequences

How seq(a) is represented, why there is one sequence type, how Iterable works, and how for loops and yield compile

What sequences do is described in Sequences and queries, Ranges, Workflows and prelude: sequences. This page gives the design behind them and says how the compiler builds them. What is still open is on Lazy sequences in Work in progress.

One type

There is one lazy sequence type, seq(a), attached to as seq or Seq, as lists are list or List; the prelude writes seq.map. The prelude declares it as Seq, a type as a user’s is, and seq is its alias (Seqs, BuiltinTypeNames); it is shown as seq(int).

There is no separate gen(a) for sequences that may be infinite. The type checker can’t prove a sequence ends: takeWhile and unfold may or may not stop, and a while loop inside seq { ... } could claim to be finite with nothing to check it. A split would also mix finiteness with purity, and purity is what contexts track. So 0.. is a seq(int), like 1..10, and what a gen type would have caught, a for over only 0.., is an error of its own (NYX0217, see for loops).

Representation

A sequence is a function that, when called, gives back the first element and the rest of the sequence, or #done:

export type Seq(a) = [k] protected (next: [k] () -> #next(a, Seq(a)) | #done)

Seq is a nominal type, not a structural alias: attached definitions such as seq.map need a type of their own to attach to, the recursion goes through a name, and since the library keeps the representation to itself it can change it later (chunking, fusion) without breaking anyone. It is protected, so a sequence is made with the library’s functions, and read with s.next(). It is generic in contexts (Types generic in contexts), and its tail, Seq(a) in its own body, is a [k] seq(a) too, since a protected type can name itself.

It is a singly linked list whose tails are functions rather than cells. The closest prior art is OCaml’s Seq (type 'a t = unit -> 'a node, in the standard library since 4.07), whose functions were the list to start from: unfold, map, filter, take, zip, fold_left, uncons. Haskell lists, Scala’s LazyList, Clojure’s lazy-seq and Scheme streams have the same shape but store each tail once it has been worked out. Rust, C#, Java and Python iterators are the other approach: a next() that changes the iterator.

What this representation gives:

  • It is pure. There is no hidden position. Calling next on the same sequence twice gives the same answer, when its steps are pure.
  • Looking ahead and going back cost nothing. Calling next moves nothing; you move on by keeping the rest. A parser can keep a position and come back to it, where a stateful iterator needs a separate peekable wrapper.
  • It reads like a list. A function matches on #next(x, rest) and recurses; zip pulls from both.

What it costs:

  • An allocation per element: the closure for the rest and the #next it is returned in, where a stateful iterator changes one object in place. Reference counting can’t reuse these the way it reuses a list held once, since each is a new closure.
  • filter must not grow the stack. Its next keeps pulling until an element passes, so it does that with a tail call. Tail calls are guaranteed for closures, so a tail-recursive filter runs in constant stack.
  • Walking a sequence twice does its work twice. Tails are not stored once worked out. Storing them would need a mutable cell in every node, and a sequence whose start is still held would keep every element worked out so far alive (the “holding onto the head” leak in Haskell and Clojure).
  • There is no cleanup hook. A sequence over an open file that is abandoned halfway has no Dispose. Contexts help: a [FileSystem] seq(string) can’t be pulled outside the scope that supplies FileSystem, so whatever opened the file is still there to close it.

Effects

A sequence whose steps use a context says so in its type: reading lines gives a [FileSystem] seq(string), which can be pulled only where FileSystem is available, and a sequence whose steps wait would be an [Async] seq(a), which is what Kotlin calls a flow. No second sequence type is needed for impure sequences.

Because a lazy function runs its callback when the result is pulled, not when it is called, it moves the callback’s contexts into the type of its result, where an eager function requires them at the call:

list.map: [c] list(a), ([c] a -> b) -> list(b)          -- runs f now: needs c now
Seq.map:  ([c] seq(a)), ([d] a -> b) -> [c, d] seq(b)   -- runs f when pulled: the result needs c and d
Seq.fold: [c, d] ([c] seq(a)), b, ([d] b, a -> b) -> b  -- runs now again

So a lambda given for d, a context variable that only the result carries, is checked as a constructor’s field is: outside the def or top-level value it is written in, which needn’t have its contexts. A pure function, or a top-level value, can make a [Console] seq(int) with seq.map, and whatever pulls it needs Console. Where a [Console] seq(int) is expected, either of [c, d] may be the one that requires Console.

A sequence whose steps read a mut cell requires Memory, so it can’t leave its memory block (Memory).

Taking anything that can be iterated

Nanyx has no subtyping, so a list(a) is not a seq(a). It doesn’t need to be one: it needs to give one. The prelude’s Iterable context says that:

export context Iterable(c) = (elem: type, toSeq: c -> seq(elem))

The prelude attaches a toSeq to list, Array, set, map and seq, and the standard library’s Slice, Stack, Queue and mutable collections attach one too. A mutable collection’s requires Memory and gives the elements it holds when called.

  • A type gets the context by attaching toSeq. The compiler builds an instance from a type’s attached definitions by member name, as it builds ToString(a) from an attached toString (Context synthesis).
  • The element type is an associated type, elem. An instance’s toSeq fixes it by unification: List.toSeq: list(x) -> seq(x) makes Iterable(list(int)).elem an int. A signature constrains only the container, and fixes the element type where it needs to, as in [Iterable(c, elem = string)].
  • The seq functions take a sequence, not any iterable. They keep their ([c] seq(a)) first parameter, so file.lines and every sequence whose steps need contexts work with them, and a list or a set goes into one through its toSeq: [1, 2, 3] \list.toSeq \seq.map { * 2 }. One function can’t take both, since Nanyx has no overloading, and Iterable can’t stand for a [k] seq(a): toSeq gives a sequence that needs no contexts, so one read through it would be pulled without the members of k. Iterable takes only values whose sequence needs none.
  • What takes Iterable is a for loop, a spread in a collection literal, and any function written to: [Iterable(c)] c -> ... reads its argument’s elements with toSeq(xs). Another of a function’s contexts can name elem, so [Iterable(c), ToString(elem)] c -> () prints each element.

The compiler doesn’t insert toSeq wherever a seq(a) is expected and a list(a) is given: unification has no direction, so whether a conversion was inserted would depend on the order types become known; it would turn an eager computation lazy without saying so; and it is subtyping by another name, which comes back as soon as someone wants a list(list(a)) to be a seq(seq(a)).

Ranges

a..b is read as the prelude’s seq.range(a, b), and a.. as seq.from(a), of any type with an Enumerable (its succ) and an Ord (InferCalls, Seqs). A range of ints is read as the prelude’s __intRange or __intFrom instead, which count and are passed no instances. Both are seq values that can be passed around and stored.

for loops

A for loop walks a list, seq, map or set as it is, and reads anything else as the prelude’s __toSeq(xs), [Iterable(c)] c -> seq(elem), its sequence through Iterable (Loops.inferFor, ForSyntax.toSeq), so a user’s type can be walked by attaching a toSeq. A loop rejects a range with no end written in place unless something that ends is walked beside it (NYX0217).

The backend walks a list and a range of ints written in place with the core IR’s ForEach, counting with the range’s bounds rather than making the sequence (Loops.inferFor keeps the range as it is written; CoreIrLowerLoops). A loop over a sequence value is a while loop instead (CoreIrLowerLoops.forEachPulling): each time round it pulls the sequence, calling its function with the members of the contexts it carries, binds the element and holds the rest for the next time round, so the body runs between pulls. A list or a range walked beside it is walked in the same loop, and the loop ends when the first of them does.

yield

A block with yield in it is a sequence, and seq { ... } makes one: the code after a yield doesn’t run until the next element is pulled. An ordinary workflow couldn’t do it: under the one desugaring rule yield x is yield(x, rest), and rest needs the builder’s context, which is gone by the time the sequence is pulled. So the prelude’s Yield context declares yield as a keyword of kind #yield, and any lambda with one in it, a block after seq included, is rewritten into the sequence itself (WorkflowDesugaring): yield x with the rest k is seq.cons(x, { k }), the end of the block seq.empty(), and a for loop whose body yields seq.append(seq.flatMap(items, body), seq.delay({ k })). seq is an ordinary prelude function, seq.delay by another name. Where the branches of an if join, a pure seq.empty() joins a branch whose sequence prints: the whole carries what any branch’s sequence does. There is no yield in a while loop: a while needs a cell, and a sequence that reads one can’t leave its memory block anyway.

list.select takes a lambda that yields, a sequence it flattens: xs \list.select { x -> if x > 0 then yield x }. Each collection type is made from a sequence with fromSeq, and from a yield block with build, Array.build { yield 1 }.