Reminds me of a stream-processing library that Michael Snoyman recently started working on:<p><a href="https://github.com/snoyberg/zerem" rel="nofollow">https://github.com/snoyberg/zerem</a><p>For background, he authored Conduit, one of the most popular Haskell stream-processing libraries:<p><a href="https://github.com/snoyberg/conduit" rel="nofollow">https://github.com/snoyberg/conduit</a>
oleg and friends claim to have disproven the 'pick two' thing. See their 'Stream Fusion, to Completeness' paper [1], and the associated Strymonas library [2].<p>[1] <a href="https://yanniss.github.io/streams-popl17.pdf" rel="nofollow">https://yanniss.github.io/streams-popl17.pdf</a><p>[2] <a href="https://strymonas.github.io/" rel="nofollow">https://strymonas.github.io/</a>
> This issue would also appear if we forced stream transducers (processing nodes) to output a fixed number of value at each invocation: it suffices to let S repeat each value of X twice, i.e., interleave X with X.<p>I don't understand how the issue would appear in that case.
Buffering one value seems to be sufficient to upsample S to the "clock" of X, ie. project S to the instants where X is defined (flow Z below) while filling missing instants with the previously known value:<p><pre><code> X : X0 X1 X2 X3 ...
S : S0 S1
Z : S0 S0 S1 S1
</code></pre>
That would look as follows in Signal:<p><pre><code> process test = (? integer x ! integer y)
(| c := not (c$ init false)
| s := (x when c) cell c
| y := x + s
|)
where
boolean c;
integer s;
end;
</code></pre>
C is the clock which alternates between false and true ($ refers to the last value), "X when C" is filtering, "E cell C" is projection of values of E to the instant of C, defaulting to the previous known value at logical instants where E is not present but C is true.<p>The clock calculus in Signal (etc.) is way to assess if a program can be generated to use constant (static) memory allocation and constant time. There are programs which fail to do so, but you then need to refine them to add explicit operations (<a href="https://www.irisa.fr/prive/talpin/papers/date08.pdf" rel="nofollow">https://www.irisa.fr/prive/talpin/papers/date08.pdf</a>)
This is interesting because I have (or had) been working on a C++ logic programming library. Many if not most similar libraries are implemented using streams. (See minikanren, LC++, etc.) Naturally as a C++ library I'm interested in if it can be done without or with a minimum of dynamic allocation, and had come to the conclusion "probably yes, but only if I give up on some subset of the things I wanted it to be able to do." So I concur with the article's opening, "choose 2 of 3."