4 ms·

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

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]: tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed ${1}q 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: (-> (it :let*-symbol series::let) (scan-file in-path-name #'read) (map-fn T #'some-function it) (collect 'list it)) 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 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.pdf?sequence=2&isAllowed=y#page=48 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.pdf?sequence=2&isAllowed=y#page=29 https://dspace.mit.edu/bitstream/handle/1721.1/6031/AIM-1083... [relooper-reference] http://troubles.md/why-do-we-need-the-relooper-algorithm-again/ http://troubles.md/why-do-we-need-the-relooper-algorithm-aga... [series-source] https://series.sourceforge.net/ https://series.sourceforge.net/ [mcilroy-source] https://franklinchen.com/blog/2011/12/08/revisiting-knuth-and-mcilroys-word-count-programs/ https://franklinchen.com/blog/2011/12/08/revisiting-knuth-an...

kazinator 3y ago
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.
- dapperdrake 3y ago
  Apologies for being slightly unclear. 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.

kazinator 3y ago

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.

dapperdrake 3y ago
Apologies for being slightly unclear. 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.