Re:Rich Hickey – Inside Transducers [video]
by Blackthorn on Friday November 21, 2014 @11:14AM
(#8641875)
Even if you forget entirely about Clojure for a second, Rich has this very rare gift to take a complicated subject and make it easy for the audience to understand.
Re:Rich Hickey – Inside Transducers [video]
by lomnakkus on Friday November 21, 2014 @01:23PM
(#8642507)
This is a double-edged sword. Forgive me a small anecdote: I once had a wonderful tutor who could explain any advanced concept in highly intuitive terms and it just made sense... until I got out of the classroom. At which point I'd just have this feeling of "Hang on, whaaaaaa...?". The first time I attempted the exam in this particular subject matter, I failed miserably (rightly so). Having learned my lesson, I went back to study the actual source material more thoroughly instead of mostly just listening to the probably-best-educator on the subject. That time I actually understood the material and passed with flying colours. (I still think the particular educator had a major role in me passing at all, but I digress.)
That that for what you will, but please be aware that a "gift for simplification" sometimes is a double-edged sword and can leave the audience thinking that they've understood when, actually, they haven't.
I'm not saying that's the case here, just something to be wary of.
Re:Rich Hickey – Inside Transducers [video]
by brudgers on Saturday November 22, 2014 @12:39AM
(#8644862)
The difference here is that Rich Hickey is explaining a fundamental computing mechanism that many programmers have come in with but few think about enough to give a name: the finite state transducer [see Wikipedia].
The name "transducers" is not an invention, it's basic computer science. The idea of using transducers to abstract over an input is not really controversial in the sense that it's the essence of what turns source into executable code on digital computers. Sure, Ther are tradeoffs relative to which flavor of Turing machine underpins any abstraction, but at least this is an area where we can achieve clarity.
This is something Hickey implemented, not invented. Like all of automata, understanding the concept is likely non-trivial for some pretty smart people since it requires thinking about first principles of computing.
Re:Rich Hickey – Inside Transducers [video]
by agumonkey on Friday November 21, 2014 @01:52PM
(#8642646)
I had similar experiences many times, and I don't know what's best, looking at an abstraction for weeks until you get the "ohh they just meant this" or knowing in advance it's not that obscure and then work to imprint said abstraction deeper.
Re:Rich Hickey – Inside Transducers [video]
by lomnakkus on Friday November 21, 2014 @02:50PM
(#8643025)
Ever since that experience, I've tried to somehow try to practice working with "X" in some concrete way, even though it might feel like a classic "math problem" situation. Personally, I find it helps me get a grasp on "X", whatever it might be. (Mind you, this is just personal experience so YMMV.)
Re:Rich Hickey – Inside Transducers [video]
by cousin_it on Friday November 21, 2014 @09:33AM
(#8641409)
Yeah. That's actually how you implement lists in lambda calculus, as opaque functions that accept a "visitor". There are two different ways of doing it:
-- Mogensen-Scott encoding
data ScottList a = ScottList (forall r. (a -> ScottList a -> r) -> r -> r)
-- Boehm-Berarducci encoding
data ChurchList a = ChurchList (forall r. (a -> r -> r) -> r -> r)
Roughly, the first encoding gives you pattern matching, and the second gives you foldr (reduce). Either of these operations is sufficient to do anything with the list.
Also note that both of these are encodings of lazy (potentially infinite) lists. To encode strict (guaranteed finite) lists, you really need algebraic data types like in ML, the visitor pattern can't do that.
Re:Rich Hickey – Inside Transducers [video]
by ultimape on Friday November 21, 2014 @07:27AM
(#8640937)
I had a similar epiphany while learning about regular expressions in Perl. That connection with text processing is what helped me understand list comprehensions. They seem strikingly similar.
For JS, I personally prefer lo-dash for this kind of work, or dropping in polyfills from MDN.
I've been looking for similar libraries that work on typed-arrays because they are so much more efficient when working with web-workers or with raw canvas data. My attempts at hacking it in feel like they are just bad ideas: http://jsperf.com/float32array-map/2
Re:Rich Hickey – Inside Transducers [video]
by grayrest on Friday November 21, 2014 @08:20AM
(#8641100)
Most people use underscore/lodash for this stuff. The difference is that the js transducers libraries don't create intermediate arrays, only do enough work to produce the requested output, and work on top of anything that can be coerced into the iteration protocol. I've seen demos of using Facebook's Immutable JS, CSP.js [1], and I don't see why you couldn't put them on top of Typed Arrays or a FRP library like Kefir.
Re:Rich Hickey – Inside Transducers [video]
by tincholio on Saturday November 22, 2014 @04:31AM
(#8645199)
Graham Hutton has a very nice tutorial [0] on the universality of fold, which shows this elegantly (in Haskell, though).
[0] Graham Hutton, "A tutorial on the universality and expressiveness of fold", J. Functional Programming 9(4): 355–372, July 1999. http://www.cs.nott.ac.uk/~gmh/fold.pdf
Re:Rich Hickey – Inside Transducers [video]
by ajuc on Friday November 21, 2014 @02:37PM
(#8642935)
Not really?
When you reduce with function f(T1, T2) -> T3 the result of previous iteration becomes first argument for the next iteration, so they must be of the same "type".
Re:Rich Hickey – Inside Transducers [video]
by dkersten on Sunday November 23, 2014 @06:24AM
(#8648470)
Ah, no, you're right.
I was thinking that mapping can be f(T1)->T2 and how reducing can change types too, but I guess I wasn't paying enough attention because of course the reduce signature is f(accumulator, input) and the output is accumulator, so yea, you're absolutely right: f(T1,T2)->T1
Re:Rich Hickey – Inside Transducers [video]
by charlysisto on Friday November 21, 2014 @08:38AM
(#8641165)
So Transducers generalize the usage of Enumerable functions such as map, reduce, filter, flatMap (...).
Please could someone tell me if this is conceptually different from ruby's Enumerable module which only needs the class its included in to implement `each` so anything can be enumerable ? Or is it a similar but just in translated to the FP world ?
Re:Rich Hickey – Inside Transducers [video]
by YuriNiyazov on Friday November 21, 2014 @08:51AM
(#8641225)
Yes; There are differences.
1. Transducers are parallel under the covers. Since the expectations is that the code that the predicate or mapping functions that you pass into map, filter and reduce are pure (no variables are changed, no state is modified, just a calculation that is only dependent on arguments) the parallelism is hidden away from you, but it's there. Ruby's Enumerable can't do parallelism
2. When you compose transducers, there are no intermediate sequences generated. The simplest example is this:
In Ruby:
[1, 2, 3].map {|x| x + 1}.map {|x| x+ 2} will generate an intermediate array [2, 3, 4] after the first map, and then will generate [4, 5, 6] when it has evaluated the whole expression.
In Clojure (I am sure I got the syntax wrong for this one)
(transduce (map #(+ 2 %) (map inc)) [1 2 3]) will create an intermediate mapping function that will first increment, then add 2 to its argument, and then will map once using that intermediate function.
Re:Rich Hickey – Inside Transducers [video]
by YuriNiyazov on Friday November 21, 2014 @09:43AM
(#8641441)
If you watch the first Rich Hickey Transducers talk, he shows that some transducers (the ones that rely in the underlying reduce implementation that uses fork/join and assumes that reducing the collection is associative) are already parallelized. I agree with you regarding `take`
Re:Rich Hickey – Inside Transducers [video]
by cfeduke on Friday November 21, 2014 @01:01PM
(#8642409)
IIRC from yesterday's talk he was explaining that these will be easy to parallelize, and its slated for 1.7. I had thought they were already parallel myself until I saw the talk; and possibly some of them are, but the item is still Open.
Re:Rich Hickey – Inside Transducers [video]
by nickik on Friday November 21, 2014 @12:46PM
(#8642339)
The big thing is not even that, the big thing is that you can seperate your logic from the data that you want to process. So instead of (map inc [1 2 3 4]) you can do (def inc-transducer (map inc)) and then use that for any datastructures, channels or whatever other transducer context people come up with. To be sure, you would not do that with (map inc) but if you have more logic, you could.
Re:Rich Hickey – Inside Transducers [video]
by Skinney on Friday November 21, 2014 @12:05PM
(#8642111)
Nah, Clojure seqs are more like .NET/LINQ enumerables.
Functions that work over seqs/enumerables return a new seq/enumerable. From what I understand, and I'm sure I am wrong, a transducer receives and transforms a value, and may call the next transducer with the transformed value.
The nice thing is that a transducer does not create intermediate results (a seq/enumerable), and that it doesn't make any assumptions on the underlying datastructure. So you can, for instance, send a value through a transducer and directly place it in a list, instead of creating a set of enumerables and then call .ToList on that. Since transducers can work with any value, you also aren't tied to enumerables. So transducers should be a little more universal and performant than enumerables.
Re:Rich Hickey – Inside Transducers [video]
by icefox on Friday November 21, 2014 @01:18PM
(#8642485)
A contrived example in C#/LINQ
Enumerable.Range(1, 100)
.Where(n => n % 2 == 0)
.Select(n => n * 2)
.ToList();
And as a transducer it could looks something like this?
sequence(
Enumerable.Range(1, 100),
compose(
filter(n => n %2 == 0),
map(x => x + 1)
)
).ToList();
On the linq side it would create only 2 enumerable objects (one for where and select) and the ToList would result in a copy the object pointer as it was passing through each enumerable. For the transducer example rather than having 2 enumerable's we would have 2 transducer objects?
I absolutely understand the case where a language's map/filter/reduce/etc results in a whole new list, but for the above case the performance/memory overhead improvement doesn't see that huge and really minor. The fact that it removes the overhead of having to support IEnumerable and as you mentioned is only dealing with functions is what seems like a win. At first I was thinking that plain old LINQ is also more readable, but my contrived c# transducer example doesn't look that bad in the end. Am I incorrect on any of this?
Re:Rich Hickey – Inside Transducers [video]
by ajanuary on Friday November 21, 2014 @04:24PM
(#8643449)
With Linq you can't really create an object/function that describes the transformation that should happen. I start with an enumerable, describe how to transform /that/ enumerable, and in the end have something that describes a transformation applied to a particular initial data. I can't do anything with it but laziy read the transformed values for the original input.
With transducers I can describe a transformation that should happen to /some/ reducable input, and in the end have something that represents just the transformation. I. An then apply that to any reducable input I have.
[edit]
Your example becomes:
var incrementedEvens = compose(
filter(n => n %2 == 0),
map(x => x + 1)
);
transduce(Enumerable.range(0, 100), incrementEvens);
var lowerAlph = compose(
filter(x => Character.isAlpha(x)),
map(x => x.ToLowercase())
);
System.in.setTransducer(lowerAlpha);
Re:Rich Hickey – Inside Transducers [video]
by charlysisto on Friday November 21, 2014 @09:24AM
(#8641359)
Thanks for the answer. Indeed Ruby in general has the limitations inherent to its "non functional" nature. However regarding 2) Enumeration can now (in ruby 2.0) be lazy and thus take each item one after the other through the whole chain.
(1..Float::INFINITY).lazy.map{|a| p a; a*10}.map{|a| p a+1}
# => 1 11 2 21 etc...
So it can work with streams & so on...
But I know (from a Jessica Kerr presentation) it also has limitations there.
Re:Rich Hickey – Inside Transducers [video]
by drostie on Friday November 21, 2014 @11:28AM
(#8641937)
Transducers are a different kind of thing, not just a generalized usage of enumerable functions.
Clojure transducers are isomorphic to functions of type `a -> [b]`, that is, functions which take some thing and return lists of other things. You can implement map and filter in this language:
tmap f a = [f a]
tfilter p a = if p a then [a] else []
You can also compose two such functions:
concat :: [[x]] -> [x]
concat [] = []
concat (x : xs) = x ++ concat xs
concatMap f list = concat (map f list)
compose lb_a lc_b = \a -> concatMap lc_b (lb_a a)
One reduction function (`foldr`) turns out to just be the identity function [a] -> [a], as I recall.
The interesting thing about Clojure transformers is that they have a strange continuation-passing form, such that this function `compose` that I wrote above for the type `a -> [b]` is actually in Clojure just a function composition. That is, instead of `a -> [b]` we see `forall r. (b -> r -> r) -> (a -> r -> r)`, which composes with normal function composition.
Re:Rich Hickey – Inside Transducers [video]
by moomin on Friday November 21, 2014 @08:51AM
(#8641224)
What's you're thinking of is more like ISeq in Clojure, or Foldable is Haskell. The more interesting generalisation is not between arrays, vectors and hashsets, but between data structures and event streams.
Re:Rich Hickey – Inside Transducers [video]
by moomin on Friday November 21, 2014 @08:55AM
(#8641246)
It's not that clear there will be one. Transducers have three steps: begin, during and end. In practice, start is only used for reduce operations and outside of reduce operations end can only be used for its side effects.
There's also definitional issues e.g. can you have an async transducer?
Re:Rich Hickey – Inside Transducers [video]
by kbeaty on Friday November 21, 2014 @10:23AM
(#8641649)
You can indeed use transducers in asynchronous contexts. In fact, that is what intrigues me most about the abstraction.
Transducers are defined such that you can abstract the context of input, output and iteration and focus on the transformation of each element from an independent source individually. The implementation of each transducer accepts another transformation in a "pipeline" (eventually the output sink) and accepts an input during an external iteration process. The implementation decides what to do with it (map changes with a function, filter ignores certain values with a predicate, etc.) You can also define transducers that send multiple values for each input (think string.split) or some that do not send any until completion (think buffered results).
Since the iteration source and sink are abstracted from the transformation, you can use the same transformation in other contexts (Promises, event streams, IO streams, CSP, etc.)
I've been experimenting with transducers in asynchronous contexts in JavaScript if anyone is interested, for example:
Re:Rich Hickey – Inside Transducers [video]
by nickik on Friday November 21, 2014 @12:48PM
(#8642347)
People keep attacking him whenever he interduces something. Why? Every time he releases something, he also shows from what research it originated. Go back to the first transducer talk and you will see the references.
Re:Rich Hickey – Inside Transducers [video]
by lomnakkus on Friday November 21, 2014 @01:34PM
(#8642563)
Personally, I don't mind him too much even though I'm a typeful-programming weenie. That said, he does have a tendency to somewhat unfoundedly say "... and you couldn't do this in a typed language" (or at least allude to it)... whereas people again and again show that, yes, it could be done in a statically typed language. In fact, this is trivially true in a sense as shown by Bob Harper[1] another person who is undoubtedly hugely influential, but who I have trouble with because of his obvious bias and trollish ways.
(I think Rich is absolutely spot on on many of the more abstract things about or industry/craft, but this is just one of those details that irks me.)
Re:Rich Hickey – Inside Transducers [video]
by ajanuary on Friday November 21, 2014 @05:26PM
(#8643745)
In the strangeloop talk his argument seemed to be that you couldn't use types to describe the entire and exact contract of transducers. Which is true (and true of almost anything), but you can at least describe a significant enough chunk of it to reduce errors.
As always it's a trade off. As you try to capture more of the contract, you massively increase complexity, sometimes to the point of reducing usability (i.e. staring at an obtuse type error, or trying to work out how to do basic things with a function just from a Scala type)
It's my interpretation that "you can't type transducers" is an invitation to think more deeply about types and the limitations in what they can express, mixed in with some "get off my back about creating a dynamically typed language".
Re:Rich Hickey – Inside Transducers [video]
by seanmcdirmid on Friday November 21, 2014 @05:35PM
(#8643787)
Isn't the problem with transducer typing is that transducers aren't very functional? In one of your posts you wrote:
System.in.setTransducer(lowerAlpha);
In the LINQ/functional origami world, you could only produce new streams, not transform an existing stream in place. Because a new stream is computed, a new type can be computed. However, from what I've seen with transducers, they would be limited to basically Func<T, Predicate<T>, T> signatures.
Re:Rich Hickey – Inside Transducers [video]
by lomnakkus on Tuesday November 25, 2014 @03:14PM
(#8659447)
That's part of it, but of course you can embed monadic types/effects within the appropriate combinators. (I think "tel" showed an example of this in the original "transducers" post)
That that for what you will, but please be aware that a "gift for simplification" sometimes is a double-edged sword and can leave the audience thinking that they've understood when, actually, they haven't.
I'm not saying that's the case here, just something to be wary of.
The name "transducers" is not an invention, it's basic computer science. The idea of using transducers to abstract over an input is not really controversial in the sense that it's the essence of what turns source into executable code on digital computers. Sure, Ther are tradeoffs relative to which flavor of Turing machine underpins any abstraction, but at least this is an area where we can achieve clarity.
This is something Hickey implemented, not invented. Like all of automata, understanding the concept is likely non-trivial for some pretty smart people since it requires thinking about first principles of computing.
"The reduce function is the base transformation; any other transformation can be expressed in terms of it (map, filter, etc)."
This seems so obvious in retrospect -- I can't believe I had never made that connection before.
Also note that both of these are encodings of lazy (potentially infinite) lists. To encode strict (guaranteed finite) lists, you really need algebraic data types like in ML, the visitor pattern can't do that.
For JS, I personally prefer lo-dash for this kind of work, or dropping in polyfills from MDN.
For some context, here are .map functions applied to normal arrays http://jsperf.com/native-vs-array-js-vs-underscore/54
I've been looking for similar libraries that work on typed-arrays because they are so much more efficient when working with web-workers or with raw canvas data. My attempts at hacking it in feel like they are just bad ideas: http://jsperf.com/float32array-map/2
[1] http://jlongster.com/s/nationjs-slides/
[0] Graham Hutton, "A tutorial on the universality and expressiveness of fold", J. Functional Programming 9(4): 355–372, July 1999. http://www.cs.nott.ac.uk/~gmh/fold.pdf
When you reduce with function f(T1, T2) -> T3 the result of previous iteration becomes first argument for the next iteration, so they must be of the same "type".
Or am I missing something?
I was thinking that mapping can be f(T1)->T2 and how reducing can change types too, but I guess I wasn't paying enough attention because of course the reduce signature is f(accumulator, input) and the output is accumulator, so yea, you're absolutely right: f(T1,T2)->T1
(Shameless plug in the hope it may be helpful to someone)
[1]: http://simplectic.com/blog/2014/transducers-explained-1/
- it was referenced in this great post detailing the transducer notion with Clojure, Scala, and Haskell: http://blog.podsnap.com/ducers2.html
Please could someone tell me if this is conceptually different from ruby's Enumerable module which only needs the class its included in to implement `each` so anything can be enumerable ? Or is it a similar but just in translated to the FP world ?
1. Transducers are parallel under the covers. Since the expectations is that the code that the predicate or mapping functions that you pass into map, filter and reduce are pure (no variables are changed, no state is modified, just a calculation that is only dependent on arguments) the parallelism is hidden away from you, but it's there. Ruby's Enumerable can't do parallelism
2. When you compose transducers, there are no intermediate sequences generated. The simplest example is this:
In Ruby: [1, 2, 3].map {|x| x + 1}.map {|x| x+ 2} will generate an intermediate array [2, 3, 4] after the first map, and then will generate [4, 5, 6] when it has evaluated the whole expression.
In Clojure (I am sure I got the syntax wrong for this one) (transduce (map #(+ 2 %) (map inc)) [1 2 3]) will create an intermediate mapping function that will first increment, then add 2 to its argument, and then will map once using that intermediate function.
The big thing is no intermediate results.
http://dev.clojure.org/jira/browse/CLJ-1553
Functions that work over seqs/enumerables return a new seq/enumerable. From what I understand, and I'm sure I am wrong, a transducer receives and transforms a value, and may call the next transducer with the transformed value.
The nice thing is that a transducer does not create intermediate results (a seq/enumerable), and that it doesn't make any assumptions on the underlying datastructure. So you can, for instance, send a value through a transducer and directly place it in a list, instead of creating a set of enumerables and then call .ToList on that. Since transducers can work with any value, you also aren't tied to enumerables. So transducers should be a little more universal and performant than enumerables.
I absolutely understand the case where a language's map/filter/reduce/etc results in a whole new list, but for the above case the performance/memory overhead improvement doesn't see that huge and really minor. The fact that it removes the overhead of having to support IEnumerable and as you mentioned is only dealing with functions is what seems like a win. At first I was thinking that plain old LINQ is also more readable, but my contrived c# transducer example doesn't look that bad in the end. Am I incorrect on any of this?
With transducers I can describe a transformation that should happen to /some/ reducable input, and in the end have something that represents just the transformation. I. An then apply that to any reducable input I have.
[edit]
Your example becomes:
You can really do that in Linq.(1..Float::INFINITY).lazy.map{|a| p a; a*10}.map{|a| p a+1} # => 1 11 2 21 etc...
So it can work with streams & so on... But I know (from a Jessica Kerr presentation) it also has limitations there.
Clojure transducers are isomorphic to functions of type `a -> [b]`, that is, functions which take some thing and return lists of other things. You can implement map and filter in this language:
You can also compose two such functions: One reduction function (`foldr`) turns out to just be the identity function [a] -> [a], as I recall.The interesting thing about Clojure transformers is that they have a strange continuation-passing form, such that this function `compose` that I wrote above for the type `a -> [b]` is actually in Clojure just a function composition. That is, instead of `a -> [b]` we see `forall r. (b -> r -> r) -> (a -> r -> r)`, which composes with normal function composition.
Transducers overall are quite intressting, I am exited to see what other transducer context people come up with.
There's also definitional issues e.g. can you have an async transducer?
Transducers are defined such that you can abstract the context of input, output and iteration and focus on the transformation of each element from an independent source individually. The implementation of each transducer accepts another transformation in a "pipeline" (eventually the output sink) and accepts an input during an external iteration process. The implementation decides what to do with it (map changes with a function, filter ignores certain values with a predicate, etc.) You can also define transducers that send multiple values for each input (think string.split) or some that do not send any until completion (think buffered results).
Since the iteration source and sink are abstracted from the transformation, you can use the same transformation in other contexts (Promises, event streams, IO streams, CSP, etc.)
I've been experimenting with transducers in asynchronous contexts in JavaScript if anyone is interested, for example:
[1]: http://simplectic.com/projects/underscore-transducer/ [2]: http://simplectic.com/projects/underarm/ [3]: https://github.com/transduce/transduce-async [4]: https://github.com/kevinbeaty/transduce-stream [5]: https://github.com/transduce/transduce-push [6]: https://github.com/transduce/transduce-then
Which might be okay, but my basic point that it's definitionally fuzzy still holds.
(I think Rich is absolutely spot on on many of the more abstract things about or industry/craft, but this is just one of those details that irks me.)
[1] http://existentialtype.wordpress.com/2011/03/19/dynamic-lang...
As always it's a trade off. As you try to capture more of the contract, you massively increase complexity, sometimes to the point of reducing usability (i.e. staring at an obtuse type error, or trying to work out how to do basic things with a function just from a Scala type)
It's my interpretation that "you can't type transducers" is an invitation to think more deeply about types and the limitations in what they can express, mixed in with some "get off my back about creating a dynamically typed language".