Rich Hickey: Reducers - A Library And Model For Collection Processing

http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html

by swannodette • 14 years ago

240 79 14 years ago

clojure.com

jules3• 14 years ago

If you use a mapped reducible twice, does that evaluate the function on each element twice?

mquander2• 14 years ago

If you call reduce on it twice, then sure, it would do all the work twice.

loumf2• 14 years ago

Jules's point is that the map is done twice, which it is. If you don't want that, you can reduce into a collection and then reduce the collection twice.

peppertree• 14 years ago

This will go nicely with Storm.

chubot• 14 years ago

I thought storm worked on infinite streams? Does this support that?

loumf2• 14 years ago

It should. It depends on which reducing function you choose -- the map step doesn't consume the stream, it just set up the mapped function to be called as you reduce. If your reducing function is lazy, then it works on infinite streams.

marshallp8• 14 years ago

Why not just do relational programming - prolog or sql. The lisp weenies still don't get it.

pestaa• 14 years ago

I'm not a supporter of Lisp myself, but still interested in what they don't get.

marshallp8• 14 years ago

Well, basically, most applications that you want to write are basically 90 percent rdbms with a thin layer on top for the views (usually php etc.). The 'power' of lisp isn't relevant. Other types of applications are usually performance critical and written in c etc, or glue code written in languages with libraries tcl/perl/python etc.

So basically the traditional niche of lisp, complex apps, has been replaced by sql.

There are apps written in lisp, like this site for example, but that's just for vanity mainly (pg is famous for his lisp books) - it would be have been easier to write it in sql.

jamii2• 14 years ago

https://github.com/clojure/core.logic

swannodette• 14 years ago

There's even a parallel branch built on top of fork/join that needs more work: https://github.com/clojure/core.logic/tree/fork-join

marshallp8• 14 years ago

So basically a thin sliver of what an sql rdbms provides.

stuarthalloway3• 14 years ago

I think we will see a Datalog made faster by parallel reduce/combine real soon now. :-)

jamii2• 14 years ago

I'm getting there. :)

francoisdevlin• 14 years ago

wrexsoul? Is that you?

jhuni• 14 years ago

> Why not just do relational programming - prolog or sql. The lisp weenies still don't get it.

John McCarthy was the first to recommend using logic in programs with his advice taker proposal. This inspired the logic programming paradigm:

http://www-formal.stanford.edu/jmc/mcc59/mcc59.html

Paul Graham (creator of the hacker news site) has an entire chapter in his book On Lisp on embedding prolog:

http://www.bookshelf.jp/texi/onlisp/onlisp_25.html

Peter Norvig's Paradigms of Artificial Intelligence programming includes an implementation of prolog in Lisp:

http://norvig.com/paip/prolog.lisp

Common Lisp relations: an extension of Lisp for logic programming proposed a mechanism for logic programming back in 1988:

http://www.lw20.com/2011051092557312.html

Franz. Inc is developing Allegro Prolog as an extension to Common Lisp:

http://www.franz.com/support/documentation/8.2/doc/prolog.ht...

The Clojure programming language includes relational programming functionality through the core/logic module:

https://github.com/frenchy64/Logic-Starter/wiki

Racklog is an embedding of Prolog-style programming in Racket.

http://docs.racket-lang.org/racklog/

The Shen programming languages includes a fully functional embedded prolog system:

http://shenlanguage.org/learn-shen/prolog.html

CycL is a declarative ontology language based upon classical first-order language which includes support for ontology components including parts and relations:

http://www.cyc.com/cycdoc/ref/cycl-syntax.html

What is it that we don't get again?

rickmode• 14 years ago

Is there no need to tune the number of threads with an approach like this? Or is there a general notion of the appropriate number of threads given the number of CPU cores?

drcode• 14 years ago

I believe the Java fork/join library handles this tuning automatically... so it's a freebie based on Rich Hickey's design.

weavejester2• 14 years ago

If you're not doing any I/O, the number of threads can be limited to the number of cores. I believe this is the default for Fork/Join.

puredanger4• 14 years ago

