Concerning stephen's item (2).
The stricter set of rules was laid out by Richard C. Waters
in Optimization of Series Expressions: Part I: User's Manual for the Series Macro Package, page 46 (document page 48). See reference Waters(1989a).
The paper's language is a bit different than contemporary (2023) language.
`map()` is called `map-fn`.
`reduce()` a.k.a. `fold` seems to be `collect-fn`, although `collecting-fn`
also seems interesting.
sorting, uniqueness and permutation seem to be covered by `producing`.
Just think of McIlroy's famous pipeline in response to Donald Knuth's trie implementation[mcilroy-source]:
As far as pipeline or stream processing diagrams are concerned, the diagram on page 13 (document page 15) of Waters(1989a) may also be worth a closer look.
What the SERIES compiler does is pipeline the loops. Think of a UNIX shell
pipeline. Think of streaming results. Waters calls this pre-order processing.
This also seems to be where Rich Hickey got the term "transducer" from.
In short it means dropping unnecessary intermediate list or array allocations.
Shameless self-plug: Eliminated unnecessary allocations in my JavaScript code
by adding support for SERIES to the PARENSCRIPT Common Lisp to JavaScript
compiler. The trick was (1) to define (series-expand ...) on series expressions so that they can be passed into (parenscript:ps ...) and (2) the parenscript
compiler was missing (tagbody ... (go ...) ...) support. The latter is
surprisingly tricky to implement. See dapperdrake(2023). Apologies for
the less than perfect blog post. Got busy actually using this tool.
Suddenly stream processing is easy, and maintainable.
When adding a Hylang-style threading macro (-> ...) you get UNIX style
pipelines without unnecessary allocations. It looks similar to this:
Sadly, the SERIES compiler available on quicklisp right now is a
bit arcane to use. It seems like it may have been more user friendly
if it would have been integrated into the ANSI Common Lisp 1995 standard
so that is has access to compiler internals. The trick seems to be to
use macros instead of (series::defun ...) and use (series::let ...) instead of (cl:let ...). Note, that the two crucial symbols 'defun and 'let
are not exported by SERIES. So using the package is insufficient
and pipelining fails without a decent warning.
Am chewing on the SERIES source code. It is available on sourceforge. [series-source].
If anybody is interested in porting it, then please reach out.
It seems to be of similar importance as Google's V8 relooper algorithm [relooper-reference].
Waters(1989b), page 27 (document page 29) even demonstrates an implementation for Pascal. So it is possible.
The paper about Series explicitly bemoans the lack of compiler integration, explaining why the hacks are that way: why Series has its own implementations of let and so on.
For both getting function composition and avoiding unnecessary intermediate
allocations, the naive approach to using the SERIES package is insufficient.
And the error messages it returns along the way are unhelpful.
Evaluating (defpackage foo (:use :cl :series)) fails to import
(series::defun ...) and (series::let ...) and (series::let* ...).
So, when you think you are following the rules of the paper, you are
invisibly not following the rules of the paper and get the appropriate
warnings about pipelining being impossible. That seems somewhat confusing.
After reading the source code, it turns out the answer is calling
(series::install :shadow T :macro T :implicit-map nil). How is
(series::install ...) supposed to be discoverable with
(describe (find-package :series)) in SBCL if it is an internal
symbol of package SERIES (?) Usability here is somewhat less than discoverable.
Listing all exported package symbols of SERIES obviously also fails here.
Furthermore, the source code and naming in "s-code.lisp" suggest that
(series::process-top ...) may be useful for expanding series expressions
to their pipelined (read optimized/streaming/lazy) implementations.
This is desirable for passing the optimized version on to PARENSCRIPT
or other compilers. Here is the catch: It fails when the series expression
is supposed to return multiple values. One of the points of using SERIES,
is that Waters and his fellow researchers already took care of handling
multiple return values. (If the lisp implementation is smart enough, this
seems to mean that these values are kept in registers during processing.)
After some tinkering, there is a solution that also handles multiple
return values:
(defun series-expand (series-expression)
"(series::process-top ...) has problems with multiple return values."
(let (series::*renames*
series::*env*)
(series::codify
(series::mergify
(series::graphify
series-expression)))))
Will submit pull requests once I am comfortable enough with the source code.
Yes, the SERIES papers Waters(1989a,b) bemoan the lack of deep integration
with Common Lisp compilers. And yes, they could have been resolved by
making SERIES part of ANSI Common Lisp like LOOP was. They could
theoretically also have been resolved by having explicit compiler and
environment interfaces in ANSI Common Lisp. That is not the world we
seem to live in today. Nevertheless, package SERIES solved all of the
hard technical problems. When people know about the documentation
failings, then SERIES is a powerful hammer for combining streaming/lazy-evaluation with function composition as well as other compilers like
PARENSCRIPT.
I think, one issue is that Series had been hacked on since that paper, which had not been updated.
Anyway, I guess series::let is an unexported symbol? I.e. not series:let? There is a good reason for that.
If series:let were exported, then you would get a clash condition by doing (:use :cl :series). The CL package system detects and flags ambiguous situations in which different symbols would become visible under the same name. You would need to a shadowing import for all the clashing symbols.
It's probably a bad idea for any package to export symbols that have the same names as CL symbols. Other people say that using :use (other than for the CL package) is a bad idea. Either way, if you have clashing symbols, whether exported or not, you're going to be importing them individually if you also use CL, which is often the case.
The paper's language is a bit different than contemporary (2023) language.
`map()` is called `map-fn`.
`reduce()` a.k.a. `fold` seems to be `collect-fn`, although `collecting-fn` also seems interesting.
sorting, uniqueness and permutation seem to be covered by `producing`.
Just think of McIlroy's famous pipeline in response to Donald Knuth's trie implementation[mcilroy-source]:
As far as pipeline or stream processing diagrams are concerned, the diagram on page 13 (document page 15) of Waters(1989a) may also be worth a closer look.What the SERIES compiler does is pipeline the loops. Think of a UNIX shell pipeline. Think of streaming results. Waters calls this pre-order processing. This also seems to be where Rich Hickey got the term "transducer" from. In short it means dropping unnecessary intermediate list or array allocations.
Shameless self-plug: Eliminated unnecessary allocations in my JavaScript code by adding support for SERIES to the PARENSCRIPT Common Lisp to JavaScript compiler. The trick was (1) to define (series-expand ...) on series expressions so that they can be passed into (parenscript:ps ...) and (2) the parenscript compiler was missing (tagbody ... (go ...) ...) support. The latter is surprisingly tricky to implement. See dapperdrake(2023). Apologies for the less than perfect blog post. Got busy actually using this tool. Suddenly stream processing is easy, and maintainable.
When adding a Hylang-style threading macro (-> ...) you get UNIX style pipelines without unnecessary allocations. It looks similar to this:
Sadly, the SERIES compiler available on quicklisp right now is a bit arcane to use. It seems like it may have been more user friendly if it would have been integrated into the ANSI Common Lisp 1995 standard so that is has access to compiler internals. The trick seems to be to use macros instead of (series::defun ...) and use (series::let ...) instead of (cl:let ...). Note, that the two crucial symbols 'defun and 'let are not exported by SERIES. So using the package is insufficient and pipelining fails without a decent warning.Am chewing on the SERIES source code. It is available on sourceforge. [series-source]. If anybody is interested in porting it, then please reach out. It seems to be of similar importance as Google's V8 relooper algorithm [relooper-reference]. Waters(1989b), page 27 (document page 29) even demonstrates an implementation for Pascal. So it is possible.
References:
dapperdrake(2023): Faster Loops in JavaScript https://dapperdrake.neocities.org/faster-loops-javascript
Waters(1989a) document page 48, paper page 46 https://dspace.mit.edu/bitstream/handle/1721.1/6035/AIM-1082...
Waters(1989b) document page 29, paper page 27 https://dspace.mit.edu/bitstream/handle/1721.1/6031/AIM-1083...
[relooper-reference] http://troubles.md/why-do-we-need-the-relooper-algorithm-aga...
[series-source] https://series.sourceforge.net/
[mcilroy-source] https://franklinchen.com/blog/2011/12/08/revisiting-knuth-an...