Has this been added? That PR got closed right? Whilst valid, it was sad that Bun didn't make it. Would be good if someone from the community or Bun team can give it another go.
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
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))
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...
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)))))
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.
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.
That's because speed isn't always top priority. Readability is very high on the list.
I would rather have a slightly slower .map or .filter in a chain than a harder to read nested for or while loop.
I often find map/reduce/filter easier to read when using named functions (or lazy data structures ) for intermediary results - depending on the language/runtime that might imply more allocations - or not.
Eg pseudocode:
Integers.filter(//non-obvious prime sieve).sum()
Vs
Primes = Integer.filter(//non-obvious prime sieve)
Primes.sum()
Or lifting the anonymous filter to primes()-filter:
Integers.primes().sum()
But I have seen "functional contraptions of horror" where those functions are both chained and nested which were completely undecipherable by mere humans.
And at least from my personal impression, people who are a fan of this type of functional style are also more likely to create such horrors (which they themselves of course find totally readable and superior to "unreadable" loops) - I suspect that there's often a bit of cargo-culting going on.
You can make a similar function that changes the data in place and will be faster. But that comes with side effects which is not functional style.
In the front-end we were making about 20 API calls to fetch data we probably don't need yet and the developer is like: the problem has to exist in the way we call them, time to optimise the loops!
Lodash is MUCH faster than native because it uses iterators so you aren't actually looping over and over.
We need builtin iterator versions of all these looped functions so it adds an implicit/explicit `.valueOf()` that calls the chain and allocates only one new array.
But it's not going to help all that much with this problem. The iterator protocol in JS involves an allocation for every individual value, and while in some cases that can be optimized out, it's pretty tricky to completely optimize.
It's always going to be difficult to beat a c-style for loop for performance.
Bun is extremely fast at data processing tasks. Shuffling data from one place to another (disk, network, APIs, etc). We use SIMD, minimize allocations/copies and pay lots of attention to what system calls are used and how often and where. A naively implemented script in Bun that moves data using Bun’s APIs will often outperform a naively implemented program written in Rust or Go. Bun’s APIs try really hard to make the obvious & default way also the fast way.
That, and Bun’s builtin build tooling are where Bun’s performance shines.
> “Mojo of TypeScript”
I’ve thought a little about this. I think it’s a project that’d take 5+ years and crazy hard to hire the right people to do it. I think it’s mostly unnecessary though. JITs are really good. The API design is usually the reason why things aren’t as fast as they could be.
Sounds exciting, do you have some example benchmarks I can run that show this?
What are the major difficulties you see? Is this estimate for supporting all existing TS code...or as the OC said, a new language with only newly written code.
The way I naively think about it is to imagine transpiling TypeScript code to Zig code. How far could that take you?
And if you restricted how much dynamic-y stuff you could do...maybe with a linter. I always get the feeling that 90% of the business logic (sequence, selection, iteration) is that same between languages whether they are interpreted or compiled, with just some memory management stuff added on top - which can be abstracted anyway.
Nice! That makes a lot of sense, and look forward to trying them.
Fwiw I sometimes worry about the slippery slope to infra that exists on the JS side, i.e. I work a lot in a GraphQL backend, and even if Bun gave us (or really our framework, so fastify/mercurius) a super-optimized way of getting the raw bytes off the wire, Mercurius is still doing GraphQL parsing, validation, routing, response building in JS land.
Granted, I want to keep my application's business logic in TS, but naively it seems tempting to push as much of the "web framework" / "graphql framework" as possible into the native side of things, where as I think historically Node/etc API have stopped at the "here's the raw HTTP request off the wire".
> I’ve thought a little about this.
Sweet! That's awesome just to hear that it's crossed your mind. Agreed it would be a moonshot. And, yeah, I'm perfectly happy leaning into JITs and good APIs.
Thanks for the reply!
This is basically just rust, no? As a TS developer, I've found picking up rust to be really neat.
Dunet is really good.
https://github.com/mcintyre321/OneOf
https://github.com/domn1995/dunet
It's on the roadmap and will arrive at some point:
https://github.com/dotnet/csharplang/blob/main/proposals/dis...
That was certainly the promise/hype of Rust ~2-3 years ago, that it was going to become so ergonomic that even "boring line-of-business applications" (i.e. JS backends) could be written in Rust, by everyday programmers, without any slow down in delivery/velocity due to the language complexity.
But, from what I've seen, that's not played out, and instead the community is still on the look out for the killer "systems-language performance, but scripting-language ergonomics" language.
It was eye-opening, in terms of how often us JS programmers play fast & loose with "a little filter" here, "a little map" there, and end up with death by a thousand allocations.
Given that context, I'm curious:
1) How much you think Bun's (super-appreciated!) fanatical OCD about optimizing everything "up to & outside of JSC" will translate to the post-boot performance of everyday backend apps, and
2) If you're tempted/could be compelled :-D to create a "Mojo of TypeScript", where you do a collab with Anders Hejlsberg to create some sort of "TypeScript-ish" language that, if a TS programmer plays by a stricter set of rules + relies on the latest borrowing inference magic, we could bring some of the Bun amazing-performance ethos to the current idiomatic FP/JS/TS style that is "lol allocations everywhere". :-)
Or, maybe with Bun bringing the right native/HTTP/etc libraries wrapped around the core runtime, doing "just the business logic" in JS really won't be that bad? Which iirc was the theory/assertion of just-js when its author was benchmark hacking Techempower, and got pretty far with that approach.
Anyway, thanks for Bun! We're not running on it yet, but it's on the todo list. :-)