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
nexton the same sequence twice gives the same answer, when its steps are pure. - Looking ahead and going back cost nothing. Calling
nextmoves 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;zippulls from both.
What it costs:
- An allocation per element: the closure for the rest and the
#nextit 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. filtermust not grow the stack. Itsnextkeeps pulling until an element passes, so it does that with a tail call. Tail calls are guaranteed for closures, so a tail-recursivefilterruns 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 suppliesFileSystem, 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 buildsToString(a)from an attachedtoString(Context synthesis). - The element type is an associated type,
elem. An instance’stoSeqfixes it by unification:List.toSeq: list(x) -> seq(x)makesIterable(list(int)).elemanint. A signature constrains only the container, and fixes the element type where it needs to, as in[Iterable(c, elem = string)]. - The
seqfunctions take a sequence, not any iterable. They keep their([c] seq(a))first parameter, sofile.linesand every sequence whose steps need contexts work with them, and a list or a set goes into one through itstoSeq:[1, 2, 3] \list.toSeq \seq.map { * 2 }. One function can’t take both, since Nanyx has no overloading, andIterablecan’t stand for a[k] seq(a):toSeqgives a sequence that needs no contexts, so one read through it would be pulled without the members ofk.Iterabletakes only values whose sequence needs none. - What takes
Iterableis aforloop, a spread in a collection literal, and any function written to:[Iterable(c)] c -> ...reads its argument’s elements withtoSeq(xs). Another of a function’s contexts can nameelem, 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 }.