Correct. ForkJoinPool defaults to Runtime.getRuntime().availableProcessors() threads (but can be adjusted). The reducers library (https://github.com/clojure/clojure/commit/89e5dce0fdfec4bc09...) seems to initialize the pool with the default constructor.

picardo• 14 years ago

Rich will be talking about this library at the next Clojure NYC meetup. If anyone is in the neighborhood, feel free to drop by.

http://www.meetup.com/Clojure-NYC/events/56212552/

nickik2• 14 years ago

Will there be a video of this? That would be very awesome.

tsdh• 14 years ago

Oh yes, please! Or at least slides & example code.

bjaress3• 14 years ago

It seems like everything I read about Closure gives me a reason to use it, but a slightly stronger reason not to.

I'm happy to see a language putting this approach to collections into its core libraries and even combining it with ideas about parallel processing of data structures.

On the other hand, the whole thing is written as if Rich Hickey had an awesome idea, wrote some awesome code, and is now sharing his awesomeness with us. It's kind of a lost opportunity to give credit to the people who gave him the ideas (and maybe the people who helped him write the code, if there were any) and it's kind of a turn-off.

One good, prior write-up about reducing as a collections interface is:

http://okmij.org/ftp/papers/LL3-collections-enumerators.txt

snprbob863• 14 years ago

This is a blog post, not an academic paper with citations. It's about conveying a message: "Here's this new thing I made. You can use it. Here are it's pros and cons."

One of the nice things about Clojure is that it's a lot of great ideas from a lot of great people, packaged up with Rich Hickey's particular brand of digestible design.

Having watched most of Rich's published talks, it's apparent to me that he is quite humble about the fact that none of his ideas are that novel. He simply takes credit for this particular arrangement and takes pride in his design approach. His design sensibilities really resonate with a lot of people, hence Clojure's popularity.

On a personal note, I wish I could give credit to all the giant's whose shoulders I have stood on. However, it's simply not possible to remember all those details. Sometimes, ideas take days, weeks, months, YEARS to bake. Sometimes, someone tells you the solution to the problem, but you don't get it. Then 5 years later, it comes to you in a dream.

bjaress3• 14 years ago

Fair enough and absolutely true in principle, but I don't think "here are its pros and cons" is the message being conveyed.

Rich Hickey might be very humble in person, and I don't think this blog post is necessarily arrogant (but you're also not going to convince me it's humble).

I'm not really complaining about a lack of humility or even about Rich Hickey. I just feel like Clojure is one of those languages caught up in a sort of Cult of Awesomeness, where people feel obligated to lionize the pros and downplay or omit the cons and the contributions of others.

I don't really want to use a language that's being driven by that. Maybe I'm mistaken about Clojure fitting that description, and maybe meeting Rich Hickey would set me straight, but I still think it's a reasonable perception to take away from this blog post.

richhickey5• 14 years ago

I make no claims to novelty, and the blog post does link to http://www.haskell.org/haskellwiki/Enumerator_and_iteratee, the most similar work and a clear influence. If more people knew about Iteratee, it would be worth spending more time talking about the connections and contrasts, but they don't, and knowledge of it is not prerequisite to understanding reducers. No one helped me write the code.

bjaress3• 14 years ago

First, thank you for implementing and promoting this approach to collections.

I did see that link, because I liked the concept enough to read it all the way through without knowing Clojure, but that's not quite what I had in mind. You're right that most people have never heard of that library, which is why the way you presented it will leave most people with no idea that it was an influence (even if they read that far). That's something you could have just said, in one sentence, without getting into detail about how it was different.

I'm not really trying to criticize you for saying or not saying certain things, and I don't think you did anything wrong. Not really acknowledging influences is just a symptom of what turned me off. I feel like this post was written from a sort of aggressive fighting-for-popularity mindset that I'm uncomfortable with in a language.

EDIT: missing word

skew2• 14 years ago

Isn't foldr/build fusion much closer? A collection is represented by a "build" function that takes the reducer, and list transformers become reducer transformers. The main difference is that it's applied automatically by list library using rewrite rules, so it's not as obvious, the reducer is supplied as a pair of "cons" function and "init" value rather than a variadic function, and there's no parallel fold.

http://research.microsoft.com/~simonpj/papers/deforestation-... The first paper (yes, that's a .ps.Z - check the date)

http://www.scs.stanford.edu/11au-cs240h/notes/omgwtfbbq.html some recent slides, which also include a bit about a "stream fusion" which isn't yet in the standard library

http://darcs.haskell.org/cgi-bin/gitweb.cgi?p=packages/base.... The details from GHC's libraries - it's all in the RULES.

Drbble2• 14 years ago

This can't really be true because there has never been anything "clear" about enumerators and iteratees. Maybe a dozen people understand what's going on there.

Also, most of what's special about enumerators is the gymnastics needed for Haskell's type system, which isn't relevant to Clojure at all...

krosaen• 14 years ago

The implementation is a nice example of clojure protocols kicking ass - the core vector and map implementations needn't know anything about implementing coll-fold as the protocol definitions can be added within the reducers library.

snprbob863• 14 years ago

Just wondering out loud... I'm interested in how this relates to the existing implementations in core.

For example, if we went back in time, would all of the core functions have been implemented this way? Would this be a possible drop in replacement in the future? Could future versions of Clojure integrate these ideas more deeply? If so, what are these backwards compatibility concerns?

puredanger4• 14 years ago

> For example, if we went back in time, would all of the code functions have been implemented this way?

I don't think so - the existing implementations work on the higher-level abstraction of sequences. Reducers are optimized parallel versions that work on collections. While parallelism is extremely useful in some parts of your code, there is overhead and I don't think you would want either the overhead or the restriction of working below the sequence abstraction in the general case.

I seem to see some of the same choices being made available in the new Java 8 collections and parallel operations work. That is, it is up to the developer when to "go parallel".

For an entirely different approach, check out Guy Steele's Fortress language which eagerly executes most things in parallel by default (like all iterations of a loop, arguments to a function, etc) and you have to tell it not to do that.

Guy's Strange Loop 2010 talk is an interesting complement to this work: http://www.infoq.com/presentations/Thinking-Parallel-Program...

chrismcbride2• 14 years ago

Well besides the implicit parallelism of fold, wouldn't this be generally useful to reduce intermediate list creation? Or do lazy-seqs already solve that problem?

jwr• 14 years ago

I've been using Clojure for a production system for about two years now. It feels so great to use a language that just keeps handing you better tools as you go along.

What's nice is that the new tools are not just syntactic sugar, as in so many other languages. They either adress specific performance pain points (non-rebindable functions and numerics) or introduce new abstractions and tools (reduce-kv is a nice small example).

I love the fact that each time I read about a new thing coming to Clojure, I immediately think "well this will fit right into what I'm building, great!".

Clojure strikes a good balance between nice ideas and practicality.

MatthewPhillips• 14 years ago

Clojure is all substance and no glitter. It's all about getting the job done, which is why it's the most important language development in 20 years.

jacobolus• 14 years ago

The best way to get “all substance and no glitter” is apparently Rich Hickey’s “hammock driven development”. http://news.ycombinator.com/item?id=1962051

“To arrive at the simplest truth, as Newton knew and practiced, requires years of contemplation. Not activity. Not reasoning. Not calculating. Not busy behaviour of any kind. Not reading. Not talking. Not making an effort. Not thinking. Simply bearing in mind what it is one needs to know. And yet those with the courage to tread this path to real discovery are not only offered practically no guidance on how to do so, they are actively discouraged and have to set abut it in secret, pretending meanwhile to be diligently engaged in the frantic diversions and to conform with the deadening personal opinions which are continually being thrust upon them.” –George Spencer Brown in The Laws of Form, 1969

pron• 14 years ago

I would add Erlang to this list. Both are not extremely popular, but their importance comes not from providing features, but from providing a clear path to developing modern software that tackles modern problems on modern hardware.

surrealize• 14 years ago

The blog post compares this to Haskell enumerators/iteratees, but I think a more direct comparison to something haskelly is to monads.

He says: "The only thing that knows how to apply a function to a collection is the collection itself." Which is like a monad in the sense that the insides of a monad are opaque; you can only interact with a monad through the functions it gives you.

The "map" function from his "reducers" library has type:

fn * reducible -> reducible

(i.e., it takes a function and a reducible and gives you back a reducible)

while monadic "fmap" is a little higher-order and has type parameters, but it does something analogous:

(t -> u) -> (M t -> M u)

(i.e., take a function from type "t" to type "u", and return a function from "monad of t" to "monad of u"). It's a little different in that Hickey's "reducers/map" applies the argument function itself, while monadic fmap gives you a function that will do that.

Of course, his "reducers" library addresses a bunch of other stuff like parallelism, which isn't something that monads themselves are concerned with. I'm just saying that part of the interface to his new collection abstraction is monad-like.

Drbble2• 14 years ago

Everywhere you wrote "monad" you should have "functor". A monad is a functor with extra structure relating to how elements are inserted into the "collection" in the first place. Functors only discuss how functions are applied to elements already collected.

leif• 14 years ago

Rich Hickey proves again that he is among the leaders, if not the leader in careful, industrial-strength application of excellent theory. Bravo.

ashish01• 14 years ago

Awesome for the linked talk alone

http://www.infoq.com/presentations/Simple-Made-Easy

If you haven't seen this just take time to watch the first 15 minutes. Really worth it.

vorg• 14 years ago

> ...producing the same result as the Clojure's seq-based fns. The difference is that, reduce being eager, and these reducers fns being out of the seq game, there's no per-step allocation overhead, so it's faster. Laziness is great when you need it, but when you don't you shouldn't have to pay for it.

Looking forward to trying this out. I've been implementing another language in Clojure (tho just experimenting for the moment). It's a non-lazy language (Groovy) so I have reduce all over the place, e.g.

  (defn multiply [a b]
    (cond (and (number? a) (number? b)) (* a b)
          (and (vector? a) (integer? b)) (reduce conj [] (flatten (repeat b a)))
          (and (string? a) (integer? b)) (reduce str (repeat b a))))

  (defn findAll [coll clos]
    (reduce conj [] (filter clos coll)))

Hope reducers give a speed boost by removing the laziness I'm not using.

sanxiyn• 14 years ago

Recommended reading: Organizing functional code for parallel execution or, foldl and foldr considered slightly harmful (2009) by Guy L. Steele, Jr.

http://dl.acm.org/citation.cfm?id=1596551

minikomi• 14 years ago

Forgive my simplified response.. Is a way to look at this.. Rather than inside out, the functions compose outside in and then evaluate the reducable as a last step. That gives the benefit, since there's only one step the laziness needs to "devolve" in?

Rich Hickey: Reducers - A Library And Model For Collection Processing

Related Stories