\chapter{Lazy Collections}
\hypertarget{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections}{}\label{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections}\index{Lazy Collections@{Lazy Collections}}
\label{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md84}%
\Hypertarget{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md84}%
 If we\textquotesingle{}re serious about a massively parallel architecture, and especially if we\textquotesingle{}re serious about passing argument evaluation off to peer processors, then it would be madness not to implement lazy collections.

Architecturally lazy collections violate the \textquotesingle{}everything is immutable\textquotesingle{} rule, but only in a special case\+: you can do the equivalent of {\ttfamily replacd} on a cell that forms part of lazy collection, but only as you create it, before you release it to another process to be consumed; and you may only do it once, to replace the {\ttfamily NIL} list termination value with a pointer to a new lazy sell.

From the consumer\textquotesingle{}s point of view, assuming for the moment that the consumer is a peer processor, it looks just like a list, except that when you request an element which is, as it were, at the write cursor --- in other words, the producing process hasn\textquotesingle{}t yet generated the next element in the collection --- the request will block.\hypertarget{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md85}{}\doxysection{\texorpdfstring{ \+How are lazy sequences created?}{ How are lazy sequences created?}}\label{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md85}
Essentially, lazy collections are created by a very few primitive functions; indeed, it may boil down to just two,{\ttfamily read} which reads characters from a stream, and {\ttfamily mapc} which applies a function to successive values from a sequence. {\ttfamily reduce} may be a third lazy-\/generating function, but I suspect that it may be possible to write {\ttfamily reduce} using {\ttfamily mapc}.\hypertarget{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md86}{}\doxysection{\texorpdfstring{ \+What does a lazy sequence look like?}{ What does a lazy sequence look like?}}\label{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md86}
Essentially you can have a lazy sequence of objects, which looks exactly like a list except that it\textquotesingle{}s lazy, of a lazy sequence of characters, which looks exactly like a string except that it\textquotesingle{}s lazy. For practical purposes it would be possible for {\ttfamily mapc} to generate perfectly normal {\ttfamily CONS} cells and for {\ttfamily read} to generate perfectly normal {\ttfamily STRG} cells, but we\textquotesingle{}ve actually no shortage of tags, and I think it would be useful for debugging and also for process scheduling to know whether one is dealing with a lazy construct or not. so I propose three new tags\+:


\begin{DoxyItemize}
\item {\ttfamily LZYC} --- like a cons cell, but lazy;
\item {\ttfamily LZYS} --- like a string cell, but lazy;
\item {\ttfamily LZYW} --- the thing at the end of a lazy sequence which does some work when kicked.
\end{DoxyItemize}

I acknowledge that, given that keywords and symbols are also sequences of characters, one might also have lazy symbols and lazy keywords but I\textquotesingle{}m struggling to think of situations in which these would be useful.\hypertarget{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md87}{}\doxysection{\texorpdfstring{ \+How do we compute with lazy sequences in practice?}{ How do we compute with lazy sequences in practice?}}\label{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md87}
Consider the note \href{Parallelism.html}{\texttt{ parallelism}}. Briefly, this proposes that a compile time judgement is made at the probable cost of evaluating each argument; that the one deemed most expensive to evaluate is reserved to be evaluated on the local node, and for the rest, a judgement is made as to whether it would be cheaper to hand them off to peers or to evaluate them locally. Well, for functions which return lazies –– and the compiler should certainly be able to infer whether a function will return a lazy --- it will always make sense to hand them off, if there is an available idle peer to which to hand off. In fact, lazy-\/producers are probably the most beneficial class of function calls to hand off, since, if handed off to a peer, the output of the function can be consumed without any fancy scheduling on the local node. Indeed, if all lazy-\/producers can be reliably handed off, we probably don\textquotesingle{}t need a scheduler at all.\hypertarget{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md88}{}\doxysection{\texorpdfstring{How do lazy sequences actually work?}{How do lazy sequences actually work?}}\label{md__2home_2simon_2workspace_2post-scarcity_2docs_2_lazy-_collections_autotoc_md88}
As you iterate down a lazy list, you may come upon a cell whose {\ttfamily CDR} points to a \textquotesingle{}Lazy Worker\textquotesingle{} ({\ttfamily WRKR}) cell. This is a pointer to a function. You (by which I mean the CDR function --- just the ordinary everyday CDR function) mark the cell as locked, and call the function.


\begin{DoxyEnumerate}
\item It may compute and return the next value; or
\item it may return a special marker (which cannot be {\ttfamily NIL}, since that\textquotesingle{}s a legitimate value), indicating that there will be no further values; or
\item it may block, waiting for the next value to arrive from a stream or something; or
\item it may return a special value (which I suspect may just be its own address) to indicate that \textquotesingle{}yes, there are in principle more values to come but they\textquotesingle{}re not ready yet\textquotesingle{}.
\end{DoxyEnumerate}

In cases 1 above, you replace the {\ttfamily CDR} (hard replace --- actual immutability defying change) of the sequence cell you were looking at with a new sequence cell of the same type whose {\ttfamily CAR} points to the newly delivered value and whose {\ttfamily CDR} points to the {\ttfamily WRKR} cell. 