Hi everyone, this is EmacsConf 2024. I'm Colin, and today
I'll be talking about transducers.
After introducing them, I'll share a bit of history about
transducers and the problems that they solve, some basics
about how we can use them, how they work, like how they're
implemented, some demonstrations of how we can actually
use them in the wild, and then some other discussions about
issues that they have.
Okay, let's get right in. What are transducers?
Transducers are a way to do streaming iteration with a
modern API.
Who are transducers for, and thereby, who is
this talk for? Well, it's for people who want to do streamed
data processing in Emacs. It's for people who perhaps
aren't satisfied with the existing APIs, for example, the
seq API, or some other common libraries that provide
similar functionality. Maybe you're not a fan of the loop
macro. Some people find it difficult to understand. Or
maybe you've done a bunch of Clojure before, and you'd like
more aspects of Clojure in your Emacs Lisp. Or maybe you're
just interested in transducers in general, because the
pattern has now been ported to multiple different Lisps.
So I'm Colin. I'm fosskers on everything online, and I do
mainly back-end programming work and a lot of open source
software. I wrote Haskell for a long time, both as a hobbyist
and professionally. Since the COVID years, I've been
writing Rust, both open source and professionally. But now
I find that in my spare time, I'm mostly writing Common Lisp.
Some things I learned from my years of Haskell was that a lot
of programming is just altering the shape of data. You know,
sometimes we work through our algorithm line by line. We're
trying to just tell the computer exactly what to do. But if we
step back, a lot of the time we're just getting in data of some
shape, changing it, and then passing it along. A lot of
these patterns are common, identified
decades ago. For instance, we have some collection, and we
want to transform every element of that collection and then
pass it on. Or maybe we're trying to filter out bad elements
in that collection. Or maybe we're looking for a specific
element in that collection. Yes, you could write all that
with for loops, but these kind of common patterns were
identified and given names decades ago. So why not use them?
They say that there are two major problems in computer
science, one being cache validation and the other being
naming things.
I've identified five other problems that
come up when we're trying to deal with collections of data,
or big streams of data. One is that if we were trying to
load a file all into memory all at once and process the whole
thing, sometimes we can have memory problems. You've
probably seen out-of-memory errors or such things.
A second issue that comes up is that if we were looking at a
giant for loop, in particular a nested for loop or such
things, it can be hard to tell just by looking at the code what
it's trying to do, what it intends. If we don't go character
by character or line by line, it can be hard to understand it.
Furthermore, and this is particularly an issue with Emacs
Lisp, is that if one call, for instance, to seq-map, then
piped into seq-filter, for instance, will have an
intermediate allocation, the map will take the source
container, allocate a new one, and then the filter will
operate over the second one. This is wasteful.
Furthermore, it can often be difficult to abort a stream.
For instance, if we were filtering through our collection,
but we knew we only wanted to go halfway, for instance, for
some reason, we have no way to stop it halfway through. We
just have to process the whole thing, even if we know we don't
need to. Another issue is that for languages that have
traits, or in Haskell they're called type classes, if you
are defining what it means to map over something, you often
have to redefine that for every kind of container or thing
that you're iterating over. Wouldn't it be nice if we could
define things like map just once and then reuse them
everywhere? Now, transducers solve all five of these,
without the addition of new language features, and with
little more than plain old function composition.
If this is your first time hearing of transducers, yeah,
no problem. They were originally invented in Clojure by
Rich Hickey, and this is a quote from him. He thinks
transducers are a fundamental primitive that decouple
critical logic from list or sequence processing, and if he
had to do Clojure all over, he'd put them at the bottom, at the
very bottom of all the fundamental primitives. Now, that's
Rich speaking quite highly of them. And I think he has a point
here.
They were invented originally in Clojure. In more
recent years, they were brought over to Scheme
via SRFI 171. That's where I found them
when I was learning the Guile language.
In the process of submitting a patch, I realized
that there were other things to be improved. So I ported the
pattern to Common Lisp, then Fennel, and then more
recently, Emacs Lisp. The Common Lisp and Emacs Lisp APIs
are identical. And the Fennel one is not identical, but
fairly similar. Overall, everywhere you find
transducers, they should basically be fairly uniform.
When I originally made the Common Lisp variant first, I
sampled the APIs from a number of different languages and
came up with what I believed to be a representative sample of
what most people would want out of such a library. I gave
functions their common modern names. For instance, map
is map and filter is filter and so on.
What does the usage of transducers look like? Well,
these examples will all be the Emacs Lisp variant, but the
Common Lisp will look basically exactly the same, minus
this little t- prefix.
Running transducers requires three things. It requires a
source. This could be an obvious thing like a list or a
vector, but it could be other things like a file, or in Emacs
list in particular, a buffer.
A reducer is a function. It's something like
the + operator or the * operator,
or certain constructors of various containers.
It takes values and collates them into some final version.
Now, finally, we have what we're calling here
a transducer chain. This could be one transducer function
or it could be multiple composed together. These are the
functions that actually take data and transform them
somehow. For instance, this. We have a list of three
elements. We want to reduce it into a vector. How we are
going to transform the elements along the way: we are doing
plus one to each of them. If this syntax is new to you, just
know that this #' just means that this thing that
comes after it is the name of the function. In Common Lisp and
Emacs Lisp, this is necessary, but for Clojure and Scheme,
it is not. So we can see here that just this example is not much
different than any other normal map call you might see made,
but if nothing else, it's a handy way to convert a list to a
vector or anything else. There are many, many reducers
available and many different forms that we can
collate the final value into.
Let's see a more involved example.
Okay, now we've got some more meat here.
Here we can see usage of the comp function
and a custom source, ints.
Ints is an infinite generator of integer values. That's not
like a list or a file. It will generate infinitely.
Comp is letting us compose multiple transducer functions
together. Notice that this is the opposite order of what
we'd usually be used to from a function like comp. The order
here is top to bottom, basically, so that the map goes first,
then the filter, and then the take. So effectively is what
we're doing is taking all the integers that exist,
positive, adding one to them, filtering out only the even
ones, but then just taking 10. Cons here is a function that
just produces the ending result as a list. So what happens
here specifically is how we are avoiding intermediate
allocations. First, the number 0 will come through.
It will be pulled out of this source internally by transduce.
It will make its way into the map. The map will add it. Then it
will immediately go into this filter step. So it's not like
all the maps occur, and then all the filters occur. We do
everything for each element. So the 0 comes in, now it's 1.
The filter would occur. Well, it's going to fail that
because it's not even, so it will just bail there. Now we'll
go to the next one. Now 1 will come, it will become 2, then
it will be saved by this evenp call, and then the take will
capture it, because we only want 10 values here. You can
see 2, 4, 6, 8, and so on is the result that we
expect. So let's play around a little bit.
Let's jump into Emacs and see what we can do.
Alright, you should see my Emacs screen here.
These are the actual notes for the actual
presentation done in Org Mode. I'll boost that up in size for
a little bit. That should be more than big enough for you.
Just by changing the reducer, we can change the result.
Okay, now it's a vector. Well, what else can we do to it? Well,
let's just add up the results. Maybe we just want to count the
results. Oh, indeed, there were 10. What if we want to find
the average of the results? What if we want to find the median
of the results? And so on. Here's some more interesting
things that we could do. We could add different steps. So
here we have all the integers. Let's add, hmm, okay, we'll
keep that. We're going to add t-enumerate. What enumerate does
is for each item that comes through, it is
going to add a sort of index to it and make it a pair. In this
case, it's going to be equal to what came in here. Well, we can
change it. If we start this at 1, now it will be different.
1 will be paired with 0, and then 2 would be paired
with 1, and so on. We'll accept that the even call will change
that a little bit. Why we're doing this is because we want
to form a hash table. Let's move that down to 3, maybe
we'll get a better result. What do we see? Okay, here now the
result is a hash table. What are its values? Well, 0 seems
to have... The key of 0 seems to be paired with 2, the key of
1 seems to be paired with 4,
and 2 seems to be paired with 6.
Maybe let's jazz that up even a little bit more.
We're going to start from a string
and we'll call it hello.
That's not going to work anymore
and neither is that, but what we could do is
we could say t-map #'string.
I believe we'll do that.
Let's see if that works. It did. So that's
going to convert a character into a string.
Let's just go two
just to make it a little easier. Now you can see that we've
constructed a hash table here. The key of 0 is mapped to the
string of h and 1 is mapped to e. Now, I really like having
this reducer in particular.
Know that hash tables are
also legal sources. I find that both in Emacs Lisp and in
Common Lisp, dealing with hash tables--like creating them
and altering them--can be a bit of a pain. Having them
immediately available like this with transducers is very
handy, I find. We can work with something that wasn't a hash
table. We can construct it in a way that makes it amenable to
that, and then reduce it down into a hash table, and here you
go. Very handy.
One last point is that you can see very clearly what
this is attempting to do, as opposed to, say, a for loop. It's
very clear what that step is doing, and then you can see what
that is doing, and you know that the result is going to be two.
Each line is kind of its own declarative step, and it should
be clear, just by staring at this, basically what you're
going to get out. This is one main difference from other
languages that have things--say, for instance, Rust's
iterator API--is the difference between the transducers
and the reducers. If we go up here, for example, the
difference between the transducers and the reducers and
the sources is not explicitly laid out, whereas with
transducers, it is. You have to be aware of how these things
are different. I think that that helps clarity.
Moving on. How do transducers work? Well,
we want to go see the README.
So, what we're going to do is
we're going to go to here.
You should still be able to see this.
This is the CL example, actually.
Let's go to transducers.el.
Their APIs and READMEs are the same,
but just for the sake of it, we will go see
how this looks on the Emacs side,
just so that nothing is a surprise.
But recall that the APIs are essentially the same
between the two. If you go to this section, writing your
own primitives, you can read about how transducers are
actually formed, whether or not you want to write them
yourself or not. We can see here t-map. We accept the
function that you want to operate with. Then you've got
this extra little lambda here that's coming in, and it's
receiving a thing that is named reducer. Now, while here
we're calling it reducer, it's actually the chain of all the
composed functions together. It's all those main
transducer steps. Finally, it's the reducer all
composed together with normal function composition.
That will matter very soon. Now here's the actual meat.
We can see the accumulative result that's coming in with the
current element. Now we need to operate on this.
Were it normally mapped, we would see us
applying the F to the input.
But here, you can see us applying the F to the input and then
continuing on. So us calling the rest of the composed chain
here is the effect of, in the previous slide, moving to the
next step. We could ignore this line for now.
If you're curious, please read the README in detail.
Now, what about reducers?
What do those look like? Well, let's just scroll
down here. Recall that a reducer is a function that's
consuming a stream, right? Zoom that up for you a little bit.
Now, in the case of count, recall that this is how it's
working, how we saw a moment ago. So clearly this list of five
elements only has five things in it. Well, a reducer by
structure is a function of two, one, or zero arguments. So we
can see here in the case of two, this is the normal iterative
case. We don't care about the input for count, we just care
about the current accumulated count that we're doing, and
we add one to it, and that's it. This then goes back to
the loop and the whole process starts again with the next
element. In this kind of done case, this is used internal to
that sort of the supervising function transduce. It's just
confirming the final result. Sometimes some
post-processing is necessary here, but in the case of
count, as it is so simple, that is not necessary. And now
here's the base case. This is also used within that
supervising transduce function at the very top. Well, if
you're counting, you have to start from somewhere, right?
In this case, well, what you're starting with is zero.
In the case of cons, you'd be starting with an empty list.
In the case of vector, you'd be starting
with an empty vector and so on.
Once again, if you are more curious, please take a look at
the README.
Okay, transducers in the wild. Well, let's go take a look at
processing some CSV data.
We're going to open up a new Emacs Lisp bracket here. So I have
a file. And in this file, let's just go look at C-x b right
there, you will see that we've got some bank transaction
information. It's got these transactions from a whole
bunch of different people into different accounts,
whether it's money coming in, money going out, and then a
basic description. How's your Latin? But for this little
test, what we want to do is we want to find Bob's final bank
balance. Let's get on to it. First of all, let's
just confirm, let's do some basic stuff.
with-current-buffer, find-file-noselect.
What's the name of that file?
This is pre-organized, so you
will just see it right here.
t-transduce and t-comp. We don't know what we're going to comp
yet. Actually, I'll just pass to show you. And then we will
see, let's just do a little t-count just to confirm. What's
our source? Well, our source is a buffer, t-buffer-read.
And note that because we're using with-current-buffer,
if we go like this, if we go current-buffer, this will just work. So
now let's... Well, that was odd. I should have done it like
that. There we go. So now we should make that a little smaller
so you can see what it is. Now if we hit RET, we should get the
right result. Okay, so there are 50,001 lines in this file,
but the one extra one is the name of the headers, right?
We want to process this file in more detail. So how can we do
that? Well, let's start by just automatically
interpreting the results as CSV. If we do that, okay, well
now we only have 50,000 entries as we expected, right?
Because it's going to pull out the header line. If we now say
we want to just filter out, you know, We only want Bob, right?
So if... gethash, it was in the row of name. Each line here is
made into, at least by default, is made into a hash map. So if
we go like this, we should see that. Okay, so 12,000 of these
lines or thereabout belong to Bob.
Let's just move that over a little bit. Actually, I suppose we don't even
need that anymore. I'll just keep that full size for you.
Okay, so all right, there's about 12,000 results for Bob of
the 50,000. What's next? Well, we want to confirm,
we want to pull out everything,
all of the in and the out entries.
Thank you. So, string to number, because we know that
everything came in as strings. Unfortunately, the from-csv
doesn't try to be smart at all, it's just pulling everything
in as string values. If you want actual things to be
numbers or whatever, that is up to you to do the parsing
yourself. Okay, so we have those two values now. We know
that we saw from the data just a moment ago that you're only
going to have a value in one column or the other. It's either
going to be 0 in the empty one, or you're going to have some
number in the other. So we know that we can just naively add
them. If it was in, it would always be positive. So we'll just
add that. But in the negative case, we want to just make it
negative really briefly before we add them all together.
let's now just prove to ourselves that we are sane here. What
we're going to do is we're going to quickly go say take
5 just to convince ourselves, and we'll go cons, and let's
see if we get kind of results that make sense. Okay, these
sort of make sense. It looks like you know Bob's got some big
expenses here. If we take say 15, does it look any better?
Okay, looks like he had a payday. All right, good job Bob.
Let's get back in there. Now we only really care about
adding the final result, right? So there we go. Add that all
together and we'll see what we get in a moment. Okay, wow,
Bob's rich. Okay, so it looks like in his 12,000
transaction, Bob has an overall net worth of $8.5 million.
Looking pretty good.
So here's an example of how you can, particularly in Emacs
Lisp, how you can very easily just get a file, consider it the
current buffer, and then just do whatever you want to it.
Note that there is sort of first-class support for both CSV
and JSON, and then you have, and both of those bring in their
values as hash maps, and then you're just free to do whatever
you want and process them, potentially both writing them
back out as CSV or JSON once again.
Some issues with transducers that can come up is
that one, a zip operator is missing, but I'm working on it.
Two is that performance, particularly in Emacs Lisp, isn't
that great. It could be due to the sort of nested lambda calls
that have to occur internally, but the common Lisp
implementation is quite good. and there's yet no support
for parallelism. You can imagine that a lot of those steps
you could potentially perform in parallel depending on the
platform, but research has not yet gotten that far. Okay,
that's all. Thank you very much. If you have any questions,
please contact me.