"functional" reactive programming

[hank]

Hi,

I became aware of RxJava through the upcoming presentation at the LambdaJam functional programming conference announced recently (http://lambdajam.com/sessions#christensen). I was wondering what makes RxJava qualify as "functional". The original .NET Rx that this is modeled after doesn't make any claims of being "functional" in any way. In particular, the implementation seems to involve cells holding the current state of an observable plus a stateful lists of subscribers which is considered "un-functional" in FP circles. I asked a similar question about an "FRP" library recently presented at Clojure/West: https://groups.google.com/d/msg/clojure/vkQR5KS08Ms/xxMrkwPA4gsJ

I am asking because I am trying to build a reactive library in Clojure myself and due to the highly concurrent scenarios that this is targeted to I am finding myself having to use functional data structures such as infinite cons sequences to share data between several consumers of a producer. It allows for concurrency and compositionality, it comes with memory management headaches.

Does your library allow for concurrent consumers in different threads? Does it employ functional data structures? In what way is it more functional than .NET Rx?

Thank you

Cheers

-- hank

[Matthias]

Correct me if I'm wrong but I don't think holding on to local state is not against the principles of functional programming. In fact it's a common pattern to hold on to a result of a computation and enter a recursion, then combining the results. Similarly, observables hold onto the observer until the observer unsubscribes or the call stack unwinds by the observable completing its computation.

As for the F in FRP. I can't speak for Rx on .NET since I have never used it. For RxJava, the functional parts manifest themselves in various ways, most prominently in treating observables as higher order functions that can be passed around and combined to obtain new functions (e.g. using map, reduce, take, zip, etc.). This is a universal pattern in the library. Secondly it makes heavy use of closures (or anonymous classes), which in conjunction with the above is used to generate new observables to perform a task. Lastly a universal pattern is to not work on mutable state. All changes to an observable will yield in a new observable, there is no mutation. An observer is passed in as a final reference and can not be overwritten. I think this is another aspect of functional programming which is very prominent in RxJava.

A main difference to Rx on .NET is that they use LINQ operators which allow you to query collections in a SQL-style way. I'm not sure whether that follows functional styles, having never used it before, but it doesn't look like it does. Hence, I guess, in the original Rx the R is more prominent than the F, but don't quote me on that.

[Joachim Hofer]

Actually, observables in Rx should be monads (as long as the implementation doesn't go wrong...), and this means that you get that nice pipelining composition of observables that imho is one of the key ingredients to good functional APIs.

I don't think that .NET Rx is very different to RxJava in this aspect.

If you want to see a way more "hardcore" functional approach to Reactive, I guess this blog and implementation (in Scala) looks quite promising: https://efasckenoth.wordpress.com/, https://github.com/stefan-hoeck/dire

Also, this paper is a must read if you ask me: http://infoscience.epfl.ch/record/176887/files/DeprecatingObservers2012.pdf

[hank]

Hi Matthias,

Thanks for addressing my concerns.

On Thursday, April 18, 2013 1:15:43 AM UTC+10, Matthias wrote:

Correct me if I'm wrong but I don't think holding on to local state is not against the principles of functional programming. In fact it's a common pattern to hold on to a result of a computation and enter a recursion, then combining the results. Similarly, observables hold onto the observer until the observer unsubscribes or the call stack unwinds by the observable completing its computation.

As for the F in FRP. I can't speak for Rx on .NET since I have never used it. For RxJava, the functional parts manifest themselves in various ways, most prominently in treating observables as higher order functions that can be passed around and combined to obtain new functions (e.g. using map, reduce, take, zip, etc.). This is a universal pattern in the library. Secondly it makes heavy use of closures (or anonymous classes), which in conjunction with the above is used to generate new observables to perform a task.

I'm not too sure I understand "holding onto state" (is that "mutating state"?) or how closures are necessarily functional, but I understand this here:

 

Lastly a universal pattern is to not work on mutable state. All changes to an observable will yield in a new observable, there is no mutation. An observer is passed in as a final reference and can not be overwritten. I think this is another aspect of functional programming which is very prominent in RxJava.

The "Subject" type Observable seems to have a mutable map of subscribers in it. Adding an observer modifies the observable in place and not yield a new Observable as you claim: https://github.com/Netflix/RxJava/blob/master/rxjava-core/src/main/java/rx/subjects/Subject.java#L40 Am I looking at the wrong piece of code?

Cheers

 -- hank

[hank]

Hi Joachim,

On Thursday, April 18, 2013 6:57:56 PM UTC+10, Joachim Hofer wrote:

If you want to see a way more "hardcore" functional approach to Reactive, I guess this blog and implementation (in Scala) looks quite promising: https://efasckenoth.wordpress.com/, https://github.com/stefan-hoeck/dire

Also, this paper is a must read if you ask me: http://infoscience.epfl.ch/record/176887/files/DeprecatingObservers2012.pdf

I'm not too sure about the former, the Scala UI thing. They talk about updating the whole graph in one thread ... if it was a true functional implementation, concurrency would result as a consequence. The latter (Scala.React, where's the implementation?) has similar problems but doesn't claim to be FRP in the first place so no problem with that.

Cheers

-- hank

[Matthias]

Hi Hank,

On Thursday, April 18, 2013 2:31:11 PM UTC+2, hank wrote:

I'm not too sure I understand "holding onto state" (is that "mutating state"?) or how closures are necessarily functional, but I understand this here:

Not mutating state, rather accumulating values by recursing over a function and returning the accumulated result. There's no mutation happening here, but clearly any such implementation deals with state (kept by nesting the call stack.) I don't see how any program could execute without any notion of state per se.

Closures, as I understand, are one way to represent lambda expressions in programming languages (anonymous, higher order functions that can be passed to other functions).

Regards,

Matthias

[benjchr...@netflix.com]

I became aware of RxJava through the upcoming presentation at the LambdaJam functional programming conference announced recently (http://lambdajam.com/sessions#christensen). I was wondering what makes RxJava qualify as "functional". The original .NET Rx that this is modeled after doesn't make any claims of being "functional" in any way. In particular, the implementation seems to involve cells holding the current state of an observable plus a stateful lists of subscribers which is considered "un-functional" in FP circles. I asked a similar question about an "FRP" library recently presented at Clojure/West: https://groups.google.com/d/msg/clojure/vkQR5KS08Ms/xxMrkwPA4gsJ

RxJava supports "functional reactive" or just "reactive" programming as well as mixing imperative and functional styles. The Netflix API team happens to favor "functional reactive" for our use cases hence we focus on those aspects of it in our communications about it. 

As for "pure functional" it is not even an attempt, Rx is a "practical" approach at functional reactive programming in imperative languages - we are not using Haskell, but Rx was created by a Haskell computer scientist so is influence by a purely functional language and all the math behind it.

Following are some notes I took while speaking with Erik Meijer (inventor of Rx) at Goto Chicago on the subject:

- a method/function definition can be "pure" but it's okay to be mutable inside the implementations

- nothing magical about a function ... a function is given arguments and always returns the same value

- "pure" functions can never do IO (have side-effects)

- mutation is just one of many effects, immutability is not a specific rule of functional programming

- effects include

... exceptions

... casting

... accepting instance A of Type T and returning instance B of Type T

... IO

- either remove all effects or embrace them

- embrace them and deal with them

- being functional by itself is not a goal, a method/function definition can be "pure" but it's okay to be mutable inside the implementations

- don't be so uptight about side-effects, we live in an imperative world so be explicit and deal with it

- think functionally and try to implement accordingly but don't think it's any better than it is

Does your library allow for concurrent consumers in different threads?

Yes you can use operators such as publish or multicast to achieve this. Also look at the various Subject implementations which provide different use cases for one-to-many publishing.

 

Does it employ functional data structures?

When you say "functional data structures" I assume you're referring to immutable structures such as Clojure has. No we don't, and it doesn't matter since those are implementation details - the same way Clojure allows mutation under the covers (generally for performance reasons) as long as the external input/output acts functionally. Rx operators all behave that way. You never have access to or are exposed to underlying data structures as those are implementation details of the operators and thus don't account for whether an operator is "functional" or not.

 

In what way is it more functional than .NET Rx?

It is no more or less functional than .Net Rx, it is how someone chooses to use it that would dictate whether you are using it just for the "reactive" qualities but programming imperatively and mutating external state and other such things, or if you follow a more "functional reactive" approach.

One thing that does affect RxJava usage patterns is that we don't have LINQ which is a C# DSL that lends itself to a more SQL style approach whereas RxJava only uses functions/closures/anonymous inner classes. 

Hope this all helps despite being very late.

 

[hank]

Thanks for clarifying this.

[rebcabin]

I worked with Erik Meijer for several years on the original LINQ and the later Rx .NET libraries, and I'd like to offer the following perspective: the primary benefit of "functional" programming, whether pure or applied, is composability. The rxjava library is a reasonably faithful implementation of the Standard Query Operators that Rx borrows from LINQ and LINQ borrowed from Haskell, and Haskell borrowed from Miranda ... all back to Lisp :)  The typical usage pattern is to chain operators, as in someObservable.filter(someLambda).map(someOtherLambda).mapMany(...).groupBy(...) yadda yadda. Each of the SQO expressions has a certain level of autonomy (due to the lambda's being closures), so can be independently rearranged, remoted, hydrated, ..., in-short, treated like data. This is a really big software-engineering advantage over the contending object-oriented style, in which liberal composition is much harder due to proliferation of types, co- and contra-variance issues, and the composition of locks and exceptions. The meaning of a concurrent execution of your program may depend on the way you nested or inherited your classes. Functional patterns are leaner (fewer features to snag you) and just built around composability from the ground up.

[Ben Christensen]

Thank you rebcabin for providing further information. With your background would you mind confirming my understanding of the terminology in this space?

Here is a simple Rx example (using Groovy):

getData()
.filter({ it.endsWith("2") })
.take(5)
.map({ stringValue -> return stringValue + "_transformed"})
.subscribe({ println "onNext => " + it})

I would describe this as "pure functions composed together and applied to data in a reactive manner". Thus, reactive and functional styles of programming are being used, hence the "functional reactive" term. 

Admittedly the pureness breaks down in the 'subscribe' since it performs IO and thus has side-effects (on purpose), but it is kept to the final subscribe and that is the practical approach taken with Rx in non-purely-functional languages. I think it's a fair argument though that all of the declarations prior to subscription are "pure" in the functional sense.

Am I correct in my assessment and descriptions above?

Would you use different terminology than "functional reactive" to describe this?

[Brian Beckman]

I think you're right, Ben. All the lambda expressions before the .subscribe are "pure" in the sense that they are deterministic functions: straight mappings from inputs to outputs with no extraneous information pulled from the environment and no side-effects pushed to the environment. 

In some sense, "println" can be viewed as a pure function, since it always produces "nil" (assuming it doesn't throw an exception), but it's not called for its ability to produce a value, it's called to produce its side-effect. This is exactly the kind of thing Haskell handles with the IO monad, which passes around a fictional object that maintains the "state of the world." When you do side-effecting operations on the world, the IO monad's "bind" operator does a transformation on that conceptual "state object," so if you do the same thing twice, you get the same answer twice (but why would you? :)

The little book "Learn You a Haskell for Great Good" I think has hit a sweet spot of showing numerous small examples that clear the fog on all this pure-versus-impure stuff and makes it really easy to understand monadic operations without getting caught up in weird analogies and vaporous abstractions.

The only problem I know of with the term "functional reactive" is that there is some claim on the term originating with Conal Elliott's work (http://conal.net/papers/push-pull-frp/) and implementations like FlapJax in JavaScript (http://www.flapjax-lang.org/). 

The Rx design is based on Erik's original observation that Observable is the categorical dual of Enumerable. This is amazingly cool because it means we don't have to invent the query language, by-and-large (we do have to worry about concurrency, throttling, delays, and time-dependent things, but map, mapMany, filter, all the monadic transforms go over with virtually NO change).  

Now, Elliott's FRP and FlapJax introduce two kinds of things: "events," which are very like our "observations," my term for things that observables produce and that observers consume; and "behaviors," which I admit I do not understand. They are some kind of more continuous time-varying gadget, but it will take a dedicated effort to understand Elliott's paper or FlapJax's programming model. I think it's highly likely that Elliott and FlapJax have a LOT in common with Rx, but that analysis has not been done. For me to find it satisfactory, we have to account for Erik's discovery, which, in my view, LIMITs the acceptable freedom in design space to those things with duality arguments behind them. The category-theory justification behind Rx is just too strong to be ignored, and I think the burden of justification rests on innovations outside Rx: you gotta show where it comes from, how it fits, and why we need it. At least, those are the questions I would ask myself if I undertook to understand Elliott or FlapJax all the way.

For now, I need to "get things done." Rx's model is REALLY easy to explain and teach: I just tell people that everything they know from SQL or from LINQ or from functional programming (pure or applied) is RIGHT. The barrier to entry is very low, and as soon as people get to start throwing away their thread-switching and locks they rejoice and are sold.  That's a pretty good track record for something so young. But, yes, Elliott's paper is on my bucket list.

[Brian Beckman]

Here is another little idea that may help with understanding this term "functional."  If you're considering a pure function: one that just maps inputs to outputs, then note that there are ONLY TWO ways to get data into the body of such a function: parameters and non-parameters. Consider the following (in Clojure)

( (fn [x y] (+ x y)) 2 3 )

(let [y 3]  ( (fn [x] (+ x y)) 2)

In the first case, the fn has two parameters and no non-parameters. It stands alone with no "linkage" to its environment. Some people call these things "pure functions" to distinguish them from "closures," but I don't buy that terminology, I'd rather call them "closed closures" or something like that: many more people use "pure function" to mean functions that have no side effects. But you will see that there is a bit of a gray area, since the dual of a side effect is getting info from the environment. 

In the second case, the fn has one parameter, x, and one non-parameter, y. Non-parameters are also called "free variables," and functions that have free variables in their bodies are called "open closures" if you're being really precise. The compiler must generate extra code for evaluating such functions at run time. That extra code knows where to find the free variables' values. Other tricks like lambda lifting converts open closures into partial applications of closed closures, etc. etc., then there is the whole story of dynamic binding: free variables that get their values depending on RUN time context, like "this" in JavaScript (insert Munch's "The Scream").

But the point to bear in mind is that no matter how complicated things look, there are just only two ways to get data into a function: parameters and free variables. Non-pure functions, like "random" or "getline" or "println", in their implementations, will refer to global variables or functions or to members or static members of their classes. In the body of the function, these appear as free variables (or as linked to a secret invisible parameter named "this" (insert more screaming about JavaScript). 

[Ben Christensen]

Brian, 

Thanks for the review and sharing further thoughts.

Regarding this point:

The only problem I know of with the term "functional reactive" is that there is some claim on the term originating with Conal Elliott's work (http://conal.net/papers/push-pull-frp/) and implementations like FlapJax in JavaScript (http://www.flapjax-lang.org/). 

I have read that paper and I'm not academically trained enough in category theory and related subjects to understand let alone analyze it. I have also tried to understand what is meant by FRP via the Haskell site http://www.haskell.org/haskellwiki/Functional_Reactive_Programming and http://www.haskell.org/haskellwiki/Reactive but can not determine via those links why "functional reactive" should not apply to Rx.

The Haskell page describes it as:

- Functional Reactive Programming (FRP) integrates time flow and compositional events into functional programming. 

Rx applies 'reactive', 'functional' and 'compositional' approaches, and I'd argue that 'time flow' is also available to it through Schedulers which allow both real and virtual time.

From the wikipedia page, which I also feel is not very clear I interpret it as follows:

• The concept of "behaviors" or "signals" which model values that vary over continuous time.
• The concept of "events" which have occurrences at finitely many points in time.

I believe Rx Observables can be said to support either of these, but 'signals' are typically converted into push events by an Observable implementation pulling from a signal with continuous time (and I believe that's what the push-pull-frp paper referred to in the opening sections).

• A means to change the FRP system in response to events, generally termed "switching."

I don't know about changing the "FRP systems" but Rx definitely reacts to events and allows "changing" the data via the application of functions in a composable manner.

• The separation of evaluation details such as sampling rate from the reactive model.

Evaluation details are embodied within an Observable implementation while operators are applied reactively so I think this is accounted for as well.

On the Elm "What is FRP?" tutorial it matches much more closely with Rx: http://elm-lang.org/learn/What-is-FRP.elm

The Elm examples are stereotypical Rx examples such as handling mouse and touch events to update a UI.

I think the "Time" examples are the most different, but I can't see why any of these wouldn't be possible by applying Scheduler behavior to a Rx sequence. 

In short, I can't see how something both "functional" and "reactive" can not use the "functional reactive" description. I want to avoid confusion if FRP truly means something else, but saying "reactive functional" or "functional and reactive" but not "functional reactive" seems pedantic.

Ben

[Ben Christensen]

Thanks for helping to clarify things on this subject, those comparisons with cells in a spreadsheet and LINQ make sense. 

(Brian's last post was accidentally sent only to me but is included below for posting to the group by his permission)

On Tue, Jul 2, 2013 at 6:17 AM, rebcabin <bc.be...@gmail.com> wrote:

RxJava is a full member of the "functional-reactive" club :)  It's my favorite, I use it every day, and it's quite likely to gain very high adoption numbers because of its exposure through the JVM and a number of languages. 

I think the "behaviors" angle is much more of a programming-language feature. Again, I don't understand them fully, but they're a kind of variable that gets updated automatically when events get propagated through a dependency graph. Rather like a cell in a spreadsheet: change anything that it depends on (transitively) and it gets updated automatically or like those wretched "dependency properties" in XAML. I understand why people might like them, but I find them spooky and they definitely require some compiler to set up the plumbing. What's the plumbing? A bunch of Observables that constitute the dependency graph and some Observers that update the variables. The "spooky" part is in writing code that uses the variables. It's a whole sublanguage embedded in the host language. 

Here is an analogy. LINQ in .NET has two manifestations: the comprehension syntax "for c in customers where c.lastName == "Jones" select c.id"; the SQO library, used in fluent style "customers.Where(c => c.lastName == "Jones").Select(c => c.id)".  The comprehension syntax requires programming-language and compiler support. The SQO's are "just" a library. Are the SQO's "less" a part of LINQ because they're not "language-integrated"?  I'd argue the other way since the comprehension syntax doesn't work without the library, but the library works without the comprehension syntax. Likewise, is RxJava less functional-reactive because it doesn't have behaviors? I'd argue the other way since behaviors can't work without event processing but event processing works without behaviors.